Talk:Nash equilibrium

From Wikipedia, the free encyclopedia

This article is part of WikiProject Game theory, an attempt to improve, grow, and standardize Wikipedia's articles related to Game theory. We need your help!

Join in | Fix a red link | Add content | Weigh in
Good article GA This article has been rated as GA-Class on the assessment scale.
Top This article is on a subject of top-importance within game theory.
Good articles Nash equilibrium has been listed as a good article under the good-article criteria. If you can improve it further, please do.
If it no longer meets these criteria, you can delist it, or ask for a review.
WikiProject Mathematics This article is within the scope of WikiProject Mathematics.
Mathematics grading: Good article GA Class High Importance Field unassessed.

Contents

[edit] Continuous set?

The article says: "if the set of strategies by player i, is a compact and continuous set"

What the heck is a continuous set?

[edit] John Nash

So what did Nash do, besides defining this equilibrium? Are there any interesting theorems here? AxelBoldt

Well, what was interesting was mainly this (I'm typing this from memory, so don't quote me or put this into the article without checking with some up-to-date math nerd): for all games for which there was previously known "solution" (for some definition of solution appropriate to that type of game), Nash proved that those existing solutions were Nash equilibria; and further, he showed that any reasonable definition of "solution" for any other type of game must be a subset of the Nash equilibria for that game. And finally, he showed how to find the Nash equilibria. So he made it much easier to solve all kinds of games--even those for which a definition of "solved" isn't clear--by reducing the problem to finding all the Nash equilibria and evaluating them. --LDC

[edit] Nash equilibria of a game

[Ed: This is an incomplete example that does not illustrate. If I choose 9 and you choose 0, I'm out two bucks. If I choose 9 and you choose 7, you make $9 and I still make $5 - why is this not superior?]

The system of strategies 9-0 is not a Nash equilibrium, because the first player can improve the outcome by choosing 0 instead of 9. The system of strategies 9-7 is not a Nash equilibium, because the first player can improve the outcome by choosing 9 instead of 7. The only Nash equilibrium of this game is 0-0, as stated. AxelBoldt 15:04 Aug 27, 2002 (PDT)

Boy, I sure don't understand this. Why is the Nash equilibrium not 10-10? Don't the players both get ten bucks if they do this? And the worst that could happen is the other player chooses a smaller number and you get less than ten. Why would anyone rational do that, when you could both pick 10 and get 10 bucks? Is there a statement missing from the problem definition? Jdavidb 04:17, 8 Apr 2004 (UTC)

The second player can chose 9 and he can get 11 while the other one will get only 8. That is why 10-10 is not at Nash equilibrium -- AM

I think the thing to keep in mind here is that it is a competition game. Both players are trying to beat the other's "score". This example would work better, I think, using points instead of dollars. Yes, there is a benefit to both players if they both win some money, but no benefit if they both win some points and they are each trying to beat the other's score. -truthandcoffee /ed: Does anyone else confirm/deny this? I would like to see this example changed from dollars to points, as I think it is much clearer and makes much more sense this way. I'd like some feedback before I go ahead and make the change. --Truthandcoffee 04:27, 13 November 2006 (UTC)

[edit] The modified version with 11 Nash equilibria

If the game is modified so that the two players win the named amount if they both choose the same number, and otherwise win nothing, then there are 11 Nash equilibria.

Does the Nash equilibrium not suppose that everybody is selfish and rational? So, if you suppose that the other player is selfish, you can savely assume that he/she chooses 10. IMHO that's the only equilibrium. Or does the Nash equilibrium not presuppose selfishness? Andy 12:53, 26 September 2006 (UTC)

[edit] Limitations of NE

I disagree with the comment "This indicates one of the limitations of using the Nash equilibrium to analyze a game".

The Nash equilibrium is a predictive tool, and indeed it correctly predicts the (unfortunate) result if self-interested players participate in a Prisoner's dilemma type situation. (as borne out in reality, for instance, over fishing of the world's oceans)

The fact that Nash equilibrium correctly predicts an undesirable result is hardly a flaw or limitation.

Robbrown

I agree with Robbrown, that is not a limitation, it correctly predicts the end out come of a prisoner's dilemma. I will change it, also there are better definitions for the Nash equilbrium out there, it might just be better to quote a source on their definition of one like here(http://www.gametheory.net/Dictionary/NashEquilibrium.html )"

Nash equilibrium, named after John Nash, is a set of strategies, one for each player, 
such that no player has incentive to unilaterally change her action. Players are in 
equilibrium if a change in strategies by any one of them would lead that player to earn 
less than if she remained with her current strategy.

--ShaunMacPherson 18:15, 15 Mar 2004 (UTC)

[edit] Nash equilibrium available online

