# cake_cutting_envy_and_truth__21616822.pdf

Cake Cutting: Envy and Truth

Xiaohui Bei, Ning Chen, Guangda Huzhang, Biaoshuai Tao and Jiajun Wu

School of Physical and Mathematical Sciences, Nanyang Technological University xhbei@ntu.edu.sg, ningc@ntu.edu.sg, ghuzhang001@e.ntu.edu.sg, wuji0017@e.ntu.edu.sg Department of Computer Science and Engineering, University of Michigan bstao@umich.edu

We study envy-free cake cutting with strategic agents, where each agent may manipulate his private information in order to receive a better allocation. We focus on piecewise constant utility functions and consider two scenarios: the general setting without any restriction on the allocations and the restricted setting where each agent has to receive a connected piece. We show that no deterministic truthful envy-free mechanism exists in the connected piece scenario, and the same impossibility result for the general setting with some additional mild assumptions on the allocations. Finally, we study a large market model where the economy is replicated and demonstrate that truth-telling converges to a Nash equilibrium.

1 Introduction Cake cutting is a classic resource allocation problem in which a central decision maker divides and allocates a divisible and heterogeneous good, known as a cake, to n agents with individual valuation functions, with the goal of balancing efficiency and fairness. Despite its seemingly simple setting, the problem compasses rich structures and has been a central topic in resource allocation for many decades (see, e.g., the books by Brams and Taylor [1996] and Robertson and Webb [1998]), as Procaccia [2013] remarked: Cake cutting is not just child s play. One of the most widely studied fairness solution concepts in cake cutting is envy-freeness. Informally speaking, an allocation is envy-free if all agents are satisfied with their own assigned pieces, compared with the allocation of any other agent. It is well known that an envy-free allocation always exists [Brams and Taylor, 1995], even if only n 1 cuts are allowed [Su, 1999], i.e., each agent receives a connected piece. The study of computing envyfree allocations has a long history [Brams and Taylor, 1995; Stromquist, 2008], and some great progress has been made recently in deriving an envy-free algorithm for arbitrary number of agents in bounded running steps [Aziz and Mackenzie, 2016a; 2016b]. However, there is a fundamental incentive issue in computing an envy-free allocation: each participating agent is self-

interested and wants to receive an allocation with as much value as possible. Agents therefore may manipulate their privately-known valuation functions in order to increase the values of their allocations. This motivates the study of cake cutting from a game-theoretical point of view: is there any algorithm, also known as a mechanism, that incentivizes all agents to report their functions truthfully (such a mechanism is called truthful or strategy-proof)? This question was first addressed in [Chen et al., 2010] in which the authors gave a truthful cake cutting mechanism for piecewise uniform valuations. In their work, they also left the problem of designing truthful mechanism for piecewise constant valuations as an open problem. For piecewise constant valuations, it is known that no truthful, proportional (i.e., one gets at least its average share) and Pareto optimal mechanism exists [Schummer, 1996; Aziz and Ye, 2014]. A characterization of truthful mechanisms for two agents was given by Maya and Nisan [2012]. If one allows randomization, an envy-free mechanism truthful in expectation is known due to Mossel and Tamuz [2010]. (See the remark after Theorem 8 for details.) In this paper, however, we deal exclusively with deterministic mechanisms. We believe that deterministic mechanisms have several advantages compared to randomized ones. For example, agents can be risk-seeking or risk-averse, thus may have different views on a randomized mechanism that is truthful in expectation. Instead of reporting their valuations in one shot (as it is in the model considered in this paper), many work considers the Robertson-Webb query model [Robertson and Webb, 1998], in which agents reveal their valuations to the allocator through iterative queries. Under this model, it has been shown that there exists no truthful, envy-free mechanism with bounded number of queries [Kurokawa et al., 2013], and that any truthful mechanism is dictatorial [Brˆanzei and Miltersen, 2015] (i.e., there exists one agent that receives no cake at all). When truthful mechanism design is concerned, the Robertson-Webb query model is fundamentally different to our model. Its iterative nature creates much more room for agents strategic behaviors. We will discuss this in detail in the last subsection of Section 3.2. There are a number of mechanisms that work quite well in practice, even though theoretically they are not truthful. A theoretical support for such phenomena is that many mar-

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

