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 classic divide and choose procedure for cake-cutting is not truthful: if the cutter knows the chooser's preferences, they 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).

Randomized mechanisms

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.

Deterministic mechanisms: piecewise-constant valuations

For deterministic mechanisms, the results are mostly negative, even when all agents have piecewise-constant valuations.

Kurokawa, Lai and Procaccia prove that there is no deterministic, truthful and envy-free mechanism that requires a bounded number of Robertson-Webb queries.^[5]

Aziz and Ye prove that there is no deterministic truthful mechanism that satisfies either one of the following properties:^[4]

• Proportional and Pareto-optimal;
• Robust-proportional and non-wasteful ("non-wasteful" means that no piece is allocated to an agent who does not want it; it is weaker than Pareto-optimality).

Menon and Larson introduce the notion of ε-truthfulness, which means that no agent gains more than a fraction ε from misreporting, where ε is a positive constant independent of the agents' valuations. They prove that no deterministic mechanism satisfies either one of the following properties:^[6]

• ε-truthful, approximately-proportional and non-wasteful (for approximation constants at most 1/n);
• Truthful, approximately-proportional and connected (for approximation constant at most 1/n).

They present a minor modification to the Even–Paz protocol and prove that it is ε-truthful with ε = 1 - 3/(2n) when n is even, and ε = 1 - 3/(2n) + 1/n² when n is odd.

Bei, Chen, Huzhang, Tao and Wu prove that there is no deterministic, truthful and envy-free mechanism, even in the direct-revelation model, that satisfies either one of the following additional properties:^[7]

• Connected pieces;
• Non-wasteful;
• Position oblivious - the allocation of a cake-part is based only on the agents' valuations of that part, and not on its relative position on the cake.

Note that these impossibility results hold with or without free disposal.

On the positive side, in a replicate economy, where each agent is replicated k times, there are envy-free mechanisms in which truth-telling is a Nash equilibrium:^[7]

• With connectivity requirement, in any envy-free mechanism, truth-telling converges to a Nash equilibrium when k approaches infinity;
• Without connectivity requirement, in the mechanism that allocates each homogeneous sub-interval equally among all agents, truth-telling is a Nash equilibrium already when k ≥ 2.

Tao improves the previous impossibility result by Bei, Chen, Huzhang, Tao and Wu and shows that there is no deterministic, truthful and proportional mechanism, even in the direct-revelation model, and even when all of the followings hold:^[8]

• There are only two agents;
• Agents are hungry: each agent's valuation is positive (i.e., cannot be 0);
• The mechanism is allowed to leave some part of the cake unallocated.

It is open whether this impossibility result extends to three or more agents.

On the positive side, Tao presents two algorithms that attain a weaker notion called "proportional risk-averse truthfulness" (PRAT). It means that, in any profitable deviation for agent i, there exist valuations of the other agents, for which i gets less than his proportional share. This property is stronger than "risk-averse truthfulness", which means that, in any profitable deviation for i, there exist valuations of the other agents, for which i gets less than his value in a truthful reporting. He presents an algorithm that is PRAT and envy-free, and an algorithm that is PRAT, proportional and connected.^[8]

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. This is a special case of piecewise-constant valuations. Several truthful algorithms have been developed for this special case.

Chen, Lai, Parkes and Procaccia present a direct-revelation mechanism that is deterministic, proportional, envy-free, Pareto-optimal, and polynomial-time.^[2] 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 relies on the free disposal assumption, i.e., the ability to discard pieces that are not desired by any agent.

Note: Aziz and Ye^[4] presented two mechanisms that extend the CLPP mechanism to piecewise-constant valuations - Constrained Cake Eating Algorithm and Market Equilibrium Algorithm. However, both these extensions are no longer truthful when the valuations are not piecewise-uniform.

Maya and Nisan show that the CLPP mechanism is unique in the following sense.^[9] 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

They also show that, even for 2 agents, any truthful mechanism achieves at most 0.93 of the optimal social welfare.

Li, Zhang and Zhang show that the CLPP mechanism works well even when there are externalities (i.e., some agents derive some benefit from the value given to others), as long as the externalities are sufficiently small. On the other hand, if the externalities (either positive or negative) are large, no truthful non-wasteful and position independent mechanism exists.^[10]

