# deterministic_strategyproof_and_fair_cake_cutting__016cc28d.pdf

Deterministic, Strategyproof, and Fair Cake Cutting

Vijay Menon and Kate Larson David R. Cheriton School of Computer Science University of Waterloo {vijay.menon, kate.larson}@uwaterloo.ca

We study the classic cake cutting problem from a mechanism design perspective, in particular focusing on deterministic mechanisms that are strategyproof and fair. We begin by looking at mechanisms that are non-wasteful and primarily show that for even the restricted class of piecewise constant valuations there exists no direct-revelation mechanism that is strategyproof and even approximately proportional. Subsequently, we remove the nonwasteful constraint and show another impossibility result stating that there is no strategyproof and approximately proportional direct-revelation mechanism that outputs contiguous allocations, again, for even the restricted class of piecewise constant valuations. In addition to the above results, we also present some negative results when considering an approximate notion of strategyproofness, show a connection between direct-revelation mechanisms and mechanisms in the Robertson-Webb model when agents have piecewise constant valuations, and finally also present a (minor) modification to the well-known Even-Paz algorithm that has better incentive-compatible properties for the cases when there are two or three agents.

1 Introduction Imagine a scenario where there is heterogeneous divisible good that is to be divided among a certain set of n agents. For an appropriately chosen notion of fairness, ideally, we would like this resource to be divided fairly among these n agents and so a natural question that arises is on how one would accomplish this. The cake-cutting problem metaphorically refers to this very scenario and it represents a fundamental problem in the theory of fair division. More formally, in the cake cutting problem, the cake is modelled as the interval [0, 1] and each of the n agents is assumed to have a valuation function over the cake. The goal, as described above, is to partition the cake so that it is fair according to some chosen notion of fairness. Starting with the work of Steinhaus [1948], it has been studied over the last several decades by mathematicians, economists, and political scientists (see e.g. the books by Brams and Taylor [1996] and Robertson

and Webb [1998]), and more recently has attracted the attention of computer scientists (see e.g. the survey by Procaccia [2016]) partly due to the nature of the challenges involved that often require an algorithm design or complexity point of view and partly due to its relevance in the design of multiagent systems [Chevaleyre et al., 2006]. Most work in the cake cutting literature focuses on addressing the above described scenario and so most of it is concerned with computing a fair allocation using proportionality or envy-freeness as the main fairness criterion (see [Aziz and Mackenzie, 2016], and also [Procaccia, 2016] for a recent survey). While addressing it is indeed the core part of the problem, the fact that the valuation functions of the agents may be their private information entails that the designed protocols or mechanisms be strategyproof meaning that there is no incentive to misreport one s valuation function for if otherwise the agents can lie about their valuation functions and potentially benefit from it. Therefore, the focus of this paper, like in [Chen et al., 2010; 2013; Mossel and Tamuz, 2010; Maya and Nisan, 2012; Aziz and Ye, 2014; Brˆanzei and Miltersen, 2015], is to look at mechanisms that are not only fair, but also strategyproof. In this paper, we look at deterministic mechanisms and we are primarily focused on the direct-revelation model one where the agents reveal their entire valuation function. Our main objective is to better understand the limits of determinism when it comes to imposing strategyproofness and fairness (or approximate notions of either of them) i.e., to see what is or is not achievable with deterministic mechanisms and to this end we make the following contributions.

a) In Section 3 we begin by looking at non-wasteful mechanisms and we show a strong impossibility which in turn strengthens an impossibility result given [Aziz and Ye, 2014, Theorem 7]. In particular, we prove (in Theorem 1) that for any n 2 and 0 ϵ1, ϵ2 < 1

n such that 3ϵ1 +ϵ2 < 1

n, there is no deterministic and non-wasteful mechanism for n agents with piecewise constant valuations that is ϵ1-strategyproof and ϵ2-proportional.

b) In Section 4 we remove the non-wasteful constraint and provide three main results. The first one (Theorem 5) shows that for any n 2 and 0 ϵ < 1 n, there is no deterministic mechanism for n agents with piecewise constant valuations that makes contiguous alloca-

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

tions and is strategyproof and ϵ-proportional. The second result (Proposition 6) establishes a connection between direct-revelation mechanisms and mechanisms in the Robertson-Webb model for the case when agents have piecewise constant valuations. And finally, the third one (Theorem 8) is a positive result where we present a (minor) modification to the well-known Even Paz algorithm that has better incentive-compatible properties for the cases when there are two or three agents.