kets of interests contain a very large number of participants. For instance, Roberts and Postlewaite [1976] proved that as the number of agents grows through replication, the utility gain of any participant from manipulations decreases to zero. Strategic analysis in large markets has been studied in, e.g., market equilibrium [Otani and Sicilian, 1982; 1990; Jackson, 1992; Jackson and Manelli, 1997], double auctions [Cripps and Swinkels, 2006; Fudenberg et al., 2007] and Gale-Shapley deferred acceptance stable matching algorithm [Roth and Peranson, 1999; Immorlica and Mahdian, 2005; Kojima and Pathak, 2009]. Most of these studies show either that the gain from manipulations converges to zero or that an equilibrium behavior converges to truth-telling. Truthful mechanism design has also been considered when allocating multiple divisible homogeneous items a problem similar to cake cutting (where a single divisible heterogeneous item is allocated) [Cole et al., 2013; Cheung, 2016; Cole and Tao, 2016]. Especially, when we restrict agents valuations to be piecewise constant, the cake can be cut into multiple pieces such that each agent s valuation is uniform on each piece. This seems to reduce the cake cutting problem to the divisible items allocation problem, with different pieces viewed as items. However, a fundamental difference lies between multiple divisible item allocation and cake cutting, because viewing the cake as multiple divisible items predefines the items. Agents could lie about the breakpoint positions in their valuation functions, therefore modify the boundaries between items, or even add new items or merge items. This has a crucial impact when truthfulness is concerned, and is why the positive results in [Cole et al., 2013; Cheung, 2016] do not carry over to the cake cutting setting.

1.1 Our Results In this paper, we study deterministic truthful envy-free mechanisms when agents have piecewise constant valuations. Note that this is one of the most natural valuation function classes that has received much attention in the cakecutting study [Bei et al., 2012; Kurokawa et al., 2013; Aziz and Ye, 2014]. Specifically, piecewise constant functions enjoy two nice properties: (i) they are concisely representable, and (ii) they can approximate any functions to an arbitrary precision. In the first part, we present a family of impossibility results. Firstly, we show that no truthful and envy-free deterministic mechanism exists if only n 1 cuts are allowed, i.e., each agent must receive a connected piece. Secondly, for the general model without any restrictions on the number of cuts, no deterministic truthful envy-free mechanism exists under either one of the two rather mild assumptions: the non-wastefulness or the position obliviousness. A mechanism is non-wasteful if it never allocates a piece to someone who does not value it; a mechanism is position oblivious if it decides the allocation of an arbitrary portion of the cake only based on the agents valuations on this portion, but not on its relative position in the cake. These results partially answer the open question raised in [Chen et al., 2010]. We also compare our results to the impossibility results in [Aziz and Ye, 2014] and [Brˆanzei and Miltersen, 2015]. Next, we consider the large market model similar to the

one in [Roberts and Postlewaite, 1976] where the economy is replicated. In the envy-free cake cutting problem, we demonstrate a similar incentive behavior for agents in large markets. Specifically, in the connected piece setting, we show that in any envy-free mechanism, truth-telling converges to a Nash equilibrium as the number of the replications grows. This is shown by providing a neat characterization of the Nash social welfare maximizing allocation, which may be of its own interest. For the general model, we give a simple deterministic truthful envy-free mechanism if the original market is replicated at least once.

2 Preliminaries In a cake cutting instance, a divisible and heterogeneous good (or a cake ), represented by the interval1 [0, 1], to be allocated to a set of n agents (or players) denoted by N = {a1, . . . , an}. Each agent ai has a density function fi : [0, 1] 7 R+ {0} which measures his preference on the cake. We assume in this paper that the density functions are all piecewise constant; that is, the whole cake can be divided into a number of intervals {X1, . . . , Xm} such that each of the density functions has a constant value on each Xt, for t = 1, . . . , m. We will use the term segment and the notation Xt exclusively to denote the t-th (from left to right) such interval in the rest of the paper. As fi is a constant on Xt, for simplicity we write fi(Xt) fi(x) for any x Xt to denote the value of fi on Xt. Notice that by our definition the partition {X1, . . . , Xm} is not pre-specified. Instead, it is determined by the n agents reported density functions {f1, . . . , fn}. Given the density function fi, for any subset S [0, 1], the value that agent ai receives from S is denoted by vi(S) = R

