Envy-free fair division, how does one do it?
A team project for MA279, Fall 2013
Team members: Erica Wimer, H. Hicks, J. David, Ehren Coburn.
Proportional fair division vs. Envy free division
In chapter 3, we learned several methods of proportional fair division. The goal of proportional fair division is always that each player will get a proportional fair share of the booty (item or items being divided). A proportional fair share is defined as a share that is worth at least 1/Nth of the total value of the booty in the eyes of the player receiving it. This can appear confusing at first because each player can have a different idea of what the booty is worth and what 1/Nth of the booty is. However the players divisions, choices, or bids will materialize what their beliefs are about the worth of the booty.
Envy free division has occurred if each player believes that no other player’s share is as valuable as his share. No player envies any other players’ share. Envy free division is always proportional, however only certain methods of proportional division are also envy free.
The 2 player divider/chooser method is always envy-free by nature (thus also proportional). However, when dealing with 3 or more players, things get more complicated. We must turn to methods such as: the Brams and Taylor envy free procedure, The Selfridge–Conway discrete procedure, and the Stromquist moving-knife procedure.
The Brams and Taylor envy free procedure can be applied to any number of people. It is thus one of the more applicable and widely used methods. Check out this video to see Steven Brams talk about how his work was applied in politics.
[[1]]
Selfridge-Conway Discrete Procedure
We will now analyze an envy-free method of dividing a cake among 3 players. I will refer to all 3 players as girls, just for simplicity.
We begin with the whole cake. Consider the first player to cut the cake to be Player 1, who cuts it into 3 equal slices (to her, each worth 1/3). However, in player 2’s eyes, slice A is the largest, so Player 2 cuts off a slice of A to make it equal (in her eyes) to the size of the 2nd largest slice.
So, at this point: Player 1 believes B=C and B>A1 and C>A1 Player 2 believes A1=B OR A1=C Player 3 believes B≥ ⅓ and C ≥ ⅓ and A1 ≥ ⅓
Since Player 2 thinks the two largest slices are equal, the order the players choose in is Player 3, Player 2, and finally, Player 1. Player 3 will choose any slice, but Player 2 is set to the limitation that if Player 3 doesn’t pick A1, then Player 2 must.
This leads to 3 Cases: Case 1: Player 3 chooses A1, then Player 2 chooses B OR C, and Player 1 gets remaining slice. Case 2: Player 3 chooses B, then Player 2 chooses A1, and Player 1 gets the remaining slice. Case 3: Player 3 chooses C, then Player 2 chooses A1, and Player 1 gets the remaining slice.
This leaves the trimmings A2, to be divided. To do this, we must define the player who chose slice A1 (either Player 2 or Player 3) “PA” and the other player “PB.” From this point on, our players will be referred to as PA, PB, and P1. Since PB is the player, between Player 2 and Player 3 that did not receive slice A1, PB gets to cut A2 into 3 equal pieces (in her eyes).
PA chooses first, say A21. P1 chooses next, say A22. PB chooses last, A23.
Now: PA has A1 and A21 PB has B and A23 P1 has C and A22
We know everyone is envy free because: 1) PA believes A1≥B and A1≥C, since he chose A1. Also, we know in PA’s eyes, A21≥A22 and A21≥A23 because PA chose first. 2) PB believes B≥A1 and B≥C. Also, since PB cut A2 into A21, A22, and A23, all pieces are ≥⅓ of A2.
3) P1 believes C≥A1 and C=B, we know this because she originally cut the cake into 3 equal slices and A was cut such that A=A1+A2, so this tells us C≥A1+A21. Also, P1 chose his piece of A2 before PB, so A22≥A23.
So all players believe they received ≥⅓ of the cake and are envy free. [[2]]
Brams-Taylor Method
The Brams-Taylor Method uses a method of trimming to make equal pieces to share using cake. You can have as many players as you want, which will create N amount of pieces where N = the amount of players. The first step is P1 cuts the cake into N equal slices. P2 gets N – 2 cuts so he can try to create N – 2 equal pieces. P3 gets N-3 cuts to try and make N - 3 equal pieces and so on. Finally, PN Chooses the piece they desire, then and then every player who cuts chooses backwards from the original order. For example P1 will choose last, because he had the opportunity to trim the most pieces. The only catch is that if a piece you trimmed is still able to be chosen, you must choose it. This makes it fair, because if you trimmed a piece too small and nobody else wants it, you must take it. Everyone in this case is satisfied with their piece, and if they are not then it is their own fault and nobody else’s, so this is truly envy-free fair division.
Moving-Knife Theorem
We again will analyze an envy-free method of dividing a cake among 3 players. I will refer to all 3 players as boys, just for simplicity. Also, a “referee” will be used in this method.
We begin with a whole cake. Have the referee move a knife along the cake until a player calls stop when they believe the knife reaches ⅓ of the cake (in their eyes). The player that calls stop will then be Player 1. This same player that called “stop” also places the second mark on the cake in such a way to divide the cake in to 3 equal slices (in his eyes). Player 2 and Player 3 did not mark the cake so obviously, in their eyes, A≤⅓, B≥⅓, and C≥⅓.
This leads to 3 Cases: Case 1: Player 2 and Player 3 want different pieces of the cake and there is no more division required. All players believe they each received ≥⅓ of the cake. Case 2: Player2 and Player 3 both prefer slice B. Case 3: Player 2 and Player 3 both prefer slice C.
Lets now take a look at Case 2. Bring back the referee and have him move a knife left, starting at the right side of slice B. Simultaneously, have player 1 move a second knife right, starting at the left side of slice, at the same speed as the referee. This is important because it ensures that slices A and C increase in size at the same rate and thus, are still of equal size in the eyes of Player 1. Obviously slice B is getting smaller in the eyes of Player 1 and he no longer wants slice B. Since slice B seemed larger in the eyes of Player 2 and Player 3, this allows slice B to get smaller as A and C get larger until, in the eyes of say, Player 2, one of the larger slices, now called A’ and C’ is of equal size to the new, smaller slice B’. When this happens, Player 2 says “stop,” and marks the new portion of each slice.
At this point: Player 1 believes A’=C’ but A’>B’ and C’>B’ Player 2 believes A’=B’ OR C’=B’ Player 3, since he never called “stop,” believes B’≥A’ and B’≥C’
So give Player 3 slice B’, give Player 2 which ever slice (A’ or C’) he believes was equal in size to B’, and give Player 1 the remaining slice. All players believe they received ≥⅓ of the cake.
Lets now take a look at Case 3. Bring back the referee and have him move the knife right, starting from the right side of B. Simultaneously, have Player 1 move a second knife right, starting at the left side of B, at the same speed as the referee. This is important because it ensures that slices A and B increase in size at the same rate and thus, are still of equal size in the eyes of Player 1. Obviously slice B is getting smaller in the eyes of Player 1 and he no longer wants slice B. Since slice C seemed larger in the eyes of Player 2 and Player 3, this allows slice C to get smaller as A and B get larger until, in the eyes of say, Player 2, one of the larger slices, now called A’ and B’ is of equal size to the new, smaller slice C’. When this happens, Player 2 says “stop,” and marks the new portion of each slice.
At this point: Player 1 believes A’=B’ but A’>C’ and B’>C’ Player 2 believes A’=C’ OR B’=C’ Player 3, since he never called “stop,” believes C’≥A’ and C’≥B’
So give Player 3 slice C’, give Player 2 whichever slice (A’ or B’) he believes was equal in size to C’, and give Player 1 the remaining slice. All players believe they received ≥⅓ of the cake and therefore, are envy-free. [[3]]
Dividing the Spoils
A political scientist named Steven Brams and a mathematician named Alan Taylor worked together for over two years to create a end-all may to fairly divide anything.
The text gives an example of a case in the bible (1 Kings 3:16-28) where King Solomon had to divide a baby between two mothers. He asked for a sword, and one mother said to split the baby in two while the other asked Solomon to stop. This ended up being the true mother. The issue of this division is that here are many people who want something and they all place different values on what is being divided.
Mathematically the problem came from 1940’s Poland, where a polish scientist named Steinhaus focused on dividing cake so that everyone receives a fair share. Steinhaus was the first to say that he more people’s desires differ in a fairness problem, the easier it is to solve. Everything depends on each player believing they have a fair share and the best share they can get. If they believe someone else has more than their share, they might break the game. Envy may make a player perceive that another has a larger share and thus may cause trouble.
During WWII, Steinhaus proved through an indirect proof that there is in fact envy-free solutions, he just didn’t have the procedure figured out. Trying to make a fair way to divide a cake into three, Brams came up with a method where player 1 custs the cake into 3 equal bits. Then player 2 trims a piece if it looks bigger than the other two to them. Player 3 chooses a piece, player 2 chooses a piece, and then player 1 gets the last piece. This of course left out the trimmings. He then got the idea to do the same procedure on the trimmings infinitely until the trimmings were so small that no one cared. He then tried to apply this to four people. Unfortunately he couldn’t figure it out and thus looked for help. Taylor, the mathematician, for 4 people came up with: player 1 divides the cake into 5 pieces, player 2 trims at most two pieces to create a 3-way tie in their eyes. Player 3 divides at most 1 piece to create a two-way tie. Player 4 chooses and then 3, 2, 1, with any player having trimmed being forced to take one of their pieces if any of them are available. This leaves a bit of cake left to be taken if anyting screwy happens. Taylor then moved to expand the game to more players. According to his formula, player 1 must cut 2n-2+1. Taylor then proved that the cake could be divided in a finite number of steps, thus satisfying everyone. The two wrote a book called Fair Division: From Cake-Cutting to Dispute Resolution.
This theory may even be used in a bads-game, so to speak. The example used in the text is diving up chores, where players may add chores to each list until they feel that each list is equal in their eyes. This method may even be applied to divorce and other such issues where players try to spite eachother rather than choose what is best for them. [[4]]
Mathematical Reactions by Ian Stewart
Simplest cases involve two people, with player1 cuts and player 2 chooses. This can be traced back 2800 years. This grows much more complicated with three people. First solution to 3 person fair-division was by Hugo Steinhaus in 1944, involving trimming outlined below:
1) Player 1 cuts cake into pieces A,B where he thinks A is of worth 1/3 and B is of worth 2/3
2) Player 2 trims A so it has 1/3 worth in player 2’s eyes if he thinks it is more than 1/3. Otherwise it is left alone.
3) Player 3 may take A or not take A.
4) a) if Player 3 takes A, players 1 and 2 do the two player division on the rest of cake. b) If player 3 doesn’t take A and A was trimmed by player 2, player two takes A. c) If player 3 doesn’t take A and A wasn't trimmed, player 1 takes A.
The premise is that anyone who isn’t happy is of their own fault and they can’t blame anyone else.
There is another method dealing with a moving knife, where players yell shout when they perceive that a knife is about to cut what they believe is cutting 1/nth of the cake. The procedure may be repeated as necessary but has its flaws.
There is the method for 3 where the cake is split in two, then each half is cut into 3, and the third person takes 1/3 from each half and the other two get what is left of theirs. [[5]]
