{'fraction_non_alphanumeric': 0.048690765844050514, 'fraction_numerical': 0.01778472946356158, 'mean_word_length': 4.121949410281136, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 37, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Existence of Truthful Fair Cake Cutting Mechanisms

We study the fair division problem on divisible heterogeneous resources (the cake cutting problem) with strategic agents, where each agent can manipulate his/her private valuation in order to receive a better allocation. A (direct-revelation) mechanism takes agents' reported valuations as input and outputs an allocation that satisfies a given fairness requirement. A natural and fundamental open problem, first raised by [Chen et al., 2010] and subsequently raised by [Procaccia, 2013] [Aziz and Ye, 2014] [Branzei and Miltersen, 2015] [Menon and Larson, 2017] [Bei et al., 2017] [Bei et al., 2020], etc., is whether there exists a deterministic, truthful and envy-free (or even proportional) cake cutting mechanism. In this paper, we resolve this open problem by proving that there does not exist a deterministic, truthful and proportional cake cutting mechanism, even in the special case where all of the following hold: 1. there are only two agents; 2. each agent's valuation is a piecewise-constant function; 3. each agent is hungry: each agent has a strictly positive value on any part of the cake. The impossibility result extends to the case where the mechanism is allowed to leave some part of the cake unallocated. To circumvent this impossibility result, we aim to design mechanisms that possess a certain degree of truthfulness. Motivated by the kind of truthfulness possessed by the classical I-cut-you-choose protocol, we propose a weaker notion of truthfulness: the proportional risk-averse truthfulness. We show that the well-known moving-knife (Dubins-Spanier) procedure and Even-Paz algorithm do not have this truthful property. We propose a mechanism that is proportionally risk-averse truthful and envy-free, and a mechanism that is proportionally risk-averse truthful that always outputs allocations with connected pieces.


Introduction
The cake cutting problem studies the allocation of a piece of divisible heterogeneous resource to multiple agents, normally with a given fairness requirement. The cake is a metaphor for divisible heterogeneous resources, which is normally modeled as an interval [0, 1]. Different agents have different valuations on different parts of the interval. Typically, each agent's valuation is described by a value density function f : [0, 1] → R ≥0 , and his/her value on a subset X ⊆ [0, 1] is given by the Riemann integral X f (x) dx. Starting with Steinhaus [39], the cake cutting problem has been widely studied by mathematicians (e.g., [25,28,17,41,16]), economists (e.g., [43,42,1]), and computer scientists (e.g., most of the papers cited by this paper). See the books [15,37], Part II of the book [18], and the survey [35].
Two of the most widely studied fairness criteria are proportionality and envy-freeness. An allocation is proportional if each agent believes (s)he receives a share with a value that is at least a 1 n fraction of the value of the entire cake (where n is the number of the agents). An allocation is envy-free if each agent believes (s)he receives a share that has weakly more value than the share allocated to each of the other agents (i.e., an agent does not envy any other agents). Formal definitions for the two notions are in Sect. 2. If we require that the entire cake needs to be allocated (i.e., discarding some part of the cake is disallowed), an envy-free allocation is always proportional. It is well-known that envy-free allocations (with the entire cake allocated) always exist [17], even if we require each agent must receive a connected interval [41]. In addition to the existence, the algorithm design aspect has also been considered for a long history [25,28,40,8,7]. In particular, we know how to compute a proportional allocation [25,28] and an envy-free allocation [7] for any number of agents.
However, a fundamental issue when deploying a certain cake cutting algorithm is that agents are self-interested and may manipulate and misreport their valuations to the algorithm to get better allocations. This motivates the study of the cake-cutting problem from a game-theoretical aspect, in particular, a mechanism design aspect. Is there a truthful and fair cake cutting mechanism such that truth-telling is each agent's dominant strategy? This question was first proposed by Chen, Lai, Parkes, and Procaccia [22].
To answer this question, we first need to address the following issue: how can we represent a value density function succinctly? Two different approaches have been considered in the past literature. In the first approach (e.g., [17,37,40,30,8,7]), the mechanism communicates with the agents by a query model called the Robertson-Webb query model, where the mechanism learns the valuation of each agent through a sequence of queries that are of the following two types: • Eval i (x, y): ask agent i his/her value on the interval [x, y]; • Cut i (x, r): ask agent i for a point y where [x, y] is worth exactly r.
In the second approach (e.g., [34,22,10,33,11,12]), the value density function is assumed to be piecewise-constant. Piecewise-constant functions can approximate most natural real functions arbitrarily closely, and they can be succinctly encoded. The mechanism then takes the n encoded value density functions as inputs and outputs an allocation. These mechanisms are called direct revelation mechanisms.
In the Robertson-Webb query model setting, the game agents are playing is an extensive-form game, whereas, in the piecewise-constant valuation setting, this is a one-round game where all the agents report their valuations simultaneously. Naturally, when truthfulness is concerned, agents in the first setting have much more room for manipulation. Indeed, for the first setting, Kurokawa et al. [30] prove that no truthful and envy-free mechanism terminates within a bounded number of Robertson-Webb queries. A strong impossibility result by Brânzei and Miltersen [19] show that, for any truthful mechanism, there exists an agent who receives a zero value. In particular, when there are only two agents, the only truthful mechanism is essentially the one that allocates the entire cake to a single agent (under some mild technical assumptions).
For direct revelation mechanisms, Chen et al. [22] give the first truthful envy-free cake cutting mechanism that works when each agent's valuation is piecewise-uniform, a special case of piecewiseconstant valuations with the additional assumption that each value density function takes value either 0 or 1. Chen et al. [22] then propose the following natural open problem. Problem 1. Does there exist a (deterministic) truthful, envy-free (or even proportional) cake cutting mechanism for piecewise-constant value density functions?
Many researchers make partial progress on this problem in the past decade. Aziz and Ye [9] show that there exists no truthful mechanism that satisfies either one of the following properties: • 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, a notion weaker than Pareto-optimality).
Menon and Larson [33] show that there exists no truthful mechanism that is even approximately proportional, with the constraint that each agent must receive a connected piece. Bei et al. [11] show that there exists no truthful, proportional mechanism under any one of the following three settings: • the mechanism is non-wasteful; • the mechanism is position-oblivious (meaning that 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); • agents report the value density functions sequentially, where an agent's strategy can depend on the reports of the previous agents.
On the positive side, the mechanism proposed by Chen et al. [22] for piecewise-uniform value density functions is further studied by Maya and Nisan [32] and Li et al. [31]. Maya and Nisan [32] characterize truthful mechanisms and show that the mechanism proposed by Chen et al. [22] is unique in some sense. Li et al. [31] show that this mechanism also works in the setting where agents have externalities. Bei et al. [12] propose a truthful envy-free mechanism for piecewiseuniform value density functions that do not need the free-disposal assumption, an assumption made in the mechanism by Chen et al. [22]. Designing truthful and fair allocations has also been studied for value density functions that are more restrictive than piecewise-uniform [2,38,4]. As can be seen above, most of the positive results are regarding piecewise-uniform valuations or even more restrictive ones.
Despite the above-mentioned progress, Problem 1 remains open. All the mechanisms mentioned above are deterministic. If we allow randomized mechanisms, a simple mechanism proposed by Mossel and Tamuz [34] is universal envy-free and truthful in expectation. However, randomized mechanisms have many drawbacks. Firstly, agents can be risk-seeking or risk-averse and may have different views on a truthful-in-expectation randomized mechanism. Secondly, agents may have concerns about the source of the randomness. It is costly to find a trustworthy random source. Agents receiving less utility due to randomness may believe they have not been treated fairly.
In Sect. 7, we discuss some additional related work that is less relevant.

