# truthful_cake_sharing__6d5c40c3.pdf

Truthful Cake Sharing

Xiaohui Bei,1 Xinhang Lu,2 Warut Suksompong3

1 School of Physical and Mathematical Sciences, Nanyang Technological University 2 School of Computer Science and Engineering, University of New South Wales 3 School of Computing, National University of Singapore

The classic cake cutting problem concerns the fair allocation of a heterogeneous resource among interested agents. In this paper, we study a public goods variant of the problem, where instead of competing with one another for the cake, the agents all share the same subset of the cake which must be chosen subject to a length constraint. We focus on the design of truthful and fair mechanisms in the presence of strategic agents who have piecewise uniform utilities over the cake. On the one hand, we show that the leximin solution is truthful and moreover maximizes an egalitarian welfare measure among all truthful and position oblivious mechanisms. On the other hand, we demonstrate that the maximum Nash welfare solution is truthful for two agents but not in general. Our results assume that mechanisms can block each agent from accessing parts that the agent does not claim to desire; we provide an impossibility result when blocking is not allowed.

1 Introduction A fundamental problem in social choice theory is the fair allocation of scarce resources among multiple agents. When the resource is heterogeneous and divisible, this problem is commonly known as cake cutting, with the cake serving as a metaphor for the heterogeneous resource. Cake cutting has been extensively studied for over half a century in mathematics and economics, and more recently in computer science (Brams and Taylor 1996; Robertson and Webb 1998; Procaccia 2016). In this paper, we consider a variant of the classic cake cutting problem where instead of competing with one another for the cake, the agents all share the same subset of the cake, which must be chosen subject to a length constraint. We refer to this setting as cake sharing. The cake sharing problem captures many real-world scenarios, such as when a group of agents need to decide the time periods for which they should reserve a sports facility or a conference room for collective use given their limited budget, or when a group of users seek to agree upon the files to store in a shared cache memory. Our goal is to design cake sharing mechanisms that are both truthful and fair. Truthfulness requires that it should be in every agent s best interest to report her true underlying preferences to the mechanism. A truthful mechanism makes

Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

it easy for agents to participate in, as they do not have to act strategically and reason about beneficial manipulations; it also simplifies the job of the mechanism designer when reasoning about the possible behavior of the agents. Note that truthfulness by itself is easy to obtain, for example by ignoring the agents reports completely and allocating a prespecified subset of the cake. However, this is a patently unfair mechanism, as it leaves any agent who has no value for that subset empty-handed. Is there a mechanism that is truthful and at the same time satisfies a certain degree of fairness for all agents? Two mechanisms that have been used in various resource allocation settings and often shown to exhibit attractive fairness properties are the maximum Nash welfare (MNW) solution and the leximin solution. The MNW solution chooses an allocation that maximizes the product of the agents utilities among all feasible allocations. The leximin solution considers all feasible allocations that maximize the minimum among the agents utilities; among all such allocations, it considers those maximizing the second smallest utility, and so on. Due to their optimization nature, both solutions fulfill an important economic efficiency criterion of Pareto optimality: there is no other feasible outcome that makes some agent better off and no agent worse off compared to the chosen outcome. Indeed, any such improved outcome would also be an improvement with respect to the corresponding optimization objective. Given the broad appeal of the two mechanisms, are they appropriate choices for our cake sharing setting, especially from the truthfulness perspective?

1.1 Our Results

As is standard in the cake cutting literature, we model the cake as an interval [0, 1]; for a given parameter α [0, 1], a subset of length at most α of the cake can be collectively allocated to the agents. We assume that the agents have piecewise uniform utilities, meaning that each agent has a desired subset of the cake which she values uniformly. Except in Section 6, we also assume that once a mechanism chooses a subset of the cake, it can block each agent from accessing certain parts of the cake, usually those that the agent does not desire according to her report. We remark here that blocking can be easily implemented in the aforementioned applications of cake sharing, for example by disallowing agents from accessing part of the cache memory that they do not de-

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

mand or restricting their access to the sports facility during the times that they claim to be unavailable. In Section 3, we focus on the leximin solution. Our main technical result establishes the truthfulness of the solution for any number of agents with arbitrary piecewise uniform utilities. At a high level, our proof proceeds by showing that the leximin solution is immune to certain types of manipulations, and then arguing that this immunity is sufficient to protect the solution against all possible manipulations. Along the way, we introduce the notion of an ε-change a tiny change from one utility vector or allocation towards another which may be useful in related settings. Additionally, we show that each agent receives the same utility in all leximin allocations (which means that tie-breaking is inconsequential) and that such an allocation can be computed in polynomial time. Since truthfulness by itself can be trivially obtained as we explained earlier, we consider in Section 4 the fairness of mechanisms. We adapt the well-known notion of proportionality from cake cutting and measure fairness using the egalitarian ratio, which is defined as the worst-case egalitarian welfare that the mechanism provides over all instances, where we normalize the agents utilities for the entire cake when computing their egalitarian welfare. We show that for any α and number of agents n, the leximin solution has egalitarian ratio exactly α/(n (n 1)α). Moreover, we prove that this ratio is already optimal among all mechanisms that are truthful and position oblivious (see Definition 4.5). Our results in Sections 3 and 4 establish the leximin solution as an attractive mechanism in the setting of cake sharing. In Section 5, we turn our attention to the MNW solution. We show that the solution is equivalent to the leximin solution in the case of two agents, and is therefore truthful in that case. In general, however, a result of Aziz, Bogomolnaia, and Moulin (2020, Theorem 3) implies the non-truthfulness of the MNW solution in our setting. We strengthen their result by showing that MNW is not truthful even when an agent is only allowed to report a subset of her true desired piece.1 Moreover, in contrast to Aziz et al. s example, the symmetry structure in our example allows us to provide a relatively short proof of the non-truthfulness that can be easily verified by hand. Finally, we demonstrate in Section 6 that the ability to block is crucial for the truthfulness of mechanisms. In particular, we show that no truthful, Pareto optimal, and position oblivious mechanism can achieve a positive egalitarian ratio when blocking is not allowed.

