Exact division

From Wikipedia, the free encyclopedia

In game theory, an exact or even division is a type of fair division where all the players believe everyone received the same amount.

There is no finite fair division procedure for exact division of divisible goods. However there are moving knife procedures for two players. For more than two players only near exact procedures are known, this is sufficient though to enable envy-free fair division procedures to be devised for any number of players.

There are a number of existence proofs derived from measure theory or topology for exact divisions in various circumstances.

Divisions of this type are much easier if the participants cooperate in establishing entitlements rather than competing as in fair division. Some authors refer to this as consensus division or consensus halving.[1][2]

Two players

The original procedure for exact division of a cake devised by A.K.Austin is as follows:[3]

  • The first player places one knife on the left of the cake and a second parallel to it on the right where he judges it splits the cake in two.
  • The first player moves both knives to the right so half the cake is always between the two knives.
  • The second player says stop when they think half the cake is between the knives.

If the first player reaches the end he must have his left knife positioned where the right knife started. The intermediate value theorem establishes the second player must be satisfied the cake is halved at some point. Giving the pieces at random to the players can be used to ensure they don't favour either part.

One knife can be used to achieve the same effect. The first player rotates the knife over the cake through 180° keeping a half on either side and the second player says when they agree. The first player must of course end the turn with the knife on the same line as where it started.

Exact division with any rational ratio of entitlements can also be achieved for two players by a slightly more complicated procedure.

Near exact division

For more than two players there is no known procedure for exact division, but near exact divisions are possible. This means for any given \epsilon >0 one can ensure the players each believe the values everyone has differ by less than \epsilon .

This is achieved by the players all splitting up the cake into tiny bits and assigning a value to each bit. This means each bit has a vector of values, one per player. The bits are then selected so the players get allocations in near exact proportion to their entitlements. This can always be done due to a theorem by V.Bergström.[4][5]

A constructive way to divide a resource in two parts with n cuts so all of n people think the halves are of equal was established in 2003.[6] This consensus halving theorem uses the Borsuk–Ulam theorem and Tucker's lemma and the n cuts is the minimum possible.

Existence proofs

Both the necklace splitting problem and a generalization of the ham sandwich theorem can be used to establish existence proofs for exact divisions in various circumstances.[7]

References

  1. ↑ de Longueville, Mark; Rade T. Živaljević (2008), "Splitting multidimensional necklaces", Advances in Mathematics 218: 926–939, doi:10.1016/j.aim.2008.02.003. 
  2. ↑ Simmons, Forest W.; Francis Edward Su (2003), "Consensus-halving via theorems of Borsuk-Ulam and Tucker", Mathematical Social Sciences 45: 15–25, doi:10.1016/S0165-4896(02)00087-2. 
  3. ↑ Jack Robertson; William Webb (1998), Cake-Cutting Algorithms: Be Fair If You Can, AK Peters Ltd, p. 66, ISBN 1-56881-076-8 
  4. ↑ V. Bergström (1930), "Zwei Sätze über ebene Vectorpolygone", Hamburgische Abhandlungen 8: 205–219 
  5. ↑ Jack Robertson; William Webb (1998), Cake-Cutting Algorithms: Be Fair If You Can, AK Peters Ltd, pp. 126–128, ISBN 1-56881-076-8 
  6. ↑ Simmons, Forest W.; Francis Edward Su (2003), "Consensus-halving via theorems of Borsuk-Ulam and Tucker", Mathematical Social Sciences 45: 15–25, doi:10.1016/S0165-4896(02)00087-2 
  7. ↑ B. Grünbaum (1960), "Partitions of mass–distributions and convex bodies by hyperplanes", Pacific J. Math 10: 1257–1261 
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.