1.1 Related Work

The cake cutting problem has been studied using two input models Robertson-Web model and the direct-revelation model. Therefore, we can classify the work on strategic aspects of cake cutting into two classes based on the input model used and look at each of them separately. Among related papers that operate in the direct-revelation model [Chen et al., 2010; 2013; Mossel and Tamuz, 2010; Maya and Nisan, 2012; Aziz and Ye, 2014; Li et al., 2015; Alijani et al., 2017], the ones which are most relevant to results in this paper are the works of Chen et al. [2010; 2013] and Aziz and Ye [2014]. Chen et al. [2010; 2013] were the first to look at strategyproof cake cutting and their main result was a deterministic, strategyproof, envy-free, proportional, and Pareto-optimal mechanism for the case when the agents have piecewise uniform valuations. Additionally, they also presented randomized algorithms that are truthful in expectation, proportional, and envy free for piecewise linear valuations. The other most relevant work that uses the same model is that of Aziz and Ye [2014]. They present two deterministic mechanisms, CCEA and MEA, for piecewise constant valuations, where CCEA is robust envy-free1and non-wasteful, and MEA is Pareto-optimal and envy-free. Although both of them generalize the mechanism proposed by Chen et al. [2010; 2013], they do not remain strategyproof for piecewise constant valuations. Additionally, they also showed that there is no mechanism that is strategyproof, robust proportional1, and non-wasteful for piecewise constant valuations. Among papers that use the Robertson-Webb model, the two that are most related are the works of Kurokawa et al. [2013] and Brˆanzei and Miltersen [2015]. Kurokawa et al. [2013] studied envy-free cake cutting and their main result was a parameterized protocol for piecewise linear valuations. Additionally, they also showed that there is no mechanism of complexity bounded only by a function of the number of agents and the total number of breakpoints that is strategyproof and envy-free for piecewise constant valuations. The other most relevant paper that operates in the Robertson-Webb model is that of Brˆanzei and Miltersen [2015]. Brˆanzei and Miltersen [2015] showed that any deterministic and strategyproof protocol is a dictatorship when there are only two hungry agents and for the case when there are more than two hungry agents they showed that there is at least one agent who gets an empty piece. Additionally, they

1Robust envy-freeness and robust proportionality are much stronger notions than envy-freeness and proportionality, respectively; see [Aziz and Ye, 2014] for more details.

also provided a randomized mechanism that is strategyproof in expectation and ϵ-proportional for any ϵ > 0. Finally, we also briefly remark on the predefined divisible goods setting which has been extensively studied in fair division (see, for instance, [Cheung, 2016] and the references therein). In the predefined goods setting, the task is to fairly allocate m divisible items among n agents, where the private information of an agent is the value she has for each of the items. So, in effect, the predefined goods setting can be considered as a special case of the setting of cake cutting with piecewise constant valuations i.e., one where the valuation functions of all the agents have the same set of breakpoints and therefore all the negative results in that setting carry over to the cake cutting setting. However, some of the nice positive results with regards to strategyproof mechanisms in this setting (see, e.g., [Cole et al., 2013] and [Cheung, 2016]) do not carry over to the cake cutting setting as here, informally, the difficulty in achieving strategyproofness arises from the fact that a mechanism has to guard against two types of manipulations: i) with regards to the breakpoints in the valuation functions and ii) with regards to the values assigned to the pieces between two consecutive breakpoints.

2 Preliminaries

The cake which is a heterogeneous divisible good is modelled as the unit interval [0, 1]. A piece of cake X is a finite union of disjoint (except at the boundaries of the intervals) subintervals of [0, 1]. An interval is denoted by I and the length of an interval I = [x, y] is given by |I| = y x. In any cake cutting instance, there are n agents who want a share of the cake and we denote them by [n] = {1, , n}. Each agent i [n] has a non-negative, integrable, and private value density function (also referred to as their utility/valuation function), vi : [0, 1] R+ {0}, that indicates how agent i values different parts of the cake, and given a piece of cake X, the value for X is defined by Vi(X) = R

X vi(x) dx = P I X R

x I vi(x) dx. (Note that the fact that the valuation functions are integrable implies additivity meaning for two disjoint intervals I and I , Vi(I I ) = Vi(I)+Vi(I ).) Without loss of generality, we assume that the valuation functions are normalized, i.e., Vi([0, 1]) = 1 for all i [n]. Additionally, we say that agent i is hungry if vi(x) > 0 for all x [0, 1].

