Le 4 mai 2021, la plateforme Yahoo Questions/Réponses fermera. Elle est désormais accessible en mode lecture seule. Aucune modification ne sera apportée aux autres sites ou services Yahoo, ni à votre compte Yahoo. Vous trouverez plus d’informations sur l'arrêt de Yahoo Questions/Réponses et sur le téléchargement de vos données sur cette page d'aide.
Incentive-Compatible Division Procedures?
So, most people should be familiar with the fail-safe way for 2 people to divide an object:
- The first person cuts the object into 2 pieces
- The second person chooses the object they wish to take first.
Since the second person is going to choose the largest available piece, the first person has a strong incentive to make an even cut, as if it is un-even, they will get less of the final product.
So, I got around to thinking about this problem in the case of N people. Here is a procedure that I think is incentive-compatible for 3 people:
- The first person makes 2 pieces, designating one as a 'small' piece and one as a 'large' piece
- The second person gets 2 choices. They may:
- Take the 'small' piece for themselves. The large piece is then divided using the 2-person division procedure between the first and third person
- Give the 'small' piece to the first person, and split the large piece with the 3rd person - using the same procedure used for 2 people.
So, here's a bunch of somewhat open-ended questions.
- Does my procedure for 3 people work? Can you prove it, preferably somewhat elegantly? If it does not work, show how it can be broken.
- The procedure for 3 people build recursively on the 2 person procedure. If this procedure works... can we construct a general procedure for N-people that also works recursively?
What do you all think?
Ah, I suppose that is correct. If 1 person makes all the cuts, but chooses last, that is the only incentive needed to force equal pieces.
So - let's keep the problem discussion interesting by mandating that each person can only ever make 1 cut, i.e. making 2 pieces out of something.
2 réponses
- ChrisLv 4il y a 9 ansRéponse favorite
The principle can be applied to any number of divisions.
The main thing is that only one person cuts all pieces and they choose last.
Say 3 people want a third of a cake - if only one person makes the cut and has last choice of piece then they will ensure they cut them as evenly as possible so they are not left with a smaller piece to the other two
It comes down to is anyone willing to make the cut and then choose last OR do you trust anyone else to do it.