S fi dx. An allocation of the cake is denoted by a vector A = (A1, A2, . . . , An) where Ai is the share allocated to ai and Ai Aj = for any i = j. An allocation is called envy-free if for any ai, vi(Ai) vi(Aj) for any j. That is, ai cannot obtain a larger value from the allocated share of any other agent. We assume without loss of generality that vi([0, 1]) > 0, i.e., agent ai desires at least one segment of the cake. This assumption implies that in any envy-free allocation (A1, A2, . . . , An), each agent ai has vi(Ai) > 0. We sometimes consider allocations with only n 1 cuts, or with the connected pieces constraint, in which case each agent is required to receive a connected piece, i.e., each Ai is an interval. A mechanism is a function M : (f1, . . . , fn) 7 (A1, A2, . . . , An). That is, given input density functions, it computes an allocation for the agents. As mentioned before, we focus on deterministic mechanism in this paper. An envyfree mechanism is one where the generated allocation is always envy-free with respect to the input density functions. Note that the allocation of a mechanism is determined completely by the input density functions. In particular, all mechanisms considered in this paper are deterministic. Since all agents are self-motivated (e.g. only interested in their own

1For the sake of ease, we occasionally denote the cake by an arbitrary interval [a, b]. Note that such an instance can be easily normalized to [0, 1].

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

obtained values), it is therefore natural that one manipulates his privately-known density function in order to derive an allocation with a larger value. We call a mechanism truthful (also known as strategy proof, or incentive compatible) if it is a dominant strategy for each agent to report his density function truthfully. Note that there exists a trivial truthful envy-free mechanism: no matter what density functions that agents report, no one obtains any share; that is, the cake is not allocated at all. To eliminate such a degenerate mechanism, we assume that every segment Xt has to be allocated if someone values the segment. Specifically, those Xt for which fi(Xt) = 0 for all agent ai are to be discarded, while those Xt for which there exists ai such that fi(Xt) > 0 should be allocated. We note that this assumption is exactly the same as the free-disposal assumption in [Chen et al., 2010], and we refer the readers to [Chen et al., 2010] for a discussion why this assumption is necessary. Finally, given all agents density functions and an allocation A, the Nash social welfare is defined by the product of all agents received values: NSW(A) = Qn i=1 vi(Ai). The Nash social welfare, dated back to the last century [Nash Jr, 1950; Kaneko and Nakamura, 1979], is a solution concept balancing fairness and (economic) efficiency. An allocation maximizing the Nash social welfare satisfies many appealing properties [Moulin, 2004], including envy-freeness, proportional fairness [Kelly, 1997] and resource monotonicity [Sziklai and Segal-Halevi, 2015]. It is also independent to the scale of each agent s valuation, which is an suitable solution where there is no price system involved, as it is in our cake cutting case. For example, an agent values 1 to [0, 0.5] and values 2 to (0.5, 1] would be essentially the same with an agent values 100 to [0, 0.5] and values 200 to (0.5, 1].

3 Impossibility Results

In this section, we present several negative results on the existence of truthful envy-free deterministic mechanisms.

3.1 Connected Pieces Setting Our first focus is on allocations with only n 1 cuts.

Theorem 1. If every agent is required to receive a connected piece, no deterministic truthful envy-free mechanism exists, for any number of agents n 2.

Proof. Let ε > 0 be a sufficiently small constant. The cake is represented by [0, 7+n]. The density functions are defined as follows.

f1(x) = 1, for x [1, 2 + ε] [5, 6] f2(x) = 1, for x [3, 4] [7 ε, 8] For i = 3, . . . , n : fi(x) = 1, for x [6 + i ε, 6 + i + ε]

The value of all density functions is zero on the unspecified intervals. Notice that the cake is [0, 9] when n = 2, in which case only f1 and f2 are defined. Under the connected piece constraint, it is easy to see that either a1 or a2 will get a value of at most 1 + ε. Without loss

of generality, assume it is a1. Considering the scenario where a1 misreports his function to be

f 1(x) = 1 x [1, 2 + ε] [5, 6] 2 x [8, 7 + n] ,

we next show that a1 can get an allocation with a value of at least 2 (with respect to f1). Given the condition that one has to receive a consecutive piece, we know that a1 cannot get a value of more than 2 from the interval [8, 7 + n], for otherwise one of the agents a3, a4, . . . , an will receive no cake at all and thus envy him. (This holds trivially for n = 2, as a1 has value exactly 2 on [8, 7 + n] = [8, 9].) However, receiving value 2 is not enough for proportionality (as R

[0,7+n] f 1(x) dx = 2n + ε), and thus, it is not enough for envy-freeness. In addition, it can be seen that a1 cannot get a superset of [7 ε, 8] on which a2 has more than half of his total value. Therefore, in order to receive a value of more than 2, a1 has to take almost the entire interval [1, 6]; this results in a value of more than 2 with respect to the true function f1. Compared with the upper bound 1 + ε that a1 receives when reporting f1 truthfully, his obtained value is increased from manipulation. Therefore, no truthful mechanism exists and the theorem follows.