Our Results
As the main result of this paper, we resolve Problem 1 by proving that there does not exist a (deterministic) truthful proportional cake cutting mechanism. This impossibility result can be extended to the setting where there are only two agents, each agent has a strictly positive value on any part of the cake (we say that the agents are hungry in this case), and the mechanism is allowed to leave some part of the cake unallocated. We further show that the impossibility result extends to the setting where only approximate proportionality is required, for some constant approximation ratio sufficiently close to 1.
Main Result: There does not exist a deterministic, truthful, and (approximately) proportional mechanism, even if there are only two agents, agents are hungry, and the mechanism is allowed to discard some parts of the cake. (Theorem 3.1 and Theorem 3.11) To circumvent this impossibility result, we propose a weaker truthful notion called risk-averse truthful. This is motivated by the truthful guarantee of the I-cut-you-choose protocol (the protocol is defined in Sect. 4, after Theorem 4.1). Our risk-averse truthful notion captures the risk-averseness of the agents and the setting where an agent does not know other agents' valuations. Informally, a mechanism is risk-averse truthful if either each agent's misreporting of his/her valuation is not beneficial, or there is a possibility that the misreporting will hurt the agent's utility (see Definition 4.2). Based on the solution concept of proportionality, we also consider a truthful notion called proportionally risk-averse truthful that is stronger than risk-averse truthful. A proportional mechanism is proportionally risk-averse truthful if either each agent's misreporting of his/her valuation is not more beneficial, or there is a possibility that the misreporting will make the agent even fail to get a proportional allocation (see Definition 4.3).
We show that those well-known algorithms, e.g., the moving-knife procedure [25] and the Even-Paz algorithm [28], do not satisfy this truthful property. We then propose a mechanism that is proportionally risk-averse truthful and envy-free, and a mechanism that is proportionally risk-averse truthful that always outputs allocations with connected pieces.

Result 2:
There exists a mechanism that is proportionally risk-averse truthful and envy-free.

(Theorem 5.2)
Result 3: There exists a mechanism that is proportionally risk-averse truthful that always outputs allocations with connected pieces. (Theorem 6.4, Theorem 6.5 and Theorem 6.6) Our risk-averse truthful notion is similar to but stronger than the truthful notion defined by Brams, Jones, and Klamler [16]. They also consider the setting where each agent does not know the valuations of the other agents, and, in their notion, a mechanism is truthful if each agent cannot misreport his/her valuation and "assuredly" do better. It is possible that misreporting will always be no harm, sometimes make the agent's utility unchanged, and sometimes be beneficial. In this case, the misreporting cannot "assuredly do better". It satisfies the truthful notion in reference [16] but not our risk-averse truthfulness. For example, the above-mentioned moving-knife procedure satisfies the truthful notion in reference [16] but not our risk-averse truthfulness. See Sect. 4 and Appendix B for details and more comparisons.

Structure of This Paper
In Sect. 2, we formally describe the model of the cake cutting problem with direct revelation mechanisms. In Sect. 3, we present our main result: resolving Problem 1 and extending the impossibility result to the approximation setting. Sect. 4 to Sect. 6 discuss the relaxations on dominant strategy truthfulness and present several mechanisms that satisfy the relaxed truthful notions. In Sect. 7, we discuss some additional related work that is less relevant. We conclude our paper and discuss some future research directions in Sect. 8.

Preliminaries
The cake is modeled as the interval [0, 1], which is allocated to n agents. Each agent i has a value density function f i : [0, 1] → R ≥0 that describes his/her preference on the cake. A value density function f i is piecewise-constant if [0, 1] can be partitioned into finitely many intervals, and f i is constant on each of these intervals. We will assume agents' value density functions are piecewiseconstant throughout the paper, although our results in Sect. 6 do not rely on this. Agent i is hungry if f i (x) > 0 for any x ∈ [0, 1]. Given a subset X ⊆ [0, 1], agent i's utility on X, denoted by v i (X), is given by 1]. Notice that an impossibility result without the entire requirement is stronger than an impossibility result with this requirement. An allocation is proportional if each agent receives his/her average share of the entire cake: An allocation is α-approximately proportional if 1 n above is changed to α n . An allocation is envy-free if each agent receives a portion that has a weakly higher value than any portion received by any other agent, based on his/her own valuation: An entire envy-free allocation is always proportional. In the case of two agents, if an allocation is entire, it is envy-free if and only if it is proportional. In Sect. 6, we consider a specific kind of allocations where each agent needs to receive a connected piece of cake, i.e., each A i is an interval.
A mechanism is a function M that maps n value density functions F = (f 1 , . . . , f n ) to an allocation (A 1 , . . . , A n ). Given M(F ) = (A 1 , . . . , A n ), we write M i (F ) = A i . That is, M i (F ) outputs the share allocated to agent i, given input F = (f 1 , . . . , f n ). A mechanism is proportional/envy-free if it always outputs a proportional/envy-free allocation with respect to the input F = (f 1 , . . . , f n ). A mechanism is entire if it always outputs entire allocations. In this paper, we consider only deterministic mechanisms.
A mechanism M is truthful if each agent's dominant strategy is to report his/her true value density function. That is, for each i ∈ [n], any (f 1 , . . . , f n ) and any As a clarification, when proportionality/envy-freeness is concerned, a mechanism must output an allocation that is proportional/envy-free with respect to the reported value density functions; when truthfulness is concerned, we require each agent's misreporting does not give this agent strictly more utility, and the utility here is with respect to this agent's true value density function.

