Envy-free cake-cutting

Last updated

An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

Contents

Unsolved problem in computer science:

What is the runtime complexity of envy-free cake-cutting?

When there are only two partners, the problem is easy and was solved in antiquity by the divide and choose protocol. When there are three or more partners, the problem becomes much more challenging.

Two major variants of the problem have been studied:

Short history

Modern research into the fair cake-cutting problem started in the 1940s. The first fairness criterion studied was proportional division, and a procedure for n partners was soon found.

The stronger criterion of envy-freeness was introduced into the cake-cutting problem by George Gamow and Marvin Stern in 1950s. [1]

A procedure for three partners and general pieces was found in 1960. A procedure for three partners and connected pieces was found only in 1980.

Envy-free division for four or more partners had been an open problem until the 1990s, when three procedures for general pieces and a procedure for connected pieces were published. All these procedures are unbounded - they may require a number of steps which is not bounded in advance. The procedure for connected pieces may even require an infinite number of steps.

Two lower bounds on the run-time complexity of envy-freeness were published in the 2000s.

In the 2010s, several approximation procedures and procedures for special cases were published. The question whether bounded-time procedures exist for the case of general pieces had remained open for a long time. The problem was finally solved in 2016. Haris Aziz and Simon Mackenzie presented a discrete envy-free protocol that requires at most or queries. [2] There is still a very large gap between the lower bound and the procedure. As of Feb 2024, the exact run-time complexity of envy-freeness is still unknown.

For the case of connected pieces, it was noted that the hardness result assumes that the entire cake must be divided. If this requirement is replaced by the weaker requirement that every partner receives a proportional value (at least 1/n of the total cake value according to their own valuation), then a bounded procedure for three partners is known, but it has remained an open problem whether there exist bounded-time procedures for four or more partners.

Connected pieces