The seminal journal paper in which Nash introduces what is now called the Nash equilibrium is "Non-Cooperative Games", John Nash, The Annals of Mathematics 54(2):286-295, 1951. It is available online to for a fee at http://links.jstor.org/sici?sici=0003-486X%28195109%292%3A54%3A2%3C286%3ANG%3E2.0.CO%3B2-G (many universities subscribe to JSTOR, so this link should work for at least some people beside me)

I'm not posting that directly to the page since I'm not sure whether it's OK to post links to for-pay resources. If it is OK, then please copy this to the article page.

--JP, Nov 10 2005

Well, I just did that yesterday, before reading this note. I will remove what I did right away. The article is available for a fee, but many universities and colleges provide free access to this and other for fee-services for their students.

--Zsolt, June 7, 2006

On the other hand, referencing the article itself, without a link to the for-fee online article is probably ok. So I just took out the link to that on-line version. This way people can still find it if they want to.

--Zsolt, June 7, 2006

[edit] Removed setence

I reverted an edit by anon, which added this setence to one section:

"choosing the best strategy given the strategies that others have chosen"

The sentence was out of context and imcomplete. If the anon would like to add it in context I'm sure it would be helpful. --Kzollman 17:59, May 11, 2005 (UTC)

[edit] Coordination game

As it turns out the entry Coordination game redirects here. Given the wide discussion of coordination games, I think it diserves its own entry. Would folks mind if I seeded the entry with the material here, and removed the redirect? thanks! -Kzollman 23:43, Jun 2, 2005 (UTC)

Presently, nothing links to Coordination game other than daughters of Nash Equilibrium, and both of these actually give its pay-off matrix (Mixed strategy, Pure strategy). Therefore, there can't be a problem expanding that article from a redirect.
Cheers, Wragge 00:56, 2005 Jun 3 (UTC)
Done! best --Kzollman 00:48, Jun 8, 2005 (UTC)

[edit] Fixed points

In my game theory class and text books we proved the existence of the Nash equilibrium using Kakutani fixed point theorem, a generalization of Brouwer fixed point theorem. Does anyone smarter than me know if Brower's is strong enough to prove the existence (as stated in the article)? --Kzollman 00:48, Jun 8, 2005 (UTC)

Okay, I fixed the proof. --best, kevin ···Kzollman | Talk··· 06:03, August 2, 2005 (UTC)


[edit] correlated equilibrium more flexible than Nash equilibrium?

All the examples in the current Nash equilibrium article seem to be "one-shot" games (is there a better term?) -- as opposed to repeated games.

Strategies such as Tit for Tat don't work for "one-shot" games.

The Robert Aumann article mentions

Aumann's greatest contribution was in the realm of repeated games, which are situations in which players encounter the same situation over and over again.
Aumann was the first to define the concept of correlated equilibrium in game theory, which is a type of equilibrium in non-cooperative games that is more flexible than the classical Nash Equilibrium.

Does that mean that

Nash equilibrium only applies to one-shot games.
correlated equilibrium is used for repeated games.

? If that's true, the article should mention it.

--DavidCary 13:40, 11 October 2005 (UTC)


David, I don't really know much about correlated equilibrium (which is why I haven't written the article). From what I understand, those contributions are two different things. Correlated equilibria are genearalizations of Nash equilibria (i.e. every Nash eq. is a Correlated eq. but there are some Correlated eq. that are not Nash). I don't know what his contributions to repeated games is. --best, kevin ···Kzollman | Talk··· 18:34, 11 October 2005 (UTC)

[edit] Nash Equilibria in a payoff matrix

Under the heading specified above, it claims that "...an NxN matrix may have 0 or N Nash Equilibriums." Shouldn't it be 1 or N NE, since at the beginning of the article it says that Nash proved the existence of equilibria for any finite game with any number of players?