Impossibility Result for Truthful Proportional Mechanism
In this section, we prove the following theorem.
Theorem 3.1. There does not exist a truthful proportional mechanism, even when all of the following hold: • there are two agents; • each agent's value density function is piecewise-constant; • each agent is hungry: each f i satisfies f i (x) > 0 for any x ∈ [0, 1]; • the mechanism needs not to be entire: the mechanism may throw away parts of the cake.
We will prove Theorem 3.1 by contradiction. Suppose there exists a truthful proportional mechanism M for two agents. For a description of the main idea behind the proof, we construct multiple cake cutting instances, analyze the outputs of M on these instances, and prove that truthfulness and proportionality cannot be guaranteed on all these instances. In particular, we will construct six instances. For the first five instances, we show that the outputs of M are unique. Based on the outputs for the first five instances, we show that any allocation output by M for the sixth instance will violate either proportionality or truthfulness. The six instances constructed are shown in Table 1.
We start with the simplest cake cutting instance.
In the instances constructed later, we let ε > 0 be a sufficiently small real number. Next, we consider the following instance.
2 ), where f The following proposition shows that the only possible allocation output by M for Instance 2 is (X 1 , X 2 ). Proof. Firstly, we must have |M 2 (F (2) )| ≤ 1 2 . Otherwise, agent 1 will receive a subset of length strictly less than 1/2. Since agent 1's valuation is uniform on [0, 1], M is not proportional.
Secondly, we must have X 2 ⊆ M 2 (F (2) ). Suppose otherwise that agent 2 does not receive all of X 2 , i.e., On the other hand, if agent 2 misreports his/her value density function to f 2 ), the mechanism receives input (f 2 ), which becomes Instance 1 since f 1 . In this case the allocation output is (X 1 , X 2 ), and agent 2's total value, in terms of his true valuation f (2) 2 , is 1 2 . Therefore, agent 2 can receive more value by misreporting his/her value density function, and M cannot be truthful.
The next instance we consider is slightly more complicated.
2 ), where The following proposition shows that each agent's allocated subset is exactly the union of half of X 1 and half of X 2 .
We provide a brief intuition behind the proof first. Firstly, agent 1 cannot receive a subset of length more than 0.5. Otherwise, in Instance 2, agent 1 will misreport his value density function from f 1 , which is more beneficial to agent 1 (as f is uniform and agent 1 receives a larger length by misreporting).
Secondly, agent 1 cannot receive less than half of X 2 . If agent 1 receives less than half of X 2 by a length of x, agent 1 needs to receive more than half of X 1 by a length of at least 2x to guarantee proportionality. This will make the total length received by agent 1 more than 0.5.
Thirdly, agent 1 cannot receive more than half of X 2 . If agent 1 receives more than half of X 2 , agent 2, having significantly less value on X 1 , will have to receive a length on X 1 that is significantly longer than half of X 1 . This will destroy the proportionality of agent 1 for that agent 2 has already taken too much.
Finally, having shown that agent 1 must receive exactly half of X 2 , the proportionality of agent 1 and the proven fact that agent 1's received total length is at most 0.5 imply that agent 1 has to receive exactly half of X 1 .
Proof of Proposition 3.4. Firstly, we must have |M 1 (F (3) )| ≤ 1 2 . Suppose this is not the case: We show that M cannot be truthful. Consider Instance 2 where agent 1's value density function is uniform. In Instance 2, if agent 1 misreports his/her value density function to f 1 , the mechanism M will see an input that is exactly the same as F (3) (notice f 2 ), and agent 1 will receive a subset with length strictly more than 1 2 . However, we have seen in Proposition 3.3 that agent 1 will receive a subset with length exactly 1 2 if (s)he reports truthfully. Since agent 1's true valuation is uniform, agent 1 will benefit from this misreporting.
On the other hand, since which implies x ≤ 0 if ε is sufficiently small. Therefore, x = 0, and we have |M 1 (F (3) ) ∩ X 2 | = 1 4 . Since agent 1 receives exactly length 1 4 on X 2 , to guarantee proportionality, agent 1 must receive at least length 1 4 on X 1 . To guarantee Finally, agent 2 must receive the remaining part of the cake to guarantee proportionality.
We will define four subsets X 11 , X 12 , X 21 , X 22 of [0, 1] that will be used for constructing other instances later.
Proof. Noticing that f 2 , for the same reason in the proof of Proposition 3.4, we must have |M 1 (F (4) )| ≤ 1 2 . Otherwise, agent 1 in Instance 2 will misreport his/her true value density function f On the other hand, if agent 1 misreports his/her true value density function f 1 , the mechanism M will see the same input as F (3) and allocate X 11 ∪ X 21 to agent 1. With respect to agent 1's true valuation f To guarantee truthfulness, agent 1 must receive a value of at least 1 4 Given that agent 1 can receive a subset of length at most 1 2 , the maximum value agent 1 can receive is 1 4 + ε 2 , by receiving the two subsets X 11 and X 21 that are most valuable to agent 1. Therefore, |M 1 (F (4) )| ≤ 1 2 and v 1 (M 1 (F (4) )) ≥ 1 4 + ε 2 imply M 1 (F (4) ) = X 11 ∪ X 21 . Finally, to guarantee proportionality, agent 2 must receive the remaining part of the cake.
Proof. Firstly, we must have |M 1 (F (5) )| ≥ 1 2 to guarantee proportionality for agent 1. Therefore, Secondly, if agent 2 misreports his/her value density function to f 2 , the mechanism M will see an input exactly the same as F (2) , and will allocate X 2 to agent 2. This is worth 1 2 with respect to agent 2's true valuation f (5) 2 . Therefore, we must have v 2 (M 2 (F (5) )) ≥ 1 2 , for otherwise agent 2 will misreport his/her value density function to f (2) 2 . Given that agent 2 can receive a length of at most 1 2 , the maximum value (s)he can receive is 1 2 , by receiving X 2 that is most valuable to agent 2. Therefore, M 2 (F 5 ) = X 2 . To guarantee proportionality for agent 1, we must also have M 1 (F (5) ) = X 1 .
Notice that, although we do not require entire allocations, the proportionality and truthfulness constraints make the output allocations of M for the first five instances entire.
Finally, we will consider our last instance below, and show that M cannot be both truthful and proportional for any allocation it outputs.
We will analyze this instance in the following sub-section.

Analysis of M(F (6) )
We show that M cannot output an allocation for Instance 6 that guarantees both truthfulness and proportionality. This will give us a contradiction and proves Theorem 3.1. To show this, we begin by proving three propositions, and then show that they cannot be simultaneously satisfied.
The proposition follows by the proportionality of agent 2.
We first give an intuitive argument to show that Proposition 3.8, 3.9 and 3.10 cannot be all satisfied. In F (6) , agent 2 has a value equal to or approximately equal to 1 on each of the three segments X 11 , X 21 and X 22 and has a negligible value on X 12 . Proposition 3.8 indicates that (s)he can receive at most (a little bit more than) half of X 21 ∪ X 22 . To guarantee proportionality (indicated by Proposition 3.10), (s)he must receive approximately half of X 11 . On the other hand, by our construction of f (6) 1 , it is easy to see that Proposition 3.9 indicates that almost the entire X 11 needs to be given to agent 1. This gives a contradiction.
Even if the entire X 12 is allocated to agent 2 (which is worth 1 4 ε), we still have For agent 1, we must then have To find an upper bound for v 1 (M 1 (F (6) )), suppose agent 1 receives all of X 12 , X 21 and X 22 . Even in this case, we have the following upper bound for v 1 (M 1 (F (6) )): Taking ε → 0, the limit of the above upper bound is 1 8 . Thus, v 1 (M 1 (F (6) )) < 1 4 + 1 4 ε for sufficiently small ε, and Proposition 3.9 cannot be satisfied.
This concludes the proof of Theorem 3.1.

Truthful, Approximately Proportional Mechanisms
We have just proved that a truthful, proportional mechanism does not exist. To deploy cake cutting mechanisms in practice, it leaves us to consider relaxations on truthfulness or proportionality.
In the theorem below, we show the non-existence of approximately proportional mechanisms if we do not relax the dominant strategy truthfulness. In the next three sections, we will consider some relaxations on truthfulness and provide some mechanisms satisfying the relaxed truthfulness (while guaranteeing fairness).
Theorem 3.11. There does not exist a truthful and 0.974031-approximately proportional mechanism, even when all of the followings hold: • there are two agents; • each agent's value density function is piecewise-constant; • each agent is hungry: each f i satisfies f i (x) > 0 for any x ∈ [0, 1]; • the mechanism needs not to be entire. The proof of the above theorem is similar to the proof of Theorem 3.1, with the addition of many approximation analyses. We defer it to Appendix A.
The existence of truthful and approximately proportional mechanisms with smaller approximation ratios is still an open problem, and we will discuss more about it in Sect. 8.

