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.
The challenge is to develop truthful mechanisms that are fair ex-post and not just ex-ante.
Suppose we have a non-truthful algorithm (or oracle) for finding an exact division.
A super-proportional division is a cake-division in which each agent receives strictly more than 1/n by their own value measures.
Mossel and Tamuz present a super-proportional randomized mechanism that is truthful in expectation:[1] 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 if it exists.
Branzei and Miltersen[3] show that the exact-division mechanism can be "discretized" and executed in the query model.
For this case, Aziz and Ye present a randomized algorithm that is more economically-efficient: Constrained Serial Dictatorship is truthful in expectation, robust proportional, and satisfies a property called unanimity: if each agent's most preferred 1/n length of the cake is disjoint from other agents, then each agent gets their most preferred 1/n length of the cake.
This is a weak form of efficiency that is not satisfied by the mechanisms based on exact division.
[4] 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] 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.
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] 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] 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] 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).
Chen, Lai, Parkes and Procaccia present a direct-revelation mechanism that is deterministic, proportional, envy-free, Pareto-optimal, and polynomial-time.
Maya and Nisan show that the CLPP mechanism is unique in the following sense.
In this model: They also show that, even for 2 agents, any truthful mechanism achieves at most 0.93 of the optimal social welfare.
[11] Alijani, Farhadi, Ghodsi, Seddighin and Tajik present several mechanisms for special cases of piecewise-uniform valuations:[12] 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:[13] 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: 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.
Ianovsky[14] proves that no truthful mechanism can attain a utilitarian-optimal cake-cutting, even when all agents have piecewise-uniform valuations.