VII: Fair Division Quick Summary

Elements of a Fair Division Problem 1. A set of N players: P₁ , P₂ , . . . , P_N 2. A set of goods, S

The problem is to divide the set S into N shares (s₁ , s₂ , . . . , s_N) so that each player gets a fair share of S.

A fair share is any share that, in the opinion of the player receiving it, has a value that is at least 1/N of the total value of the set of goods, S.
(N is the number of players.)

A fair division scheme is a set of rules that, when properly applied, produces a fair division of the objects to be divided.

We expect any fair division scheme to satisfy the following conditions:

• The procedure is decisive. If the rules are followed, a fair division is assured.

• The procedure is internal to the players. It requires no outside intervention.

• Players have no knowledge of each others’ value systems (likes, dislikes, etc.).

• Players are rational. (They make logical decisions).

A Fair Division Scheme does NOT guarantee each player a fair share. (A player may misplay the game.)
It DOES guarantee that it is impossible for other players or bad luck to deny a player his/her fair share.

3 Continuous Fair Division Schemes

The Divider-Chooser Method (The ‘You cut, I choose’ Method. Works only when there are 2 players) Procedure:

• A randomly chosen player (the Divider) divides the set S into 2 pieces.
• The other player (the Chooser) selects the piece.

 

The Lone Divider Method (Procedure for 3 players):

• A randomly chosen player (the Divider) divides the set S into 3 pieces s₁ , s₂ , s₃.

• The other players (the Choosers) independently list all acceptable pieces.

• Case 1: A player selects more than 1 piece
  RESULT: Each player is given an acceptable piece.
  Case 2: Choosers select different pieces
  RESULT: Each player is given an acceptable piece.
  Case 3: Choosers select only one piece but it is the same piece
  RESULT: Standoff resolved by randomly giving one of the other two pieces to the divider, recombining the 2 remaining pieces and applying the Divider-Chooser Method.

   

The Last Diminisher Method Procedure:

• Randomly order Players: P₁ , P₂ , … , P_N.
• P₁ cuts a piece.
• P₂ either claims a subpiece of P₁’s piece (becomes a Diminisher) or passes to contend for a piece of the rest.
• Case 1: P₂ becomes a Diminisher.
  RESULT: The difference between the 2 claims is put back and P₁ becomes a Contender.
  Case 2: P₂ passes.
  RESULT: Play passes to P₃.
• Each remaining player, in turn, diminishes or passes. When all have played, the last diminisher gets his/her piece and departs.
• The process begins again with one less player. When 2 players remain, use Divider-Chooser.

2 Discrete Fair Division Methods

The Method of Sealed Bids Procedure:

• Each player makes a sealed bid, giving an estimate of the dollar value of each item. Each player’s fair share is computed by
  dividing the total of the player’s bids by the # of players.
• Each item goes to the highest bidder for that item (breaking ties in a pre-determined fashion) and the player adds/subtracts from the pot the difference between his/her fair share and the total value of the items allocated to that player.
• Any cash left in the pot at the end of this process is divided evenly among the players.

Necessary conditions:

• Each player must have enough money to play.
• Each player must accept money as a substitute.
• Player’s must have no useful information about each other’s value systems prior to the bidding.

The Method of Markers Procedure (requires many more items than players):

• The items are linearly ordered.
• Each player independently & secretly divides the items into N consecutive segments with markers.
• From the set of all players’ first markers, choose the player with the first (leftmost) marker and give that player his/her first segment.
  Remove all of that player’s markers.
• Move to the second set of markers & repeat the process above. (Player with first marker in the second set receives his/her 2nd segment.)
• Continue until each player has a segment. (The last player receives his/her last segment.)
• Leftovers: If there are more leftovers than players, use the Method of Markers again. Otherwise, use a lottery.

Necessary conditions:

• There must be many more items than Players.
• Every Player must be able to divide the array of items into segments of equal value.

Practical way to carry out the Methods of Markers procedure (using an example)

EXAMPLE:  Three players (A, B & C) agree to divide the 12 items below (numbered 1 - 12).  Their markers have already been placed.

STEP 1: Put the items in a line and if they are not already numbered, number them (from left to right).

STEP 2: Put down the markers if that is not already done.

STEP 3: Create a table with the name of each player as a row label.  Label the columns with the segment numbers that the items will be divided into (3 players = 3 segments, 4 players = 4 segments, etc.).

STEP 4: Complete the table by listing each player's segments as determined by their markers.

STEP 5: Give away a first segment to the Player whose first segment ends first.

Since Player A's first segment ends at 1, Player A gets his/her first segment. (Item 1)

STEP 6: Mark the Player who got a segment out of the table and move to the second segment.  Give away a second segment to the Player whose second segment ends first.

Since Player C's second segment ends before all remaining Players' second segments, Player C gets his/her second segment. (Items 4-9)

STEP 7: Continue this process, giving away segments until each Player has a segment.

Since Player B is the only Player yet to get a segment, give Player B his/her third segment. (Items 11-12)

STEP 8: List the set of Leftover Items.

Leftovers: Items 2, 3, 10

Back