Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

When teaching basic fair division algorithms, the students always propose some simple and (at the first glance) correct solutions for $n$ players, which unfortunately are not correct! The only way I know to prove that such an algorithm is not fair is to set an extreme example and talk about the different valuations of the player. But the students' reaction usually is something like this: "Is he [=on of the players] an idiot? How can he think that this piece is bigger that that one?!"

My question: How can the differences between valuations be explained to prevent from these reactions? Are there better stories for the problem (instead of dividing water) so that the different valuations emerge more naturally and be believable?

Let's look at an example. This is one of such incorrect solutions for the three-player:

problem: A and B and C are going to divide some water, fairly.

  1. A pours the water in three glasses equally (from his view point).
  2. B and C each select two glasses with less water.
  3. There has to be at least one glass in common. This is will be A's glass.
  4. Now B and C follow the solution for two-player problem (i.e. B devides whole the water in remaining two glasses into two glasses equally and C selects one of them. The last glass is C's).

This pictures show the steps above, with B's valuation:

1.

enter image description here

2.

enter image description here

3.

enter image description here

So if B divides the water in two glasses equally, then he gets to $\dfrac{1}{2} (50\%+2\%)=26\%$ of the whole water which is less than $\dfrac{1}{3}$ according to B's valuation.

share|improve this question
1  
Does the resource to be divided have to be homogeneous? Or could the resource have parts which are different, say, like a cake with different toppings? –  Joel Reyes Noche Nov 20 '13 at 10:06
    
It can have different parts. But when some part is undesirable to one player and desirable to the other, then the competition can become trivial, can't it? –  Behzad Nov 20 '13 at 10:10
    
Yes, but at least the valuations will become "believable." Player A prefers nuts, Player B hates them, Player C has no preference. We don't think that any of the players are idiots. –  Joel Reyes Noche Nov 20 '13 at 10:12
1  
Well, you don't have to make the figures so extreme. You could use 29/35/36 instead of 2/48/50, for example. If the glasses have different shapes, it's often difficult to make these judgments correctly. –  TonyK Nov 20 '13 at 10:31
    
@TonyK Yes, you're examples works as well. But it's not the main point: The students should understand that there is no scale that all of the players accept (not weight, neither the number of water drops). So your'e suggestion is just half way into solving the difficulty. –  Behzad Nov 20 '13 at 10:36
add comment

1 Answer

In Brams, Jones, and Klamler's article in the Notices of the AMS, they illustrate differences in valuations using a cake that is part chocolate and part vanilla (see page 1315). The advantage with this approach is that the valuations are believable.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.