Envy-free
Encyclopedia
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.
A division is envy-free if each recipient believes that according to his measure no other recipient has received more than he has. This requirement is stronger than proportional division
.
There is a discrete procedure for three players and a moving-knife procedure
for four players. Both have a bounded number of cuts. There is also a discrete procedure for any number of players, but this procedure has no fixed bound on the number of cuts required.
The concept generalizes naturally to chore division
: in this case, a division is envy-free if each player believes their share is smaller than the other players'. The crucial issue is that no player would wish to swap their share with any other player.
is a simple and practical example. The first sibling divides the cake into two pieces, and the second sibling chooses which piece to take. Since both siblings wish to maximize their share of the cake, the first sibling will divide the cake evenly in his estimation and the second sibling will take the one perceived as more desirable. Even if there is icing unevenly on the cake that the siblings want, the first sibling can divide the cake to compensate for the perceived benefit of the icing in his view making them even, and then the second sibling chooses the piece he prefers.
Note that for two players envy-free division is the same as proportional division
.
is a solution to the envy-free problem for three players.
s is that they cannot be translated into discrete queries to the players involved in the procedure. The Stromquist moving-knife procedure
is a solution to the envy-free problem for three players.
, Taylor
and Zwicker moving knife algorithm devised in 1997 can ensure an envy free division amongst four people.
For five or more players the only known algorithms have no fixed bound on the number of cuts required.
Mathematical sociology
Mathematical sociology is the usage of mathematics to construct social theories. Mathematical sociology aims to take sociological theory, which is strong in intuitive content but weak from a formal point of view, and to express it in formal terms...
and especially game theory
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...
, envy-free is a property of certain 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...
algorithms for a divisible heterogeneous good over which different players may have different preferences.
A division is envy-free if each recipient believes that according to his measure no other recipient has received more than he has. This requirement is stronger than proportional division
Proportional (fair division)
Proportional division or simple fair division is the original and simplest problem in fair division. Fair division problems are also called cake-cutting problems. A proportional division of a cake between N people would ensure each of them got at least 1/N of the cake by their own valuation...
.
There is a discrete procedure for three players and a moving-knife procedure
Moving-knife procedure
In the mathematics of social science, and especially game theory, a moving-knife procedure is a type of solution to the fair division problem. The canonical example is the division of a cake using a knife....
for four players. Both have a bounded number of cuts. There is also a discrete procedure for any number of players, but this procedure has no fixed bound on the number of cuts required.
The concept generalizes naturally to chore division
Chore division
In problems of fair division, a resource is to be divided amongst a finite number of players; the resource is assumed to be desirable, and more is assumed to be better...
: in this case, a division is envy-free if each player believes their share is smaller than the other players'. The crucial issue is that no player would wish to swap their share with any other player.
Two players
Two siblings dividing the last piece of cake using divide and chooseDivide and choose
In problems of fair division, divide and choose is a two-party proportional envy-free allocation protocol. The protocol also works for dividing an undesirable, as in chore division....
is a simple and practical example. The first sibling divides the cake into two pieces, and the second sibling chooses which piece to take. Since both siblings wish to maximize their share of the cake, the first sibling will divide the cake evenly in his estimation and the second sibling will take the one perceived as more desirable. Even if there is icing unevenly on the cake that the siblings want, the first sibling can divide the cake to compensate for the perceived benefit of the icing in his view making them even, and then the second sibling chooses the piece he prefers.
Note that for two players envy-free division is the same as proportional division
Proportional (fair division)
Proportional division or simple fair division is the original and simplest problem in fair division. Fair division problems are also called cake-cutting problems. A proportional division of a cake between N people would ensure each of them got at least 1/N of the cake by their own valuation...
.
Discrete procedure
Discrete procedures involve only discrete queries to the players. The Selfridge–Conway discrete procedureSelfridge–Conway discrete procedure
In problems of envy-free division, the Selfridge–Conway discrete procedure presents a solution for three players. It is named after John Selfridge and John Horton Conway who discovered it independently in 1960...
is a solution to the envy-free problem for three players.
Moving knife procedure
The drawback of moving-knife procedureMoving-knife procedure
In the mathematics of social science, and especially game theory, a moving-knife procedure is a type of solution to the fair division problem. The canonical example is the division of a cake using a knife....
s is that they cannot be translated into discrete queries to the players involved in the procedure. The Stromquist moving-knife procedure
Stromquist moving-knife procedure
In problems of envy-free division, the Stromquist moving-knife procedure is a moving-knife procedure for three players. It is named after Walter Stromquist who presented it in 1980....
is a solution to the envy-free problem for three players.
Four players
The BramsSteven Brams
Steven J. Brams is a game theorist and political scientist at the New York University Department of Politics. Brams is best known for using the techniques of game theory and public choice to research voting systems and fair division. He is one of the independent discoverers of approval voting...
, Taylor
Alan D. Taylor
Alan Dana Taylor is a mathematician who, with Steven Brams, solved the problem of envy-free fair division for an arbitrary number of people with the Brams–Taylor procedure.Taylor received his Ph.D...
and Zwicker moving knife algorithm devised in 1997 can ensure an envy free division amongst four people.
Five players and more
In 1995 Brams and Taylor devised an envy free procedure for any number of people. This is discrete but the number of cuts is unbounded, it is not determined in advance.For five or more players the only known algorithms have no fixed bound on the number of cuts required.