2.1 Input Models

The way we have defined the valuation functions above, it is not necessary that they have a discrete representation. Therefore, most of the work in cake cutting assumes a query model commonly known as the Robertson-Webb query model that allows only the following two types of queries.

1. Eval query: given an interval [x, y], eval(i, x, y) asks agent i for its value for [x, y], i.e., eval(i, x, y) = Vi(x, y).

2. Cut query: given a point x and r [0, 1], cut(i, x, r) asks agent i for the minimum (i.e., the leftmost) point y such that Vi(x, y) = r.

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

While the Robertson-Webb model is the most widely studied, there is recent work (e.g., [Chen et al., 2010; 2013], [Bei et al., 2012], [Aziz and Ye, 2014]) which restricts the agents valuation functions to ones that have a concise representation, thus in turn giving rise to another model (referred to as the direct-revelation model) where the entire valuation functions of the agents are given as input to a mechanism. In this paper, we consider one fundamental class of restricted valuations, namely, piecewise constant valuations. An agent i is said to have a piecewise constant valuation if [0, 1] can be partitioned into a finite number of intervals such that vi is a constant over each interval (i.e., it is a step function). A special case of piecewise constant valuations are the piecewise uniform valuations where, for some constant c, the function can only take the values 0 or c. One of the reasons why piecewise constant valuations are interesting is because they are expressive enough to be able to approximate any general valuation function. In this paper, we make use of both input models. All our negative (impossibility) results are in the direct-revelation model, while the algorithm we present is in the Robertson Webb model. Note that the existence of a mechanism in the Robertson-Webb model implies an existence in the directrevelation model, but the converse is not necessarily true, and hence our negative results, in particular, are strong. Also, all our negative results are true for even the restricted class of piecewise constant valuations and hence naturally carry over to anything more general (like piecewise linear valuations).

2.2 Properties of Cake Cutting Mechanisms A direct-revelation cake cutting mechanism M takes the valuation functions (v1, , vn) of the agents (which we refer to as a profile) as input and it outputs an allocation A = (A1, , An), where Ai is the allocation to agent i, and i, j( = i), Ai and Aj are disjoint (except at the boundaries of the intervals). While in general Ai can be any arbitrary piece of cake, sometimes we concern ourselves only with contiguous allocations where each Ai is a single interval. Throughout, we assume that the mechanism allocates (to some agent) all the pieces of cake that are valued at greater than zero by at least one of the agents. Additionally, we often use Mi(vi, v i) to denote Ai, where v i denotes the valuation functions of all the agents except i. A mechanism is said to be non-wasteful if it allocates every piece that is desired meaning that the piece is assigned a value greater than zero by at least one agent to an agent who desires it. More formally, if I is a subinterval of [0, 1] and D(I) = {i [n] | Vi(I) > 0}, then a mechanism is non-wasteful if it always makes an allocation A such that I, I i D(I)Ai. In this paper, we consider both nonwasteful and wasteful mechanisms. Additionally, for all our negative results we assume free disposal, meaning that the mechanism can throw away pieces of cake that aren t valued (at greater than zero) by any of the agents without incurring a cost. Note that the existence of a mechanism without the free disposal assumption implies the existence of a mechanism with the free disposal assumption, but the converse is not necessarily true. Hence, in the context of negative results, such an assumption only makes them stronger.

In this paper, we use (approximate) proportionality as our main fairness criterion. In the definition below, proportionality refers to the special case when ϵ = 0.

Definition 1 (ϵ-proportionality). For any ϵ 0, 1

n , a mechanism M is said to be ϵ-proportional if it always returns an allocation (A1, , An) such that i [n], Vi(Ai) 1

Along with (approximate) proportionality, the other major property we are concerned with is (approximate) strategyproofness. Informally, for any ϵ [0, 1], a cake cutting mechanism M is said to be ϵ-strategyproof if an agent can gain a utility of at most ϵ by misreporting her valuation function. More formally, we have the following definition.

Definition 2 (ϵ-strategyproofness). For any ϵ [0, 1], a mechanism M is said to be ϵ-strategyproof if for every agent i [n], and for all v i, v i, Vi(Mi(vi, v i)) Vi(Mi(v i, v i)) ϵ.