On Weaker Truthful Guarantees, Risk-Averse Truthfulness
We have seen in the previous section that standard dominant strategy truthfulness cannot be guaranteed if we want a proportional mechanism or even an approximately proportional mechanism with a sufficiently large approximation ratio. In this section, we will consider weaker truthful criteria.
One natural idea of relaxing truthfulness is to consider approximation on truthfulness, where an agent will not receive a utility that is more than α times the utility (s)he would have received by truth-telling. However, such a notion is unconvincing in the game theory aspect, although it may be compatible in the spirit of approximation algorithm. An agent will still misreport his/her valuation under an α-approximately truthful mechanism. On the other hand, there may be other much more stable equilibria than the truth-telling profile. Agents' behaviors are still largely unpredictable under an α-approximately truthful mechanism. Therefore, we seek some other relaxation on truthfulness.
A common truthful criterion is to require that the truth-telling profile forms a Nash Equilibrium. In many applications, this is a significantly weaker guarantee than dominant strategy truthfulness. However, in our cake cutting case with direct revelation mechanisms, this truthful criteria is equivalent to the dominant strategy truthfulness, as the following theorem shows.
In this new profile, for each j = i, the function f ′ j , being the reported function in the previous case, becomes the true valuation for agent j. In this new setting, if the remaining n − 1 agents truthfully report their value density functions, which are . . , f ′ n , agent i's best response is to report f ′ i instead of his/her true valuation f i (as we have seen in the first setting). This indicates that truth-telling is not a Nash equilibrium, which is a contradiction.
Even though we do not have any progress on many standard truthful guarantees in game theory, there are still mechanisms that can achieve "a certain degree of truthfulness" in practice. Most notably, the I-cut-you-choose protocol achieves some kind of truthfulness. The protocol works for proportional/envy-free cake cutting with two agents: agent 1 find a point x on the cake [0, 1] such 1] that is more valuable to him/her, and the other piece is allocated to agent 1. It is easy to see that agent 2's dominant strategy is truth-telling: (s)he has no control over the position of x, and truth-telling can ensure (s)he gets a piece with a larger value. On the other hand, although it is not a dominant strategy for agent 1 to tell the truth, agent 1 still does not have the incentive to lie in the case (s)he has no knowledge of agent 2's valuation. If (s)he reports a value density function that results in a different position of x, there is always a risk that (s)he will receive a piece with a value less than 1/2 of the entire cake (i.e., less than the value guaranteed by proportionality).
There are two reasons behind agent 1's truth-telling incentive. Firstly, as mentioned, (s)he does not have prior knowledge of agent 2's valuations. Secondly, (s)he is a risk-averse agent: whenever there is a risk of receiving a value that is less than what (s)he would have received by truth-telling, (s)he prefers to avoid the risk.
Motivated by this example, we define and consider a new truthful criterion: the risk-averse truthfulness.

Definition 4.2.
A mechanism M is risk-averse truthful if, for each agent i with value density function f i and for any f ′ i , either one of the following holds: In other words, a mechanism is risk-averse truthful if either an agent's misreporting is nonbeneficial, or the misreporting can potentially cause the agent to receive a piece with a value that is less than what (s)he would have received by truth-telling.
The I-cut-you-choose protocol can achieve a stronger truthful property: if agent 1 modifies the cut-point x by misreporting his/her value density function, there is always a chance that (s)he will receive a piece with a value that is even less than his/her proportional value. Motivated by this, we define a stronger truthful notion based on the fairness criterion of proportionality.

Definition 4.3.
A mechanism M is proportionally risk-averse truthful if M is proportional and, for each agent i with value density function f i and for any f ′ i , either one of the following holds: Brams et al. [16] also define a truthful notion in the spirit of agents' risk-averseness and uncertainty about other agents' valuations. Their notion is weaker than our risk-averse truthfulness (and so further weaker than the proportional risk-averse truthfulness). In Appendix B, we will discuss the difference between our truthful notions and theirs, and we will also point out a minor mistake made in their paper.
We remark that there are other truthful notions that relax the dominant-strategy truthfulness with the consideration of agents' uncertainty about each other's utility. For example, Troyan and Morrill [44] define a truthful notion called "not obviously manipulatable" which requires that manipulation should not be strictly better off in both the worst case and the best case. Besides many technical differences, Troyan and Morrill's notion is also conceptually different from our (proportionally) risk-averse truthfulness. The (proportionally) risk-averse truthfulness puts more focus on agents' risk-averseness, whereas more focus is put on the difficulty of finding a deviation in Troyan and Morrill's notion. Comparing the strength of our notion with Troyan and Morrill's, neither one implies the other.
Finally, we remark that a common Bayesian model captures the uncertainty of other agents' private information: define a probability distribution from which an agent believes that the other agents' private information is drawn (typically, this distribution depends on the information this agent has). This is a typical setting in the auction theory (e.g., an agent believes that another agent's valuation on an item is drawn uniformly at random from [0, 1]). However, in our case, we do not see any natural way to define a probability distribution over piecewise-constant functions.

Risk-Averse Truthful Envy-Free Mechanisms
There exists a simple algorithm that outputs envy-free allocations for n agents with piecewiseconstant value density functions. The algorithm first collects all the points of discontinuity from all agents. This partitions the cake into multiple intervals where each agent's value density function is uniform on each of these intervals. Then, the algorithm uniformly allocates each interval to all agents. The output allocation (A 1 , . . . , A n ) of this algorithm satisfies v i (A j ) = 1 n v i ([0, 1]) (this property of an allocation is called perfect), which is clearly envy-free. However, to make the algorithm deterministic, we need to specify a left-to-right order of the n agents on how each interval is allocated. The algorithm is described in Mechanism 1.

MECHANISM 1:
A simple envy-free cake cutting algorithm 1 let X i be the set of all points of discontinuity for f i ; 2 let X = n i=1 X i ; 3 let X = {x 1 , . . . , x m−1 } be sorted by ascending order, and let x 0 = 0, x m = 1; 4 initialize A i = ∅ for each i = 1, . . . , n; 5 for each j = 0, 1, . . . , m − 1 do 6 for each agent i = 1, . . . , n do However, Mechanism 1 is not even risk-averse truthful.
To show 1), consider f 2 (x) = · · · = f n (x) = 1 for x ∈ [0, 1]. If agent 1 truthfully reports f 1 , (s)he will receive [0, 1 n 2 ) ∪ [ 1 n , 1 n + n−1 n 2 ), which is worth 1 n 2 + n−1 2n 2 . If agent 1 reports f ′ 1 , the mechanism will see n uniform functions, and allocation [0, 1 n ) to agent 1, which is worth 1 n , which is more than 1 n 2 + n−1 2n 2 . To show 2), consider any f 2 , . . . , f n . Suppose agent 1 reports f ′ 1 . Let X be defined in Step 2 and 3 of the mechanism with respect to f ′ 1 , f 2 , . . . , f n . Agent 1 always receives the leftmost 1/n fraction of each [x j , x j+1 ). Since f 1 is monotonically decreasing, this is worth at least 1/n of v([x j , x j+1 )), and agent 1 receives at least his/her proportional share overall. On the other hand, if agent 1 truthfully reports f 1 , (s)he will always receive exactly his/her proportional share, which is weakly less than what (s)he would receive by reporting f ′ 1 .
The reason for Mechanism 1 not being risk-averse truthful is that an agent can "delete" a point of continuity to merge two intervals [x j , x j+1 ) and [x j+1 , x j+2 ). This may be more beneficial if his/her value is higher on [x j , x j+1 ) (or [x j+1 , x j+2 )) and (s)he knows that the mechanism will allocate a piece on the very left (or very right) of [x j , x j+2 ). Therefore, it is the deterministic left-to-right order on each interval that compromises the truthfulness. It is easy to randomize Mechanism 1 such that Mechanism 1 is truthful in expectation, meaning that an expected utility optimizing agent's dominant strategy is truth-telling. To achieve this, we just need to partition each [x j , x j+1 ) evenly into n pieces and allocate these n pieces to the n agents by a random perfect matching. This is essentially the Mechanism proposed by Mossel and Tamuz [34].
We propose a deterministic proportionally risk-averse truthful and envy-free mechanism that uses similar ideas. The mechanism is the same as Mechanism 1, except that the left-to-right order on each interval [x j , x j+1 ) depends on the index j. Intuitively, if an agent tries to merge two intervals, (s)he does not know where exactly his/her 1/n fraction of [x j , x j+1 ) is, as (s)he does not know other agents' value density functions. This makes it possible that (s)he ends up receiving a portion where (s)he has less value. The mechanism is shown in Mechanism 2.