Existence proof

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

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 they weakly prefer. 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 they are indifferent between them but like 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 (that is similar to the Knaster–Kuratowski–Mazurkiewicz 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

For three agents, an envy-free division can be found using several different procedures:

These are continuous procedures - they rely on people moving knives continuously and simultaneously. They cannot be executed in a finite number of discrete steps.

For n agents, an 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. The convergence might take infinitely many steps.

It is not a coincidence that all these algorithms may require infinitely many queries. As we show in the following subsection, it may be impossible to find an envy-free cake-cutting with connected pieces with a finite number of queries.

Hardness result

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

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 reduces 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. This might require an infinite number of questions.

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

Construct a set of three measures with these two properties:

  1. The density of each measure is always strictly between 2/2 and 2 (so for a given piece, the agents' valuations differ by a factor of less than 2).
  2. The values of the pieces determined by x and y are as in the table:
Agent[0,x][x,y][y,1]
Atts
Bstt
Ctst

Then, every envy-free division among Alice Bob and Carl must have cuts at x and y (there are exactly two such divisions), since all other options lead to envy:

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

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 we are 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.

Approximations

Since envy-free cake-cutting with connected pieces cannot be done in finite time, cake-cutters have tried to find work-arounds.

One work-around is looking for divisions which are only approximately-envy-free. There are two ways to define the approximation - in units of length or in units of value.

Length-based approximation uses the following definitions:

The parameter δ represents the tolerance of the partners in units of length. E.g., if land is divided and the partners agree that a difference of 0.01 meter in the location of the border is not relevant to them, then it makes sense to look for a 0.01-multi-partition which is envy-free. Deng at al [6] present a modification of Simmons' cake-cutting protocol which finds an envy-free δ-multi-partition using queries. Moreover, they prove a lower bound of queries. Even when the utility functions are given explicitly by polynomial-time algorithms, the envy-free cake-cutting problem is PPAD-complete.

Value-based approximation uses the following definitions:

If all value measures are Lipschitz continuous, then the two approximation definitions are related. Let . Then, every partition in an envy-free δ-multi-partition is ε-envy-free. [6] Hence, Deng et al.'s results prove that, if all partners have Lipschitz continuous valuations, an ε-envy-free partition can be found with queries with general valuations.

With additive valuations, for any ε > 0, an ε-envy-free connected cake-cutting requires at least Ω(log ε−1) queries. For 3 agents, an O(log ε−1) protocol exists. For 4 or more agents, the best known protocol requires O(n ε−1), which shows an exponential gap in the query complexity. [7] Moreover, although the latter protocol has query complexity polynomial in n, its computational complexity is exponential in n, even for constant ε. If polynomial-time computation is required, the best-known approximation is -envy-freeness. [8]

Offline calculation is a second work-around that finds a totally-envy-free division but only for a restricted class of valuations. If all value measures are polynomials of degree at most d, there is an algorithm which is polynomial in n and d. [9] Given d, the algorithm asks the agents d+1 evaluation queries, which give d+1 points in the graph of the value measure. It is known that d+1 points are sufficient to interpolate a polynomial of degree d. Hence, the algorithm can interpolate the entire value measures of all agents, and find an envy-free division offline. The number of required queries is .

Another restriction on the valuations is that they are piecewise-constant - for each agent, there are at most m desired intervals, and the agent's value-density in each interval is constant. Under this assumption, a connected envy-free allocation can be found by solving linear programs. Thus, when n is constant, the problem is polynomial in m. [10]

Free disposal is a third work-around that keeps the requirement that the division be totally envy-free and works for all value measures, but drops the requirement that the entire cake must be divided. I.e, it allows to divide a subset of the cake and discard the remainder. Without further requirements the problem is trivial, since it is always envy-free to give nothing to all agents. Thus, the real goal is to give each agent a strictly positive value. Every cake allocation can be characterized by its level of proportionality, which is the value of the least fortunate agent. An envy-free division of the entire cake is also a proportional division, and its proportionality level is at least , which is the best possible. But when free disposal is allowed, an envy-free division may have a lower proportionality level, and the goal is to find an envy-free division with the highest possible proportionality. The currently known bounds are:

It is not known whether there exists a bounded-time envy-free and proportional division procedure for four or more partners with connected pieces.

Variants

Most procedures for cake-cutting with connected pieces assume that the cake is a 1-dimensional interval and the pieces are 1-dimensional sub-intervals. Often, it is desirable that the pieces have a certain geometric shape, such as a square. With such constraints, it may be impossible to divide the entire cake (e.g., a square cannot be divided to two squares), so we must allow free disposal. As explained above, when free disposal is allowed, the procedures are measured by their level of proportionality - the value that they guarantee to all agents. The following results are currently known: [12]

An envy-free division exists even with non-additive value functions, multi-dimensional simplex cake, and the pieces must be polytopes. [13]

Disconnected pieces

Procedures

For three partners, the Selfridge–Conway discrete procedure makes an envy-free division with at most 5 cuts. Other procedures using moving knives require fewer cuts:

For four partners, The Brams–Taylor–Zwicker procedure makes an envy-free division with at most 11 cuts. [15] For five partners, a procedure by Saberi and Wang makes an envy-free division with a bounded number of cuts. [16] Both these procedures use Austin's procedure for two partners and general fractions as an initial step. Hence, these procedures should be considered infinite - they cannot be completed using a finite number of steps.

For four or more partners, there are three algorithms which are finite but unbounded - there is no fixed bound on the number of cuts required. [17] There are three such algorithms:

Although the protocols are different, the main idea behind them is similar: Divide the cake to a finite but unbounded number of "crumbs", each of which is so small that its value for all partners is negligible. Then combine the crumbs in a sophisticated way to get the desired division. William Gasarch has compared the three unbounded algorithms using ordinal numbers. [19]

The question of whether envy-free cake-cutting can be done in bounded time for four or more partners had been open for many years. It was finally solved in 2016 by Haris Aziz and Simon Mackenzie. Initially they developed a bounded-time algorithm for four partners. [20] Then they extended their algorithm to handle any number of partners. [2] Their algorithm requires at most queries. While this number is bounded, it is very far from the lower bound of . So the question of how many queries are required for envy-free cake-cutting is still open.

Approximations and partial solutions

A reentrant variant of the last diminisher protocol finds an additive approximation to an envy-free division in bounded time. Specifically, for every constant , it returns a division in which the value of each partner is at least the largest value minus , in time .

If all value measures are piecewise linear, there is an algorithm which is polynomial in the size of the representation of the value functions. [21] The number of queries is , where is the number of discontinuities in the derivatives of the value density functions.

Hardness result

Every envy-free procedure for n people requires at least Ω(n2) queries in the Robertson–Webb query model. [22] 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).

Existence proofs and variants

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.

Some other variants are:

Envy-free division with different entitlements

A common generalization of the envy-free criterion is that each of the partners has a different entitlement. I.e., for every partner i there is a weight wi describing the fraction of the cake that they are entitled to receive (the sum of all wi is 1). Then a weighted-envy-free division is defined as follows. For every agent i with value measure Vi, and for every other agent j:

I.e., every partner thinks that their allocation relative to their entitlement is at least as large as any other allocation relative to the other partner's entitlement.

When all weights are the same (and equal to 1/n), this definition reduces to the standard definition of envy-freeness.

When the pieces may be disconnected, a weighted envy-free division always exists and can be found by the Robertson-Webb protocol, for any set of weights. Zeng presented an alternative algorithm for approximate weighted envy-free division, which requires a smaller number of cuts. [25]

But when the pieces must be connected, a weighted envy-free division may not exist. To see this, note that every weighted-envy-free division is also weighted-proportional with the same weight-vector; this means that, for every agent i with value measure Vi:

It is known that weighted-proportional allocation with connected pieces may not exist: see proportional cake-cutting with different entitlements for an example.

Note that there is an alternative definition of weighted-envy-free division, where the weights are assigned to pieces rather than to agents. With this definition, a weighted envy-free division is known to exist in the following cases (each case generalizes the previous case):

Dividing a 'bad' cake

In some cases, the 'cake' to be divided has a negative value. For example, it might be piece of lawn that has to be mowed, or a piece of wasteland that has to be cleaned. Then, the cake is a 'heterogeneous bad' rather than a 'heterogeneous good'.

Some procedures for envy-free cake-cutting can be adapted to work for a bad cake, but the adaptation is often not trivial. See envy-free chore division for more details.

Summary tables

Summary by result
NameTypeCakePieces
#partners (n)
#queries#cutsenvy
proportionality [28]
Comments
Divide and choose Discrete procAnyConnected221 (optimal)None1/2
Stromquist Moving-knife procIntervalConnected32 (optimal)None1/3
Selfridge–Conway Discrete procAnyDisconnected395None1/3
Brams–Taylor–Zwicker Moving-knife procAnyDisconnected411None1/4
Saberi–Wang [16] Discrete procAnyDisconnected4BoundedBoundedNone1/4Free disposal
Aziz–Mackenzie [20] Discrete procAnyDisconnected4584203None1/4
Saberi–Wang [16] Moving-knife procAnyDisconnected5BoundedNone1/5
Stromquist ExistenceIntervalConnectednn-1None1/n
Simmons Discrete procIntervalConnectednn-1None1/n
Deng-Qi-Saberi Discrete procIntervalConnectednn-1Additive Only when valuations are Lipschitz continuous
Branzei [9] Discrete procIntervalConnectedn ?None1/nOnly when value densities are polynomial with degree at most d.
Waste-Makes-Haste Discrete procIntervalConnected394None1/3Free disposal
Waste-Makes-Haste Discrete procAnyConnected4166None1/7Free disposal
Waste-Makes-Haste Discrete procAnyConnectednNoneFree disposal
Aziz-Mackenzie ConnectedPieces [2] Discrete procAnyConnectednNoneFree disposal
Brams-Taylor Discrete procAnyDisconnectednUnboundedUnboundedNone1/n
Robertson-Webb Discrete procAnyDisconnectednUnboundedUnboundedNone1/nWeighted-envy-free.
Pikhurko [18] Discrete procAnyDisconnectednUnboundedUnboundedNone1/n
Aziz–Mackenzie [2] Discrete procAnyDisconnectednNone1/n
Reentrant last diminisher Discrete procIntervalDisconnectedn ?Additive 1/n
Kurokawa-Lai-Procaccia [21] Discrete procIntervalDisconnectedn ?None1/nOnly when value densities are piecewise linear with at most k discontinuities.
Weller ExistenceAnyDisconnectednNone1/n Pareto efficient.
2-D Discrete procSquareConnected and Square222None1/4Free disposal
2-D Moving-knife procSquareConnected and Square36None1/10Free disposal

Summary by number of agents and type of pieces:

# agentsConnected piecesGeneral pieces
2 Divide and choose
3 Stromquist moving-knives procedure (infinite time);
Waste-makes-haste (bounded-time, bounded cuts, free disposal, proportional)
Selfridge–Conway discrete procedure (bounded-time, at most 5 cuts).
4 Waste-makes-haste (bounded-time, bounded cuts, free disposal, proportionality 1/7). Brams–Taylor–Zwicker moving knives procedure (infinite time, at most 11 cuts).
Saberi–Wang discrete procedure [16] (bounded time, bounded cuts, free disposal, proportional).
Aziz–Mackenzie discrete procedure [20] (bounded time, bounded cuts, proportional).
5Saberi–Wang moving-knives procedure [16] (infinite time, bounded cuts).
n Simmons' protocol (infinite time)
Deng-Qi-Saberi (approximately envy-free, exponential time).
Waste-makes-haste (fully envy-free, exponential time, free-disposal, exponential proportionality)
Aziz-Mackenzie ConnectedPieces [2] (fully envy-free, exponential time, free-disposal, linear proportionality)
Brams and Taylor (1995);
Robertson and Webb (1998).
- Both algorithms require a finite but unbounded number of cuts.

Aziz-Mackenzie discrete procedure [2] (bounded time, bounded cuts, proportional).

HardnessAll algorithms for n  3 must be infinite (Stromquist, 2008).All algorithms must use at least Ω(n2) steps (Procaccia, 2009).
VariantsA weighted envy-free division exists for arbitrary weights (Idzik, 1995), even when the cake and pieces are simplexes (Idzik and Ichiishi, 1996).


An envy-free division exists even with non-additive preferences (Dall'Aglio and Maccheroni, 2009).

Robertson-Webb can find weighted-envy-free divisions for arbitrary weights.
A perfect division exists (Dubins&Spanier, 1961).
An envy-free and efficient cake-cutting exists (Weller's theorem).

See also

Related Research Articles

Chore division is a fair division problem in which the divided resource is undesirable, so that each participant wants to get as little as possible. It is the mirror-image of the fair cake-cutting problem, in which the divided resource is desirable so that each participant wants to get as much as possible. Both problems have heterogeneous resources, meaning that the resources are nonuniform. In cake division, cakes can have edge, corner, and middle pieces along with different amounts of frosting. Whereas in chore division, there are different chore types and different amounts of time needed to finish each chore. Similarly, both problems assume that the resources are divisible. Chores can be infinitely divisible, because the finite set of chores can be partitioned by chore or by time. For example, a load of laundry could be partitioned by the number of articles of clothing and/or by the amount of time spent loading the machine. The problems differ, however, in the desirability of the resources. The chore division problem was introduced by Martin Gardner in 1978.

Consensus splitting, also called exact division, is a partition of a continuous resource ("cake") into some k pieces, such that each of n people with different tastes agree on the value of each of the pieces. For example, consider a cake which is half chocolate and half vanilla. Alice values only the chocolate and George values only the vanilla. The cake is divided into three pieces: one piece contains 20% of the chocolate and 20% of the vanilla, the second contains 50% of the chocolate and 50% of the vanilla, and the third contains the rest of the cake. This is an exact division (with k = 3 and n = 2), as both Alice and George value the three pieces as 20%, 50% and 30% respectively. Several common variants and special cases are known by different terms:

<span class="mw-page-title-main">Fair cake-cutting</span> Fair division problem

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

The last diminisher procedure is a procedure for fair cake-cutting. It involves a certain heterogenous and divisible resource, such as a birthday cake, and n partners with different preferences over different parts of the cake. It allows the n people to achieve a proportional division, i.e., divide the cake among them such that each person receives a piece with a value of at least 1/n of the total value according to his own subjective valuation. For example, if Alice values the entire cake as $100 and there are 5 partners then Alice can receive a piece that she values as at least $20, regardless of what the other partners think or do.

Efficient cake-cutting is a problem in economics and computer science. It involves a heterogeneous resource, such as a cake with different toppings or a land with different coverings, that is assumed to be divisible - it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible, etc. The allocation should be economically efficient. Several notions of efficiency have been studied:

The Simmons–Su protocols are several protocols for envy-free division. They are based on Sperner's lemma. The merits of these protocols is that they put few restrictions on the preferences of the partners, and ask the partners only simple queries such as "which piece do you prefer?".

The Robertson–Webb protocol is a protocol for envy-free cake-cutting which is also near-exact. It has the following properties:

A strongly proportional division is a kind of a fair division. It is a division of resources among n partners, in which the value received by each partner is strictly more than his/her due share of 1/n of the total value. Formally, in a strongly proportional division of a resource C among n partners, each partner i, with value measure Vi, receives a share Xi such that

.

The fair pie-cutting problem is a variation of the fair cake-cutting problem, in which the resource to be divided is circular.

Equitable (EQ) cake-cutting is a kind of a fair cake-cutting problem, in which the fairness criterion is equitability. It is a cake-allocation in which the subjective value of all partners is the same, i.e., each partner is equally happy with his/her share. Mathematically, that means that for all partners i and j:

A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/n of the total.

Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among n partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency.

Utilitarian cake-cutting is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting.

In the fair cake-cutting problem, the partners often have different entitlements. For example, the resource may belong to two shareholders such that Alice holds 8/13 and George holds 5/13. This leads to the criterion of weighted proportionality (WPR): there are several weights that sum up to 1, and every partner should receive at least a fraction of the resource by their own valuation.

The lone divider procedure is a procedure for proportional cake-cutting. It involves a heterogenous and divisible resource, such as a birthday cake, and n partners with different preferences over different parts of the cake. It allows the n people to divide the cake among them such that each person receives a piece with a value of at least 1/n of the total value according to his own subjective valuation.

Symmetric fair cake-cutting is a variant of the fair cake-cutting problem, in which fairness is applied not only to the final outcome, but also to the assignment of roles in the division procedure.

Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake.

In computer science, the Robertson–Webb (RW) query model is a model of computation used by algorithms for the problem of fair cake-cutting. In this problem, there is a resource called a "cake", and several agents with different value measures on the cake. The goal is to divide the cake among the agents such that each agent will consider his/her piece as "fair" by his/her personal value measure. Since the agents' valuations can be very complex, they cannot - in general - be given as inputs to a fair division algorithm. The RW model specifies two kinds of queries that a fair division algorithm may ask the agents: Eval and Cut. Informally, an Eval query asks an agent to specify his/her value to a given piece of the cake, and a Cut query asks an agent to specify a piece of cake with a given value.

A super-envy-free division is a kind of a fair division. It is a division of resources among n partners, in which each partner values his/her share at strictly more than his/her due share of 1/n of the total value, and simultaneously, values the share of every other partner at strictly less than 1/n. Formally, in a super-envy-free division of a resource C among n partners, each partner i, with value measure Vi, receives a share Xi such that:

.

References

  1. Gamow, George; Stern, Marvin (1958). Puzzle-math. Viking Press. ISBN   978-0670583355.
  2. 1 2 3 4 5 6 7 Aziz, Haris; Mackenzie, Simon (2016). "A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents". 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). New Brunswick, NJ, USA: IEEE. pp. 416–427. arXiv: 1604.03655 . Bibcode:2016arXiv160403655A. doi:10.1109/FOCS.2016.52.
  3. Stromquist, Walter (1980). "How to Cut a Cake Fairly". The American Mathematical Monthly. 87 (8): 640–644. doi:10.2307/2320951. JSTOR   2320951.
  4. Stromquist, Walter (2008). "Envy-free cake divisions cannot be found by finite protocols" (PDF). Electronic Journal of Combinatorics. 15. doi:10.37236/735.
  5. Stromquist moving-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.
  6. 1 2 Deng, X.; Qi, Q.; Saberi, A. (2012). "Algorithmic Solutions for Envy-Free Cake Cutting". Operations Research. 60 (6): 1461–1476. doi:10.1287/opre.1120.1116. S2CID   4430655.
  7. Branzei, Simina; Nisan, Noam (2022-12-06). "The Query Complexity of Cake Cutting". Advances in Neural Information Processing Systems. 35: 37905–37919., arXiv : 1705.02946.
  8. Goldberg, Paul W.; Hollender, Alexandros; Suksompong, Warut (2020). "Contiguous Cake Cutting: Hardness Results and Approximation Algorithms". Journal of Artificial Intelligence Research. 69: 109–141. arXiv: 1911.05416 . doi:10.1613/jair.1.12222. S2CID   221865778.
  9. 1 2 Brânzei, S. (2015). "A note on envy-free cake cutting with polynomial valuations". Information Processing Letters. 115 (2): 93–95. doi:10.1016/j.ipl.2014.07.005.
  10. Alijani, Reza; Farhadi, Majid; Ghodsi, Mohammad; Seddighin, Masoud; Tajik, Ahmad S. (2017-02-10). "Envy-Free Mechanisms with Minimum Number of Cuts". Thirty-First AAAI Conference on Artificial Intelligence. 31. doi: 10.1609/aaai.v31i1.10584 . S2CID   789550.
  11. 1 2 Segal-Halevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (2016). "Waste Makes Haste". ACM Transactions on Algorithms. 13: 1–32. arXiv: 1511.02599 . doi:10.1145/2988232. S2CID   11358086.
  12. Erel Segal-Halevi and Avinatan Hassidim and Yonatan Aumann (Jan 2015). Envy-Free Cake-Cutting in Two Dimensions. The 29th AAAI Conference on Artificial Intelligence (AAAI-15). Austin, Texas. pp. 1021–1028. doi:10.13140/RG.2.1.5047.7923.
  13. Dall'Aglio, M.; MacCheroni, F. (2009). "Disputed lands" (PDF). Games and Economic Behavior. 66: 57–77. doi:10.1016/j.geb.2008.04.006.
  14. Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge University Press. ISBN   0-521-55644-9.
  15. Brams, Steven J.; Taylor, Alan D.; Zwicker, William S. (1997). "A Moving-Knife Solution to the Four-Person Envy-Free Cake Division" (PDF). Proceedings of the American Mathematical Society. 125 (2): 547–555. doi:10.1090/S0002-9939-97-03614-9. S2CID   17233874 . Retrieved 2 September 2014.
  16. 1 2 3 4 5 Amin Saberi and Ying Wang (2009). Cutting a Cake for Five People. Algorithmic Aspects in Information and Management. doi:10.1007/978-3-642-02158-9_25.
  17. 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
  18. 1 2 Pikhurko, O. (2000). "On Envy-Free Cake Division". The American Mathematical Monthly. 107 (8): 736–738. doi:10.2307/2695471. JSTOR   2695471.
  19. Gasarch, William (2015). "Which Unbounded Protocol for Envy Free Cake Cutting is Better?". arXiv: 1507.08497 [math.LO].
  20. 1 2 3 Aziz, Haris; MacKenzie, Simon (2016). "A discrete and bounded envy-free cake cutting protocol for four agents". Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing – STOC 2016. p. 454. arXiv: 1508.05143 . doi:10.1145/2897518.2897522. ISBN   9781450341325.
  21. 1 2 Kurokawa, David; Lai, John K.; Procaccia, Ariel D (2013). "How to Cut a Cake Before the Party Ends". AAAI. 27: 555–561. doi: 10.1609/aaai.v27i1.8629 . S2CID   12638556 . Retrieved 2 September 2014.
  22. Procaccia, Ariel (2009). "Thou Shalt Covet Thy Neighbor's Cake". IJCAI'09 Proceedings of the 21st International Joint Conference on Artificial Intelligence: 239–244.
  23. 1 2 Barbanel, Julius B. (1996-01-01). "Super Envy-Free Cake Division and Independence of Measures". Journal of Mathematical Analysis and Applications. 197 (1): 54–60. doi: 10.1006/S0022-247X(96)90006-2 . ISSN   0022-247X.
  24. Webb, William A. (1999-11-01). "An Algorithm For Super Envy-Free Cake Division". Journal of Mathematical Analysis and Applications. 239 (1): 175–179. doi: 10.1006/jmaa.1999.6581 . ISSN   0022-247X.
  25. Zeng, Dao-Zhi (2000). "Approximate Envy-Free Procedures". Game Practice: Contributions from Applied Game Theory. Theory and Decision Library. Vol. 23. Springer. pp. 259–271. doi:10.1007/978-1-4615-4627-6_17. ISBN   9781461546276.
  26. Idzik, Adam (1995). Optimal divisions of the unit interval. International Conference in Honor of Robert J. Aumann on his 65th Birthday. Jerusalem.
  27. Ichiishi, T.; Idzik, A. (1999). "Equitable allocation of divisible goods". Journal of Mathematical Economics. 32 (4): 389–400. doi:10.1016/s0304-4068(98)00053-6.
  28. Proportionality = the value (as fraction of the whole cake) that is guaranteed to each agent with additive valuations. When there is no envy and the entire cake is divided, the proportionality is always 1/n, which is the best possible.