Fair Division: Method of Markers

The method of markers applies to problems of fair division in which the goods could be arranged in a linear fashion. This may be the case of a large number of small items to be shared, or a continuous item, like a gold chain, to be cut into pieces. That done, each of the N players indicates his or her opinion as regard a fair division by placing N-1 markers and agrees to accept any segment of the goods that lies between any pair of his or her consecutive markers.

The algorithm works this way. First consider all the first markers - one from each player, and find the leftmost among them. The owner of the marker receives the first segment (the one from the left end and up to the marker itself) and all the remaining markers of that player are removed from further consideration.

Next find the leftmost among the second markers. The owner of the marker receives the segment of the goods that ends at that marker and starts with the previous marker of that same player. All other markers of the player are removed from further consideration. And so on.

Chances are that after each of the players received what in his or her view is necessarily a fair share, some items will remain undivided. (These are black portions of the top multicolor bar in the applet.)

(The colorful horizontal bars are rails on which the vertical bars - the markers - slide. The points of intersection with the small circle drawn are draggable. The top bar represents the goods to be shared in the required linear arrangement.)

Copyright © 1996-2009 Alexander Bogomolny