Envy-free

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematical sociology and especially fair division, An envy-free allocation is an allocation of resources among several partners with different preferences, such that every partner feels that his allocated share is at least as good as any other share.

The general concept was introduced (without using the term "envy free") by Duncan Foley in 1967.[1] It was later studied in several contexts, including resource allocation and fair cake-cutting.

In the context of fair cake-cutting, envy-freeness means that each partner believes that their share is at least as large as any other share. In the context of chore division, envy-freeness means that each partner believes their share is at least as small as any other share. The crucial issue is that no partner would wish to swap their share with any other partner.

When there are two partners, the Divide and choose protocol guarantees an envy-free division of a cake. When there are three or more partners, envy-free cake-cutting becomes much more challenging. Two variants of the problem have been studied

  1. In one variant, the pieces must be connected. The 'cake' can be considered a 1-dimensional interval, and each partner must receive a single interval. If there are n partners, only n-1 cuts are needed.
  2. In another variant, the pieces may be disconnected, i.e. each partner can receive any number of pieces.

Connected pieces[edit]

Existence proof[edit]

An envy-free division for n agents with connected pieces always exists under the following mild assumptions:[2]

  • No agent prefers an empty piece over a non-empty piece.
  • The preferences of the agents are continuous.

Note that it is not required that the preferences of the agents are represented by an additive function.

The main concept in the proof is the simplex of partitions. Suppose the cake is the interval [0,1]. Each partition with connected pieces can be uniquely represented by n-1 numbers in [0,1] which represent the cut locations. The union of all partitions is a simplex.

For each partition, each agent has one or more pieces which he weakly prefers. E.g., for the partition represented by "0.3,0.5", one agent may prefer piece #1 (the piece [0,0.3]) while another agent might prefer piece #2 (the piece [0.3,0.5]) while a third agent might prefer both piece #1 and piece #2 (which means that he is indifferent between them but likes any of them more than piece #3).

For every agent, the partition simplex is covered by n parts, possibly overlapping at their boundaries, such that for all partitions in part i, the agent prefers piece i. In the interior of part i, the agent prefers only piece i, while in the boundary of part i, the agent also prefers some other pieces. So for every i, there is a certain region in the partition simplex in which at least one agent prefers only piece i. Call this region Ui. Using a certain topological lemma, it is possible to prove that the intersection of all Ui's is non-empty. Hence, there is a partition in which every piece is the unique preference of an agent. Since the number of pieces equals the number of agents, we can allocate each piece to the agent that prefers it and get an envy-free allocation.

Procedures[edit]

For 3 agents, an envy-free division can be found by the Stromquist three-knives procedure.

For n agents, an approximate envy-free division can be found by Simmons' cake-cutting protocol. The protocol uses a simplex of partitions similar to the one used in Stromquist's existence proof. It generates a sequence of partitions which converges to an envy-free partition. Alternatively, for every desired tolerance, it is possible to find a division which is envy-free up to that tolerance. E.g, if land is divided and the partners agree that a difference of 1 centimeter is not relevant to them, then it is possible to find an envy-free division which is envy-free plus-or-minus 1 centimeter.

Hardness result[edit]

An envy-free division with connected pieces for 3 or more agents cannot be found by a finite protocol. [3] The reason this result doesn't contradict the previously mentioned algorithms is that they are not finite in the mathematical sense.[4]

The impossibility proof uses a rigid measure system (RMS) - a system of n value measures, for which an envy-free division must cut the cake at very specific locations. Then, finding an envy-free division amounts to finding these specific locations. Assuming the cake is the real interval [0,1], finding an envy-free division using queries to the agents is equivalent to finding a real number in the interval [0,1] using yes/no questions, which obviously might take an infinite time.

A RMS for 3 agents can be constructed as follows. Let x, y, s, and t be parameters satisfying:

  • 0 < x < y < 1
  • 0 < s < 1/3 < t < 1/2
  • s + 2t = 1.

Construct a set of three measures with these two properties:

  1. The density of each measure is always strictly between √2/2 and √2.
  2. The values of the pieces determined by x and y are as in the table:
Agent [0,x] [x,y] [y,1]
A t t s
B s t t
C t s t

