Classifying games like the Prisoner's Dilemma

[-]Raemon5y322

I'd heard another friend discuss this idea a few months back, and thought it was a useful thing for someone to write up.

Something I found a bit difficult reading this was the arbitrariness of W, X, Y and Z (I had trouble remembering which was which). I think I'd have found it a little easier to parse the examples if they used something like XX, XY, YX, and YY. (Honestly, CC, CD, DC, DD would have been easiest to map onto my existing models, although I get part of the point here was to break from the Cooperate/Defect concept)

[-]philh5y30

Ah, yeah. I had the same trouble and that would have been way better.

[-]Raemon5y250

Curated.

A year ago, a mathematician friend of mine commented that "as far as I can tell, nobody has published a paper that just outlines all the different types of 2x2 quadrant-game payoffs", and they spent a weekend charting out the different payoff matrixes, and just meditating on how they felt about each one, and how it fit into their various game theory intuitions. But, they didn't get around to publishing it AFAICT.

This seems like a really obvious thing to do, but prior to this post I don't think anyone had written it up publicly. (if someone does know of an existing article, feel free to link here). But regardless I think a good writeup of this is useful to have in the LessWrong body of knowledge.

Real life is obviously more complicated than 2x2 payoff games, but having a set of crisp formulations is helpful for orientation on more complex issues. And, the fact that many people default to using prisoner's dilemma all the time even when it's not really appropriate seems like an actual problem that needed fixing.

I have some sense that the pedagogy of this post could be improved. I'd previously commented that using different symbols would be helpful for me. I have a nagging sense that there is other more useful feedback I could give on how to articulate some of the games, but don't have clear examples.

Those concerns are relatively minor though. Overall, thanks for the great post. :)

[-]Zack_M_Davis5y230

if someone does know of an existing article

Herbert Gintis's Game Theory Evolving (2nd edition) offers the following exercise. (Bolding and hyperlinks mine.)

6.15 Characterizing 2 x 2 Normal Form Games I

We say a normal form game is generic if no two payoffs for the same player are equal. Suppose $A = (a_{i j})$ and $B = (b_{i j})$ are the payoff matrices for Alice and Bob, so the payoff to Alice's strategy $s_{i}$ against Bob's strategy $t_{j}$ is $a_{i j}$ for Alice and $b_{i j}$ for Bob. We say two generic 2 x 2 games with payoff matrices (A, B) and (C, D) are equivalent if, for all i, j, k, l = 1, 2:

$a_{i j} > a_{k l} if and only if c_{i j} > c_{k l}$

and

$b_{i j} > b_{k l} if and only if d_{i j} > d_{k l}$

In particular, if a constant is added to the payoffs to all the pure strategies of one player when played against a given pure strategy of the other player, the resulting game is equivalent to the original.

Show that equivalent 2 x 2 generic games have the same number of pure Nash equilibria and the same number of strictly mixed Nash equilibria. Show also that every generic 2 x 2 game is equivalent to either the prisoner's dilemma (§3.11), the battle of the sexes (§3.9), or the hawk-dove (§3.10). Note that this list does not include throwing fingers (§3.8), which is not generic.

[-]philh5y160

Thanks for finding this! I'm a bit confused, though; it suggests that the game with payoffs

3,3   2,1
1,2   0,0

(an instance of Cake Eating), is equivalent to one of those named games. But... which? It only has one pure Nash equilibrium, so it can't be either hawk-dove or BOS, which both have two. And it can't be equivalent to PD - an instance of that would be

3,3   1,4
4,1   0,0

and these aren't equivalent. We have $a_{11} > a_{21}$ (3 > 1) but $c_{11} < c_{21}$ (3 < 4). So what am I missing?

(I had intended to try look this up myself, but I'm unlikely to do that in a timely manner, so I'm just leaving a comment. No obligation on you, of course.)

[-]Ben3y10

My best guess is that the book considers cake-eating to be trivial (just both eat cake), and is therefore not worried about even thinking about it, so it slipped the list.

[-]Nisan5y150

Von Neumann and Morgenstern also classify the two-player games, but they get only two games, up to equivalence. The reason is they assume the players get to negotiate beforehand. The only properties that matter for this are:

The maximin value $v_{1} = max (min (W, X), min (Y, Z))$ , which represents each player's best alternative to negotiated agreement (BATNA).
The maximum total utility $v_{2} = max (2 W, X + Y, 2 Z)$ .

There are two cases:

The inessential case, $v_{2} = 2 v_{1}$ . This includes the Abundant Commons with $2 W > X + Y$ . No player has any incentive to negotiate, because the BATNA is Pareto-optimal.
The essential case, $v_{2} > 2 v_{1}$ . This includes all other games in the OP.