MECHANISM 2:
A risk-averse truthful envy-free cake cutting mechanism 1 let X i be the set of all points of discontinuity for f i ; 2 let X = n i=1 X i ; 3 let X = {x 1 , . . . , x m−1 } be sorted by ascending order, and let x 0 = 0, x m = 1; 4 initialize A i = ∅ for each i = 1, . . . , n; 5 for each j = 0, 1, . . . , m − 1 do 6 for each agent i do Proof. The envy-freeness is trivial. We will focus on proportional risk-averse truthfulness. The part of proportionality is also trivial, as an entire envy-free allocation is always proportional and Mechanism 2 is entire.
We focus on agent 1 without loss of generality. Let f 1 be agent 1's true value density function. Consider an arbitrary f ′ 1 that agent 1 reports. Let X 1 and X ′ 1 be the sets of all points of discontinuity for f 1 and f ′ 1 respectively. Suppose X 1 ⊆ X ′ 1 . It is easy to see that agent 1 will still get a value of 1 n v 1 ([0, 1]) by reporting f ′ 1 . This is because any subdivision of an interval where agent 1 has a uniform value gives only smaller intervals each of which agent 1 has a uniform value. This kind of misreporting is captured by 1 of Definition 4.3.
Suppose X 1 ⊆ X ′ 1 . Pick an arbitrary t ∈ X 1 \ X ′ 1 . Assume without loss of generality that lim . Consider a sufficiently small ε > 0 such that [t − ε, t + (n − 1)ε] do not contain any points in X 1 ∪ X ′ 1 \ {t}. We can construct f 2 , . . . , f n such that 1) n i=2 X i contains X 1 ∪ X ′ 1 ∪ {t − ε, t + (n − 1)ε} \ {t}, 2) n i=2 X i do not intersect the open interval (t − ε, t + (n − 1)ε), and 3) t − ε is the j-th point from left to right with j being a multiple of n. By our mechanism, agent 1 will receive [t − ε, t) on the j-th interval [t − ε, t + (n − 1)ε), which is worth less than 1 n v 1 ([t − ε, t + (n − 1)ε)). Agent 1 will receive value exactly 1 n v 1 ([0, 1] \ [t − ε, t + (n − 1)ε)) on the remaining part of the cake. Therefore, the overall value agent 1 receives is below the proportional value. We have shown that this type of misreporting may cause agent 1's received value to be less than the proportional value, which corresponds to 2 of Definition 4.3.

Risk-Averse Truthful Proportional Mechanisms with Connected Pieces
We have seen that Mechanism 2 is proportionally risk-averse truthful. However, each agent may receive a union of quite many intervals instead of a single interval. This is undesirable in many applications where people want a contiguous piece of resource, e.g., dividing a piece of land, or allocating meeting time slots. In this section, we are looking for proportionally risk-averse truthful mechanisms that satisfy the connected pieces property. That is, we require that each agent must receive a connected interval of the cake. Many existing algorithms output proportional allocations with connected pieces. Two notable ones are the moving-knife procedure [25] and the Even-Paz algorithm [28]. We will see in this section that both algorithms are not proportionally risk-averse truthful. In particular, the moving-knife procedure is not even risk-averse truthful. We conclude this section by proposing a proportionally risk-averse truthful mechanism with connected pieces.
Moving-knife (Dubins-Spanier) procedure Let a i = 1 n v i ([0, 1]) be agent i's proportional value. The moving-knife procedure marks for each agent i a point x i such that [0, x i ) is worth exactly a i to agent i. Then, the algorithm finds the smallest value x i * among x 1 , . . . , x n , and allocates [0, x i * ) to agent i * . Next, for the remaining part of the cake [x i * , 1], the algorithm marks for each of the n − 1 remaining agents a point x ′ i such that [x i * , x ′ i ) is worth exactly a i to agent i. The algorithm then finds the smallest value x i † among those n − 1 x ′ i s, and allocates [x i * , x i † ) to agent i † . This is repeated until the (n − 1)-th agent is allocated an interval, and then the last agent gets the remaining part of the cake. It is easy to verify that each of the first n − 1 agents receives an interval that is worth exactly his/her proportional value a i , while the last agent may receive more than his/her proportional value.
Even-Paz algorithm The Even-Paz algorithm is a divide-and-conquer-based algorithm. For each agent i, Even-Paz algorithm finds a point x i such that v i ([0, x i ]) = ⌊ n 2 ⌋v i ([0, 1]). It then find the median x * for x 1 , . . . , x n . Let L be the set of agents i with x i < x * and R be the set of agents i with x i ≥ x * . Since each agent i in L believes v i ([0, x * ]) ≥ ⌊ n 2 ⌋v i ([0, 1]) and there are ⌊ n 2 ⌋ agents in L, there exists an allocation of [0, x * ] to agents in L such that each agent i receives at least his/her proportional value 1 n v i ([0, 1]). For the similar reasons, there exists an allocation of (x * , 1] to agents in R such that each agent i receives at least his/her proportional value 1 n v i ([0, 1]). The algorithm then solves these two problems recursively. It is also easy to prove that the Even-Paz algorithm always outputs proportional allocations.
To show that both algorithms are not proportionally risk-averse truthful. We first define the following two value density functions.
Notice that The following lemma shows that any allocation that is proportional in either ℓ (n) or r (n) is also proportional in the uniform value density function. Lemma 6.1. Let f (x) = 1 for x ∈ [0, 1]. For any interval I such that I ℓ (n) (x) dx ≥ 1 n , we have I f (x) dx ≥ 1 n . For any interval I such that I r (n) (x) dx ≥ 1 n , we have I f (x) dx ≥ 1 n .
Proof. We only prove the lemma for I ℓ (n) (x) dx ≥ 1 n , as the part for I r (n) (x) dx ≥ 1 n is similar. It is straightforward to see that I ℓ (n) (x) dx = 1 n implies |I| ≥ 1 n . In particular, |I| = 1 n if the left endpoint of I belongs to {0} ∪ [ 1 n , 1 − 1 n ], and |I| > 1 n if the left endpoint of I belongs to (0, 1 n ). For |I| ≥ 1 n , we have I f (x) dx ≥ 1 n . If I ℓ (n) (x) dx > 1 n , there exists I ′ ⊆ I such that I ′ ℓ (n) (x) dx = 1 n . By our previous analysis, Theorem 6.2. The moving-knife procedure is not risk-averse truthful.
To see 2), suppose agent 1 reports f ′ 1 . Since the moving-knife procedure is proportional, regardless of what the remaining n − 1 agents report, agent 1 will receive an interval that has a value of at least 1 n with respect to f ′ 1 . By Lemma 6.1, agent 1 receives an interval that is worth at least 1 n with respect to his/her true valuation f 1 . This already shows that the moving-knife procedure is not proportionally risk-averse truthful.
We can further show that the procedure is not even risk-averse truthful. Consider any f 2 , . . . , f n . If agent 1 is not the last agent receiving an interval by reporting f 1 truthfully, agent 1 receives exactly value 1 n by the nature of the moving-knife procedure. Since we have shown that reporting f ′ 1 also guarantees the proportionality of agent 1, reporting f ′ 1 will not harm agent 1. Suppose agent 1 is the last agent receiving an interval by reporting f 1 truthfully. Now, suppose agent 1 reports f ′ 1 . In each iteration of the procedure, by Lemma 6.1, agent 1's marked point for reporting f ′ 1 is the same as, or on the right-hand side of, agent 1's marked point for reporting f 1 . This indicates that agent 1 will still be the last agent to receive an interval when reporting f ′ 1 . Moreover, the first n − 1 points cut by the procedure will only depend on f 2 , . . . , f n . Thus, when agent 1 reports f ′ 1 , agent 1 receives the same interval as it is in the case where agent 1 reports f 1 . In this case, reporting f ′ 1 does not harm agent 1 as well.
Theorem 6.3. The Even-Paz algorithm is not proportionally risk-averse truthful.
Proof. Consider the scenario with n = 5 agents. Let f 1 (x) = 1 for x ∈ [0, 1] be the true value density function for agent 1. We show that agent 1 can misreport his/her value density func- 1]). Since the Even-Paz algorithm is proportional, Lemma 6.1 immediately implies 2). It remains to show 1).
Let ε > 0 be a small number less than It is easy to verify that, in both cases, after the first round of the algorithm, an allocation of [0, 1 − 3 5 ε] to agent 1 and 2 is to be decided, and an allocation of (1 − 3 5 ε, 1] to agent 3, 4, 5 is to be decided. In the next round, the algorithm will find the half-half point for each of agent 1 and 2 on [0, 1 − 3 5 ε], and the algorithm will cut at the median of the two points, which is the average of the two points, and allocate the right-hand side interval to agent 1. By some simple calculations, the half-half point of f 1 on [0, 1 − 3 5 ε] is to the right of the half-half point of f ′ 1 on [0, 1 − 3 5 ε]. As a result, agent 1 will receives a larger length of interval if (s)he reports f ′ 1 . Since the true value density function f 1 is uniform, reporting f ′ 1 will give agent 1 more utility.
To conclude this section, we present a mechanism that is proportionally risk-averse truthful. In particular, if we require the entire allocations, it is proportionally risk-averse truthful for hungry agents. The mechanism is shown in Mechanism 3. Later, we will show that we can modify the mechanism by a little bit to make it proportionally risk-averse truthful (without assuming the agents are hungry) if we do not require entire allocations (while still guaranteeing proportionality and connected pieces).