1.2 Related Work

While the model of cake sharing is new to the best of our knowledge, the selection of a collective subset from a given set subject to a size or budget constraint has been studied in several lines of work. In multiwinner voting, the goal is to choose a certain number of candidates to form a committee,

1We remark that subset manipulation is a highly restricted form of manipulation. Indeed, Peters (2018) noted that reporting a subset is a particularly simple fashion of manipulating, and used subset manipulation as the official notion of truthfulness.

where criteria can include excellence and diversity see the survey by Faliszewski et al. (2017). In that setting, Peters (2018) proved that no rule can simultaneously satisfy a form of fairness and a form of truthfulness when agents have approval preferences (analogous to piecewise uniform utilities in our setting). A key difference between multiwinner voting and cake sharing is that the candidates in the former are discrete and cannot be divided into arbitrarily small pieces. Variants where discrete items instead of candidates are selected have also been considered (Skowron, Faliszewski, and Lang 2016; Manurangsi and Suksompong 2019). A long list of recent papers have addressed the problem of participatory budgeting, where the citizens decide how a public budget should be spent on possible projects in their community see the survey by Aziz and Shah (2021). Some models assume that projects are discrete (each project can either be fully completed or not at all), while others assume that they are divisible (partial completion of a project yields some utility to the citizens). In either case, there is a prespecified set of projects and the preference of an agent within a project is uniform, so participatory budgeting cannot capture our cake sharing model where there is no predetermined division of the cake into homogeneous units. Aziz, Bogomolnaia, and Moulin (2020) studied a probabilistic voting setting in which agents have dichotomous preferences over m alternatives and the goal is to output a probability distribution over the alternatives. Their model corresponds to a special case of our model where for each j = 1, . . . , m, the interval [(j 1)/m, j/m] represents alternative j, and α = 1/m; in this special case, agents are not allowed to have breakpoints that are not multiples of 1/m in their utility functions (see the precise definition of a breakpoint in Section 2). Like us, Aziz et al. showed that the leximin solution is truthful.2 Our results on the leximin solution generalize and strengthen theirs in three important ways. First, we allow agents to report arbitrary breakpoints this considerably enlarges the strategy space of the agents and introduces an aspect that cannot be captured by their model. Second, our model allows an arbitrary value of α instead of only α = 1/m. Third, we establish a tight bound on the egalitarian ratio and show that the leximin solution achieves this bound. Therefore, we believe that overall, our results make a significantly stronger case in favor of the leximin solution. Friedman et al. (2019) investigated a model in which agents share a cache memory unit, focusing on truthfulness and fairness like we do. In their model, each agent has a private file that no other agent is interested in, and there is a large public file that may be of interest to multiple agents. The challenge of the mechanism is to elicit the true ratio between each agent s utility for the public file and that for her private file. These authors demonstrated that the ability to block can also help mechanisms achieve better guarantees in their setting, in particular by preventing free riding . Truthfulness in cake cutting has been considered in several papers (Maya and Nisan 2012; Chen et al. 2013; Kurokawa, Lai, and Procaccia 2013; Aziz and Ye 2014;

2They called the notion excludable strategyproofness, which is equivalent to truthfulness with blocking in our setting.

Brˆanzei and Miltersen 2015; Bei et al. 2017; Menon and Larson 2017; Bei, Huzhang, and Suksompong 2020; Tao 2021). Like our paper, a number of these papers also address the case of piecewise uniform utilities. Two important fairness properties in cake cutting are envy-freeness and proportionality. Note that envy-freeness is always fulfilled in our setting (as long as the mechanism does not block any agent s valued cake), since all agents share the same subset of the cake. On the other hand, proportionality has a similar flavor as our egalitarian ratio notion, where we want to guarantee a certain level of utility for every agent. Finally, both the leximin and MNW solutions have been examined in a variety of settings and often shown to exhibit desirable properties (Bogomolnaia and Moulin 2004; Kurokawa, Procaccia, and Shah 2018; Caragiannis et al. 2019; Segal-Halevi and Sziklai 2019; Aziz, Bogomolnaia, and Moulin 2020; Halpern et al. 2020; Plaut and Roughgarden 2020; Brandl et al. 2022).