3.2 General Setting Without the connected pieces constraint, we show that truthful envy-free mechanism does not exist under either the nonwasteful assumption or the position oblivious assumption.

The non-wasteful assumption An allocation (A1, . . . , An) is non-wasteful if fi(x) > 0 for any x Ai. That is, no agent receives any portion with value 0. Under this assumption, we next show that no truthful envyfree deterministic mechanism exists. Theorem 2. There does not exist deterministic non-wasteful truthful envy-free mechanism even with two players.

Proof. Suppose otherwise that there is a non-wasteful truthful envy-free mechanism M. Consider the cake cutting instance with two agents whose density functions are f1(x) = 1 and f2(x) = 1 on the whole cake. The allocation A = (A1, A2) given by M must satisfy |A1| = |A2| = 0.5. Consider another cake cutting instance with two agents whose value density functions are

g1(x) = 1 x A1 0 otherwise and g2(x) = 1.

For this instance (g1, g2), the first agent a1 will get the whole A1 if M is truthful, as otherwise a1 can bid g 1(x) = 1 and get A1. Moreover, a1 cannot get more than A1, because otherwise a2 will envy a1. Thus, A = (A1, A2) is the only possible allocation generated by M for the instance (g1, g2). However, by taking advantage of the non-wasteful condition, a2 can misreport his density function and get a better allocation than A2. For example, a2 can bid the following function g 2:

g 2(x) = 1 x A1 0.5 otherwise .

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

For the instance (g1, g 2), a2 will receive the entire A2 according to the non-wasteful condition. In addition, he will receive some of A1 to guarantee envy-freeness. Thus, a2 will receive a strictly larger value from manipulation, which implies that M cannot be truthful.

The position oblivious assumption Definition 1. Given a vector of n piecewise constant density functions f = (f1, f2, . . . , fn), define the indicator function Lf : Rn 7 R, where

Lf(r1, . . . , rn) = |{x | i, fi(x) = ri}|.

Similarly, assume A = (A1, . . . , An) is an allocation produced by some mechanism with these density functions, define LAi f : Rn 7 R, where

LAi f (r1, . . . , rn) = |{x Ai | i, fi(x) = ri}|.

Definition 2. A mechanism M is position oblivious if for any two cake cutting instances with density functions f = (f1, f2, ..., fn) and f = (f 1, f 2, ..., f n) such that Lf Lf , the mechanism always outputs two allocations M(f) = (A1, . . . , An) and M(f ) = (A 1, . . . , A n) such that LAi f

LA i f for every i. Intuitively, a position oblivious mechanism will decide the allocation only based on the set of segments {Xt | t = 1, . . . , m} and each agent s values on these segments, but not on these segments relative positions on [0, 1]. Below we show that position oblivious, truthful and envyfree mechanism does not exist. First we consider a special piecewise uniform case. Lemma 1. For any I1, I2 [0, 1] such that I1 I2 = and |I1| = |I2|, given two density functions

f1(x) = 1 if x I1 I2 0 otherwise and f2(x) = 1 if x I2 0 otherwise ,

any mechanism M that is truthful, envy-free and position oblivious would produce an allocation M(f1, f2) = (A1, A2) such that I2 A2.

Proof. First consider the case where both players have density function f1. By the envy-free condition, both players will get half of I1 I2. That is, we have M(f1, f1) = (A1, A2) with |A1 (I1 I2)| = |A2 (I1 I2)| = |I1| = |I2|. Next consider another case where player 2 has density function

g2(x) = 1 if x A2 (I1 I2) 0 otherwise

Because M is truthful, one must have M(f1, g2) = (A 1, A 2) with A2 A 2, since otherwise player 2 can bid g2 = f1 to receive whole A2. Finally, due to the position oblivious property and the fact that L(f1,f2) = L(f1,g2), we know with input (f1, f2) mechanism should also give the whole I2 to player 2. This proves the lemma.

Theorem 3. There is no truthful, envy-free, and position oblivious deterministic mechanism even with two players.

Proof. Assume by contradiction that such mechanism M exists. Consider the cake cutting instance (f1, f2) with

