Many Players
The problem can be extended to three or more people, but the method for finding an optimum solution becomes complicated.
A simple method, the Successive Pairs Algorithm, continues the division to successively smaller "equal" portions. The first person divides the resource into what they believe are equal halves. The second then chooses a half, leaving the remainder for the first person. Each of these two people then divide their respective portions into thirds. The third person picks two of the resulting portions: one from the first person and one from the second person. If there are four people, each of the first three people divides their portions into fourths, and the process continues.
An early method due to Banach and Knaster, the Last Diminisher Algorithm, depends on trimming pieces. It begins with the first person portioning off of the resource (for people). Each following person then examines the portion in turn, removing a part for themselves if they believe the portion to be larger than . The last person to remove part receives the portion. The process continues until the entire resource has been fairly divided.
Straightforward algorithms like those above can lead to the resource being divided into a very large number of tiny bits. Straightforward use of the successive pairs algorithm would generate pieces, in fact only about are needed as each person only really needs to do cuts when the th player comes along. Last diminsher only needs cuts. Algorithms using divide and conquer can reduce the number considerably to bring the number of cuts down to about .
The Dubins-Spanier moving knife procedure also achieves proportional division. It was the first example of a continuous procedure in fair division. The knife is passed over the cake from one end to the other. A player says stop when they think of the cake is to the left of the knife, the cake is cut and they get that piece. Repeat with the remaining cake and players, the last player gets the remainder of the cake. Similar to the last diminisher procedure, it can be used to cut the cake into contiguous parts for each player.
Proportional division, where the entitlements of players differs, can for rational ratios be handled by treating each player as a number of proxy players each entitled to the same amount.
Read more about this topic: Proportional (fair Division)
Famous quotes containing the word players:
“People stress the violence. That’s the smallest part of it. Football is brutal only from a distance. In the middle of it there’s a calm, a tranquility. The players accept pain. There’s a sense of order even at the end of a running play with bodies stewn everywhere. When the systems interlock, there’s a satisfaction to the game that can’t be duplicated. There’s a harmony.”
—Don Delillo (b. 1926)
“The whole idea of image is so confused. On the one hand, Madison Avenue is worried about the image of the players in a tennis tour. On the other hand, sports events are often sponsored by the makers of junk food, beer, and cigarettes. What’s the message when an athlete who works at keeping her body fit is sponsored by a sugar-filled snack that does more harm than good?”
—Martina Navratilova (b. 1956)