2 Preliminaries Our setting includes a set of agents denoted by N = {1, 2, . . . , n} and a heterogeneous divisible good (or cake) represented by the normalized interval [0, 1]. A piece of cake is a union of finitely many disjoint (closed) intervals. Denote by ℓ(I) the length of an interval I, that is, ℓ([a, b]) = b a. For a piece of cake S consisting of a set of intervals IS, we denote ℓ(S) = P I IS ℓ(I). Each agent i N is endowed with a density function fi : [0, 1] R 0, which captures how the agent values different parts of the cake. We assume that the agents have piecewise uniform utilities: for each agent i, each part of the cake is either desired or undesired, and the density function fi takes on the value 1 for all desired parts and 0 for all undesired parts. Let Wi [0, 1] denote the (not necessarily contiguous) piece of cake on which fi = 1. The utility of agent i for any piece of cake S is given by ui(S) := ℓ(S Wi).3 We assume that ℓ(Wi) > 0 for every i, since we can simply ignore an agent i with ℓ(Wi) = 0. Let α [0, 1] be a given parameter. We refer to a setting with agents, their density functions, and the parameter α as an instance. A mechanism M(R) chooses from any given instance R a piece of cake A with ℓ(A) α. However, this does not mean all agents have full access to A, because we allow the mechanism to block each agent from accessing certain parts of the selected piece. Specifically, after choosing A, the mechanism assigns piece Ai A to agent i; we call A = (A, A1, . . . , An) an allocation. The utility of agent i from the allocation A is ui(Ai). Since the cases α = 0 and α = 1 are trivial, we assume from now on that α (0, 1). Given an instance, every point that is a left or right endpoint of an interval in Wi for at least one i is called a breakpoint; the points 0 and 1 are also considered to be breakpoints. Observe that for any instance, the agents utilities for a piece of cake S depend only on the amounts of cake between consecutive pairs of breakpoints included in S. We now define the central property of our paper.

3Some cake cutting papers normalize the utility functions so that ui([0, 1]) = 1 for all i N; we do not follow this convention. See also the end of Section 3 for a discussion of normalization.

Definition 2.1 (Truthfulness). A mechanism is truthful if for any instance R with M(R) = (A, A1, . . . , An) and any agent i N, if the agent reports W i = Wi and the mechanism returns the allocation A = (A , A 1, . . . , A n) on the modified instance, then ui(Ai) ui(A i).

Next, we define the two main mechanisms in this paper.

Definition 2.2 (Leximin). Given an instance, the leximin solution considers pieces of cake A with ℓ(A) α such that the minimum among the utilities u1(A), . . . , un(A) is maximized; among all such pieces A, it considers those for which the second smallest utility is maximized, and so on, until after considering the largest utility, it chooses one of the pieces A that remain. It then assigns Ai = A Wi for all i N.

Definition 2.3 (MNW). Given an instance, the maximum Nash welfare (MNW) solution chooses a piece of cake A with ℓ(A) α such that the product Q i N ui(A) is maximized. It then assigns Ai = A Wi for all i N.

The following example illustrates some of our definitions.

Example 2.4. Let α = 1/2. Consider an instance with two agents whose utility functions are given as follows:

W1 = [0, 1/2], W2 = [1/4, 7/8].

A possible piece A selected by both leximin and MNW is A = [1/8, 5/8].4 Then, agent 1 has access to the piece A1 = A W1 = [1/8, 1/2] while agent 2 has access to the piece A2 = A W2 = [1/4, 5/8]. Both agents receive utility 3/8.

0 1/8 1/4 1/2 5/8 7/8 1

Since both leximin and MNW always choose Ai = A Wi for all i N, we can represent an allocation A simply by the set A when we discuss these mechanisms. Note that ui(Ai) = ℓ(Ai Wi) = ℓ(A Wi) = ui(A), so it also suffices to consider the agents utilities with respect to A. By a standard compactness argument and our observation above that the agents utilities depend only on the amounts of cake between breakpoints, both solutions are well-defined (i.e., the desired maxima are attained). There may be several maximizing allocations A to choose from, in which case we generally allow arbitrary tie-breaking as we will see later, this tie-breaking does not influence the utility that each agent receives and therefore does not play a significant role. We call an allocation that is returned by the MNW solution (resp., leximin solution) under some tie-breaking an MNW allocation (resp., leximin allocation). By our assumptions that α > 0 and ℓ(Wi) > 0 for every i, all MNW allocations and leximin allocations give every agent a strictly positive utility. All omitted proofs can be found in the full version of our paper (Bei, Lu, and Suksompong 2021).

4We show in Theorem 5.2 that leximin and MNW are equivalent in the case of two agents.