Alijani, Farhadi, Ghodsi, Seddighin and Tajik present several mechanisms for special cases of piecewise-uniform valuations:^[11]

• The expansion process handles piecewise-uniform valuations where each agent has a single desired interval, and moreover, the agents' desired intervals satisfy an ordering property. It is polynomial-time, truthful, envy-free, and guarantees connected pieces.
• The expansion process with unlocking handles piecewise-uniform valuations where each agent has a single desired interval, but without the ordering requirement. It is polynomial-time, truthful, envy-free, and not necessarily connected, but it makes at most 2n-2 cuts.

Bei, Huzhang and Suksompong present 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 allocated:^[12]

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 the 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.^[12]

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].

Ianovsky^[13] proves that no truthful mechanism can attain a utilitarian-optimal cake-cutting, even when all agents have piecewise-uniform valuations. Moreover, no truthful mechanism can attain an allocation with utilitarian welfare at least as large as any other mechanism. However, there is a simple truthful mechanism (denoted Lex Order) that is non-wasteful: give to agent 1 all pieces that he likes; then, give to agent 2 all pieces that he likes and were not yet given to agent 1; etc. A variant of this mechanism is the Length Game, in which the agents are renamed by the total length of their desired intervals, such that the agent with the shortest interval is called 1, the agent with the next-shortest interval is called 2, etc. This is not a truthful mechanism, however:

• If all agents are truthful, then it produces a utilitarian-optimal allocation.
• If the agents are strategic, then all its well-behaved Nash equilibria are Pareto-efficient and envy-free, and yield the same payoffs as the CLPP mechanism.

Summary of truthful mechanisms and impossibility results

Name	Type	Deterministic?	#agents(n)	Valuations[14]	Chores?[15]	Run time	All?[16]	PO?[17]	EF?[18]	Anon?[19]	Conn?[20]	Pos.Ob.?[21]	No Waste?[22]
Exact division[1][2]	Direct	No	Many	General	Yes	Unbounded[23]	Yes	No	Yes	Yes	No	?	?
Super-proportional[1]	Direct	No	Many	General	Yes	Unbounded	Yes	No	No	Yes	No	?	?
Discrete exact division[3]	Queries	No	Many	General	Yes	${\displaystyle O(n^{2}/\epsilon )}$	Yes	No	${\displaystyle \epsilon }$-EF	Yes	No	?	?
Constrained Serial Dictatorship[4]	Direct	No	Many	PWC	?	?	No	Unanimity	Prop.	?	No	?	?
CLPP[2]	Direct	Yes	Many	PWU	No	Polynomial	No	Yes	Yes	Yes	No	?	Yes
BHS 1, 2	Direct	Yes	2	PWU	Yes	Polynomial	Yes	Yes	Yes	No	No	No	Yes
BHS 3, 4	Direct	Yes	Many	PWU1	Yes	Polynomial	Yes	Yes	Yes (for cakes)	?	?	?	Yes
Expansion[11]	Direct	Yes	Many	PWU1+order	?	Polynomial	?	?	Yes	?	Yes	?	?
Expansion+ Unlocking	Direct	Yes	Many	PWU1	?	Polynomial	?	?	Yes	?	2n-2 cuts	?	?
IMPOSSIBLE COMBINATIONS:
[BM][3]	Queries	Yes	2+	Any
[BHS][12]	Direct	Yes	2+	PWU			Yes		Yes	Yes
[BHS]	Direct	Yes	2+	PWU			Yes		Yes		Yes
[BHS]	Direct	Yes	2+	PWU			Yes		Yes			Yes
[T][8]	Direct	Yes	2+	PWC					Yes(even for Prop.)
[BCHTW][7]	Direct	Yes	2+	PWC			Yes		Yes		Yes
[BCHTW]	Direct	Yes	2+	PWC			Yes		Yes			Yes
[BCHTW]	Direct	Yes	2+	PWC			Yes		Yes				Yes
[BCHTW]	Sequential	Yes	2+	PWC			Yes		Yes

See also

• Strategic fair division
• Truthful resource allocation

References