Truthful cake-cutting

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.

The clasic divide and choose procedure for cake-cutting is not truthful: if the cutter knows the chooser's preferences, he can get much more than 1/2 by acting strategically. For example, suppose the cutter values a piece by its size while the chooser values a piece by the amount of chocolate in it. So the cutter can cut the cake into two pieces with almost the same amount of chocolate, such that the smaller piece has slightly more chocolate. Then, the chooser will take the smaller piece and the cutter will win the larger piece, which may be worth much more than 1/2 (depending on how the chocolate is distributed).

There is a trivial randomized truthful mechanism for fair cake-cutting: select a single agent uniformly at random, and give him/her the entire cake. This mechanism is trivially truthful because it asks no questions. Moreover, it is fair in expectation: the expected value of each partner is exactly 1/n. However, the resulting allocation is not fair. The challenge is to develop truthful mechanisms that are fair ex-post and not just ex-ante. Several such mechanisms have been developed.

Exact division mechanism

An exact division (aka consensus division) is a partition of the cake into n pieces such that each agent values each piece at exactly 1/n. The existence of such a division is a corollary of the Dubins–Spanier convexity theorem. Moreover, there exists such a division with a small number of cuts; this is a corollary of the Stromquist–Woodall theorem.

In general, an exact division cannot be found by a finite algorithm. However, it can be found in some special cases, for example when all agents have piecewise-linear valuations. Suppose we have a non-truthful algorithm (or oracle) for finding an exact division. It can be used to construct a randomized mechanism that is truthful in expectation. The randomized mechanism is a direct-revelation mechanism - it starts by asking all agents to reveal their entire value-measures:

1. Ask the agents to report their value measures.
2. Use the existing algorithm/oracle to generate an exact division.
3. Perform a random permutation on the consensus partition and give each partner one of the pieces.

Here, the expected value of each agent is always 1/n regardless of the reported value function. Hence, the mechanism is truthful – no agent can gain anything from lying. Moreover, a truthful partner is guaranteed a value of exactly 1/n with probability 1 (not only in expectation). Hence the partners have an incentive to reveal their true value functions.

Super-proportional mechanism

A super-proportional division is a cake-division in which each agent receives strictly more than 1/n by their own value measures. Such a division is known to exist if and only if there are at least two agents that have different valuations to at least one piece of the cake. Any deterministic mechanism that always returns a proportional division, and always returns a super-proportional division when it exists, cannot be truthful. However, there is a super-proportional randomized mechanism that is truthful in expectation:

1. Pick a division from a certain distribution D over divisions.
2. Ask each agent to evaluate his/her piece.
3. If all n evaluations are more than 1/n, then implement the allocation and finish.
4. Otherwise, use the exact-division mechanism.

The distribution D in step 1 should be chosen such that, regardless of the agents' valuations, there is a positive probability that a super-proportional division be selected iff it exists. Then, in step 2 it is optimal for each agent to report the true value: reporting a lower value either has no effect or might cause the agent's value to drop from super-proportional to just proportional (in step 4); reporting a higher value either has no effect or might cause the agent's value to drop from proportional to less than 1/n (in step 3).

Mechanisms for piecewise-uniform valuations

Suppose all agents have piecewise-uniform valuations. This means that, for each agent, there is a subset of the cake that is desirable for the agent, and the agent's value for each piece is just the amount of desirable cake that it contains. For example, suppose some parts of the cake are covered by a uniform layer of chocolate, while other parts are not. An agent who values each piece only by the amount of chocolate it contains has a piecewise-uniform valuation. Several truthful algorithms have been developed for this special case.

Chen, Lai, Parkes and Procaccia developed a direct-revelation mechanism that is deterministic, proportional, envy-free, Pareto-optimal, and polynomial-time. It works for any number of agents. Here is an illustration of the CLPP mechanism for two agents (where the cake is an interval).

1. Ask each agent to report his/her desired intervals.
2. Each sub-interval, that is desired by no agent, is discarded.
3. Each sub-interval, that is desired by exactly one agent, is allocated to that agent.
4. The sub-intervals, that are desired by both agents, are allocated such that both agents get an equal total length.

Now, if an agent says that he wants an interval that he actually does not want, then he may get more useless cake in step 3 and less useful cake in step 4. If he says that he does not want an interval that he actually wants, then he gets less useful cake in step 3 and more useful cake in step 4, however, the amount given in step 4 is shared with the other agent, so all in all, the lying agent is at a loss. The mechanism can be generalized to any number of agents.

The CLPP mechanism is unique in the following sense. Consider the special case of two agents with piecewise-uniform valuations, where the cake is [0,1], Alice wants only the subinterval [0,a] for some a<1, and Bob desires only the subinterval [1-b,1] for some b<1. Consider only non-wasteful mechanisms - mechanisms that allocate each piece desired by at least one player to a player who wants it. Each such mechanism must give Alice a subset [0,c] for some c<1 and Bob a subset [1-d,1] for some d<1. In this model:

• A non-wasteful determininstic mechanism is truthful iff, for some parameter t in [0,1], it gives Alice the interval [0, min(a, max(1-b,t))] and Bob the interval [1-min(b,max(1-a,1-t)),1]
• Such mechanism is envy-free iff t=1/2; in this case it is equivalent to the CLPP mechanism.

The CLPP mechanism relies on the free disposal assumption, i.e., the ability to discard pieces that are not desired by any agent.

Bei, Huzhang and Suksompong developed a mechanism for two agents with piecewise-uniform valuations, that has the same properties of CLPP (truthful, deterministic, proportional, envy-free, Pareto-optimal and runs in polynomial time), but guarantees that the entire cake is alocated:

1. Find the smallest x in [0,1] such that Alice's desired length in [0,x] equals Bob's desired length in [x,1].
2. Give Alice the intervals in [0,x] valued by Alice and the intervals in [x,1] not valued by Bob; give the remainder to Bob.

The BHS mechanism works both for cake-cutting and for chore division (where the agents' valuations are negative). Note that BHS does not satisfy some natural desirable properties:

• It does not guarantee connected pieces, for example when Alice wants [0,1] and Bob wants [0,0.5], then x=0.25, Alice gets [0,0.25] and [0.5,1], and Bob gets [0.25,0.5].
• It is not anonymous (see symmetric fair cake-cutting): if Alice wants [0,1] and Bob wants [0,0.5], then Alice gets a desired length of 0.75 and Bob gets 0.25, but if the valuations are switched (Alice wants [0,0.5] and Bob wants [0,1]), then x=0.5 and both agents get desired length 0.5.
• It is not position oblivious: if Alice wants [0,0.5] and Bob wants [0,1] then both agents get value 0.5, but if Alice's desired interval moves to [0.5,1] then x=0.75 and Alice gets 0.25 and Bob gets 0.75.

This is not a problem with this specific mechanism: it is provably impossible to have a truthful and envy-free mechanism that allocates the entire cake and guarantees any of these three properties, even for two agents with piecewise-uniform valuations.

Moreover, it is impossible to have a truthful and envy-free mechanism that guarantees any of these properties, even with free disposal, when the valuations are piecewise-constant.

The BHS mechanism was extended to any number of agents, but only for a special case of piecewise-uniform valuations, in which each agent desires only a single interval of the form [0, x_i].