Then, every envy-free division among the three agents A, B and C must have cuts at x and y (there are exactly two such divisions). All other options lead to envy: if cuts are made to the left of x and to the right of y, then agents A and B both insist on getting the middle piece; if cuts are made to the right of x and to the left of y, then no agent would accept the middle piece; if cuts are made to the right of x and to the right of y, then both A and C prefer the leftmost piece to the rightmost piece, so agent B must agree to accept the rightmost piece, but in that case, both A and C insist on the leftmost piece. The fourth case (cuts to the left of x and to the left of y) is symmetric.

For every RMS, every agent i and every constant ε>0, there is a slightly different RMS with the following properties:

  • The new value measure of agent i is completely identical to his old value measure;
  • The new value measures of the other two agents are identical to their old value measure everywhere except in an ε-neighbourhood of x and y.

This implies that, if all queries answered so far were outside the ε-neighbourhood of x and y, then agent i has no way to know whether he is in the old RMS or in the new RMS.

Equipped with this knowledge, an adversary can trick every envy-free division protocol to go on forever:

  1. Start with any RMS, e.g. with parameters x=1/3, y=2/3, s=0.3 and t=0.35.
  2. As long as the protocol makes cuts at points other than x and y, let it continue.
  3. Whenever the protocol asks agent i to make a cut at x or y, switch to a different RMS with x'≠x and y'≠y, making sure that the values are the same for all previously made cuts.

Thus the protocol can never make cuts at the correct x and y required for an envy-free division.

Hardness of approximation[edit]

While an envy-free division with connected pieces can be approximated to any precision using a finite protocol (e.g. Simmons-Su protocols), the approximation might take a long time. In particular:[5]

  • When the utility functions are accessible only through oracles, the number of queries for achieving an envy of less than ϵ is \Theta(\frac{1}{\epsilon^n}).
  • When the utility functions are given explicitly by polynomial-time algorithms, the envy-free cake-cutting problem has the same complexity as finding a Brouwer fixed-point, i.e. PPAD-complete.

Disconnected pieces[edit]

Procedures[edit]

For 3 partners, the Selfridge–Conway discrete procedure guarantees an envy-free division with at most 5 cuts.

For 4 partners, The Brams-Taylor-Zwicker moving knives procedure guarantees an envy-free division with at most 11 cuts.[6]

For 5 or more partners, the only known exact algorithms are unbounded - there is no fixed bound on the number of cuts required.[7] There are two such algorithms:

  • The Brams and Taylor algorithm, devised in 1995.[8]
  • The Robertson and Webb algorithm, published in 1998.[9]

If the valuation functions of the agents are piecewise-linear, there is an algorithm which is polynomial in the size of the representation of the valuation functions.[10]

Hardness result[edit]

Every envy-free procedure for n people requires at least Ω(n2) queries.[11] The proof relies on a careful analysis of the amount of information the algorithm has on each partner.

A. Assume that the cake is the 1-dimensional interval [0,1], and that the value of the entire cake for each of the partners is normalized 1. In each step, the algorithm asks a certain partner either to evaluate a certain interval contained in [0,1], or to mark an interval with a specified value. In both cases, the algorithm gathers information only about intervals whose end-points were mentioned in the query or in the reply. Let's call these endpoints landmarks. Initially the only landmarks of i are 0 and 1 since the only thing the algorithm knows about partner i is that vi([0,1])=1. If the algorithm asks partner i to evaluate the interval [0.2,1], then after the reply the landmarks of i are {0,0.2,1}. The algorithm can calculate vi([0,0.2]), but not the value of any interval whose endpoint is different than 0.2. The number of landmarks increases by at most 2 in each query. In particular, the value of the interval [0,0.2] might be concentrated entirely near 0, or entirely near 0.2, or anywhere in between.

B. An interval between two consecutive landmarks of partner i is called a landmark-interval of partner i, When the algorithm decides to allocate a piece of cake to partner i, it must allocate a piece whose total value for i is at least as large as any landmark-interval of i. The proof is by contradiction: suppose there is a certain landmark-interval J whose value for i is more than the value actually allocated to i. Some other partner, say j, will necessarily receive some part of the landmark-interval J. By paragraph A, it is possible that all the value of interval J is concentrated inside the share allocated to partner j. Thus, i envies j and the division is not envy-free.