It might seem strange that VNM consider, say, Cake Eating to be equivalent to Prisoner's Dilemma. But in the VNM framework, Player 1 can threaten not to eat cake in order to extract a side payment from Player 2, and this is equivalent to threatening to defect.

[-]Jameson Quinn5y100

Nicely done.

In my experience, "Farmer's Dilemma" (aka Chicken/Snowdrift) is both more common than PD, and harder for human players to coordinate away from pathological outcomes. I think it should be the prototypical "nasty" game instead of PD. We've all been assigned a group project at school; we have not all been interrogated by the police in a situation where the payoffs are truly PD.

[-]Gunnar_Zarncke4y60Review for 2020 Review

This is the only one I rated 9. It looks like a boring post full of formulas but it is actually quite short and - as Reamon wrote in the curation - completes the system of all possible cooperation games giving them succinct definitions and names.

[-]abramdemski5y60

(Under "farmer's dilemma":)

If 2W>X+Y then the socially optimal outcome is Work/Work, and a means to coordinate on that outcome would be socially useful. If 2W<X+Y, the socially optimal outcome is for one player to Work while the other Shirks, but with no obvious choice for which one of you it should be.

(Under PD / too many cooks:)

(I'm a little surprised that this is the only case where I've wanted to rename the game depending on the social preference of the outcomes. That said, the only other games where X+Y isn't forced to be greater or less than 2X are the Farmer's Dilemma and the Abundant Commons, and those are the ones I'd most expect to want to split in future.)

To my personal taste, "chicken" is the game where 2W<X+Y; I think of chicken as fundamentally being a game where there isn't a fair and socially optimal outcome w/o correlated randomness (ie in correlated equilibria, we have the "stop light" solution where one player gets a signal to go straight, with fair odds of who gets to go). It becomes "hawk/dove" when 2W $\geq$ X+Y, representing the idea that fighting can't increase the amount of resources (at best the hawk strategy doesn't destroy anything unless there's another hawk; realistically it burns some resources either way, just a lot more when there are two hawks). However, I realize this isn't standard -- it seems like a lot of people consider both games to be "chicken".

(By the way, I was surprised you labelled the section "farmer's dilemma" -- just from my experience, "chicken" is far more common, and "hawk/dove" is also quite common, but not as common as "chicken"; whereas I'd never actually heard "farmer's dilemma" before.)

[I also want to briefly point out that it's questionable to assume that the utility functions of the two players are comparable, and hence, that social welfare is necessarily captured by the sum of the two payoffs. Utility functions are always "up to a scalar", so really "symmetric game" should mean something more complicated ... but all that being said, I think you handled this the right way in the end, because we don't want to deal with that extra complexity in a classification like this.]

[-]philh5y120

To my personal taste, “chicken” is the game where 2W<X+Y; I think of chicken as fundamentally being a game where there isn’t a fair and socially optimal outcome w/o correlated randomness (ie in correlated equilibria, we have the “stop light” solution where one player gets a signal to go straight, with fair odds of who gets to go). It becomes “hawk/dove” when 2W≥X+Y, representing the idea that fighting can’t increase the amount of resources (at best the hawk strategy doesn’t destroy anything unless there’s another hawk; realistically it burns some resources either way, just a lot more when there are two hawks).

Hm. I agree that Hawk/Dove feels weird with $2 W < X + Y$ . Chicken... I think I don't have strong feelings on the question. To the extent that I do, it's hard to disentangle from "actually, the outcome where you crash into each other really is super super bad", but that's not actually necessarily true. If I think in terms of "if you both swerve, then you're both cowards", then yeah, $2 W < X + Y$ does feel natural. For the Farmer's Dilemma I feel like it can go both ways - there can be gains from working together, but also inefficiencies if e.g. you only have one bulldozer.

Farmer's Dilemma is definitely the less common name. (I didn't think I coined it myself but couldn't find any other references to it. From memory, I wrote most of the linked article without realizing it was the same as Chicken.) But I also just like it better as a name, and I have the vague sense that people equipped with that name will have an easier time recognizing instances of the problem. It's probably relevant that Order Without Law talks about problems that it calls Prisoner's Dilemmas, that I think are often Farmer's Dilemmas, in the context of... well, ranching, but close enough.

[-]abramdemski5y60

Yep, very interesting :) The different names/stories definitely make me think about the games in very different ways, such that it feels quite non-obvious that the Farmer's Dilemma is Chicken (or Hawk/Dove), intuitively.

(Actually, my mental tag for this is going to be the problem of cleaning common spaces/dishes in an apartment -- it's better if someone does it, but no one wants to do it individually.)

Also, I've probably heard people refer to the commons game as a PD, too. I think PD informally becomes a tag for a coming-apart of the individual and social good.

[-]TurnTrout5y60

If $2 W < X + Y$ , then defecting while your playmate cooperates creates value (relative to cooperating). From a social perspective, Krump/Flitz or Flitz/Krump is preferable to Krump/Krump; and in an iterated game of this sort, you'd prefer to alternate $X$ with $Y$ , than to get a constant $W$ . Wikipedia still classes this as a Prisoner's Dilemma, but I think that's dubious terminology, and I don't think it's standard. I might offhand suggest calling it the Too Many Cooks game.

But the only Nash is still $Z, Z$ , and so there is an incentive to defect from Krump/Flitz. Furthermore, that defection reduces total social welfare, so I think it makes sense to call this variant "PD" still.

[-]philh5y80

I absolutely think it makes sense, I just don't know if I endorse it. Maybe it's context dependent; someone who just wants to write about the Nash equilibria of games won't have any reason to distinguish these cases, and lumping them all under "Prisoner's Dilemma" seems absolutely fine. But Iterated Prisoner's Dilemma (in my sense) is probably a very different game from Iterated Too Many Cooks, but I'm not sure I've ever heard anyone talk about ITMC. And from a social perspective, "punish anyone who defects in a PD" makes sense but "punish anyone who doesn't cook in TMC" risks leaving value on the table.

Maybe it would make sense to call them a "(something) Prisoner's Dilemma" and a "(something else) Prisoner's Dilemma" but I'm not sure what the somethings would be.

[-]philh4y20

Maybe it would make sense to call them a “(something) Prisoner’s Dilemma” and a “(something else) Prisoner’s Dilemma” but I’m not sure what the somethings would be.

Later I used synergistic/discordant as these somethings.

[-]habryka5y60

I just cleaned up all the formatting and converted the LaTeX. Sorry for the inconvenience!

[-]philh5y40

Thanks!

[-]romeostevensit5y60

Would love to see similar for public goods games as there are so many simulations based off of them.

Very tempting to meme the graph of relations into the kabbalah tree of life diagram.

[-]philh5y60

It does seem like the "best" game, Cake Eating, takes the "most holy" slot and the "worst" one, PD, takes the "most profane" slot. TINACBNIEAC.

[-]Oscar_Cunningham5y60

I've been wanting to do something like this for a while, so it's good to see it properly worked out here.

If you wanted to expand this you could look at games which weren't symmetrical in the players. So you'd have eight variables, W, X, Y and Z, and w, x, y and z. But you'd only have to look at the possible orderings within each set of four, since it's not necessarily valid to compare utilities between people. You'd also be able to reduce the number of games by using the swap-the-players symmetry.

[-]philh5y130

Oh, I hadn't seen it before, but this file on wikipedia seems like it might be roughly that expanded version? Info Direct link to pdf I haven't looked closely at it though. The pdf doesn't render in firefox for me, but does render in evince, my external pdf viewer.

[-]philh5y30

I don't in general think there's anything wrong with comparing utilities between people in these things - that's what I'm doing when I talk about whether $2 W > X + Y$ - but it would be simpler not to do so. Still, even then I think extending to all 8 would give far too many possibilities to be manually tractable - I make it $4! \cdot 4! / 2 = 288$ .

But it wouldn't be too hard to write a program to classify them according to Nash equilibria, if someone wanted to do that. That might be a decent start.

[-]Sniffnoy4y40

I'm reminded of this paper, which discusses a smaller set of two-player games. What you call "Cake Eating" they call the "Harmony Game". They also use the more suggestive variable names -- which I believe come from existing literature -- R (reward), S (sucker's payoff), T (temptation), P (punishment) instead of (W, X, Y, Z). Note that in addition to R > P (W > Z) they also added the restrictions T > P (Y > Z) and R > S (W > X) so that the two options could be meaningfully labeled "cooperate" and "defect" instead of "Krump" and "Flitz" (the cooperate option is always better for the other player, regardless of whether it's better or worse for you). (I'm ignoring cases of things being equal, just like you are.)

(Of course, the paper isn't actually about classifying games, it's an empirical study of how people actually play these games! But I remember it for being the first place I saw such a classification...)

With these additional restrictions, there are only four games: Harmony Game (Cake Eating), Chicken (Hawk-Dove/Snowdrift/Farmer's Dilemma), Stag Hunt, and Prisoner's Dilemma (Too Many Cooks).

I'd basically been using that as my way of thinking about two-player games, but this broader set might be useful. Thanks for taking the time to do this and assign names to these.

I do have to wonder about that result that Zack_M_Davis mentions... as you mentioned, where's the Harmony Game in it? Also, isn't Battle of the Sexes more like Chicken than like Stag Hunt? I would expect to see Chicken and Stag Hunt, not Battle of the Sexes and Chicken, which sounds like the same thing twice and seems to leave out Stag Hunt. But maybe Battle of the Sexes is actually equivalent, in the sense described, to Stag Hunt rather than Chicken? That would be surprising, but I didn't set down to check whether the definition is satsified or not...

[-]sab5y30

Note: the math and the picture didn't transfer. I may try to fix it in future, but for now you might want to just read it at the original site.

Could you add a link?

[-]philh5y20

Ah, GreaterWrong makes the link very obvious, but I couldn't see it on LW. Have done, thanks.

[-]philh4y*20

I might get around to editing the post at some point, but unless/until I do, a note:

Anti-coordination: (two games)

In this game, the goal is to play a different move than your playmate. If $X = Y$ then there’s no reason to prefer one move over another, but if they’re not equal there’ll be some maneuvering around who gets which reward. If you’re not happy with the outcome, then changing the move you play will harm your playmate more than it harms you. The Nash equilibria are when you play different moves, and these are socially optimal.

Correction: if you're not happy with the outcome, changing your move will harm your playmate more than it harms you if $Y > X$ , and harm you more than them if $X > Y$ .

Also, Battle of the Sexes is an instance of this game if you relabel the moves. If you label them "do the thing you/they prefer", you get $X > Y > W \geq Z$ . ( $X$ is "we both do my thing", $Y$ is "we both do their thing", $W$ is "I do my thing and they do theirs" and $Z$ is "I do their thing and they do mine". $W = Z$ if going alone to either is equally bad.) If you label them "do the thing they/you prefer", you get $Y > X > W = Z$ . You won't get $Y > X > W > Z$ . (That would imply payoffs like: I most want to do "my thing" together. Failing that I want to do "their thing" together. But if we do go separately, I'd rather do "their thing" than "my thing". Which wouldn't be a BoS.)

[-]Jerdle4y20

X>W>Z>Y is interesting. It's similar to a PD, and so it appears that many of the same systems that evolved to enforce cooperation in PDs misfire in those cases and end up with Z (based on some observation, not any good evidence). However, unlike in a PD, Z is a worse outcome than the purely selfish X.

If a PD has the option to transfer value to your playmate and create more value, a XWZY (aka Deadlock) has the option to transfer value to your playmate inefficiently, so, in the inefficient state Z, both people are sacrificing to benefit the other, and yet each would be better off if the norm of sacrifice were not present.

EDIT: All of this assumes 2W > X + Y.

[-]MikkW5y20

I like the analysis, but W, X, Y, Z is confusing terminology- it'd be easier to read and process if I didn't have to constantly remind myself which situation each variable corresponds to

LESSWRONG
LW

LESSWRONG
LW

111

Classifying games like the Prisoner's Dilemma

111

111

6.15 Characterizing 2 x 2 Normal Form Games I

Cake Eating: $W > ∙ > ∙ > Z$ (two games)

Let's Party: $W > Z > ∙ > ∙$ (two games)

Studying For a Test: $W > X > Z > Y$ (two games)

Stag hunt: $W > Y > Z > X$ (two games)

The Abundant Commons: $X > W > ∙ > ∙$ (five games)

Farmer's Dilemma: $Y > W > X > Z$ (two games)

Anti-coordination: $∙ > ∙ > W > Z$ (two games)

Prisoner's Dilemma/Too Many Cooks: $Y > W > Z > X$ (three games)

A graph

A change of basis?

Footnotes

111

Classifying games like the Prisoner's Dilemma

111

111

6.15 Characterizing 2 x 2 Normal Form Games I

Cake Eating: W>∙>∙>Z (two games)

Let's Party: W>Z>∙>∙ (two games)

Studying For a Test: W>X>Z>Y (two games)

Stag hunt: W>Y>Z>X (two games)

The Abundant Commons: X>W>∙>∙ (five games)

Farmer's Dilemma: Y>W>X>Z (two games)

Anti-coordination: ∙>∙>W>Z (two games)

Prisoner's Dilemma/Too Many Cooks: Y>W>Z>X (three games)

A graph

A change of basis?

Footnotes

Cake Eating: $W > ∙ > ∙ > Z$ (two games)

Let's Party: $W > Z > ∙ > ∙$ (two games)

Studying For a Test: $W > X > Z > Y$ (two games)

Stag hunt: $W > Y > Z > X$ (two games)

The Abundant Commons: $X > W > ∙ > ∙$ (five games)

Farmer's Dilemma: $Y > W > X > Z$ (two games)

Anti-coordination: $∙ > ∙ > W > Z$ (two games)

Prisoner's Dilemma/Too Many Cooks: $Y > W > Z > X$ (three games)