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?
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.