3 Leximin Solution In this section, we consider the leximin solution. We begin by establishing basic properties of the solution. Our first result is that the utility of each agent is the same in all leximin allocations, which means that tie-breaking is not an important issue. The proof proceeds by assuming for contradiction that two leximin allocations give some agent different utilities, and arguing that the average of these two allocations would have been a better choice with respect to the leximin ordering. Proposition 3.1. Given any instance, for each agent i, the utility that i receives is the same in all leximin allocations. Next, we show that a leximin allocation can be computed efficiently via a linear programming-based approach similar to the one used by Airiau et al. (2019) in the context of portioning. Recall that in our setting, the utility functions of the agents can be described explicitly by the sets Wi. Proposition 3.2. There exists an algorithm that computes a leximin allocation in time polynomial in the input size. We now come to our main result of this section, which establishes the truthfulness of the leximin solution. Theorem 3.3. For arbitrary tie-breaking, the leximin solution is truthful. At a high level, the proof of Theorem 3.3 proceeds by identifying specific types of manipulations, arguing that such manipulations cannot be beneficial when the leximin solution is used, and then showing that being immune to these manipulations implies being immune to all manipulations. We start by defining an ε-change, a useful concept in our proof. Definition 3.4 (ε-change). Given two vectors of real numbers x = (x1, x2, . . . , xn) and x = (x 1, x 2, . . . , x n), an εchange from x towards x refers to the following continuous operation: for each i {1, 2, . . . , n}, xi changes linearly to x i := xi + ε(x i xi), where ε is sufficiently small so that if xi < xj, then x i < x j . For ease of expression, we will also use an ε-change to refer to the outcome of such an operation, i.e., the vector x . When we discuss ε-changes, we will not specify the exact value of ε: any ε satisfying the above condition works. The following lemma establishes a useful property of ε-changes. Lemma 3.5. Given two vectors x and y, if y is a better vector with respect to the leximin ordering than x, then an ε-change from x to y is also a leximin improvement. We now extend the definition of an ε-change to allocations. Recall that for the leximin solution, it suffices to consider the set A instead of the entire allocation A. Given two allocations A and A , an ε-change from A towards A can be captured by dividing the cake into intervals according to the breakpoints and changing A towards A so that the length of cake included in the allocation in each interval changes linearly. Note that when we perform an ε-change from A towards A , by linearity, we also obtain a corresponding ε-change from the vector (u1(A), . . . , un(A)) towards (u1(A ), . . . , un(A )), and any allocation obtained during the process is feasible.

Next, we present auxiliary lemmas used for proving the truthfulness of leximin solution. These lemmas discuss how the leximin allocation can change when an agent modifies her density function in various ways. For notational convenience, in these lemmas we assume that instance R (resp., R ) contains the density functions corresponding to W1, . . . , Wn (resp., W 1, . . . , W n). Our first lemma says that whenever an agent shrinks her desired piece in such a way that it contains the entire portion she receives, then she should still receive the same portion in the new instance.

Lemma 3.6. Given a leximin allocation A for instance R, let R be an instance such that A Wi W i Wi for an agent i N and W j = Wj for all j N \ {i}. Then, A is also a leximin allocation for R .

Our second lemma says that when an agent shrinks her desired piece, she should not get a higher utility than before.

Lemma 3.7. Given a leximin allocation A for instance R, let R be an instance such that W i Wi for an agent i N and W j = Wj for all j N \ {i}. Let A be a leximin allocation for R . Then, ℓ(A W i) ℓ(A Wi).

Our third lemma says that if an agent is already getting her entire desired piece, then whenever she shrinks her desired piece, she should still be at maximum utility.

Lemma 3.8. Given a leximin allocation A for instance R with Wi A for an agent i N, let R be an instance such that W i Wi and W j = Wj for all j N \ {i}. Let A be a leximin allocation for R . Then, W i A .

We are now ready to prove Theorem 3.3.

Proof of Theorem 3.3. Suppose for contradiction that the leximin solution is not truthful. This means that there exists an instance R with leximin allocation A such that if agent i reports c Wi instead of Wi, a leximin allocation b A in the new instance b R satisfies ℓ( b A c Wi Wi) > ℓ(A Wi). We will keep the desired pieces Wj of agents j N \{i} unchanged throughout this proof. First, consider an instance b R where c W i = c Wi b A. By Lemma 3.6 applied to b R and b R , b A is also a leximin allocation for b R . Next, consider an instance b R in which c W i = c Wi b A Wi. Since c W i b A, by Lemma 3.8 applied to b R and b R , any leximin allocation for b R must contain the entire c W i . Recall that ℓ(c W i ) > ℓ(A Wi). Finally, consider the instances R and b R . From the former to the latter, agent i s desired piece shrinks from Wi to c W i Wi. By Lemma 3.7, the agent should not get a higher utility through this shrinking. However, the agent s utility is ℓ(A Wi) before the shrinking, and ℓ(c W i ) afterwards. This is a contradiction.

Observe that unlike MNW, the leximin solution depends on the normalization of the agents utilities. Besides our normalization, another common choice in cake cutting is to normalize the utility of every agent for the whole cake to 1 this leads to an alternative definition of the leximin solution. We remark here that this variant of leximin is not truthful. To