Strategyproofness refers to the special case in the above definition when ϵ = 0. In addition to the above mentioned properties, we also talk about (approximate) envy-freeness and Pareto-efficiency. For an ϵ [0, 1], a cake cutting mechanism is said to be ϵ-envy-free if it always returns an allocation (A1, , An) such that i, j [n], Vi(Ai) Vi(Aj) ϵ. Envy-freeness refers to the special case in the above definition when ϵ = 0. A cake cutting mechanism is said to be Pareto-efficient if it always returns an allocation (A1, , An) that is not Pareto-dominated meaning that there is no other allocation (A 1, , A n) such that i [n], Vi(A i) Vi(Ai), with the inequality being strict for at least one agent. Note that nonwastefulness, as defined above, can be considered as a weak form of efficiency where all it is doing is restricting a mechanism from allocating a piece of zero value to an agent if there is some other agent who has a non-zero value for it.

3 Non-wasteful Mechanisms

Chen et al. [2010; 2013] were the first to consider directrevelation mechanisms for cake cutting and they proposed a polynomial-time deterministic mechanism that is strategyproof, proportional, envy-free, and Pareto-efficient for piecewise uniform valuations. In light of such a result, one natural question that arises is if there exists a mechanism for at least the more general class of piecewise constant valuations that is strategyproof, Pareto-efficient, and fair (for some notion of fairness). We already have an answer to this question due to Schummer [1996] who considered the predefined divisible goods setting and showed that the only mechanism that is strategyproof and Pareto-efficient is a dictatorship. And since this predefined goods setting is a special case of the setting with piecewise constant valuations, we know that there is no hope for achieving strategyproofness, Paretoefficiency, and any notion of fairness. Therefore, in this context, another notion to consider is non-wastefulness which, as defined in Section 2, is a weaker notion of efficiency. In fact, Aziz and Ye [2014] considered this notion and showed an impossibility result saying that there is no strategyproof, robust proportional (which is a much stronger notion of proportionality; see [Aziz and Ye, 2014]), and non-wasteful mechanism

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

[Aziz and Ye, 2014, Theorem 7]. Below, we show a stronger impossibility which says that there is no deterministic and non-wasteful mechanism that is even ϵ1-strategyproof and ϵ2proportional for ϵ1, ϵ2 such that 0 3ϵ1 + ϵ2 < 1

Theorem 1. For any n 2 and 0 ϵ1, ϵ2 < 1 n such that 3ϵ1 + ϵ2 < 1 n, there is no deterministic and non-wasteful mechanism for n agents with piecewise constant valuations that is ϵ1-strategyproof and ϵ2-proportional.

Proof. Let us assume that there exists a deterministic, ϵ1strategyproof, ϵ2-proportional, and non-wasteful mechanism M for n agents. First, consider the profile (u, u, y, , y), where

