MA 111 Agenda - Wednesday, 12.7.2011(Notes from Elizabeth Weaver.)12.7.1 The Method of Markers• The method of markers is a discrete fair division method. Unlike the method of sealed bids, players are not requiredto put up any money.• This method can be used when there are more items to be divided than there are players in the game and when allof the items are reasonably close in value.• The Method of Markers for N Players:1. Preliminaries: The items are lined up randomly in a fixed sequence called an array.2. Bidding: Each player independently divides the array into N segments by placing N − 1 m arkers along thearray. These markers divide the array into N segments of consecutive items.3. Allocations: Scan the array from left to right and locate the first first marker. The player owning this markergoes first and gets the first segment in his bid. (In the case of a tie, flip a coin.) This player’s markers areremoved. Continue scanning from left to right, and locate the first sec ond marker. The player owning thismarker then receives the second segment in his bid. Continue this process until everyone has received a segmentof their bid. The last player will receive the last segment of their bid.4. Dividing the Surplus: The players get to go in some random order and pick one item at a time until all thesurplus items are given out.• Example: Four players (A,B,C,and D) are dividing the array of 18 items shown below using the metho d of markers.The players’ bids are as indicated in the figure.(a) Which items go to A?(b) Which items go to B?(c) Which items go to C?(d) Which items go to D?(e) Which items are left over?• Example: Four players (A,B,C,and D) are dividing the array of 15 items shown below using the metho d of markers.The players’ bids are as indicated in the figure.(a) Which items go to A?(b) Which items go to B?(c) Which items go to C?(d) Which items go to D?(e) Which items are left over?• Example: Sheldon, Leonard and Penny are dividing 3 Snickers bars, 3 Nestle Crunch bars and 3 bags of Skittles.The following table shows the amount of money each player is willing to pay for each type of candy.Sheldon $1.50 $0.50 $1.00Leonard $0.00 $0.00 $1.00Penny $1.00 $1.00 $1.00Assume the candy is arranged as below:(a) Find the dollar value of each player’s fair share. (Remember that there are 3 Snickers bars, 3 Crunch bars, and3 bags of Skittles.)(b) Place the markers for each player in the figure above. (Use S1,S2 for Sheldon, L1,L2 for Leonard, and P1,P2 forPenny.)(c) Describe the allocation of candy to each player and which candy is left over.(d) Suppos e that the players decide to divide the leftover pieces by a random lottery in which each player gets tochoose one piece. Suppose that Sheldon gets to choose first, Penny second, and Leonard last. Describe thedivision of the left over pieces.12.7.2 After this lecture, you should be able to...• find a fair division using the metho d of markers• place players’ markers based on their value
View Full Document
Unlocking...