see this, consider two agents with W1 = [0, 1/3] and W2 = [1/3, 2/3], and let α = 1/3. In this instance, the (alternative) leximin solution gives each agent length 1/6 of the cake. However, if agent 2 misreports that W2 = [1/3, 1], then it is possible that the agent receives the interval [1/3, 5/9] and therefore length 2/9 > 1/6 of her valued cake. Let us emphasize that once we fix a mechanism, whether the mechanism is truthful or not is independent of the normalization, because truthfulness does not depend on the normalization. Hence, our normalization for leximin is the correct one to use if we desire truthfulness. In the next section, we provide further evidence that this normalization is appropriate by showing that our version of the leximin solution achieves a strong fairness guarantee in terms of egalitarian welfare.

4 Egalitarian Ratio

As we mentioned in the introduction, truthfulness by itself is easy to achieve, for example by always allocating a fixed piece of cake of length α. However, this may leave certain agents with zero utility, a patently unfair outcome. To measure fairness, we adapt the standard notion of proportionality from cake cutting5 and consider the minimum among the utilities of all agents. In order to perform meaningful interpersonal comparisons of utilities, we compare the utilities that the agents receive to their utilities for the entire cake in the following definition.

Definition 4.1 (Egalitarian ratio). Given an instance R and an allocation A, the egalitarian ratio of A is defined as

Egal-ratio-alloc R(A) = min i N ui(Ai) ui([0, 1]).

For a mechanism M and parameters n and α, the egalitarian ratio of M with respect to n and α is defined as

Egal-ration,α(M) = inf R Egal-ratio-alloc R(M(R)),

where the infimum is taken over all instances with n agents and parameter α.

In other words, the egalitarian ratio of M with respect to n and α is the smallest ratio between an agent s utility for her piece allocated by M and her utility for the entire cake, taken over all instances with parameters n and α. For example, if a mechanism always allocates a fixed piece of length α regardless of the agents utility functions, then its egalitarian ratio with respect to any n and α (0, 1) is 0. We first present a tight upper bound on the egalitarian ratio.

Proposition 4.2. For all n 1 and α (0, 1),

0 Egal-ration,α(M) α

for any mechanism M. Moreover, for each inequality, there exists a mechanism M such that the inequality is tight.

Our next result gives the precise egalitarian ratio of the leximin solution.

5Recall that in cake cutting, proportionality stipulates that every agent receives at least 1/n of her value for the entire cake.

Theorem 4.3. For all n 1 and α (0, 1),

Egal-ration,α(leximin) = α n (n 1)α.

Theorem 4.3 shows that the leximin solution achieves a non-trivial egalitarian ratio. However, it is unclear how good this ratio is compared to that of other truthful mechanisms. We will therefore show that the solution attains the highest possible ratio among all truthful mechanisms satisfying a natural condition. Given a vector of piecewise uniform density functions f = (f1, . . . , fn), let Lf be a vector with 2n components such that each component represents a distinct subset of agents and the value of the component is the length of the piece desired by exactly that subset of agents (and not by any agent outside the subset). Example 4.4. Consider the instance in Example 2.4. The corresponding Lf of this instance is (1/8, 1/4, 3/8, 1/4), where the components correspond to the lengths of the pieces desired by exactly the set of agents , {1}, {2}, and {1, 2}, respectively. Definition 4.5 (Position obliviousness). A mechanism M is position oblivious if the following holds: Let f and f be any vectors of density functions such that Lf = Lf , and let R and R be instances represented by these respective vectors and a given parameter α. If M(R) = (A, A1, . . . , An) and M(R ) = (A , A 1, . . . , A n), then ui(Ai) = u i(A i) for every i N. Position obliviousness has previously been studied by Bei, Huzhang, and Suksompong (2020). Intuitively, for a position oblivious mechanism, the utility of an agent depends only on the lengths of the pieces desired by various subsets of agents and not on the positions of these pieces. It follows directly from the definition that the leximin solution is position oblivious.6

Theorem 4.6. Let M be a truthful and position oblivious mechanism. Then, for all n 1 and α (0, 1),

Egal-ration,α(M) α n (n 1)α.

Proof. Assume for the sake of contradiction that there exists a truthful and position oblivious mechanism M with Egal-ration,α(M) = α n (n 1)α + δ for some δ > 0. For each i N, let Ci be a piece of length ℓ(Ci) = α/n + ε such that Ci Cj = for every pair i, j N, where ε > 0 is such that

ε < min 1 α

n , δ(n (n 1)α)2

n(n 1)(α + δ(n (n 1)α))

Consider an instance R where Wi = Ci for all i N. Since M can allocate length at most α of the cake, it must return an allocation for which some agent receives utility at most α/n. Assume without loss of generality that M returns an allocation A with u1(A1) α/n. Next, consider an instance R where W i = Ci for all i N \{1} and W 1 = [0, 1]\S i N\{1} Ci. (We use the notation

6Bei et al. (2017) considered a slightly stronger version of position obliviousness, which the leximin solution also satisfies.

W i for instance R to distinguish from Wi for instance R.) For this instance, we have ℓ(W 1) = 1 (n 1) (α/n + ε). Let A = M(R ), and let Y = A 1 W 1. By the definition of egalitarian ratio, we have u1(A 1)/u1([0, 1]) Egal-ration,α(M), that is,