No. For example the matrix [ 0,1 0,1 ][ 1,0 1,0 ] has no equilibrium. I assume the proof doesn't apply to that matrix because it's not a matrix representing a finite game (but that's just a guess).
I do think the sentence is wrong on the other side though, and it should be 0 to NxN equilibriums (note also that it's 0 TO N in the original, not 0 OR N) for the degenerate case of a matrix where all the cells have the same value. Hirudo 06:29, 31 March 2006 (UTC)
Every finite game has a Nash equilibrium in its mixed extension. Some games, don't have pure strategy Nash equilibria, and I assume that what is meant by the article. I will fix it. --best, kevin [kzollman][talk] 07:23, 31 March 2006 (UTC)

[edit] Strategy profile

On this page, the phrase

resulting in strategy profile x = (x1,..,xn)

indicates that a strategy profile is simply a vector of strategies, one for each player. I agree. However, if one follows the link, a strategy profile is defined as something that "identifices, describes, and lastly examines a player's chosen strategy". It is conceivable that someone somewhere defined strategy profile in this way, but the "vector"-meaning of the term is much more common. So, at least the link, if not the page linked to is misleading.

Also there is something slightly wrong in the notation concerning strategy profiles on this page itself. You say that

S is the set of strategy profiles.

Okay, but then each element of S is a vector of strategies. Still, you write

x_i \in S

where xi is a single strategy. I think you want to write

S = S_1 \times S_2 \times ... \times S_n is the set of strategy profiles

and

x_i \in S_i.

Bromille 11:50, 31 May 2006 (UTC)

The strategy (game theory) article really needs some fixing. I reverted Littlebear1227's definition of strategy profile to the more correct one... Pete.Hurd 13:16, 31 May 2006 (UTC)


[edit] "Occurence" section

There are some issues in the "Occurrence" section.

First, whatever the stated conditions are, they can only be sufficient, not necessary for equilibrium play. To see this, observe that nothing prevents a bunch of completely non-rational agents from playing the Nash equilibrium, not because it is a rational thing to do, but because non-rational agents can do anything they want.

Second, conditions 1. and 5. together say that agents are rational and they all believe that the other agents are also rational. But these are not sufficent conditions on rationality for equilibrium play. A classical counterexample is Rosenthal's centipede which has a unique Nash equilibrium as assumed. In this game, if you and I play the game and I believe you are rational and you believe I am rational, we still might not play the equilibrium, if, for instance, I do not believe that you believe that I am rational. This could be the case, even if I do believe that you are rational. What is needed to ensure that the equilibrium is played in the case of Rosenthal's centipede is common knowledge of rationality (CKR) which means that

A: I am rational, B: You are rational, C: I believe B, D: You believe A, E: I believe D, F: You believe C, G: I believe F, H: You believe E, etc.. etc..

The difference may seem like splitting hairs but is actually the key to understanding the discrepancy between how Rosenthal's centipede is actually played by rational-seeming people and the equilibrium play.

Reference: Robert Aumann, Backward induction and common knowledge of rationality, Games and Economic Behavior 8 (1995), p. 6--19.

Third, for general games, even if CKR is assumed, this usually only ensures that a correlated equilibrium is played, not a Nash equilibrium. The fact that a unique Nash equilibrium is assumed may make this ok - I'm not sure about this.

Bromille 13:54, 1 June 2006 (UTC)

Bromille, this is definitely right. I have intended for some time to rewrite this section to incorporate some of these issues. But you are welcome to beat me to it! :) We do have a page on common knowledge (logic) which explains some issues about common knowledge. --best, kevin [kzollman][talk] 17:51, 1 June 2006 (UTC)

[edit] GA Re-Review and In-line citations

Members of the Wikipedia:WikiProject Good articles are in the process of doing a re-review of current Good Article listings to ensure compliance with the standards of the Good Article Criteria. (Discussion of the changes and re-review can be found here). A significant change to the GA criteria is the mandatory use of some sort of in-line citation (In accordance to WP:CITE) to be used in order for an article to pass the verification and reference criteria. Currently this article does not include in-line citations. It is recommended that the article's editors take a look at the inclusion of in-line citations as well as how the article stacks up against the rest of the Good Article criteria. GA reviewers will give you at least a week's time from the date of this notice to work on the in-line citations before doing a full re-review and deciding if the article still merits being considered a Good Article or would need to be de-listed. If you have any questions, please don't hesitate to contact us on the Good Article project talk page or you may contact me personally. On behalf of the Good Articles Project, I want to thank you for all the time and effort that you have put into working on this article and improving the overall quality of the Wikipedia project. Agne 05:49, 26 September 2006 (UTC)

[edit] Relationship to regulation??

I am curious about the relationship between NE and government regulation. Consider the case of airbags in cars. Without regulation requiring airbags, normal supply and demand will dictate the number of airbags produced. If air bags are mandated by the government, the unit cost will be much lower, and more consumers will choose to purchase cars with airbags and receive the consumer surplus from the purchase. The consumer was able to move to a better outcome through the intervention of a third party. In this case it is hard to say how the auto manufacturer is impacted. It is possible that they benefited because they can now offer new cars with more value at a lower cost than without regulation. More people buy a new car vs. a used car to benefit from the air bag. Measuring if there was a benefit to the auto company is impossible, but let's assume there is. Did the regulation help both parties move out of a NE to a better outcome? 65.198.133.254 20:36, 30 November 2006 (UTC)David Wilson

Retrieved from "http://en.wikipedia.org../../../n/a/s/Talk%7ENash_equilibrium_0ad1.html"