Message Font: Serif | Sans-Serif
 
UnThreaded | Threaded | Whole Thread (20) | Ignore Thread Prev Thread | Next Thread
Author: euphoriant Big red star, 1000 posts Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: of 1389  
Subject: Nash Equilibrium Date: 2/20/2002 1:07 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 1
Can anyone explain this to me in simple terms?

Thanks,
e
Print the post Back To Top
Author: LorenCobb Big gold star, 5000 posts Top Favorite Fools Top Recommended Fools Feste Award Nominee! Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 536 of 1389
Subject: Re: Nash Equilibrium Date: 2/20/2002 4:17 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 13
Euphoriant asked, "Can anyone explain the Nash Equilibrium to me in simple terms?"

I will be glad to try. If my answer is not clear, try reading the extended article on Game Theory in the Encyclopedia Britannica.

The Nash Equilibrium appears in the literature on two-person non-zero-sum games. "Non-zero-sum" means that the two players may be able to cooperate with each other so as to both receive a positive payoff. Zero-sum games are never cooperative, and are much easier to analyze. Nash found a way to predict the cooperative solution to a broad category of such games, given only six reasonable assumptions (the Nash Axioms) and knowledge of each player's utility function.

For example, suppose a very rich man and a poor man are told that they will receive a total of $10,000, if they can agree on how it is to be divided between them. If they cannot agree, then they receive nothing. As the two men negotiate, each can threaten the other with breaking off the negotiations. The Nash Equilibirum is, essentially, an agreement that maximizes the product of the two utilities. The exact amounts to be distributed to the two men depend, of course, on the utility functions for the two men.

The Nash Equilibrium is remarkable and mathematically interesting because Nash was able to show that his six axioms always give a unique solution. Nobody had imagined that such a result was possible, hence the fame of his theorem. The actual equilibrium itself is also sometimes surprising. In the above example, if the rich man has a utility function which is proportional to the dollar amount while the poor man has a utility function which is proportional to the square root of the dollar amount, then the poor man will end up with only one-third of the cash (see below for details). In effect, the poor man has less bargaining power because small amounts of money have much more utility for him than for the rich man.

Details of the calculation: we need to maximize g(x) = (ax)( b sqrt(10000-x) ). Differentiating g with respect to x and setting the result equal to zero, we obtain:

0 = ab sqrt(10000-x) - (1/2)abx / sqrt(10000-x).

This has the solution x = $6666.67 for the rich man and $3333.33 for the poor man. Notice that we get these exact figures even without knowing the proportionality constants a and b!

I hope this helps somewhat.
Loren


Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Print the post Back To Top
Author: euphoriant Big red star, 1000 posts Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 537 of 1389
Subject: Re: Nash Equilibrium Date: 2/20/2002 7:53 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 0
Thanks Loren! That helps a lot. One more question, if I can...

What are his six axioms?

Thanks,
e

Print the post Back To Top
Author: jbking Big gold star, 5000 posts Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 538 of 1389
Subject: Re: Nash Equilibrium Date: 2/20/2002 9:58 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 2
Greetings euphoriant,

http://cwis.kub.nl/~few5/center/staff/vdamme/nashap.pdf is an 8 page essay that may also be of some interest.

JB

Print the post Back To Top
Author: WilliamLipp Big red star, 1000 posts Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 539 of 1389
Subject: Re: Nash Equilibrium Date: 2/20/2002 11:01 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 0
This has the solution x = $6666.67 for the rich man and $3333.33 for the poor man.

Can you explain in what sense this is an equilibrium? I'm imagining that "equilibrium" means that the poor man would rather take nothing than settle for $8,000/$2,000, and the rich man would rather take nothing than settle for $5,000/$5,000. I don't see how to demonstrate that from the information. Or does "equilibrium" mean something different?

Print the post Back To Top
Author: jbking Big gold star, 5000 posts Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 540 of 1389
Subject: Re: Nash Equilibrium Date: 2/21/2002 1:31 AM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 1
Greetings WilliamLipp,

Hope you don't mind someone else trying to answer the Qs here.

Can you explain in what sense this is an equilibrium?