MECHANISM 3:
A proportionally risk-averse truthful cake cutting mechanism with connected pieces // the set of agents who have not been allocated 4 for each j = 1, . . . , n − 1 do Unallocated ← Unallocated \ {i j }; 9 end 10 allocate the remaining unallocated interval to the one remaining agent in Unallocated. Theorem 6.4. Mechanism 3 is entire and proportional and always outputs allocations with connected pieces.
Proof. It is trivial that the mechanism is entire and always outputs allocations with connected pieces. It remains to show the proportionality. It suffices to show that, in each iteration j, we have [x Theorem 6.5. Mechanism 3 is proportionally risk-averse truthful for hungry agents.
Proof. Without loss of generality, we consider the potential misreport for agent 1. Let f 1 be agent 1's true value density function, and consider an arbitrary f ′ 1 . If the values for x n−1 (in Step 1 of the mechanism) are the same for f 1 and f ′ 1 , the mechanism will output the same allocation for f 1 and f ′ 1 . In this case, reporting f ′ 1 is not strictly more beneficial. We will conclude the proof by showing that, if the values for x . . , f n such that agent 1 will receive an interval with value less than the proportional value (with respect to the true valuation f 1 ). Suppose j * is the minimum index such that x (1) j * is not the same for f 1 and f ′ 1 . Let y be the value of x (1) j * for f 1 and y ′ be the value of x (1) j * for f ′ 1 . We consider two cases: y ′ < y and y ′ > y. Let ε > 0 be a sufficiently small number.
If the agents are not hungry, the set of points x n−1 being exactly what (s)he want) and potentially receive a better allocation. However, in the case this agent does not know other agents' valuations, it is equally likely that an agent's selection is not as good as the mechanism's default selection. Therefore, Mechanism 3 is still risk-averse truthful for agents that are not necessarily hungry.
It is possible to get rid of the hungry agents assumption. The trick is to make sure that each agent i receives one of [0, x n−1 that does not satisfy the condition, the same arguments in the proof of Theorem 6.5 show that there is always a scenario that (s)he will receive a value less than the proportional value. These prove the theorem below, which is stated with the formal proof left to the readers. Theorem 6.6. If changing Step 7 of Mechanism 3 to "allocate [x (i j ) j−1 , c j ) to agent i j ", Mechanism 3 is proportionally risk-averse truthful (but not entire).

Additional Related Work
In Sect. 1, we have discussed some related work for the cake-cutting problem, with the main focus on the mechanism design aspect where truthfulness is a major concern in addition to fairness. In this section, we will go through some related work in other aspects.

Computational Complexity
Although computational complexity of mechanisms is not the main focus of this paper (in fact, the impossibility results in Sect. 3 is irrelevant to computational complexity, and they also exclude the possibility of super-polynomial time mechanisms), being able to be executed in a polynomial time is still a desirable property for a practical mechanism. It is easy to check that our mechanisms in Sect. 5 and Sect. 6 can be implemented in polynomial time (in terms of the length of the string encoding all the n value density functions). If we do not consider truthfulness and focus exclusively on fairness (envy-freeness and proportionality in particular), the computational complexity for computing a fair allocation has been well studied.
Under Robertson-Webb query model. Naturally, the complexity of computing a fair allocation under the Robertson-Webb query model is measured by the number of queries. The words "algorithm" and "protocol" are used interchangeably below.
For computing a proportional allocation, both the moving-knife algorithm [25] and Even-Paz algorithm [28] described in Sect. 6 compute proportional allocations with connected pieces. It is easy to see that both algorithms can be implemented under the Robertson-Webb query model, with complexity Θ(n 2 ) and Θ(n log n) respectively. Edmonds and Pruhs [27] provide a Ω(n log n) lower bound on the complexity of deterministic proportional algorithms, which matches the upper bound.
Computing an envy-free allocation under the Robertson-Webb query model is much more challenging. The I-cut-you-choose protocol can easily find an envy-free allocation for two agents. Selfridge and Conway independently found an envy-free protocol for three agents in 1960 (both Selfridge and Conway did not publish their work), and it requires 11 queries under the Robertson-Webb query model. After more than 50 years later, Aziz and Mackenzie [8] discover an envy-free protocol that requires 584 queries for four agents. Finally, Aziz and Mackenzie [7] propose a protocol for computing an envy-free allocation for n agents, with O n n n n n n queries. On the other hand, Procaccia [36] shows that every envy-free protocol requires Ω(n 2 ) queries. There is still a large gap between the upper bound and the lower bound for the complexity of computing an envy-free allocation under the Robertson-Webb query model. For envy-free allocations with connected pieces, although the existence of such allocations is guaranteed [41], Stromquist [40] show that it cannot be found by any finite protocol (i.e., a protocol with finitely many queries), even for three agents (for two agents, the I-cut-you-choose protocol always outputs envy-free allocations with connected pieces).
The complexity for computing approximately fair allocations has also been studied [26,24,20,29]. We will not elaborate on it in this paper.
Under direct revelation model. The computation of a proportional allocation under the direct revelation model can be done in a polynomial time, even under the connected pieces requirement (e.g., the moving knife algorithm, Even-Paz algorithm, etc). Without the connected pieces requirement, computing an envy-free allocation for piecewise-constant value density functions can also be done in a polynomial time (e.g., Mechanism 1). Notice that the time complexity is measured in terms of the length of the input that encodes those n value density functions, as it is standard in the complexity theory. The remaining problem is the computational complexity for computing an envy-free allocation with connected pieces.
Deng et al. [24] show that this problem is PPAD-complete. However, instead of assuming value density functions are piecewise-constant, Deng et al. [24] consider a "polynomial-time function model" where value density functions are given by polynomial-time algorithms. For piecewiseconstant value density functions, Seddighin et al. [38] show that envy-free allocations with connected pieces can be computed in a polynomial time with a constant number of agents. For a general number of agents, the computational complexity for the problem of finding an envy-free allocation with connected pieces for piecewise-constant value density functions is still unknown.

Economic Efficiency of Allocations
Other than fairness, another well-motivated criterion for an allocation is (economic) efficiency, also known as social welfare, which is defined as the sum of the agents' values on their allocated shares n i=1 v i (A i ). Social welfare measures the overall happiness of all the agents. There are mainly two directions of research. One of them studies the optimization problem of maximizing social welfare while guaranteeing fairness (typically, proportionality or envy-freeness). The other one studies the price of fairness, which is defined as the ratio between the optimal social welfare and the optimal social welfare under a fairness constraint.
For the first direction, most work focuses on the direct revelation model assuming piecewiseconstant value density functions. Under this setting, Cohler et al. [23] discover that the problem of maximizing social welfare while guaranteeing proportionality and the same optimization problem with an envy-freeness guarantee can both be formulated by linear programs, and thus can be solved in a polynomial time. The properties of those "optimal fair allocations" are further studied by Brams et al. [14]. If we impose the connected pieces requirement, Bei et al. [10] show that, when guaranteeing proportionality, approximating the optimal social welfare to within a factor of Ω(1/ √ n) is NP-hard. If we completely drop the fairness requirement and focus exclusively on social welfare, Aumann et al. [6] show that the optimization problem is strongly NP-hard. Aumann et al. [6] also present a (polynomial-time) (8 + o(1))-approximation algorithm to complement the hardness result. The notion of the price of fairness was introduced by Bertsimas et al. [13] and Caragiannis et al. [21] independently. Caragiannis et al. [21] show that the price of proportionality is Θ( √ n) when agents' value density functions are piecewise-constant. This implies that the price of envyfreeness is Ω( √ n), as envy-freeness is a stronger fairness constraint than proportionality. The price of fairness has also been studied for allocations with connected pieces [5]. In this case, allowing allocations that are not entire may help improve social welfare. Arzi et al. [3] show that social welfare can be improved by a factor of √ n if we are allowed to discard some parts of the cake.

Conclusion and Future Work
We have proved that a truthful proportional cake cutting mechanism does not exist, even in the restrictive setting with two agents whose value density functions are piecewise-constant and strictly positive. The impossibility result extends to the setting where it is not required that the entire cake needs to be allocated. This resolves the long-standing fundamental open problem in the cake cutting literature. The main take-home message for this paper is that dominant-strategy truthfulness and fairness cannot be both guaranteed for the cake cutting problem. Therefore, to deploy a cake-cutting mechanism, we need to further relax dominant-strategy truthfulness or fairness.
Relaxing truthfulness. For relaxing dominant-strategy truthfulness, we have proposed a new truthful notion called (proportionally) risk-averse truthfulness, which is motivated by the truthful property that the I-cut-you-choose mechanism possesses. We have shown that some well-known cake cutting algorithms do not satisfy this truthful criterion. We have provided a proportionally risk-averse truthful and envy-free mechanism and a proportionally risk-averse truthful mechanism that always outputs allocations with connected pieces.
In some scenarios where randomized mechanisms are acceptable and agents are generally riskneutral, another option is the randomized mechanism proposed by Mossel and Tamuz [34] that is truthful in expectation.
Relaxing proportionality. On the other hand, we can relax the proportionality requirement, and instead, consider the approximation of proportionality. We have seen in Theorem 3.11 that there does not exist a truthful and 0.974031-approximately proportional mechanism. How about smaller approximation ratios?
Open Problem 1. Does there exist an α > 0 such that there exists a truthful, α-approximately proportional mechanism?
Designing dominant-strategy truthful mechanisms for piecewise-constant value density functions is still a largely unexplored research area. To the best of the author's knowledge, there is no known "natural" dominant-strategy truthful mechanism if agents' value density functions are piecewiseconstant. We only know some "unnatural" truthful mechanisms that either are oblivious to one or more agents' valuations (e.g., allocate the whole cake to a fixed single agent, allocate the cake evenly to n agents such that each agent receives a length of 1 n disregarding agents' valuations, etc), or cannot even guarantee each agent a positive value (e.g., the mechanism can arbitrarily fix two different allocations (A 1 , . . . , A n ) and (A ′ 1 , . . . , A ′ n ) and let the n agents vote for the more preferred allocation; this mechanism is truthful and non-oblivious to all agents' valuations, but some agents may receive pieces with a zero value). These mechanisms cannot guarantee even the minimum level of fairness.
Indeed, the author does not even know the existence of a truthful mechanism that guarantees each agent a positive value. If the answer to the following open problem is no, we have the same impossibility result as the result of Brânzei and Miltersen [19] for the Robertson-Webb query model.
Open Problem 2. Does there exist a truthful mechanism that always allocates each agent a subset on which the agent has a positive value?
Of course, if agents are hungry, the answer to the problem above is yes, as the mechanism can just allocate [0, 1] to the agents such that each agent receives a length of 1 n , disregarding the agents' reports.
In conclusion, designing a "reasonable" truthful mechanism is still a challenging problem.
Cake cutting with more than two agents. We have proved the impossibility result on truthful proportional mechanisms with n = 2. Although this implies such mechanisms do not exist in general, it still makes sense to consider this problem with a fixed number of agents that is more than 2. The author conjectures that the impossibility result holds for any fixed n ≥ 2.
Open Problem 3. Does there exist a positive integer n ≥ 3 such that there exists a truthful proportional mechanism with n agents?
Empirical studies. We have proposed two mechanisms that are risk-averse truthful. It is also interesting to test them empirically by simulations or sociological experiments and compare their performances with other classical algorithms such as the moving-knife procedure and the Even-Paz algorithm.
2 ), where f This instance is the same as the second instance in the proof of Theorem 3.1, except that X 1 and X 2 are defined differently.
Proof. Firstly, we must have |M 2 (F (2) )| ≤ |X 2 |. Otherwise, in the first instance, agent 2 will misreport f and receive an interval with a length of more than |X 2 |, which is more beneficial. This will violate truthfulness.
The third instance is also similar to before. To optimize the approximation ratio for proportionality in this impossibility result, we set the value for f 2 ), where We will define X 11 , X 12 , X 21 and X 22 as follows.
We show that both |X 11 | and |X 21 | are approximately 1 4 . The proof is similar to the proof of Proposition 3.4, with some extra calculations.
On the other hand, we have Combining this with (10), we have For agent 2, we then have (3) and (8)) 2 ), where f The following proposition says that agent 1 must receive most of X 11 and agent 2 must receive exactly X 2 .
Proof. The reason for M 2 (F (5) ) = X 2 is similar as it is in the proof of Proposition 3.7: firstly, we must have |M 2 (F (5) )| ≤ |X 2 |, for otherwise agent 2 in Instance 1 will misreport his/her value density function to f (5) 2 ; secondly, given |M 2 (F (5) )| ≤ |X 2 |, the maximum value agent 2 can get is |X 2 | by receiving X 2 , and we must allocate X 2 to agent 2 to avoid him/her to misreport f (1) 2 . This proves the second half of the proposition.
Next, we show that most part of |X 11 | are not allocated to agent 2.
Proof. Suppose agent 1 report f 1 instead of his/her true value density function f 1 . The instance becomes Instance 5, and Proposition A.6 implies agent 1 will receive a length of at least |X 11 | − τ on X 11 , which is worth |X 11 | − τ with respect to f (6) 1 . To guarantee truthfulness, we must have v 1 (M 1 (F (6) )) ≥ |X 11 | − τ .
Putting those together, we have Finally, we show that Proposition A.7 and Proposition A.8 imply that the (1 − τ )-approximate proportionality cannot be satisfied for agent 2 if τ is small.
The two propositions imply the following upper bound on the value agent 2 gets: ε + ε (Proposition A.7 and Proposition A.8) On the other hand, we have (3) and (9)) Therefore, to guarantee the (1 − τ )-approximate proportionality for agent 2, a necessary condition is 1 4 Elementary calculations show that for τ ∈ [0, 0.025969]. By considering a sufficiently small ε, the (1 − τ )-approximate proportionality cannot hold for agent 2 if τ ≤ 0.025969, which concludes Theorem 3.11.

