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 classic 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.
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.Exact division mechanism
An exact 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 at most cuts; this is a corollary of the Stromquist–Woodall theorem and the necklace splitting 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 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:
- Ask the agents to report their value measures.
- Use the existing algorithm/oracle to generate an exact division.
- Perform a random permutation on the consensus partition and give each partner one of the pieces.
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.Mossel and Tamuz present a super-proportional randomized mechanism that is truthful in expectation:
- Pick a division from a certain distribution D over divisions.
- Ask each agent to evaluate his/her piece.
- If all n evaluations are more than 1/n, then implement the allocation and finish.
- Otherwise, use the exact-division mechanism.
Approximate exact division using queries
Suppose that, rather than directly revealing their valuations, the agents reveal their values indirectly by answering mark and eval queries.Branzei and Miltersen show that the exact-division mechanism can be "discretized" and executed in the query model. This yields, for any, a randomized query-based protocol, that asks at most queries, is truthful in expectation, and allocates each agent a piece of value between and, by the valuations of all agents.
On the other hand, they prove that, in any deterministic truthful query-based protocol, if all agents value all parts of the cake positively, there is at least one agent who gets the empty piece. This implies that, if there are only two agents, then at least one agent is a "dictator" and gets the entire cake. Obviously, any such mechanism cannot be envy-free.
Randomized mechanism for piecewise-constant valuations
Suppose all agents have piecewise-constant valuations. This means that, for each agent, the cake is partitioned into finitely many subsets, and the agent's value density in each subset is constant. 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. When there are only two agents, it is also polynomial-time and robust envy-free.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.
Aziz and Ye prove that there is no deterministic truthful mechanism that satisfies either one of the following properties:'
- Proportional and Pareto-optimal;
- Robust-proportional and non-wasteful.
- Approximately-truthful, approximately-proportional and non-wasteful ;
- Truthful, approximately-proportional and connected.
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:
- 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.
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:
- 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.
Piecewise-uniform valuations
Chen, Lai, Parkes and Procaccia present 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.
- Ask each agent to report his/her desired intervals.
- Each sub-interval, that is desired by no agent, is discarded.
- Each sub-interval, that is desired by exactly one agent, is allocated to that agent.
- The sub-intervals, that are desired by both agents, are allocated such that both agents get an equal total length.
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 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. Consider the special case of two agents with piecewise-uniform valuations, where the cake is , Alice wants only the subinterval for some a<1, and Bob desires only the subinterval 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 for some c<1 and Bob a subset for some d<1. In this model:
- A non-wasteful determininstic mechanism is truthful iff, for some parameter t in , it gives Alice the interval and Bob the interval
- Such mechanism is envy-free iff t=1/2; in this case it is equivalent to the CLPP mechanism
Li, Zhang and Zhang show that the CLPP mechanism works well even when there are externalities, as long as the externalities are sufficiently small. On the other hand, if the externalities are large, no truthful non-wasteful and position independent mechanism exists.
Alijani, Farhadi, Ghodsi, Seddighin and Tajik present several mechanisms for special cases of piecewise-uniform valuations:
- 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.
- Find the smallest x in such that Alice's desired length in equals Bob's desired length in .
- Give Alice the intervals in valued by Alice and the intervals in not valued by Bob; give the remainder to Bob.
- It does not guarantee connected pieces, for example when Alice wants and Bob wants , then x=0.25, Alice gets and , and Bob gets .
- It is not anonymous : if Alice wants and Bob wants , then Alice gets a desired length of 0.75 and Bob gets 0.25, but if the valuations are switched, then x=0.5 and both agents get desired length 0.5.
- It is not position oblivious: if Alice wants and Bob wants then both agents get value 0.5, but if Alice's desired interval moves to then x=0.75 and Alice gets 0.25 and Bob gets 0.75.
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 .
Ianovsky 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 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.