( n 2 x [0, 2

n, 1] y(x) =

( 0 x [0, 2

n n 2 x ( 2

Let M make an allocation A1, A2 to agent 1 and agent 2, respectively. Without loss of generality, we can assume that |A1| |A2|. Now, since M is non-wasteful, |A1| + |A2| = 2 n, and so this implies that |A1| 1

n. Next, let us consider the profile (v, u, y, , y), where v(x) = 1 |A1| when x A1 and 0 otherwise. Since M is non-wasteful and ϵ1-strategyproof, agent 1 has to get a utility of at least 1 ϵ1 from the allocation in this profile, because if it allocates anything less, then agent 1 will deviate to Profile 1. Therefore, if M allocates A 1 and A 2 to agent 1 and 2, respectively, then (1 ϵ1) |A1| |A 1| and so |A 2| |A2| + ϵ1 |A1|. Finally, consider the profile (v, w, y, , y), where

1 δ |A1| x A1

δ |A2| x A2 0 otherwise

Now, here, since M is non-wasteful and because agent 1 does not desire any part of A2, agent 2 gets at least A2. However, agent 2 has a total utility of only δ for A2, and since we assumed that M is also ϵ2-proportional, it has to get a piece of length, say, ℓ, of A1, where

δ + ℓ |A1|(1 δ) 1

n ϵ2 = ℓ |A1| ( 1

If M allocates A 1 and A 2 to agent 1 and 2, respectively, in this profile, then |A 2| |A2| + ℓ |A2| + |A1| ( 1

(1 δ) . Also, from the profile (v, u, y, , y) we know that |A 2| |A2| + ϵ1 |A1|. Therefore, if n

2 |A2| + |A1| ( 1

n 2 (|A2| + ϵ1 |A1|) + ϵ1, then agent 2 can deviate from (v, u, y, , y) to (v, w, y, , y) and as a result gain strictly more than ϵ1. So, considering this inequality, we have,

|A2| + |A1| ( 1

2 (|A2| + ϵ1|A1|) + ϵ1

nϵ1 (as |A1| 1

δ < 1 n(3ϵ1 + ϵ2)

This in turn implies that for every 0 ϵ1, ϵ2 < 1

n such that 3ϵ1 + ϵ2 < 1 n, we can always find a 0 < δ < 1 n(3ϵ1+ϵ2)

n(1 3ϵ1) to fit in the definition of the function w(x) such that the inequality and hence our theorem will be true.

With respect to the above theorem, we highlight the following corollaries which are basically special cases when ϵ1 and ϵ2 are zero, respectively. The first one rules out the possibility of guaranteeing some value (however small) to all the agents if the mechanism has to be non-wasteful and strategyproof. The second one, on the other hand, provides a lower bound for the natural question on whether we can come up with mechanisms that can guarantee proportionality and nonwastefulness and at the same time allow only a maximum gain of ϵ, where 0 ϵ < (1 1

n), from misreporting. Unfortunately, we do not have an accompanying upper bound result for this and so the question of an upper bound remains open.

Corollary 2. For any n 2 and 0 ϵ < 1

n, there is no deterministic, strategyproof, ϵ-proportional, and non-wasteful mechanism for n agents with piecewise constant valuations.

Corollary 3. For any n 2 and 0 ϵ < 1 3n, there is no deterministic, ϵ-strategyproof, proportional, and non-wasteful mechanism for n agents with piecewise constant valuations.

4 Removing Non-wastefulness

While non-wastefulness is certainly a desirable property, it seems like the negative results in the previous section were largely driven by this constraint as it severely restricts the kind of allocations that a mechanism can make. So, what if we remove this constraint? Do similar impossibilities still hold, or are there mechanisms that satisfy some of those properties? These are the questions we try to answer here. Chen et al. [2010; 2013] provided a deterministic and strategyproof mechanism for piecewise uniform valuations and one of the main open questions they had posed was on generalizing their mechanism for piecewise constant valuations. Subsequently, Aziz and Ye [2014] and Brˆanzei and Miltersen [2015] had posed the same question regarding the existence of mechanisms that are strategyproof and proportional for piecewise constant valuations. Here we address a special case of this question when the mechanism makes contiguous allocations and show that there exists no deterministic direct-revelation mechanism that is strategyproof and ϵproportional, for any 0 ϵ < 1

n. Additionally, we also prove a stronger result (Proposition 4) for the case of two agents. Informally, at a high-level, the proofs of both of these results follow the same theme as in the proof of Theorem 1 where we construct valuation profiles with an aim of arriving at a contradiction. However, unlike in Theorem 1, we now no longer have the non-wasteful constraint, and so this requires some additional arguments which use the fact that the allocations are contiguous. Due to space constraints, the proofs of both of the statements below have been deferred to the full version [Menon and Larson, 2017].

Proposition 4. For any 0 ϵ1, ϵ2 < 1 2 such that ϵ1 + ϵ2 < 1 2, there exists no deterministic mechanism for two hungry agents with piecewise constant valuations that

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

makes contiguous allocations and is ϵ1-strategyproof and ϵ2proportional.

As an aside, note that the ϵ2 = 0 case in Proposition 4 essentially says that if we insist on contiguous and proportional allocations, then one cannot provide any guarantee on strategyproofness (i.e., such mechanisms cannot be ϵ-strategyproof for any feasible ϵ). Later on, in Theorem 8, we show how one can circumvent this and obtain a 1

4-strategyproof and proportional mechanism for two agents by giving each of them at most two contiguous pieces.

Theorem 5. For any n 2 and 0 ϵ < 1

n, there is no deterministic mechanism for n agents with piecewise constant valuations that makes contiguous allocations and is strategyproof and ϵ-proportional.

Given Theorem 5, the first natural question that arises is if we can extend it to the case when the mechanism can make arbitrary allocations. Unfortunately, we do not have an answer to this question. Instead, below, we show a connection between direct-revelation mechanisms and mechanisms in the Robertson-Webb model for the case when agents have piecewise constant valuations. We believe that it will be useful in either of the cases i.e., if the answer to the above question is either in the positive or if we want to prove that such a mechanism does not exist. In the case that such a mechanism exists, the connection basically shows that when given an upper bound on the maximum number of breakpoints in any agent s valuation function, one can construct a mechanism in the Robertson-Webb model that approximately achieves both of the properties. And in the case that one wants to prove that such a mechanism does not exist, one can use this connection to prove a non-existence (of mechanisms that are ϵ-strategyproof and ϵ-proportional for some ϵ > 0) in the Robertson-Webb model and then map it back to show that there is no (finite) direct-revelation mechanism that is strategyproof and proportional.

Proposition 6. Let P1, P2, P3 denote the property of strategyproofness, proportionality, and envy-freeness, respectively, and let P {P1, P2, P3}. Given k, an upper bound on the maximum number of breakpoints in any agent s valuation function, and any n 2, if there exists a (finite) deterministic direct-revelation mechanism for n agents with piecewise constant valuations that satisfies Pi, Pi P, then, for any ϵ > 0, there exists a mechanism in the Robertson-Webb model for n agents with piecewise constant valuations that asks at most (n 2k

ϵ ) queries on each input and is ϵ-Pi, Pi P.

Proof (sketch). Since in the Robertson-Webb model we only have query access to the valuation functions, the first step is to basically learn these functions to a sufficiently good approximation using only eval and cut queries. Subsequently, once we have that, we can essentially feed these functions to the direct-revelation mechanism in order to create a mechanism in the Robertson-Webb model that achieves an approximate version of all the properties. For the first step, the key observation is following claim.

Claim 1. Given an ϵ > 0, we can use 2k

ϵ cut queries to ϵ-approximate any piecewise constant function v(x) that has

Input: An agent i s piecewise constant valuation function vi(x), ϵ > 0, and k Output: A piecewise constant function wi(x) that ϵapproximates vi(x) 1: N 2k

ϵ , x0 0, x N+1 1 2: for j {1, , N} do 3: xj cut i, xj 1, ϵ

2k , cj ϵ 2k (xj xj 1) 4: wi(x) = cj, x [xj 1, xj] 5: end for 6: if XN = 1 then

7: wi(x) = (1 ϵ

2k N) x N+1 x N , x [x N, x N+1] 8: end if 9: return wi(x)

Algorithm 1: ϵ-approximation of a piecewise constant function using 2k

ϵ cut queries.

at most k breakpoints by another piecewise constant function w(x) such that W([0, 1]) = 1 and for any piece of cake X, Z

X v(x) dx ϵ

X w(x) dx Z

X v(x) dx + ϵ

Proof (sketch). Algorithm 1 describes how to convert v(x) to w(x) by using 2k

ϵ cut queries. It is easy to see that W([0, 1]) = 1. To prove that for any piece of cake X, R

X v(x) dx ϵ

X w(x) dx R

X v(x) dx + ϵ

2, consider some arbitrary X. If we denote the breakpoints of v by {b1, , bk} (since there are only a maximum of k breakpoints), where 0 = b0 < b1 < < bk+1 = 1, and if we let Ci = X [xi 1, xi], then we know that R

X w(x) dx = PN+1 i=1 R

Ci w(x) dx. Additionally, also note that if [xi 1, xi] does not contain any breakpoint bj of the original function v(x), then R

Ci w(x) dx = R

Ci v(x) dx since we know that v(x) is constant over this interval (as there are no breakpoints) and so v(x) = ϵ 2k (xi xi 1) = w(x), x [xi 1, xi]. This, along with the fact that v(x) has at most k breakpoints, implies that there are at most k Ci s for which R

Ci w(x) dx = R

Ci v(x) dx. Now, if we assume without loss of generality that these are C1 , Ck, then using the fact that R

Ci w(x) dx ϵ 2k and R

Ci v(x) dx ϵ 2k we have that for every i {1, , k},

Ci w(x) dx Z

Ci v(x) dx ϵ

Now, since R

X[w(x) v(x)] dx = Pk i=1( R

Ci[w(x) v(x)] dx), we can now use equation 2 to prove our claim.

Given the above claim, we can now build a mechanism MRW in the Robertson-Webb model in the following way, where (v1, , vn) are the original valuation functions and (w1, , wn) are the corresponding ϵ-approximated functions. i [n], MRW i (v1, , vn) = Mi(w1, , wn). (3)

It is clear that MRW makes at most (n 2k

ϵ ) queries on each input. To prove that MRW is ϵ-Pi for all Pi P satisfied by M, let us consider each of the properties separately.

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

i) When M satisfies P1 (strategyproofness). Since M is strategyproof, the only way for an agent i with a valuation function vi to manipulate MRW is to pretend as if its function is some v i and answer the queries accordingly. This in turn will result in w i being the ϵ-approximated function instead of wi if it reported truthfully. However, we know that w i, w i, Wi(Mi(wi, w i)) Wi(Mi(w i, w i)). This in turn implies that using equation 1 we have,

Vi(Mi(wi, w i)) + ϵ

2 Wi(Mi(wi, w i))

Wi(Mi(w i, w i)) Vi(Mi(w i, w i)) ϵ

And so, now, using equation 3, we have that for all v i, v i, Vi(MRW i (v i, v i)) Vi(MRW i (vi, v i)) ϵ. The other two cases can be proved similarly and we defer the complete proof to the full version.

Although, as mentioned above, it remains open as to whether a strategyproof and proportional mechanism exists, another goal one could still consider is on finding better proportional mechanisms (in terms of ϵ-strategyproofness). Below, we begin the pursuit of this goal and as our final question in this paper ask if there are positive results at least regarding mechanisms that are proportional and ϵ-strategyproof for some ϵ < (1 1

n). We answer it with a Yes and in particular we first prove by showing a bound on the maximum gain an agent can get by misreporting that the well-known Even-Paz algorithm [Even and Paz, 1984] satisfies the above criterion for the case when there are at least four agents. And following this, we present a minor modification to the same that has better incentive compatible properties than the original Even-Paz algorithm for the cases when there are two or three agents. Due to space constraints, proofs of Proposition 7 and Theorem 8 have been deferred to the full version. Proposition 7. For n 2 agents, the Even-Paz algorithm is deterministic, proportional, and ϵ-strategyproof, where

1 2 when n = 2 or n = 4

2 3 when n = 3 or n = 5 1 2

n when n 6. Next, we show that the bounds on ϵ can be improved for the cases when there are two or three agents. In particular, we show that Algorithm 2 is proportional and ϵ-strategyproof, where ϵ = (1 3 2n) or ϵ = (1 3 2n + 1 2n2 ) depending on whether n is even or odd, respectively. And so, for the cases when there are two or three agents, the gain is 1

9, respectively, as opposed to 1

3 in the Even-Paz algorithm. Theorem 8. Algorithm 2 is deterministic, proportional, and ϵ-strategyproof, where

( 1 3 2n when n is even 1 3 2n + 1 2n2 when n is odd.

5 Discussion One of the main open questions raised by Chen et al. [2010; 2013] (and also by Aziz and Ye [2014] and Brˆanzei and Miltersen [2015]) was on the existence of deterministic mechanisms that are strategyproof and fair for piecewise constant

Procedure: modified EP([a, b], S) Input: ([a, b], S), where [a, b] [0, 1] is the cake to be proportionally allocated among k = |S| agents 1: If k == 1, then return ([a, b]) 2: for each i S do

3: ci = cut i, a, k

2 k Vi(a, b)

4: end for 5: Let {d1, , dk} be the sorted order of the ci s, SL {i S | ci d k

2 }, and SR S \ SL.

6: Proportionally allocate the cake h d k

among the k agents using the Even-Paz algorithm.

7: Recursively call modified EP on h a, d k

i and h d k

2 +1, b i with SL and SR, respectively. Return the allocations so formed along with the proportional allocation of the piece h d k

2 +1 i . Main:

8: output modified EP([0, 1], S = {1, , n}).

Algorithm 2: Modified Even-Paz algorithm.

valuations. Here we addressed a special case of this and we showed (in Theorem 5) that for any n 2 agents there is no deterministic mechanism that makes contiguous allocations and is strategyproof and even ϵ-proportional. Although the contiguous allocations constraint captures some interesting scenarios, we believe that answering the above question without this (rather strong) constraint is important. In particular, when given the fact that there exists randomized mechanisms that are a) truthful in expectation, proportional, and envyfree for piecewise linear valuations in the direct-revelation model [Chen et al., 2013] and b) truthful in expectation and ϵproportional in the Robertson-Webb model [Brˆanzei and Miltersen, 2015], we believe that resolving this question can give us a clearer picture regarding the limits of determinism. Moving away from the above result, in Section 4 we showed (in Theorem 8) that there exists a proportional mechanism that has better incentive-compatible properties than the Even-Paz algorithm for the cases when there are two or three agents. With regards to this result, one of the main questions that arise is the following and we suggest it as an open problem: for n 2 agents, what is the minimum achievable ϵ for which there exists a deterministic mechanism that is proportional and ϵ-strategyproof? It is unclear how we can provide a lower bound, or improve the proposed mechanism to get smaller values of ϵ. And also, at the same time there is the question of whether we can make Algorithm 2 nonwasteful when agents have concisely representable valuation functions. Therefore, given our lower bound (Theorem 1) in Section 3, another problem that remains open is whether we can guarantee non-wastefulness along with proportionality and ϵ-strategyproofness, where 1 3n ϵ < (1 1

Acknowledgments

We thank Simina Brˆanzei for useful discussions.

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

[Alijani et al., 2017] Reza Alijani, Majid Farhadi, Mohammad Ghodsi, Masoud Seddighin, and Ahmad S Tajik. Envy-free mechanisms with minimum number of cuts. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 312 318, 2017.

[Aziz and Mackenzie, 2016] Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for any number of agents. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 416 427, 2016.

[Aziz and Ye, 2014] Haris Aziz and Chun Ye. Cake cutting algorithms for piecewise constant and piecewise uniform valuations. In Proceedings of the 10th International Conference on Web and Internet Economics (WINE), pages 1 14. Springer, 2014.

[Bei et al., 2012] Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, and Endong Yang. Optimal proportional cake cutting with connected pieces. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI), pages 1263 1269, 2012.

[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. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 482 488, 2015.

[Chen et al., 2010] Yiling Chen, John K Lai, David Parkes, and Ariel D Procaccia. Truth, justice, and cake cutting. In Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI), pages 626 631, 2010.

[Chen et al., 2013] Yiling Chen, John K Lai, David C Parkes, and Ariel D Procaccia. Truth, justice, and cake cutting. Games and Economic Behavior, 77(1):284 297, 2013.

[Cheung, 2016] Yun Kuen Cheung. Better strategyproof mechanisms without payments or prior - an analytic approach. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pages 194 200, 2016.

[Chevaleyre et al., 2006] Yann Chevaleyre, Paul E Dunne, Ulle Endriss, J erˆome Lang, Michel Lemaitre, Nicolas Maudet, Julian Padget, Steve Phelps, Juan A Rodriguez Aguilar, and Paulo Sousa. Issues in multiagent resource allocation. Informatica, 30(1):3 31, 2006.

[Cole et al., 2013] Richard Cole, Vasilis Gkatzelis, and Gagan Goel. Mechanism design for fair division: allocating divisible items without payments. In ACM Conference on Electronic Commerce (EC), pages 251 268, 2013.

[Even and Paz, 1984] Shimon Even and Azaria Paz. A note on cake cutting. Discrete Applied Mathematics, 7(3):285 296, 1984.

[Kurokawa et al., 2013] David Kurokawa, John K Lai, and Ariel D Procaccia. How to cut a cake before the party ends. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI), pages 555 561, 2013. [Li et al., 2015] Minming Li, Jialin Zhang, and Qiang Zhang. Truthful cake cutting mechanisms with externalities: Do not make them care for others too much. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 589 595, 2015. [Maya and Nisan, 2012] Avishay Maya and Noam Nisan. Incentive compatible two player cake cutting. In Proceedings of the 8th Workshop on Internet and Network Economics (WINE), pages 170 183. Springer, 2012. [Menon and Larson, 2017] Vijay Menon and Kate Larson. Deterministic, strategyproof, and fair cake cutting. ar Xiv preprint, abs/1705.06306, 2017. [Mossel and Tamuz, 2010] Elchanan Mossel and Omer Tamuz. Truthful fair division. In International Symposium on Algorithmic Game Theory (SAGT), pages 288 299. Springer, 2010. [Procaccia, 2016] Ariel D Procaccia. Cake cutting algorithms. In Vincent Conitzer, Ulle Endriss, Jerome Lang, and Ariel D Procaccia, editors, Handbook of Computational Social Choice, chapter 13. Cambridge University Press, 2016. [Robertson and Webb, 1998] Jack Robertson and William Webb. Cake-Cutting Algorithms: Be Fair If You Can. A.K. Peters., 1998. [Schummer, 1996] James Schummer. Strategy-proofness versus efficiency on restricted domains of exchange economies. Social Choice and Welfare, 14(1):47 56, 1996. [Steinhaus, 1948] Hugo Steinhaus. The problem of fair division. Econometrica, 16(1):101 104, 1948.

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