B Discussions on Brams, Jones, and Klamler's Truthful Notion and Mechanisms
Brams et al. [16] define a truthful notion called strategy-proofness which is similar but slightly weaker than our risk-averse truthfulness. In this section, we will use the word "strategy-proof" to refer to the truthful notion defined by Brams et al. [16] (although strategy-proofness is more often used for dominant strategy truthfulness). In Sect. B.1, we will define strategy-proofness and compare it with our (proportional) risk-averse truthfulness. In Sect. B.2, we will describe the equitability procedure, a mechanism proposed by Brams et al. [16] that is strategy-proof and proportional which always outputs allocations with connected pieces (see the first paragraph in Sect. 6 for allocations with connected pieces), and we will compare it with our Mechanism 3.

B.1 Strategy-Proofness in Brams et al. [16]
In reference [16], a mechanism is strategy-vulnerable if a (risk-averse) agent can misreport his/her value density function and "assuredly" do better, regardless of the functions reported by other players. A mechanism is strategy-proof if it is not strategy-vulnerable. This notion is slightly weaker than our risk-averse truthfulness (and so further weaker than the proportional risk-averse truthfulness). Consider a scenario where an agent i misreports f i to f ′ i . If f i and f ′ i give the same worst-case utility to agent i, and f ′ i sometimes performs strictly better, the mechanism is strategy-proof in Brams et al.'s definition, but it does not satisfy Definition 4.2.
Perhaps an illustrating example is the moving-knife procedure (see Sect. 6). We have seen that the moving-knife procedure is not risk-averse truthful (Theorem 6.2). However, it is strategy-proof.
Theorem B.1. The moving-knife procedure is strategy-proof.
Let x 0 = 0 and x n = 1. We define x 1 , . . . , x n−1 iteratively as follows: given x i−1 , let x i be the smallest number such that Clearly, for each i = 1, . . . , n, the interval [x i−1 , x i ] is worth exactly the proportional value in terms of f ′ 1 .
. We have n−1