C. Suppose all partners answer all queries as if their value measure is uniform (i.e. the value of an interval is equal to its length). By paragraph B, the algorithm may assign a piece to partner i, only if it is longer than all landmark-intervals of i. At least n/2 partners must receive an interval with a length of at most 2/n; hence all their landmark-intervals must have a length of at most 2/n; hence they must have at least n/2 landmark-intervals; hence they must have at least n/2 landmarks.

D. Each query answered by partner i involves at most two new endpoints, so it increases the number of landmarks of i by at most 2. Hence, in the case described by paragraph C, the algorithm must ask each of n/2 partners, at least n/4 queries. The total number of queries is thus at least n2/8 = Ω(n2).

It is an open question whether a bounded algorithm exists for arbitrary valuation functions. Thus there is a huge gap between the lower bound of Ω(n2) and the best currently known algorithm which is finite but unbounded.

Existence proofs and variants[edit]

In addition to the general existence proofs implied by the algorithms described above, there are proofs for the existence of envy-free partitions with additional properties:

Both proofs work only for additive and non-atomic value measures, and rely on the ability to give each partner a large number of disconnected pieces.

Summarizing table[edit]

# agents Connected pieces General pieces
2 Divide and choose
3 Stromquist three-knives procedure Selfridge–Conway discrete procedure (at most 5 cuts).
4 Brams-Taylor-Zwicker moving knives procedure (at most 11 cuts).
5+ Simmons' protocol Brams and Taylor (1995);
Robertson and Webb (1998).
Both algorithms require a finite but unbounded number of cuts.
n All algorithms for n≥3 must be infinite (Stromquist, 2008). All algorithms must use at least Ω(n2) steps (Procaccia, 2009).
Variants A perfect division exists (Dubins&Spanier, 1961).
An envy-free and efficient cake-cutting exists (Weller, 1985).

See also[edit]

References[edit]

  1. ^ Foley, Duncan (1967). "Resource allocation and the public sector". Yale Econ Essays 7 (1): 45–98. 
  2. ^ Stromquist, Walter (1980). "How to Cut a Cake Fairly". The American Mathematical Monthly 87 (8): 640. doi:10.2307/2320951.  edit
  3. ^ Stromquist, Walter (2008). "Envy-free cake divisions cannot be found by finite protocols". Electronic Journal of Combinatorics. 
  4. ^ Stromquist three-knives procedure requires the three agents to adjust their knives whenever the sword of the referee moves. Since the sword moves continuously, the number of steps required is an uncountable infinity. Simmons cake-cutting protocol converges to an envy-free division, but the convergence might require an infinite number of steps.
  5. ^ Deng, X.; Qi, Q.; Saberi, A. (2012). "Algorithmic Solutions for Envy-Free Cake Cutting". Operations Research 60 (6): 1461. doi:10.1287/opre.1120.1116.  edit
  6. ^ Brams, Steven J.; Taylor, Alan D.; Zwicker, William S. (1997). "A Moving-Knife Solution to the Four-Person Envy-Free Cake Division". PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY. Retrieved 2 September 2014. 
  7. ^ S. J. Brams, M. A. Jones, and C. Klamler, "Better ways to cut a cake," Notices of the AMS, 2005. [Online]. Available: http://www.ams.org/notices/200611/fea-brams.pdf
  8. ^ Brams, S. J.; Taylor, A. D. (1995). "An Envy-Free Cake Division Protocol". The American Mathematical Monthly 102: 9. doi:10.2307/2974850. JSTOR 2974850.  edit
  9. ^ Robertson, Jack; William Webb. "10". Cake-Cutting Algorithms: be fair if you can. A.K.Peters Limited. pp. 133–136. ISBN 1-56881-076-8. 
  10. ^ Kurokawa, David; Lai, John K.; Procaccia, Ariel D (2013). "How to Cut a Cake Before the Party Ends". AAAI. Retrieved 2 September 2014. 
  11. ^ Procaccia, Ariel (2009). "Thou Shalt Covet Thy Neighbor’s Cake". IJCAI. 
  12. ^ Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly 68: 1. doi:10.2307/2311357. JSTOR 2311357.  edit