I think the key is to understand that there are constraints on the variables and that in theory one should state that there should be a value chosen by each player such that their sum is $10,000 and each is greater than zero and a real value.

IOW, let x denote the rich man's amount and y the poor man and state the problem as follows:

maximize g(x,y) = ax*b(y^1/2)

such that:
x+y=10000
x>0, y>0 and x,y elements of Real number system.

Thus, one could reduce the problem to:

g(x) = ax*b((10000-x)^1/2))

where 0<=x<=10000, x in real number system. Noting that the function is zero at the endpoints one should check where the derivative is zero for an optimal solution.

I'm imagining that "equilibrium" means that the poor man would rather take nothing than settle for $8,000/$2,000, and the rich man would rather take nothing than settle for $5,000/$5,000.

No, equilibrium here is that a set is defined of feasible values or in other words certain constraints are met. http://online.sfsu.edu/~langlois/class_14.pdf on page 2 has such a note in the list of strategy set, S.

Or does "equilibrium" mean something different?

Equilibria can be thought of as rules or constraints that must be valid in the game.

JB

Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Print the post Back To Top
Author: LorenCobb Big gold star, 5000 posts Top Favorite Fools Top Recommended Fools Feste Award Nominee! Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 541 of 1389
Subject: Re: Nash Equilibrium Date: 2/21/2002 2:48 AM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 5
1. Euphoriant asked for the six axioms that are sufficient to provide a unique Nash equilibrium.

It would take several pages to set up the notation and quote the axioms, and the constraints of TMF text messages make the effort rather difficult. Instead, let me try to render them in something approximating English. These axioms describe the properties that we can assume any reasonable "bargaining solution" must have. A bargaining solution is the pair of utilities that the two players will receive if each acts in accordance with an agreement that they worked out together for the game, using a set S of feasible outcomes.

The set S is known as the feasible set. It is the set of all pairs of utilities that can be obtained from a play of the game.

1. Individual Rationality: the utility of the bargaining solution for each player must be at least as good as what the player could receive without an agreement.

2. Feasibility: The bargaining solution must be an element of the feasible set.

3. Pareto Optimality: If (x,y) is a feasible outcome and (x,y) is at least as good as the bargaining solution for each player, then (x,y) is exactly the bargaining solution.

4. Independence of irrelevant alternatives: If the bargaining solution is an element of a subset T of S, then it will still be the bargaining solution if the game is restricted to T.

5. Equivalence up to affine transformation: If a new game is created by an affine transformation of the feasible set, then the bargaining solution in the new game can be obtained by applying the affine transformation to the bargaining solution of the old game. [An affine transformation is just a change of zero-point composed with a scale change, e.g. L(x) = b(x-a).]

6. Symmetry: If the feasible set is symmetric and the two players have equal non-cooperative outcomes, then the bargaining solution will give equal utility to each player. [A set of ordered pairs is symmetric if for every element (a,b) there is also an element (b,a).]

The first three of these axioms are pretty obvious. The last three are a little more subtle, and indeed can be controversial. The only way to really see the beauty of Nash's theory is to read the axioms in their full mathematical form, and then play around with them to see what they mean and how they affect the uniqueness of the bargaining solution. The level of math required is pre-calculus, but the reasoning may stretch you out a little if you have never worked with set theory before. Somewhat amazingly, the proof of Nash's theorem is very geometrical, and requires no heavy machinery.

2. WilliamLipp wondered in why the bargaining solution is called an "equilibrium". My answer is that the bargaining process by which the two players arrive at an agreement somewhat resembles an iterative process that gradually homes in on a stationary point. The analogy with equilibria in physics is very loose, and is not supposed to be exact.

Loren

Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Print the post Back To Top
Author: euphoriant Big red star, 1000 posts Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 542 of 1389
Subject: Re: Nash Equilibrium Date: 2/21/2002 7:45 AM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 0
Thank you!!! All of you.

e

Print the post Back To Top
Author: WilliamLipp Big red star, 1000 posts Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 543 of 1389
Subject: Re: Nash Equilibrium Date: 2/21/2002 1:44 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 0
WilliamLipp wondered in why the bargaining solution is called an "equilibrium"