B.2 Equitability Procedure
Brams et al. [16] propose a strategy-proof mechanism, the equitability procedure, that always outputs a proportional allocation. In addition, Brams et al. [16] claim that, under the equitability procedure, an agent may receive a share that is worth less than his/her proportional share if (s)he misreports his/her value density function (see Theorem 3 of the paper). This claim is even stronger than saying that the procedure is proportionally risk-averse truthful. We will show that this claim is wrong, and the mechanism is not even proportionally risk-averse truthful.
Definition B.2. Given a valuation profile (f 1 , . . . , f n ), an allocation (A 1 , . . . , A n ) is equitable if A mechanism is equitable if it always outputs equitable allocations with respect to the reported value density functions.
The equitability procedure always outputs equitable, proportional, and entire allocations with connected pieces. An entire allocation with connected pieces can be characterized by a permutation of (1, . . . , n) which specifies a left-to-right order of the agents and a set of n − 1 cut points x 1 , . . . , x n−1 that divide the cake to n intervals such that the i-th interval is allocated to the i-th agent in the order specified by the permutation. The equitability procedure computes x 1 , . . . , x n−1 that yield an equitable allocation for each of the n! permutations. Then it outputs an allocation that maximizes the fractional value A i f i (x) dx 1 0 f i (x) dx (notice that the fraction has the same value for all the agents, as the allocation is equitable). This finishes the description of the equitability procedure.
It is proved by Brams et al. [16] that the procedure is strategy-proof. In addition, the procedure always outputs a proportional allocation (stated in the first half of Theorem 3 in their paper). Intuitively, in the moving-knife procedure, the first n − 1 agents receive exactly their proportional shares, while the last agent may receive more. Consider the same left-to-right order. By shifting the n − 1 cut points rightward for a little bit, we can make the allocation equitable while making sure each agent receives a piece with a slightly larger value. Thus, there exist "good" left-to-right orders where the resultant equitable allocations are proportional.
As we mentioned, Brams et al. [16] misclaim in Theorem 3 that, under the equitability procedure, an agent may receive a piece with a value less than the proportional value if (s)he misreports his/her value density function. Before we disprove this claim, we first note that value density functions are normalized with 1 0 f i (x) dx = 1 in reference [16], and two value density functions are considered the same if one rescales the other. However, the uniform function f (x) = 1 and the two functions ℓ (n) , r (n) defined in (2) are all normalized, and they are distinct. Suppose f (x) = 1 is an agent's true value density function, Lemma 6.1 implies that reporting ℓ (n) or r (n) can still guarantee a proportional share for this agent since the equitability procedure always outputs proportional allocations with respect to the reported value density functions. Since ℓ (n) , r (n) and f are different even up to normalization, this disproves the claim made by Brams et al. [16].
In addition, the equitability procedure is not proportionally risk-averse truthful: an agent with the uniform value density function can misreport his/her valuation to ℓ (n) or r (n) , which is sometimes more beneficial while still guaranteeing to receive a proportional share.
Theorem B.3. The equitability procedure is not proportionally risk-averse truthful.
Proof. Let f 1 (x) = 1 for x ∈ [0, 1] be agent 1's true value density function. Lemma 6.1 implies that reporting ℓ (n) still guarantees a proportional share for agent 1. It remains to show that there exist f 2 , . . . , f n such that reporting ℓ (n) is strictly more beneficial for agent 1 than truthfully reporting f 1 . Let f 2 (x) = 1 for x ∈ [0, 1 n ] and f 2 (x) = 0 for x ∈ ( 1 n , 1], and f 3 (x) = · · · = f n (x) = 0 for x ∈ [0, n−1 n ) and f 3 (x) = · · · = f n (x) = 1 for x ∈ [ n−1 n , 1]. For both scenarios where agent 1 reports f 1 and ℓ (n) respectively, agent 1 will be the second agent in the left-to-right order of the allocation. Let I be the interval allocated to agent 1 when (s)he truthfully reports f 1 . Then I is an interval that is near the left edge of the cake. By misreporting ℓ (n) , the value of I in terms of ℓ (n) is smaller than its value in terms of f 1 . To maintain equitability, the equitability procedure will stretch I to make sure the fractional value for agent 1 matches the fractional value for the remaining agents. This will make misreporting ℓ (n) more beneficial.
Notice that the author of this paper does not know if the equitability procedure is risk-averse truthful.
Comparison between the equitability procedure and Mechanism 3. The advantage of the equitability procedure is its equitability guarantee. Equitability is a desirable property for fairness in many applications. In our Mechanism 3, the first agent in the left-to-right order receives exactly his/her proportional share, while the remaining agents may receive more than their proportional shares. This may be viewed as being unfair to the first agent.
If we make the change in Theorem 6.6 for Mechanism 3, the mechanism becomes equitable: each agent receives exactly 1 n of the value of the whole cake. The equitability procedure outperforms this mechanism by allocation efficiency. The equitability procedure always outputs entire allocations, and each agent may receive a piece with more than his/her proportional value.
The advantage of Mechanism 3 is its stronger truthful guarantee, as we have already seen. In addition, the equitability procedure runs in exponential time (the mechanism needs to enumerate all the n! permutations of the n agents), while Mechanism 3, as well as all our mechanisms in Sect. 5 and Sect. 6, run in polynomial time.