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.
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 at most n ( n − 1 ) 2 {\displaystyle n(n-1)^{2}} 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 (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:
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. 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. 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. 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. 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).
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 (as in the Robertson-Webb model). Branzei and Miltersen show that the exact-division mechanism can be "discretized" and executed in the query model. This yields, for any ϵ > 0 {\displaystyle \epsilon >0} , a randomized query-based protocol, that asks at most O ( n 2 / ϵ ) {\displaystyle O(n^{2}/\epsilon )} queries, is truthful in expectation, and allocates each agent a piece of value between 1 / n − ϵ {\displaystyle 1/n-\epsilon } and 1 / n + ϵ {\displaystyle 1/n+\epsilon } , 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.
… excerpt ends here. Continue reading the full article.