f1(x) = 1 if x [0, 1

3] 0 otherwise and f2(x) = 1 if x [0, 1

3] ϵ if x ( 1

with some small ϵ > 0. Assume that with these inputs M produces the allocation A = (A1, A2). By the envy-free condition of a1, we know |A1 [0, 1

3]| 1 6, which implies |A2 [0, 1

3]| 1 6, and by the envy-freeness of a2 we have 1

6 |A2 [0, 1/3]| 1 6(1 O(ϵ)), and |A2 (1/3, 1]| 1

3. Next, consider another cake cutting instance (g1, g2) with

g1 = f1 and g2(x) = 1 if x [0, 1

3] I 0 otherwise ,

where we have picked I A2 (1/3, 1] such that |I| = 1

3. By Lemma 1, when reporting the true valuations, M would produce the allocation M(g1, g2) = (A1, A2) with [0, 1

3] A1. Thus a2 s utility will be no more than |I| = 1

3. On the other hand, by reporting his density function as g2 = f2, a2 will receive the whole A2 according to case (a), and his utility will be at least 1

6(1 O(ϵ)) + 1

2 O(ϵ). With ϵ small enough, this value is strictly larger than 1

3, which implies that M cannot be truthful.

We note that we do not know if a deterministic truthful mechanism exists or not without any condition; we conjecture that the answer is negative.

Comparison to other impossibility results Our result in Theorem 2 is stronger than the impossibility results in [Aziz and Ye, 2014]. When there are only two agents, envy-freeness is equivalent to proportionality, so Theorem 2 implies that no non-wasteful proportional mechanism exists. The three impossibility results in [Aziz and Ye, 2014], on the other hand, either requires the extra Pareto optimality assumption, or is based on a stronger notion called robust proportionality. Another similar impossibility result is given in [Brˆanzei and Miltersen, 2015], in which the authors show that any truthful mechanism must be dictatorial. Our result is not comparable to this. Although dictatorship is stronger than non-envy-freeness, Brˆanzei and Miltersen consider mechanisms based on the Robertson-Webb query model. Revealing agents density functions through such iterative queries provides much more room for agents strategic behaviors, as the agents answering the queries in later iterations can observe the actions of the agents who answer the queries in the first few iterations, and have their strategies being adaptive. In fact, if we consider an analogous setting in our case such that agents report their density functions sequentially (instead of simultaneously), we can have the below impossibility result with no additional assumptions like non-wastefulness and position obliviousness. Theorem 4. If agents report their density functions sequentially in a fixed order such that fi is made public at the time agent ai reports it, then there does not exist any deterministic truthful envy-free mechanism even with two players.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

Proof. Suppose there is a truthful envy-free mechanism M. We assume without loss of generality that a1 reports first. Let f1, f2, A1, A2, g1, g2, g 2 denote the same meanings as in the proof of Theorem 2. Following the same analysis, M must output A = (A1, A2) for both (f1, f2) and (g1, g2). Consider another profile (h1, h2) where h1 = g1 and h2 = g 2. Due to the envy-free condition, a1 cannot receive the entire A1. Since h1 = 0 on A2, this means a1 receives a value strictly less than 0.5. Consider the following strategy for a2: if a1 reports f1, report f2; otherwise, report his true valuation h2. Fixing this strategy for a2, if a1 truthfully reports h1, then a2 shall report h2, and we have seen that a1 will receive value strictly less than 0.5. On the other hand, if a1 lies, and reports f1 instead, then a2 shall report f2, in which case the input to M is (f1, f2), and we know the output allocation is (A1, A2). Now, a1 receives value exactly 0.5. This shows that truthtelling is not a dominant strategy for a1, and we conclude the proof.

4 Large Markets In a large market, the original market (with n agents) is replicated k times, i.e., there are nk agents in total. The definitions of envy-freeness is the same as the one in original markets. However, rather than the dominant strategy truthfulness, in this section we are interested in mechanisms in which every agent reporting his valuation truthfully form a Nash equilibrium. This is because the large market assumption requires agents valuations to form groups of identicals. Such assumption would play no role in the definition of dominant strategy truthfulness. Further, it is reasonable to assume that in a large market there will be enough participants who are truth-telling. Such notion of truthfulness has also been used in several works of other research topics such as prediction markets, crowdsourcing [Miller et al., 2005; Dasgupta and Ghosh, 2013; Shnayder et al., 2016]. Again, we consider both the connected pieces setting (Section 4.1) and the general setting (Section 4.2). Before these, we first provide a characterization of the Nash social welfare optimal allocations. Such characterization can be found useful in the analysis for the connected pieces setting, as well as other potential applications. A known property for Nash social welfare maximizing allocations is the proportional fairness [Kelly, 1997]. Theorem 5. An allocation A = (A1, . . . , An) maximizes the Nash social welfare NSW(A) if and only if Pn i=1 vi(A i) vi(Ai) vi(Ai) 0 for any allocation A .

Theorem 5 implies the following important characterization of the Nash social welfare maximizing allocations. Theorem 6. An allocation A = (A1, . . . , An) maximizes the Nash social welfare NSW(A) if and only if the following condition holds for each segment Xt:

if Ai Xt = , then fi(Xt)

vi(Ai) fj(Xt)

vj(Aj) for all i, j. (*)

Proof. The only-if direction follows immediately from Theorem 5: if we let A be the allocation in which, starting

from A, we take some fraction ε > 0 of Xt allocated to ai and give it to aj, the inequality in Theorem 5 becomes εfj(Xt)/vj(Aj) εfi(Xt)/vi(Ai) 0, which yields (*). To show the if direction, suppose an allocation A satisfies (*). Consider an arbitrary allocation A . We have vi(A i) = Pm t=1 fi(Xt)|A i Xt|, so vi(A i) vi(Ai) = Pm t=1 fi(Xt) vi(Ai) |A i Xt|.

Summing all those vi(A i) vi(Ai), we have

vi(A i) vi(Ai) =

vi(Ai) |A i Xt|

vi(Ai) |A i Xt|

t=1 |Xt| max 1 j n fj(Xt) vj(Aj)

max 1 j n fj(Xt) vj(Aj)

i=1 |Ai Xt|

vi(Ai) |Ai Xt|

(By (*), Ai Xt = implies fi(Xt)

vi(Ai) is maximum)

t=1 fi(Xt)|Ai Xt|

vi(Ai) vi(Ai),

which is exactly the proportional fairness. We conclude the if direction by Theorem 5 again.

Finally, we need the following lemma in the next subsection, which shows that the maximum Nash social welfare is insensitive when a small extra amount of cake is allocated. Lemma 2 follows easily from the resource monotonicity, another known property that a Nash social welfare maximizing allocation has [Sziklai and Segal-Halevi, 2015]. We omit its proof due to space limit.

Lemma 2. For I [0, 1], let A = (A1, . . . , An) be an allocation on [0, 1] and A = (A 1 , . . . , A n ) be an allocation on [0, 1] \ I such that both maximize the Nash social welfare. If there exists ε > 0 such that vi(I) εvi(Ai) holds for all i, then (1 ε)nvi(Ai) vi(A i ) vi(Ai).

4.1 Connected Pieces Setting In this subsection, we consider the connected pieces setting in the large market model. Recall that in a large market, the original market with n agents is replicated k times, i.e., there are nk agents in total in the market. For each i, let Ni = {ai,j | j = 1, . . . , k} be the set of agents replicated from ai. Thus, the whole agent set is given by N = i=1,...,n Ni. Let A = (Ai,j)i=1,...,n,j=1,...,k denote an allocation, and Bi = j=1,...,k Ai,j be the bundle of allocated shares of agents in Ni. Let fi and vi denote the density and value functions, respectively, shared by all agents in Ni.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

Notice that in an envy-free allocation, all agents in the same set Ni must receive the same value vi(Ai,j) = vi(Bi)

k . This is because they have the same valuation function and should not envy each other. The lemma below is an immediate implication of this observation.

Lemma 3. If there is an agent set Ni such that the piece received by an agent in Ni totally lies in a segment Xt, then fi(Xt) vi(Bi) fj(Xt)

vj(Bj) for any other agent set Nj.

Proof. If the piece received by an agent in Ni totally lies in Xt, then the length of this piece is vi(Bi) kfi(Xt). By the envy-free

condition, we have vj(Bj)

k fj(Xt) vi(Bi)

kfi(Xt) for all j. Hence,

fi(Xt) vi(Bi) fj(Xt)

The inequality in the above lemma is similar to the condition (*) in Theorem 6. Note that as k tends to infinity, the length of the piece that each agent gets approaches to zero. Since there are at most m 1 agents whose allocated pieces do not completely fall into a single segment, technically, (B1, . . . , Bn) maximizes the Nash social welfare if we ignore those m 1 agents allocated pieces. Based on this idea, we present the following result saying that truth-telling converges to a Nash equilibrium as k tends to infinity.

Theorem 7. For the large market model where the original instance with n agents is replicated by k copies, given any envy-free mechanism M, if all agents report their true valuations, the utility gain of any agent from misreporting approaches to zero as k .

Proof (Sketch). Suppose a1,1 plays the best strategy by reporting f 1, and let A be the resultant allocation output by M. We aim to show v1(A 1,1)/v1(A1,1) 1 as k . To keep other agents in group N1 from envying a1,1, it should still hold that v1(A 1,1) v1(A 1,j) for all j = 2, . . . , k. We therefore have

v1(A 1,1) v1(A1,1) = kv1(A 1,1) kv1(A1,1)

Pk j=1 v1(A 1,j)

kv1(A1,1) = v1(B 1) v1(B1),

so it will be enough to show v1(B 1)/v1(B1) 1. Let I be the union of those agents allocated pieces in the allocation A which do no fall into a single segment, i.e., those Ai,j such that there exists t with Ai,j Xt = and Ai,j Xt+1 = . Similarly, let I be the same union corresponding to the allocation A . It is easy to see that both |I| and |I | tend to zero as k . Therefore, for each i = 1, . . . , n, both vi(I) and vi(I ) tend to zero. Finally, consider an allocation S of [0, 1] to only n players with the same density functions f1, . . . , fn which maximizes NSW(S). By Lemma 3 and Theorem 6, we can see that B maximizes the Nash social welfare on [0, 1] \ I and B maximizes the Nash social welfare on [0, 1]\I . By Lemma 2, we have v1(B1) v1(S1) and v1(B 1) v1(S1), which implies v1(B 1)/v1(B1) 1.

4.2 General Setting For general setting without the connected pieces constraint, we present a truthful mechanism for large markets. Theorem 8. For each k 2, the mechanism that allocates each segment Xt evenly to all nk agents (in any deterministic way) is envy-free and truthful.

Proof. Since each segment Xt, on which all agents have uniform valuation, is evenly divided, each agent receives exactly 1/nk of the total value on the cake, and believes any other agents receive the same value. This implies the envyfreeness. It remains to show the truthfulness. Consider the m 1 break points between segments X1, . . . , Xm defined by (f1, . . . , fn). When the market is replicated, even if an agent misreports his valuation function, the break point between Xt and Xt+1 still exists (because the replicated agents still report their true functions). Therefore, although there might be new break points, the existing break points do not vanish. No matter how Xt is further subdivided, it is still evenly distributed among all agents. Hence, the mechanism is truthful.

We comment that the claim still holds if we slightly change the mechanism by assigning each segment Xt evenly to those who values the segment positively (i.e., the mechanism is non-wasteful). When k = 1 (i.e., the large market degenerates to the normal market), if we allocate each segment to all agents uniformly and randomly, [Chen et al., 2010] and [Mossel and Tamuz, 2010] showed that such randomized mechanism is truthful in expectation. However, it is easy to see that the mechanism is not universally truthful.

5 Conclusion We study the problem of designing deterministic truthful envy-free cake cutting mechanisms when agents have piecewise constant value density functions. Our results indicate that truthfulness cannot be achieved by an envy-free mechanism in many settings. This partially answers an open question raised in [Chen et al., 2010]. In addition, we consider cake cutting mechanisms in large markets and show that when the economy is replicated, there exist mechanisms in which truth-telling converges to a Nash equilibrium. The negative results (Theorem 2, 3 and 4) in Section 3.2 are based on certain assumptions. We believe it is an interesting and important open question to determine if the negative result still holds without these assumptions, that is: for piecewise constant valuations, does there exist a deterministic truthful envy-free mechanism (without the connected pieces constraint)? If the answer to this question is still negative, another natural direction for future research is to study truthful mechanisms for piecewise constant valuations that are approximately envy-free.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

References [Aziz and Mackenzie, 2016a] Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for any number of agents. FOCS, 2016. [Aziz and Mackenzie, 2016b] Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for four agents. STOC, 2016. [Aziz and Ye, 2014] Haris Aziz and Chun Ye. Cake cutting algorithms for piecewise constant and piecewise uniform valuations. In WINE, 2014. [Bei et al., 2012] Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, and Endong Yang. Optimal proportional cake cutting with connected pieces. In AAAI, 2012. [Brams and Taylor, 1995] Steven J Brams and Alan D Taylor. An envy-free cake division protocol. American Mathematical Monthly, 102(1), 1995. [Brams and Taylor, 1996] Steven J Brams and Alan D Taylor. Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, 1996. [Brˆanzei and Miltersen, 2015] Simina Brˆanzei and Peter Bro Miltersen. A dictatorship theorem for cake cutting. IJCAI, 2015. [Chen et al., 2010] Yiling Chen, John Lai, David Parkes, and Ariel D Procaccia. Truth, justice, and cake cutting. In AAAI, 2010. [Cheung, 2016] Yun Kuen Cheung. Better strategyproof mechanisms without payments or prior an analytic approach. ar Xiv preprint ar Xiv:1604.05243, 2016. [Cole and Tao, 2016] Richard Cole and Yixin Tao. Large market games with near optimal efficiency. In EC, 2016. [Cole et al., 2013] Richard Cole, Vasilis Gkatzelis, and Gagan Goel. Mechanism design for fair division: allocating divisible items without payments. In EC, 2013. [Cripps and Swinkels, 2006] Martin W. Cripps and Jeroen M. Swinkels. Efficiency of large double auctions. Econometrica, 74(1), 2006. [Dasgupta and Ghosh, 2013] Anirban Dasgupta and Arpita Ghosh. Crowdsourced judgement elicitation with endogenous proficiency. In WWW, 2013. [Fudenberg et al., 2007] Drew Fudenberg, Markus M. Mobius, and Adam Szeidl. Existence of equilibria in large double auctions. JET, 133(1), 2007. [Immorlica and Mahdian, 2005] Nicole Immorlica and Mohammad Mahdian. Marriage, honesty, and stability. In SODA, 2005. [Jackson and Manelli, 1997] Matthew O. Jackson and Alejandro M. Manelli. Approximately competitive equilibria in large finite economies. JET, 77(2), 1997. [Jackson, 1992] Matthew O. Jackson. Incentive compatibility and competitive allocations. Economics Letters, 1992. [Kaneko and Nakamura, 1979] Mamoru Kaneko and Kenjiro Nakamura. The nash social welfare function. Econometrica, 1979.

[Kelly, 1997] Frank Kelly. Charging and rate control for elastic traffic. ETT, 8(1), 1997. [Kojima and Pathak, 2009] Fuhito Kojima and Parag A. Pathak. Incentives and stability in large two-sided matching markets. JET, 99(3), 2009. [Kurokawa et al., 2013] David Kurokawa, John K Lai, and Ariel D Procaccia. How to cut a cake before the party ends. In AAAI, 2013. [Maya and Nisan, 2012] Avishay Maya and Noam Nisan. Incentive compatible two player cake cutting. In WINE, 2012. [Miller et al., 2005] Nolan Miller, Paul Resnick, and Richard Zeckhauser. Eliciting informative feedback: The peerprediction method. Management Science, 2005. [Mossel and Tamuz, 2010] Elchanan Mossel and Omer Tamuz. Truthful fair division. In SAGT, 2010. [Moulin, 2004] Herv e Moulin. Fair division and collective welfare. MIT press, 2004. [Nash Jr, 1950] John F Nash Jr. The bargaining problem. Econometrica, 1950. [Otani and Sicilian, 1982] Yoshihiko Otani and Joseph Sicilian. Equilibrium allocations of walrasian preference games. JET, 27(1), 1982. [Otani and Sicilian, 1990] Yoshihiko Otani and Joseph Sicilian. Limit properties of equilibrium allocations of walrasian strategic games. JET, 51(2), 1990. [Procaccia, 2013] Ariel D Procaccia. Cake cutting: Not just child s play. Communications of the ACM, 2013. [Roberts and Postlewaite, 1976] Donald John Roberts and Andrew Postlewaite. The incentives for price-taking behavior in large exchange economies. Econometrica, 1976. [Robertson and Webb, 1998] Jack Robertson and William Webb. Cake-Cutting Algorithms: Be Fair if You Can. Peters/CRC Press, 1998. [Roth and Peranson, 1999] Alvin E. Roth and Elliott Peranson. The redesign of the matching market for american physicians: Some engineering aspects of economic design. American Economic Review, 89(4), 1999. [Schummer, 1996] James Schummer. Strategy-proofness versus efficiency on restricted domains of exchange economies. Social Choice and Welfare, 14(1), 1996. [Shnayder et al., 2016] Victor Shnayder, Arpit Agarwal, Rafael Frongillo, and David C Parkes. Informed truthfulness in multi-task peer prediction. In EC, 2016. [Stromquist, 2008] Walter Stromquist. Envy-free cake divisions cannot be found by finite protocols. The Electronic Journal of Combinatorics, 15(1), 2008. [Su, 1999] Francis E. Su. Rental harmony: Sperner s lemma in fair division. American Mathematical Monthly, 1999. [Sziklai and Segal-Halevi, 2015] Bal azs Sziklai and Erel Segal-Halevi. Resource-monotonicity and population-monotonicity in cake-cutting. ar Xiv preprint ar Xiv:1510.05229, 2015.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)