I expressed myself poorly. My question is really "Prove to me the rich man and poor man would really settle this way." The game was introduced as:

a very rich man and a poor man are told that they will receive a total of $10,000, if they can agree on how it is to be divided between them. If they cannot agree, then they receive nothing. As the two men negotiate, each can threaten the other with breaking off the negotiations.

The first approach was "suppose the poor man insisted on $5K/$5K. Then the rich man would refuse because he would have greater utility by refusing than by accepting." Except that's not true - his utility for $5K is greater than his utility for $0. At this point I understood that I don't have an adequate model of how the "game" works. Next I thought "perhaps it's a game they play every week - suppose they have been playing $5K/$5K - perhaps the rich man will occasionally refuse to agree, so that his average utility is higher" - but that doesn't work either. So I'm having trouble seeing that this is the right answer - although these ideas also didn't suggest anything else was the right answer, either.

My latest thought is that I should view the negotiations as a bidding war. We give each player N utility points, and we auction the $10,000 off in $1,000 (or $1) increments. This looks promising - the poor player should be willing to pay more for the first $1K because it has greater utility to him. It would take some work, though, to make this into a full demonstration.



Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Print the post Back To Top
Author: euphoriant Big red star, 1000 posts Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 544 of 1389
Subject: Re: Nash Equilibrium Date: 2/21/2002 2:08 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 0
WilliamLipp wondered in why the bargaining solution is called an "equilibrium"


I don't have an answer, but another way to look at the problem.

Instead of viewing it as a game, view it as real life. For example, the original words...

a very rich man and a poor man are told that they will receive a total of $10,000, if they can agree on how it is to be divided between them. If they cannot agree, then they receive nothing. As the two men negotiate, each can threaten the other with breaking off the negotiations.

Now, make it real by saying that the poor man is suing the rich man for $10,000. If they mediate prior to going to court they will try to settle on an amount between $0 and $10,000, knowning that if they do not settle they will end up in court where the rich man could lose 10 times that amount. Is it easier to see in this situation that the equilibrium (the amount both are willing to settle at) may not be the "middle"?

Trying to help,
e


Print the post Back To Top
Author: jrr7 Big gold star, 5000 posts Feste Award Nominee! Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 545 of 1389
Subject: Re: Nash Equilibrium Date: 2/21/2002 2:44 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 0
The first approach was "suppose the poor man insisted on $5K/$5K. Then the rich man would refuse because he would have greater utility by refusing than by accepting." Except that's not true - his utility for $5K is greater than his utility for $0.

As I understand it, the poor man wouldn't bother to deliver that ultimatum, because in doing so he'd guarantee he'd get zero, and getting something is better than nothing.

What I don't understand is why the overall utility function is the product of the utility functions of the players.

Print the post Back To Top
Author: WilliamLipp Big red star, 1000 posts Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 546 of 1389
Subject: Re: Nash Equilibrium Date: 2/21/2002 3:44 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 0
WilliamLipp: The first approach was "suppose the poor man insisted on $5K/$5K. Then the rich man would refuse because he would have greater utility by refusing than by accepting." Except that's not true - his utility for $5K is greater than his utility for $0.

jrr7: As I understand it, the poor man wouldn't bother to deliver that ultimatum, because in doing so he'd guarantee he'd get zero, and getting something is better than nothing.

I'm believe your line of analysis is correct in a properly constructed example. It doesn't work out that way in my example - I take that as evidence that my example fails to capture the essence of the process. In my example the rich man is the one saying "something is better than nothing," so he accepts the ultimatum. Of course by the same reasoning, if the rich man issued an ultimatum the poor man would accept it.

These ultimatum based views aren't shedding any light on things. The Nash Equilibrium means, I think, that there is some sense in which these players would be "more satisfied" with at 6K/4K decision than with a 5K/5K decision. Or perhaps "more likely to agree upon," or something like that.

Print the post Back To Top
Author: Deppen One star, 50 posts Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 547 of 1389
Subject: Re: Nash Equilibrium Date: 2/21/2002 5:10 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 0
Where were you guys when I was waiding through Nash, Prefect Nash and perfect euqilibria in my grad school game theory class.....That was a great and as concise an explaination as I seen.

