You could generalize to games where all players can achieve their best possible utilities by coordinating, and these utilities don’t have to be symmetric. For example, a coordination game with (5,5) and (10,20). Maybe your proof already works for this case.
Then you could try generalizing to games where some subset of players can jointly enforce their best possible utilities regardless of what other players do, but unfortunately that fails. For example, imagine three people, one of whom must be sacrificed to Cthulhu so the other two may live. The person to be killed is chosen by majority vote, and in case of tie they all die. Then any two people can ensure maximum utility for themselves by voting to kill the third, but the solution isn’t unique.
I believe the same proof method works when players share the same ordering on outcomes; the important thing is that it’s more likely to jump from a bad state to a good state than vice versa.
I think the main issue with the Cthulhu example is that, if person A is voting for person B and person B is voting for person A, then person C is indifferent between voting for person A or person B. But I expect that the same proof method from the post shows that, if any subset can ensure their strict maximum utility by coordinating, then they will.
What does “strict maximum utility” mean—achieving the unique outcome that maximizes utility? That seems too restrictive, e.g. in a coordination game with (10,10) and (10,10) I want the players to find an optimal outcome even though it’s not unique. Can you make it precise?
Edit: your condition “all players share the same ordering on outcomes” also seems too restrictive. My condition “all players can achieve their best possible utilities by coordinating” is more lenient, because it doesn’t care about ordering of non-optimal outcomes. So maybe you could push in that direction as well.
Yes, that is what I meant by strict maximum utility. Agree this is too restrictive. I don’t know what similar criterion would be both good to have and achievable, given the Cthulhu example.
Regarding all players achieving their best possible utilities by coordinating: what about a case where player A’s utility is always 0, and player B’s utility is 1 if player A takes action 1 and 0 if player A takes action 2? They can both achieve their best possible utilities by coordinating but I don’t think that means player A should necessarily take action 1.
Great example, I didn’t think of that. Maybe the right criterion is that some achievable utility vector must be strictly superior to all other achievable utility vectors on all coordinates. But it shouldn’t have to correspond to a unique outcome, so the (10,10) (10,10) example could still work. Would that be possible with your approach?
You could generalize to games where all players can achieve their best possible utilities by coordinating, and these utilities don’t have to be symmetric. For example, a coordination game with (5,5) and (10,20). Maybe your proof already works for this case.
Then you could try generalizing to games where some subset of players can jointly enforce their best possible utilities regardless of what other players do, but unfortunately that fails. For example, imagine three people, one of whom must be sacrificed to Cthulhu so the other two may live. The person to be killed is chosen by majority vote, and in case of tie they all die. Then any two people can ensure maximum utility for themselves by voting to kill the third, but the solution isn’t unique.
I believe the same proof method works when players share the same ordering on outcomes; the important thing is that it’s more likely to jump from a bad state to a good state than vice versa.
I think the main issue with the Cthulhu example is that, if person A is voting for person B and person B is voting for person A, then person C is indifferent between voting for person A or person B. But I expect that the same proof method from the post shows that, if any subset can ensure their strict maximum utility by coordinating, then they will.
What does “strict maximum utility” mean—achieving the unique outcome that maximizes utility? That seems too restrictive, e.g. in a coordination game with (10,10) and (10,10) I want the players to find an optimal outcome even though it’s not unique. Can you make it precise?
Edit: your condition “all players share the same ordering on outcomes” also seems too restrictive. My condition “all players can achieve their best possible utilities by coordinating” is more lenient, because it doesn’t care about ordering of non-optimal outcomes. So maybe you could push in that direction as well.
Yes, that is what I meant by strict maximum utility. Agree this is too restrictive. I don’t know what similar criterion would be both good to have and achievable, given the Cthulhu example.
Regarding all players achieving their best possible utilities by coordinating: what about a case where player A’s utility is always 0, and player B’s utility is 1 if player A takes action 1 and 0 if player A takes action 2? They can both achieve their best possible utilities by coordinating but I don’t think that means player A should necessarily take action 1.
Great example, I didn’t think of that. Maybe the right criterion is that some achievable utility vector must be strictly superior to all other achievable utility vectors on all coordinates. But it shouldn’t have to correspond to a unique outcome, so the (10,10) (10,10) example could still work. Would that be possible with your approach?
Yes, I think that will work.