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 required to 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 all of 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 markers along the array 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 marker goes first and gets the first segment in his bid In the case of a tie flip a coin This player s markers are removed Continue scanning from left to right and locate the first second marker The player owning this marker then receives the second segment in his bid Continue this process until everyone has received a segment of 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 the surplus items are given out Example Four players A B C and D are dividing the array of 18 items shown below using the method 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 method 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 Leonard Penny 1 50 0 00 1 00 0 50 0 00 1 00 1 00 1 00 1 00 Assume 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 and 3 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 for Penny c Describe the allocation of candy to each player and which candy is left over d Suppose that the players decide to divide the leftover pieces by a random lottery in which each player gets to choose one piece Suppose that Sheldon gets to choose first Penny second and Leonard last Describe the division of the left over pieces 12 7 2 After this lecture you should be able to find a fair division using the method of markers place players markers based on their value systems
View Full Document
Unlocking...