ℓ(Y ) Egal-ration,α(M) ℓ(W 1)

= α n (n 1)α + δ 1 (n 1) α

which is greater than α/n by our choice of ε. Finally, consider an instance R where W i = Ci for all i N \{1}, while W 1 is a subset of [0, 1]\S i N\{1} Ci of length ℓ(W 1 ) = α/n+ε such that ℓ(W 1 Y ) > α/n. Since M is position oblivious, by comparing instances R with R, agent 1 must also get a utility of at most α/n in instance R . However, if the agent reports [0, 1] \ S i N\{1} Ci as in R , she gets a utility of ℓ(W 1 Y ) > α/n. This means that M is not truthful and yields the desired contradiction.

Comparing this ratio with highest possible ratio of α without the truthfulness condition (Proposition 4.2),7 one can see that adding the truthfulness requirement incurs a (multiplicative) price of n (n 1)α on the best egalitarian ratio. This price can be as large as n when α is close to 0, and decreases to 1 as α approaches 1.

5 Maximum Nash Welfare In this section, we address the MNW solution. We start by showing that like the leximin solution (Proposition 3.1), the utility that each agent receives is the same in all MNW allocations; this renders the tie-breaking issue insignificant.

Proposition 5.1. Given any instance, for each agent i, the utility that i receives is the same in all MNW allocations.

In the case of two agents, we show that MNW and leximin are in fact equivalent. The high-level idea is that both solutions can be obtained via the following process: First, select portions of the cake desired by both agents. If the quota α has not been reached, let the agents eat their desired piece using the same speed, until either (i) one of the agents has no more desired cake, in which case we let the other agent continue eating, or (ii) we run out of quota.

Theorem 5.2. Consider an instance with two agents. Any leximin allocation is an MNW allocation, and vice versa.

Theorems 3.3 and 5.2 together imply the following:

Corollary 5.3. For two agents and arbitrary tie-breaking, the MNW solution is truthful.

When n 3, the two mechanisms are no longer equivalent. This can be seen from the instance with W1 = [0, 1/2] and Wi = [1/2, 1] for all 2 i n, and α = 1/2. The leximin solution selects length 1/4 from each half of the cake, while MNW selects length 1 2n from the first half and n 1

2n from the second half. For our main result of this section, we demonstrate that the MNW solution is not truthful even

7Note that the mechanism that achieves egalitarian ratio α in Proposition 4.2 satisfies position obliviousness.

when an agent is only allowed to report a subset of her true desired piece as discussed in Section 1.1, this strengthens the non-truthfulness result of Aziz, Bogomolnaia, and Moulin (2020) where the manipulation is not of this simple nature. In particular, we construct an instance with six agents such that one of the agents can obtain a higher utility by reporting a subset of her actual desired piece.

Theorem 5.4. The MNW solution is not truthful under subset reporting regardless of tie-breaking.

We remark here that even if we allow the MNW solution to choose any Ai such that A Wi Ai A instead of always choosing Ai = A Wi (that is, the mechanism may give agent i some parts of A that she does not value, along with all parts of A that she values), our example in Theorem 5.4 still shows that any resulting mechanism is not truthful under subset reporting.

6 Impossibility Result Without Blocking

As we have so far assumed that mechanisms can block agents from accessing certain parts of the resource, an interesting question is what guarantees the mechanisms can achieve without the ability to block. Indeed, while blocking can be easily implemented in our introductory applications by restricting access to the sports facility or files in a cache memory, it may be harder or more costly in other situations, e.g., cleaning streets or constructing public parks. In this section, we consider mechanisms without the blocking ability. When no blocking is allowed, given an input instance, a mechanism M simply chooses a piece of cake A with ℓ(A) α, and each agent i receives a utility of ui(A) = ℓ(A Wi). First, we observe that while the leximin solution is truthful if it has the ability to block (Theorem 3.3), this is no longer the case in the absence of blocking.

Example 6.1 (Leximin is not truthful without blocking). Let α = 1/2. First, consider an instance R with two agents whose utility functions are given as follows:

W1 = [0, 1/2], W2 = [1/2, 1].

Assume without loss of generality that the tie-breaking rule chooses A = [1/4, 3/4]. Next, consider an instance R with the following utility functions:

W1 = [0, 3/4], W2 = [1/2, 1].

Agent 1 receives a utility of 3/8 in every leximin allocation for R . However, if agent 1 misreports that W1 = [0, 1/2], the instance becomes the same as R, and agent 1 receives a utility of 1/2 from the allocation A.

Our main result of this section shows that Example 6.1 is in fact not a coincidence.

Theorem 6.2. Without blocking, for every α (0, 1), no truthful, Pareto optimal, and position oblivious mechanism can achieve a positive egalitarian ratio even in the case of two agents.

0 1/2 1 Cake

W 1 1 W 1 2 W 2 1 W 2 2 W 3 1 W 3 2 W 4 1 W 4 2

