Exact division
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 entitlement
s rather than competing as in fair division
. Some authors refer to this as consensus division or consensus halving.
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 entitlement
s can also be achieved for two players by a slightly more complicated procedure.
one can ensure the players each believe the values everyone has differ by less than 
.
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.
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. This consensus halving theorem uses the Borsuk–Ulam theorem
and Tucker's lemma and the n cuts is the minimum possible.
and a generalization of the ham sandwich theorem
can be used to establish existence proofs for exact divisions in various circumstances.
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, an exact or even division is a type of fair division
Fair division
Fair division, also known as the cake-cutting problem, is the problem of dividing a resource in such a way that all recipients believe that they have received a fair amount...
where all the players believe everyone received the same amount.
There is no finite fair division
Fair division
Fair division, also known as the cake-cutting problem, is the problem of dividing a resource in such a way that all recipients believe that they have received a fair amount...
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
Envy-free
In mathematical sociology and especially game theory, envy-free is a property of certain fair division algorithms for a divisible heterogeneous good over which different players may have different preferences....
fair division procedures to be devised for any number of players.
There are a number of existence proofs derived from measure theory or topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
for exact divisions in various circumstances.
Divisions of this type are much easier if the participants cooperate in establishing entitlement
Entitlement (fair division)
Entitlement in fair division describes that proportion of the resources or goods to be divided that a player can expect to receive. The idea is based on the normal idea of entitlement...
s rather than competing as in fair division
Fair division
Fair division, also known as the cake-cutting problem, is the problem of dividing a resource in such a way that all recipients believe that they have received a fair amount...
. Some authors refer to this as consensus division or consensus halving.
Two players
The original procedure for exact division of a cake devised by A.K.Austin is as follows:- 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
Intermediate value theorem
In mathematical analysis, the intermediate value theorem states that for each value between the least upper bound and greatest lower bound of the image of a continuous function there is at least one point in its domain that the function maps to that value....
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 entitlement
Entitlement (fair division)
Entitlement in fair division describes that proportion of the resources or goods to be divided that a player can expect to receive. The idea is based on the normal idea of entitlement...
s 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 one can ensure the players each believe the values everyone has differ by less than .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.
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. This consensus halving theorem uses the Borsuk–Ulam theorem
Borsuk–Ulam theorem
In mathematics, the Borsuk–Ulam theorem, named after Stanisław Ulam and Karol Borsuk, states that every continuous function from an n-sphere into Euclidean n-space maps some pair of antipodal points to the same point....
and Tucker's lemma and the n cuts is the minimum possible.
Existence proofs
Both the necklace splitting problemNecklace splitting problem
In mathematics, and in particular combinatorics, the necklace splitting problem arises in a variety of contexts including exact division; its picturesque name is due to mathematicians Noga Alon and Douglas B. West....
and a generalization of the ham sandwich theorem
Ham sandwich theorem
In measure theory, a branch of mathematics, the ham sandwich theorem, also called the Stone–Tukey theorem after Arthur H. Stone and John Tukey, states that given measurable "objects" in -dimensional space, it is possible to divide all of them in half with a single -dimensional hyperplane...
can be used to establish existence proofs for exact divisions in various circumstances.