Stephen

Print the post Back To Top
Author: jrr7 Big gold star, 5000 posts Feste Award Nominee! Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 548 of 1389
Subject: Re: Nash Equilibrium Date: 2/21/2002 5:31 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 1
The Nash Equilibirum is, essentially, an agreement that maximizes the product of the two utilities.

This I don't understand. Why is it the product, and not the sum, or some other two-argument commutative function?

Print the post Back To Top
Author: LorenCobb Big gold star, 5000 posts Top Favorite Fools Top Recommended Fools Feste Award Nominee! Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 549 of 1389
Subject: Re: Nash Equilibrium Date: 2/22/2002 12:39 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 4
jrr7: "This I don't understand. Why is it the product, and not the sum, or some other two-argument commutative function?"

A good part of the power and beauty of Nash's theorem comes from the fact that he proved that maximizing this particular function gives the unique best bargaining solution. It is surprising that the answer should be so simple. The full answer to the Why question is the proof itself -- that's what a proof is, after all.

I'm not going to quote the proof -- you can find it in any college-level book on game theory -- but I can try to give some of its flavor.

The first step is to establish a much simpler fact, namely that if there is any pair (u,v) in the feasible set S which is better than the non-cooperative solution (s,t), then there is a unique pair (a,b) which maximizes the function g(u,v) = (u-s)(v-t). This is where the product first appears. Most of the rest of the theorem involves showing that the unique maximum (a,b) for g is in fact the unique bargaining solution for the cooperative game.

The second step is to show that (a,b) satisfies all six axioms. Let's take that for granted. The third and crucial step is to show that maximizing g is the only way to find the solution. The argument proceeds by showing that any other solution can be transformed into this one. In order to prove this, Nash had to rely heavily on Axiom 4, which was precisely the axiom that attracted the most criticism in the first place.

The fourth and last step is just cleanup. We need to check the special case in which there is no pair (u,v) in the feasible set that is better than the non-cooperative solution.

If there is a weakness in the Nash theory of bargaining, then it clearly lies in the absolutely crucial Axiom 4. It's been many years since I last looked at the literature, but I believe that to date no wonderful alternative has surfaced. That's not to say that tomorrow somebody might not discover a different and better way to axiomatize the bargaining problem.

When it comes time to apply the Nash theory to real-world situations, a certain circularity appears. If Nash was correct, then every bargain that is struck between to cooperative players reflects the maximization of the product of their respective utility functions. What are their utility functions? Well, we can deduce them statistically from the bargains that they strike, as long as they are consistent, by exposing them to a series of games against a variety of other players. I don't know whether anyone has actually tried to do this, but it would make an interesting experiment.

I think it is fair to say that the primary impact of the Nash theory has been its contribution to utility theory, rather than on understanding human behavior. It was a gigantic step forward for game theory, but had no impact whatsoever on real bargaining.

Loren Cobb


Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Print the post Back To Top
Author: xraymd Big gold star, 5000 posts Feste Award Nominee! Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 551 of 1389
Subject: Re: Nash Equilibrium Date: 2/24/2002 5:16 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 0
The first approach was "suppose the poor man insisted on $5K/$5K. Then the rich man would refuse because he would have greater utility by refusing than by accepting." Except that's not true - his utility for $5K is greater than his utility for $0.

As I understand it, the poor man wouldn't bother to deliver that ultimatum, because in doing so he'd guarantee he'd get zero, and getting something is better than nothing.


Greetings, I read somewhere recently (Scientific American, I think) that the actual outcome of the game rested less on zero-summing than on whether the disadvantaged party felt sufficiently taken advantage of by having to accept a smaller share of the pot that he would break off negotiations at a cost of getting $0 simply to prevent the other party from profiting either! So in this case, getting nothing was better than getting something. Does the Nash Equilibrium accout for this outcome?

xraymd