Figure 1: Example instances in the proof of Theorem 6.2.

Proof. We assume for contradiction that there exists some α (0, 1) and a truthful, Pareto optimal, and position oblivious mechanism M with Egal-ratio2,α(M) > 0. We consider a sequence of instances with two agents, which we illustrate in Figure 1. In the following, the superscripts denote the indices of the instances. In all of the instances that we consider, every part of the cake is desired by at least one agent, so Pareto optimality implies that M must allocate exactly α of the cake.

Instance R1: W 1 1 = [0, 0.5], W 1 2 = [0.5, 1]. Let M(R1) = A1. Because α < 1, at least one of the agents will not obtain her maximum utility of 0.5. Assume without loss of generality that ℓ(W 1 1 A1) = x < 0.5; in other words, W 1 1 \ A1 is nonempty. Since M has a positive egalitarian ratio, it must hold that 0 < x < α. Instance R2: W 2 1 = [0, 0.5], W 2 2 = A1 [0.5, 1]. Let M(R2) = A2. We must have A2 W 2 2 ; in other words, agent 2 will receive utility α. This is because otherwise, agent 2 can benefit by reporting W 2 2 = [0.5, 1] and the instance becomes R1, in which case agent 2 will receive utility α from the output allocation A1. Note that because A2 is contained entirely in W 2 2 , we still have ℓ(W 2 1 A2) x. Instance R3: W 3 1 = [0, 0.5] \ A1, W 3 2 = A1 [0.5, 1]. Let M(R3) = A3. By the positive egalitarian ratio, we have ℓ(W 3 1 A3) = y > 0. Instance R4: W 4 1 = [0, 0.5] \ A1 B, W 4 2 = A1 [0.5, 1], where B is an interval of length x contained in W 3 2 with the largest intersection with A3. That is, if ℓ(W 4 2 A3) x, let B be any subset of W 4 2 A3 of length x; if ℓ(W 4 2 A3) < x, let B be any interval of length x that contains W 4 2 A3. Let M(R4) = A4. In this instance, we must have u1(A4) > x. This is because otherwise, agent 1 can benefit by reporting W 4 1 = [0, 0.5] \ A1 and the instance becomes R3, in which case agent 1 will obtain a utility of x + y (when ℓ(W 4 2 A3) x) or a utility of α (when ℓ(W 4 2 A3) < x). In both cases this value is strictly larger than x.

Finally, observe that instances R2 and R4 have the same Lf vector. In particular, we have ℓ(W 2 1 ) = ℓ(W 4 1 ) = 1/2, ℓ(W 2 2 ) = ℓ(W 4 2 ) = 1/2 + x, and ℓ(W 2 1 W 2 2 ) = ℓ(W 4 1 W 4 2 ) = x. This means that each agent should receive the same utility in these two instances from our position oblivious mechanism M. However, agent 1 receives utility at most x in R2 and utility strictly larger than x in R4. We have reached a contradiction.

7 Conclusion and Future Work In this paper, we have studied truthful and fair mechanisms in the cake sharing setting where all agents share the same subset of a heterogeneous divisible resource. Our results established the leximin solution as an attractive mechanism due to its truthfulness and its optimal egalitarian ratio among all truthful and position oblivious mechanisms. On the other hand, we constructed an intricate example showing that the maximum Nash welfare solution, which often exhibits desirable properties in other settings, fails to yield truthfulness in cake sharing even when the agents are restricted to subset reporting. Moreover, we showed that in the absence of blocking, no truthful, Pareto optimal, and position oblivious mechanism can achieve a positive egalitarian ratio in particular, this implies that the leximin solution is not truthful without blocking. An intriguing question is whether the impossibility still holds if we remove Pareto optimality or position obliviousness (or both), or whether there is a truthful mechanism that attains a non-trivial fairness guarantee even when blocking is not allowed. In future research, it would be interesting to extend our cake sharing model to capture other practical scenarios. One natural direction is to allow agents to have more complex preferences beyond piecewise uniform utilities. The first step in this direction would be to consider piecewise constant utilities, where an agent s density function is constant over subintervals of the cake. Another extension is to allow non-uniform costs over the cake this models, for example, the fact that reserving a sports facility or a conference room can be more expensive during peak periods. In the full version of our paper (Bei, Lu, and Suksompong 2021), we show that a natural generalization of the leximin solution is still truthful and achieves the optimal egalitarian ratio for piecewise constant cost functions. Furthermore, as in cake cutting, it may be fruitful to consider scenarios in which there are constraints on the shared cake (Suksompong 2021).8 Other questions addressed in cake cutting, such as the price of truthfulness and the price of fairness that is, the loss of social welfare due to truthfulness and fairness, respectively (Caragiannis et al. 2012; Maya and Nisan 2012) are equally relevant and worthy of exploration in cake sharing as well.

8A desirable property in certain applications is contiguity for example, a contiguous time slot is often more useful than a union of disconnected slots. However, note that if contiguity is imposed, we may not be able to avoid leaving some agents empty-handed. A trivial example is when one agent only values a small piece of cake at the left end while another agent only values one at the right end. In this case, unless α is very close to 1, one of the agents will necessarily receive utility 0.

