Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
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 Answers
- ?Lv 49 years agoFavorite Answer
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.