Talk:Discoordination game
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! |
|
|
|
Aiming towards replacing Chicken (game) with this article. Pete.Hurd 20:25, 5 November 2006 (UTC)
Note, see Chicken (game) for edit history of material prior to 5NOV2006. I copied everything from there over here then. Pete.Hurd 00:06, 8 November 2006 (UTC)
On page 30 of A course in game theory (MIT, 1994, ISBN 0-262-65040-1) Osborne & Rubenstein write the sentence " Hawk-Dove is also known as "Chicken". " (quotes, ital as in original). Pete.Hurd 18:15, 7 November 2006 (UTC)
The page Talk:Chicken (game) has all the discussion that ought to be here, it may be worth discussing things there rather than here... Pete.Hurd 06:40, 9 November 2006 (UTC)
- Do you think we should move this to Congestion game and include the possibility of multiplayer games? Between discoordination, crowding, and congestion game all three terms are relatively obscure, but I think congestion wins out. Monderer & Shapley credit Rosenthal, R. W. (1973). “A Class of Games Possessing Pure-Strategy Nash Equilibria,” Int. J. Game Theory 2, 65–67. with defining the term, but I haven't looked that one up yet. ~ trialsanderrors 07:40, 18 November 2006 (UTC)
-
- Hmmm, I'll look into this Pete.Hurd 19:55, 18 November 2006 (UTC)
- Rosenthal article online here. ← Turns out the term appears nowhere in the paper, still a good reference. ~ trialsanderrors 11:33, 19 November 2006 (UTC)
Contents |
[edit] Tragedy of commons/matching pennies
| Private | Public | |
| Private | 0, 0 | 0, P |
| Public | P, 0 | P-1, P-1 |
| 2player ToC | ||
I'm not sure I understand the two comparisons in the introduction. I always thought that tragedy of the commons was a prisoner's dilemma and not a version of chicken. I also don't understand the comparison with matching pennies, which is a game without any shared interests. --best, kevin [kzollman][talk] 02:16, 5 January 2007 (UTC)
- Hmmm, I'm with you on ToC==PD. As for matching pennies, one player has the reaction correspondence of a player in a coordination game, while the other has a reaction correspondence from a discoordination game; the sentence makes sense in that light, but it is kind of a subtle shade... Pete.Hurd 04:35, 5 January 2007 (UTC)
- Not quite, the payoff of choosing "Private" in ToC is always the same (zero), no matter what the other players do, the payoff of choosing "Public" is P - N, with N the number of other players choosing Public as well. You can't construct a T > R > P > S payoff scheme for a two-player ToC. The 2-player ToC is actually pretty lame (it's close to Chicken if P = 0.5). But I admit the intro paragraph contains quite a bit of original research, and I'm having a hard time finding
a tight definitionconsistent definitions of either discoordination, crowding or congestion game in the literature. I'm not sure if anyone has clearly defined it beyond "It's better not to do what the other player does". ~ trialsanderrors 05:54, 5 January 2007 (UTC)- Maybe I'm misremembering, but I always thought that the tragedy of the commons went like this: There is a finite common resource from which every individual takes. Individuals can choose to take large or small amounts for themselves. Everyone taking small amounts is best for social welfare, since it allows the finite resource to last a long time. But since the resource is valuable each individual has an incentive to take large. As a result, everyone takes large. This destroys the resource faster (e.g. the animals are hunted to extinction) and as a result everyone is worse off as a result. This is definitely a n-player prisoner's dilemma. This, at least, sounds like what is in our tragedy of the commons article. Am I confused? --best, kevin [kzollman][talk] 06:27, 5 January 2007 (UTC)
- Sounds similar, with Small = Private (grazing on private land) and Large = Public (grazing on public commons). "Everyone taking small amounts" is usally not the socially optimal outcome, but more players take Large than is socially beneficial because the increase in payoffs for the N+1st player of choosing Large is P-(N+1), meaning the player will pick Large if P > N+1, while the external cost to all other N players playing Large adds up to N. So the social payoff difference is P-2N-1. If P is just barely bigger than N+1, that becomes a social net loss. ~ trialsanderrors 06:49, 5 January 2007 (UTC)
- Okay, I looked it up. Ginits' Game Theory Evolving says "When formalized as a game, the [tragedy of the commons] is simply an n-person repeated Prisoner's Dilemma..." (256). Either way, I don't thinks its particular elucidating (since it mostly confused me :), so I'm going to remove it. Perhaps, the relationship could be discussed in more detail in a later section. --best, kevin [kzollman][talk] 18:49, 5 January 2007 (UTC)
- Not sure how this would work out but ok to remove from here. ~ trialsanderrors 19:45, 5 January 2007 (UTC)
- Also, isn't the N-player PD a Public goods game? ~ ~ trialsanderrors 22:45, 5 January 2007 (UTC)
- Yup, right after that blurb I quoted in Gintis, he talks about public goods game. They both are variations of repeated n-player PD (or so says Gintis). The difference between the two games is in TC, the individuals are able to differentially take from a common pool. In the second, individuals are able to differentially contribute to a common pool which is divided evenly. In both cases there is incentive for every individual to take too much/contribute too little and in both cases the socially optimal thing is for everyone to take a little/contribute a lot. --best, kevin [kzollman][talk] 23:00, 5 January 2007 (UTC)
- From my admitedly basic understanding, Tragedy of the Commons is a multi-player PD for the reasons that Kevin mentioned above as discussed in Ginits. The multiplayer portion is obvious--n number of people can play the given because there is no defined size for the commons (i.e. if we were playing a fishing game there would a million fish or fourteen). The PD portion comes in because compromising would result in the best solution for the community, but if you happen to outsmart your opponents (in this case by taking more than your fair share) you are at a considerable advantage. If no one else does this, you can continue this advantage. Infomanager 07:55, 6 January 2007 (UTC)
- I think I figured it out where the discrepancy comes from (or rather, how PD and Crowding game are related). That's of course OR, but if anyone is interested let me know and I post it. ~ trialsanderrors 20:55, 6 January 2007 (UTC)
- Okay, I looked it up. Ginits' Game Theory Evolving says "When formalized as a game, the [tragedy of the commons] is simply an n-person repeated Prisoner's Dilemma..." (256). Either way, I don't thinks its particular elucidating (since it mostly confused me :), so I'm going to remove it. Perhaps, the relationship could be discussed in more detail in a later section. --best, kevin [kzollman][talk] 18:49, 5 January 2007 (UTC)
- Sounds similar, with Small = Private (grazing on private land) and Large = Public (grazing on public commons). "Everyone taking small amounts" is usally not the socially optimal outcome, but more players take Large than is socially beneficial because the increase in payoffs for the N+1st player of choosing Large is P-(N+1), meaning the player will pick Large if P > N+1, while the external cost to all other N players playing Large adds up to N. So the social payoff difference is P-2N-1. If P is just barely bigger than N+1, that becomes a social net loss. ~ trialsanderrors 06:49, 5 January 2007 (UTC)
- Maybe I'm misremembering, but I always thought that the tragedy of the commons went like this: There is a finite common resource from which every individual takes. Individuals can choose to take large or small amounts for themselves. Everyone taking small amounts is best for social welfare, since it allows the finite resource to last a long time. But since the resource is valuable each individual has an incentive to take large. As a result, everyone takes large. This destroys the resource faster (e.g. the animals are hunted to extinction) and as a result everyone is worse off as a result. This is definitely a n-player prisoner's dilemma. This, at least, sounds like what is in our tragedy of the commons article. Am I confused? --best, kevin [kzollman][talk] 06:27, 5 January 2007 (UTC)
- Not quite, the payoff of choosing "Private" in ToC is always the same (zero), no matter what the other players do, the payoff of choosing "Public" is P - N, with N the number of other players choosing Public as well. You can't construct a T > R > P > S payoff scheme for a two-player ToC. The 2-player ToC is actually pretty lame (it's close to Chicken if P = 0.5). But I admit the intro paragraph contains quite a bit of original research, and I'm having a hard time finding
[edit] Some definitions
Surfing around on Google Scholar a bit, I notice that some authors, including a certain Peter L. Hurd, define discoordination game similar to Hawk-Dove while others define it as game without pure NE, meaning matching pennies. ~ trialsanderrors 06:52, 5 January 2007 (UTC)
- Hmmm, I was thinking maybe the whole "discoordination game" term was going to qualify as WP:OR, then Google Scholar turns up some imposter besmirching my name... bad to worse... ;) Pete.Hurd 07:12, 5 January 2007 (UTC)
| H | D | |
| H | P, P | T, N |
| D | N, T | C, C |
| Table A2 Generic discoordination game | ||
- "A crowding game is a normal-form game in which the players share a common set of actions and the payoff a particular player receives for choosing a particular action is a nonincreasing function of the total number of players choosing that action." : Igal Milchtaich : Crowding games are sequentially solvable : International Journal of Game Theory : Volume 27, Number 4 / December, 1998
- (Congestion game) "A network of roads is given. Each of n people must travel (at about the same time) through the network from certain origins to certain destinations. The time it takes to travel on any road is an increasing function of the number of people selecting that road. Each person wishes to travel from his origin to his destination in minimum time.) : A Class of Games Possessing Pure-Strategy Nash Equilibria : Robert W. Rosenthal : 1973
- "Any 2 x 2 game in which the payoffs rank as P<N and C<T (Table A2) is a discoordination game, and will have all the properties of the Hawk–Dove game." : Resource holding potential, subjective resource value, and game theoretical models of aggressiveness signalling : Peter L. Hurd : Journal of Theoretical Biology 241 (2006) 639–648
- "Discoordination games have a single equilibrium, in mixed strategies. The payoffs are such that either (a) a > c, d > c, x > w, and y > z, or (b) c > a, b > d, w > x, and z < y. The Welfare Game is a discoordination game, as is Auditing Game I in the next section and Matching Pennies in Problem 3.3" : Games and Information : Eric Rasmusen : 2001 : Blackwell Publishing : ISBN 0631210954
- Of course the last one doesn't make sense because under (b) the game has a pure NE, namely {c, y}. ~ trialsanderrors 08:00, 5 January 2007 (UTC)
- "This is a discoordination game, with no Nash equilibrium in pure strategies." : The Dark Side of the Force: Economic Foundations of Conflict Theory : Jack Hirshleifer : 2001 Cambridge University Press : ISBN 0521009170
- "This yachting rivalry is a classic example of a discoordination game which has no equilibrium in pure strategies" : International Regulatory Competition and Coordination : William Bratton : 1996 : Oxford University Press : ISBN 0198260350
- (same) : Economics of Standards in Information Networks : Tim Weitzel : 2004 : Springer : ISBN 3790800767
- It looks like Pete might be outnumbered on this one... ~ trialsanderrors 20:14, 5 January 2007 (UTC)
| h | t | |
| H | +1, +1 | –1, +2 |
| T | –1, –1 | +1, –2 |
| Almost-matching pennies | ||
-
-
-
- FWIW, I don't think the five points above contradict each other, my JtB excerpt above argues that anything that meets the definition will be a discoordination game, and the others point out that discoordination games have no pure Nash (*disclaimer: unless they have an uncorrelated asymmetry). I don't think any of these are really *defining* discoordination games, and all are true. Unless I misunderstand your point. Pete.Hurd 21:47, 5 January 2007 (UTC)
- Those are all "textbook definitions", and I'm not sure if anyone tried to come up with a more precise definition, but if I understand your JtB definition correctly it would include both H-D/Ch and a mirrored BoS, all with two pure NE's in the off-diagonal cells. That contradicts the "no pure NE" stipulation of the other definitions, although maybe there is a source out there that includes both possibilities under an umbrella definition of discoordination game (or any other term). ~ trialsanderrors 21:59, 5 January 2007 (UTC)
- I think the offdiagonal (aka bourgeois) solution isn't considered a "pure NE" in the sense that the textbook definitions intend, since it's contingent upon a role asymmetry assumed not to exist for vanilla symmetrical 2x2 games like chicken. The more I think about this the more I'm convinced that matching pennies is the only 2x2 game that has no pure NE if role asymmetries are allowed. Pete.Hurd 22:11, 5 January 2007 (UTC)
- Not quite sure if I follow this. I can create asymmetric variations of MP that have different goal conflict properties, so I'm guessing they're encapsulated in the "textbook definition" above, although I'm not sure if anyone has investigated them. ~ trialsanderrors 22:27, 5 January 2007 (UTC)
- I think the offdiagonal (aka bourgeois) solution isn't considered a "pure NE" in the sense that the textbook definitions intend, since it's contingent upon a role asymmetry assumed not to exist for vanilla symmetrical 2x2 games like chicken. The more I think about this the more I'm convinced that matching pennies is the only 2x2 game that has no pure NE if role asymmetries are allowed. Pete.Hurd 22:11, 5 January 2007 (UTC)
- Those are all "textbook definitions", and I'm not sure if anyone tried to come up with a more precise definition, but if I understand your JtB definition correctly it would include both H-D/Ch and a mirrored BoS, all with two pure NE's in the off-diagonal cells. That contradicts the "no pure NE" stipulation of the other definitions, although maybe there is a source out there that includes both possibilities under an umbrella definition of discoordination game (or any other term). ~ trialsanderrors 21:59, 5 January 2007 (UTC)
- FWIW, I don't think the five points above contradict each other, my JtB excerpt above argues that anything that meets the definition will be a discoordination game, and the others point out that discoordination games have no pure Nash (*disclaimer: unless they have an uncorrelated asymmetry). I don't think any of these are really *defining* discoordination games, and all are true. Unless I misunderstand your point. Pete.Hurd 21:47, 5 January 2007 (UTC)
- I was going to bring something like this up in relation to the introduction anyway. There are two ways to be "the opposite of a coordination game". One way, is to be a version of chicken, another is to be a game of pure conflict (as its sometimes called). I kind of thought that the forking of this article from Chicken was primarily to appease objections which were questionable to begin with. Although, perhaps, Pete had reasons of which I wasn't aware... Shall we re-merge this back into Chicken? --best, kevin [kzollman][talk] 20:25, 5 January 2007 (UTC)
- We might turn this into a disambig page and move most of the Chicken/H-D content back into Chicken. ~ trialsanderrors 20:27, 5 January 2007 (UTC)
- Fine by me (I hadn't intended on forking, but moving everything to one article under the discoordination game, I got distracted part way through the operation, and the peace/War thing just made thing muddleder). I'm still of two minds as to whether Chicken and Hawk-Dove ought to be two pages or not. This afternoon, I'm leaning towards two with some duplication... Strong opinion anyone? weak ones? ... Pete.Hurd 21:42, 5 January 2007 (UTC)
- Sorry about the phrasing, I realized you didn't mean to fork them. I'm weakly of the opinion that everything should be at either chicken (game) or hawk-dove game. Mostly, this is just because duplication is a pain. I won't be the least upset if you want them distinct, however. --best, kevin [kzollman][talk] 23:05, 5 January 2007 (UTC)
- Whups! my bad, didn't mean to sound huffy! Nothing wrong with your phrasing. The benefits of everything in one place is clear... we'll go with that... Pete.Hurd 02:19, 6 January 2007 (UTC)
- Sorry about the phrasing, I realized you didn't mean to fork them. I'm weakly of the opinion that everything should be at either chicken (game) or hawk-dove game. Mostly, this is just because duplication is a pain. I won't be the least upset if you want them distinct, however. --best, kevin [kzollman][talk] 23:05, 5 January 2007 (UTC)
- Fine by me (I hadn't intended on forking, but moving everything to one article under the discoordination game, I got distracted part way through the operation, and the peace/War thing just made thing muddleder). I'm still of two minds as to whether Chicken and Hawk-Dove ought to be two pages or not. This afternoon, I'm leaning towards two with some duplication... Strong opinion anyone? weak ones? ... Pete.Hurd 21:42, 5 January 2007 (UTC)
- We might turn this into a disambig page and move most of the Chicken/H-D content back into Chicken. ~ trialsanderrors 20:27, 5 January 2007 (UTC)
-
-
- Ummmm, see also El Farol bar problem ... Pete.Hurd 07:23, 5 January 2007 (UTC)
- Yeah, there's a ton of those which are all variants of negative externality games. ~ trialsanderrors 07:29, 5 January 2007 (UTC)
[edit] Replace Chicken (game)?
I propose we replace Chicken (game) with this article, then continue fixing it. I'm not sure how best to go about doing that, whether to simply redirect chicken & hawk dove here, or move this page to chicken and redir other things there. Pete.Hurd 03:11, 6 January 2007 (UTC)
- I can userfy Chicken and then move Disco into its old spot. ~ trialsanderrors 03:52, 6 January 2007 (UTC)
- Actually, I think doing that might not be GFDL compatible. When this article was created material from Chicken (game) was copied here, with a mention to see the history of chicken for its authors. If chicken is moved, then the history will be moved with it, and that history of the article will be lost. I think the thing to do, is
copycut and paste this article over the top of chicken. Trials, Pete, and I are the only people in the history of this article, and I suspect we don't care about attribution. (In fact, I think Pete releases his edits into the public domain, so screw what he thinks. ;) --best, kevin [kzollman][talk] 18:55, 6 January 2007 (UTC)- Yeah that sounds better. I'll release my edits to this article into the public domain. As for the rest of my valuable contributions, I'll have to consult with my team of lawyers. ~ trialsanderrors 20:53, 6 January 2007 (UTC)
- Actually, I think doing that might not be GFDL compatible. When this article was created material from Chicken (game) was copied here, with a mention to see the history of chicken for its authors. If chicken is moved, then the history will be moved with it, and that history of the article will be lost. I think the thing to do, is
[edit] Minority game
According to Bruce Edmonds' website:
- So it is in the interest of each agent to do the opposite of the majority of the other agents. In other words this is a discoordination game [note 1].
- Note 1. This has since been recently renamed as the "minority game". See the URL [1] for more details and several papers about this game.
So should we merge discoordination game with minority game, since that article is currently a stub anyway? ~ trialsanderrors 00:16, 7 January 2007 (UTC)
- And continuing the search for a proper label, there is a bit of traction for anti-coordination game. The definition matches Pete's definition of a discoordination game (symmetric, a<b, c<d), which also includes mirrored coordination games. The minority game is defined only for an odd number of players in the original Challet/Zhang paper, so while we could bend the definition a bit to make it apply to 2-player games, but I haven't seen anyone actually do that. Currently I'm inclined to redirect to coordination game and add a paragraph on on anti/discoord/minority games there. ~ trialsanderrors 09:08, 8 January 2007 (UTC)
- That's not a bad idea. Now that you bring it up, I do remember hearing anti-coordination as a name for the class of games including chicken. I don't remember where, unfortunately. --best, kevin [kzollman][talk] 18:23, 8 January 2007 (UTC)
- OK, here is what I have then: 2-player: Chicken/Hawk-Dove, Matching pennies (a discoordination game); multi-player: Crowding (negative network externalities), Congestion (multi-pick crowding game in networks), Minority (choosing sides, minority choice wins), El Farol bar (instance of a minority game). More? ~ trialsanderrors 21:28, 8 January 2007 (UTC)
- Matching pennies is only a discoordination game from the perspective of one player, for the other it's a coordination game, no? Pete.Hurd 04:06, 9 January 2007 (UTC)
- From my admittedly not very thorough survey of uses: coordination: both players want to coordinate; discoordination: one player wants, the other doesn't; anti-coordination: neither player wants to coordinate. ~ trialsanderrors 05:18, 9 January 2007 (UTC)
- Aha! now I get it. Thanks! Pete.Hurd 05:38, 9 January 2007 (UTC)
- From my admittedly not very thorough survey of uses: coordination: both players want to coordinate; discoordination: one player wants, the other doesn't; anti-coordination: neither player wants to coordinate. ~ trialsanderrors 05:18, 9 January 2007 (UTC)
- Matching pennies is only a discoordination game from the perspective of one player, for the other it's a coordination game, no? Pete.Hurd 04:06, 9 January 2007 (UTC)
- OK, here is what I have then: 2-player: Chicken/Hawk-Dove, Matching pennies (a discoordination game); multi-player: Crowding (negative network externalities), Congestion (multi-pick crowding game in networks), Minority (choosing sides, minority choice wins), El Farol bar (instance of a minority game). More? ~ trialsanderrors 21:28, 8 January 2007 (UTC)
- That's not a bad idea. Now that you bring it up, I do remember hearing anti-coordination as a name for the class of games including chicken. I don't remember where, unfortunately. --best, kevin [kzollman][talk] 18:23, 8 January 2007 (UTC)
- First draft at Coordination game#Other games with externalities. ~ trialsanderrors 06:39, 11 January 2007 (UTC)
[edit] I'm so confused...
Okay, I think I've lost track of the plan somewhere. Is this article going to become a short article on the different uses of "Discoordination game" (either a disambig or a glorified disambig)? If I want to make some edits, should I do so here or at Chicken (game)? Help me, I'm lost! --best, kevin [kzollman][talk] 20:13, 7 January 2007 (UTC)
- I think this is the article to be improved, but we should either move or cut-and-paste it into Chicken (game), as soon as Pete OK's it. ~ trialsanderrors 20:18, 7 January 2007 (UTC)
- Ummm, I made an edit to this page by accident, I had intended to make it to Chicken. I think I've ported all the post-fork diffs to Chicken, and will now redirect this page there, we'll make further changes to that page. If there's a better use for this page, then we'll undirect it... Pete.Hurd 23:58, 7 January 2007 (UTC)
- OK, now we settled this, ok to archive both talk pages at Talk:Chicken (game) and redirect this page to Talk:Chicken (game)? I'm getting confused with two parallel discussions. ~ trialsanderrors 06:59, 8 January 2007 (UTC)
- Ummm, I made an edit to this page by accident, I had intended to make it to Chicken. I think I've ported all the post-fork diffs to Chicken, and will now redirect this page there, we'll make further changes to that page. If there's a better use for this page, then we'll undirect it... Pete.Hurd 23:58, 7 January 2007 (UTC)