Acknowledgments This work was partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG23/20), and by an NUS Start-up Grant. The work was mostly done while the second author was at Nanyang Technological University and the National University of Singapore. We would like to thank Ilya Bogdanov for help with the proof of Theorem 5.4 and the anonymous reviewers for their valuable feedback.

References Airiau, S.; Aziz, H.; Caragiannis, I.; Kruger, J.; Lang, J.; and Peters, D. 2019. Portioning using ordinal preferences: Fairness and efficiency. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 11 17. Aziz, H.; Bogomolnaia, A.; and Moulin, H. 2020. Fair mixing: the case of dichotomous preferences. ACM Transactions on Economics and Computation, 8(4): 18:1 18:27. Aziz, H.; and Shah, N. 2021. Participatory budgeting: Models and approaches. In Rudas, T.; and P eli, G., eds., Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations, 215 236. Springer International Publishing. Aziz, H.; and Ye, C. 2014. Cake cutting algorithms for piecewise constant and piecewise uniform valuations. In Proceedings of the 10th Conference on Web and Internet Economics (WINE), 1 14. Bei, X.; Chen, N.; Huzhang, G.; Tao, B.; and Wu, J. 2017. Cake cutting: Envy and truth. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 3625 3631. Bei, X.; Huzhang, G.; and Suksompong, W. 2020. Truthful fair division without free disposal. Social Choice and Welfare, 55(3): 523 545. Bei, X.; Lu, X.; and Suksompong, W. 2021. Truthful cake sharing. Co RR, abs/2112.05632. Bogomolnaia, A.; and Moulin, H. 2004. Random matching under dichotomous preferences. Econometrica, 72(1): 257 279. Brams, S. J.; and Taylor, A. D. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press. Brandl, F.; Brandt, F.; Greger, M.; Peters, D.; Stricker, C.; and Suksompong, W. 2022. Funding public projects: a case for the Nash product rule. Journal of Mathematical Economics. Forthcoming. Brˆanzei, S.; and Miltersen, P. B. 2015. A dictatorship theorem for cake cutting. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), 482 488. Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; and Kyropoulou, M. 2012. The efficiency of fair division. Theory of Computing Systems, 50(4): 589 610. Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2019. The unreasonable fairness of

maximum Nash welfare. ACM Transactions on Economics and Computation, 7(3): 12:1 12:32. Chen, Y.; Lai, J. K.; Parkes, D. C.; and Procaccia, A. D. 2013. Truth, justice, and cake cutting. Games and Economic Behavior, 77: 284 297. Faliszewski, P.; Skowron, P.; Slinko, A.; and Talmon, N. 2017. Multiwinner voting: a new challenge for social choice theory. In Endriss, U., ed., Trends in Computational Social Choice, chapter 2, 27 47. AI Access. Friedman, E. J.; Gkatzelis, V.; Psomas, C.-A.; and Shenker, S. 2019. Fair and efficient memory sharing: Confronting free riders. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), 1965 1972. Halpern, D.; Procaccia, A. D.; Psomas, A.; and Shah, N. 2020. Fair division with binary valuations: One rule to rule them all. In Proceedings of the 16th Conference on Web and Internet Economics (WINE), 370 383. Kurokawa, D.; Lai, J. K.; and Procaccia, A. D. 2013. How to cut a cake before the party ends. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI), 555 561. Kurokawa, D.; Procaccia, A. D.; and Shah, N. 2018. Leximin allocations in the real world. ACM Transactions on Economics and Computation, 6(3 4): 11:1 11:24. Manurangsi, P.; and Suksompong, W. 2019. Computing a small agreeable set of indivisible items. Artificial Intelligence, 268: 96 114. Maya, A.; and Nisan, N. 2012. Incentive compatible two player cake cutting. In Proceedings of the 8th Conference on Web and Internet Economics (WINE), 170 183. Menon, V.; and Larson, K. 2017. Deterministic, strategyproof, and fair cake cutting. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 352 358. Peters, D. 2018. Proportionality and strategyproofness in multiwinner elections. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1549 1557. Plaut, B.; and Roughgarden, T. 2020. Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 34(2): 1039 1068. Procaccia, A. D. 2016. Cake cutting algorithms. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice, chapter 13, 311 329. Cambridge University Press. Robertson, J.; and Webb, W. 1998. Cake-Cutting Algorithms: Be Fair if You Can. Peters/CRC Press. Segal-Halevi, E.; and Sziklai, B. R. 2019. Monotonicity and competitive equilibrium in cake-cutting. Economic Theory, 68(2): 363 401. Skowron, P.; Faliszewski, P.; and Lang, J. 2016. Finding a collective set of items: From proportional multirepresentation to group recommendation. Artificial Intelligence, 241: 191 216. Suksompong, W. 2021. Constraints in fair division. ACM SIGecom Exchanges, 19(2): 46 61.

Tao, B. 2021. On existence of truthful fair cake cutting mechanisms. Co RR, abs/2104.07387.