Print the post Back To Top
Author: jrr7 Big gold star, 5000 posts Feste Award Nominee! Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 552 of 1389
Subject: Re: Nash Equilibrium Date: 2/25/2002 10:26 AM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 0
Greetings, I read somewhere recently (Scientific American, I think) that the actual outcome of the game rested less on zero-summing than on whether the disadvantaged party felt sufficiently taken advantage of by having to accept a smaller share of the pot that he would break off negotiations at a cost of getting $0 simply to prevent the other party from profiting either! So in this case, getting nothing was better than getting something. Does the Nash Equilibrium accout for this outcome?


I was talking with the Nash Equilibrium with my boss, and he brought this very thing up.

The Nash Equilibrium does not account for any spite, disadvantage, or resentment the individuals may have at the partner getting something. Example: there are $10 million in government grants available and 2 businesses competing for the grants. Each business requests a certain amount in grants. If the total of the requests is more than $10 million, neither company gets the grant. If the two companies compete with each other, each would prefer that the other get zero. This preference is so strong that even if the other side offers to apply for only a dollar, it will be rejected.

Nash assumes that the parties don't care about what happens to the other and have no relationship other than being in the same game. I believe a consequence of this is that each side would prefer something to nothing.

Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Print the post Back To Top
Author: WilliamLipp Big red star, 1000 posts Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 553 of 1389
Subject: Re: Nash Equilibrium Date: 2/25/2002 11:09 AM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 1
The Nash Equilibrium does not account for any spite, disadvantage, or resentment the individuals may have at the partner getting something.

I think Nash would handle these things fine - you just have to include these effects in the utility functions. The whole point of using utility functions is to capture payoff effects that differ from dollar effects.

Print the post Back To Top
Author: WilliamLipp Big red star, 1000 posts Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 554 of 1389
Subject: Re: Nash Equilibrium Date: 2/25/2002 12:01 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 2
My question is really "Prove to me the rich man and poor man would really settle this way."

Here is my answer to my question.

Although we can't say much about the actual process of negotiation, the utility functions allow us to measure how hard each party will negotiate at any proposed solution. Given a proposal of receiving x dollars, the increase from getting another dollar is U(x+1)/U(x)

Suppose they are considering the even split of $5000/$5000. The Poor Man sees the value of another dollar as sqrt(5001)/sqrt(5000) = 1.000100. The Rich Man sees 5001/5000 = 1.000200. The Rich Man is fighting for 200 millipoints here, versus the Poor Man fighting for only 100 millipoints. The Rich Man cares more, so he will negotiate harder, changing the proposal in favor of the Rich Man.

Suppose they are considering a 2000/8000 proposal. The Poor Man sees another dollar as worth sqrt(2001)/sqrt(2000) = 1.000250. The Rich Man sees 8001/8000 = 1.000125. The Poor Man is fighting for 250 millipoints, versus only 125 for the Rich Man, so he will negotiate harder, moving the proposal in favor of the Poor Man.

Suppose they are considering the Nash proposal of $3333/$6666. The Poor Man will see another dollar as worth sqrt(3334)/sqrt(3333) = 1.000150. The Rich Man will see another dollar as worth sqrt(6668)/sqrt(6667) = 1.000150. Here they feel equally intense about a change - neither feels strongly enough to overcome the other. At this balance of intensities the negotiations settle.

That's my proposal for showing the Rich Man and Poor Man would settle at the Nash Equilibrium.

Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Print the post Back To Top
Author: jrr7 Big gold star, 5000 posts Feste Award Nominee! Old School Fool Add to my Favorite Fools Ignore this person (you won't see their posts anymore) Number: 555 of 1389
Subject: Re: Nash Equilibrium Date: 2/25/2002 3:25 PM
Post New | Post Reply | Reply Later | Create Poll Report this Post | Recommend it!
Recommendations: 0
The problem with this situation is that the person's utility function depends on what the other side gets, at one point: if one side gets zero, their utility is based on whether the other side got 0 or 10,000. For Nash's postulates to apply, each person's utility function should be based solely on their own take.

Because of this discontinuity you can't use the "differential" method that was posted. The function is not monotonic (it's not even a single-variable function).

Print the post Back To Top
UnThreaded | Threaded | Whole Thread (20) | Ignore Thread Prev Thread | Next Thread
Advertisement