Another stumper was presented to me by Robin Hanson at an OBLW meetup. Suppose you have ten ideal game-theoretic selfish agents and a pie to be divided by majority vote. Let’s say that six of them form a coalition and decide to vote to divide the pie among themselves, one-sixth each. But then two of them think, “Hey, this leaves four agents out in the cold. We’ll get together with those four agents and offer them to divide half the pie among the four of them, leaving one quarter apiece for the two of us. We get a larger share than one-sixth that way, and they get a larger share than zero, so it’s an improvement from the perspectives of all six of us—they should take the deal.” And those six then form a new coalition and redivide the pie. Then another two of the agents think: “The two of us are getting one-eighth apiece, while four other agents are getting zero—we should form a coalition with them, and by majority vote, give each of us one-sixth.”
How I would approach this problem:
Suppose that it is easier to adjust the proportions within your existing coalitions than to switch coalitions. An agent will not consider switching coalitions until it cannot improve its share in its present coalition. Therefore, any coalition will reach a stable configuration before you need consider agents switching to another coalition. If you can show that the only stable configuration is an equal division, then there will be no coalition-switching.
You can probably show that any agent receiving less than its share can receive a larger share by switching to a different coalition. Assume the other agents know this proof. You may then be able to show that they can hold onto a larger share by giving that agent its fair share than by letting it quit the coalition. You may need to use derivatives to do this. Or not.
How I would approach this problem:
Suppose that it is easier to adjust the proportions within your existing coalitions than to switch coalitions. An agent will not consider switching coalitions until it cannot improve its share in its present coalition. Therefore, any coalition will reach a stable configuration before you need consider agents switching to another coalition. If you can show that the only stable configuration is an equal division, then there will be no coalition-switching.
You can probably show that any agent receiving less than its share can receive a larger share by switching to a different coalition. Assume the other agents know this proof. You may then be able to show that they can hold onto a larger share by giving that agent its fair share than by letting it quit the coalition. You may need to use derivatives to do this. Or not.