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 (i.e., approval) utilities over the cake. On the one hand, we show that the leximin solution is excludably truthful (meaning it is truthful when it can block each agent from accessing parts of the cake that the agent does not claim to desire) and moreover maximizes the guaranteed normalized egalitarian welfare among all excludably truthful and position oblivious mechanisms. On the other hand, we demonstrate that the maximum Nash welfare solution is excludably truthful for two agents (as it coincides with leximin in that case) but not in general. We also provide an impossibility result on truthfulness when blocking is not allowed, and adapt notions of representation to our setting.
Notes
A preliminary version of this paper appears in Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022). This version contains additional results on justified representation notions (Sect. 7) and non-uniform costs (Appendix A), as well as all proofs omitted from the conference version.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
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, for example:
A group of workers 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. One worker is an early riser but has commitments in the afternoon, so she is available between 7:40 am–12:55 pm and after 5:10 pm. Another worker has an early morning commitment and is therefore free from 10:35 am onwards.
A number of agents seek to agree upon the files to store in a shared cache memory. These files could contain movie series, lecture series, or music, and the agents have varying preferences on parts that they like to watch or listen to. The parts that are stored in the cache can be accessed at high speed, so the agents can benefit from having as much of their preferred parts in the cache as possible.1
An ice-cream company has received permission to sell its ice-cream on the city’s main tourist street, but they are only entitled to a certain length of the street. The employees of the company want to decide on the locations via a vote. One employee likes an area close to the subway entrance because a large number of people pass through it, while another employee prefers a location near the park since she believes people are more likely to buy ice-cream there.
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 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?
Advertisement
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 \(\alpha \in [0,1]\), a subset of length at most \(\alpha\) 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 (corresponding to a finite union of intervals) which she values uniformly. Except in Sect. 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 most aforementioned applications of cake sharing, for example by disallowing agents from accessing the part of the cache memory that they do not demand or restricting their access to the sports facility during the times that they claim to be unavailable. When a mechanism uses its ability to block, we speak of excludable truthfulness in order to distinguish it from truthfulness for non-blocking mechanisms.
In Sect. 3, we focus on the leximin solution. Our main technical result establishes the excludable 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 \(\varepsilon\)-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 Sect. 4 the fairness of mechanisms. In order to perform meaningful interpersonal comparisons of utilities, we normalize the utility of each agent for the entire cake to 1, and define the guaranteed normalized egalitarian welfare (GNEW) of a mechanism to be the worst-case egalitarian welfare (based on the normalized utilities) that the mechanism provides over all instances. We show that for any \(\alpha\) and number of agents n, the leximin solution (based on the unnormalized utilities) has GNEW exactly \(\alpha /(n-(n-1)\alpha )\). We also prove that this GNEW is optimal among all mechanisms that are excludably truthful and position oblivious (see Definition 4.5). Our results in Sects. 3 and 4 establish the leximin solution as an attractive mechanism in cake sharing.
Advertisement
In Sect. 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 excludably truthful in that case. In general, however, a result of Aziz et al. (2020, Theorem 3) implies the failure of the MNW solution to satisfy excludable truthfulness in our setting. We strengthen their result by showing that MNW is not excludably truthful even when an agent is only allowed to report a subset of her true desired piece.2 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 violation of excludable truthfulness that can be easily verified by hand.
Next, we demonstrate in Sect. 6 that the ability to block is crucial for the truthfulness of mechanisms. In particular, we show that even for two agents, no truthful, Pareto optimal, and position oblivious mechanism can achieve a positive GNEW when blocking is not allowed.
Finally, in Sect. 7, we adapt known notions of representation, proportional justified representation (PJR) and extended justified representation (EJR), to our cake sharing setting. We show that unlike with truthfulness, MNW fares better than leximin with respect to these notions: MNW satisfies both of the notions, whereas leximin fails both of them. We further characterize MNW as the only “welfare-maximizer rule” that satisfies either of these notions.
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, where criteria can include excellence and diversity—see the surveys by Faliszewski et al. (2017) and Lackner and Skowron (2023). 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. The representation notions that we study in Sect. 7 are adapted from the multiwinner voting literature.
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 our cake sharing model, in which there is no predetermined division of the cake into homogeneous units, does not fall under the framework of participatory budgeting.
Aziz et al. (2020) studied a probabilistic voting setting called fair mixing, 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,\ldots ,m\), the interval \([(j-1)/m, j/m]\) represents alternative j, and \(\alpha = 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 Sect. 2). Like us, Aziz et al. showed that the leximin solution is excludably truthful. Our results on the leximin solution generalize and strengthen theirs in three ways. First, we allow agents to report arbitrary breakpoints—this 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 \(\alpha\) instead of only \(\alpha = 1/m\). Third, we establish a tight bound on the GNEW and show that the leximin solution achieves this bound. Therefore, we believe that overall, our results make a stronger case in favor of the leximin solution. We refer to the related literature section of Aziz et al.’s paper for further work on fair mixing and similar settings.
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 et al. 2013; Aziz and Ye 2014; Brânzei and Miltersen 2015; Bei et al. 2017; Menon and Larson 2017; Bei et al. 2020; Bu et al. 2023). 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 GNEW 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 et al. 2018; Caragiannis et al. 2019; Segal-Halevi and Sziklai 2019; Aziz et al. 2020; Halpern et al. 2020; Plaut and Roughgarden 2020; Brandl et al. 2022; Suksompong 2023; Yuen and Suksompong 2023).
2 Preliminaries
Our setting includes a set of agents denoted by \(N = \{1, 2, \ldots , 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 \(\ell (I)\) the length of an interval I, that is, \(\ell ([a, b]) = b - a\). For a piece of cake S consisting of a set of intervals \({\mathcal {I}}_S\), we denote \(\ell (S) = \sum _{I \in {\mathcal {I}}_S} \ell (I)\). Each agent \(i \in N\) is endowed with a density function\(f_i :[0, 1] \rightarrow {\mathbb {R}}_{\ge 0}\), which captures how the agent values different parts of the cake. We assume that the agents have piecewise uniform utilities: each agent i has a (not necessarily contiguous) piece of cake \(A_i\) that she desires, and her density function \(f_i\) takes on the value 1 for all desired parts and 0 for all remaining parts. The utility of agent i for any piece of cake S is given by \(u_i(S):= \ell (S\cap A_i)\). We assume that \(\ell (A_i) > 0\) for every i, since we can simply ignore an agent i with \(\ell (A_i) = 0\).
Let \(\alpha \in [0,1]\) be a given parameter. We refer to a setting with agents, their density functions, and the parameter \(\alpha\) as an instance. A mechanism\({\mathcal {M}}(R)\) chooses from any given instance R a piece of cake W with \(\ell (W)\le \alpha\). However, this does not mean all agents have full access to W, because we allow the mechanism to block each agent from accessing certain parts of the selected piece. Specifically, after choosing W, the mechanism assigns piece \(W_i\subseteq W\) to agent i; we call \({\mathcal {W}}=(W,W_1,\ldots ,W_n)\) an allocation. The utility of agent i from the allocation \({\mathcal {W}}\) is \(u_i(W_i)\). Since the cases \(\alpha =0\) and \(\alpha =1\) are trivial, we assume from now on that \(\alpha \in (0,1)\). Given an instance, every point that is a left or right endpoint of an interval in \(A_i\) 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.
Definition 2.1
(Excludable truthfulness) A mechanism is excludably truthful if for any instance R with \({\mathcal {M}}(R) = (W, W_1, \ldots , W_n)\) and any agent \(i\in N\), if the agent reports \(A_i'\ne A_i\) and the mechanism returns the allocation \({\mathcal {W}}'=(W',W_1',\ldots ,W_n')\) on the modified instance, then \(u_i(W_i)\ge u_i(W_i')\).
If the mechanism does not use its ability to block (that is, it sets \(W_i = W\) for all \(i\in N\)), then we refer to excludable truthfulness simply as truthfulness.
Next, we define the two main mechanisms in this paper.
Definition 2.2
(Leximin) Given an instance, the leximin solution considers pieces of cake W with \(\ell (W)\le \alpha\) such that the minimum among the utilities \(u_1(W),\ldots ,u_n(W)\) is maximized; among all such pieces W, 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 W that remain. It then assigns \(W_i = W\cap A_i\) for all \(i\in N\).
Definition 2.3
(MNW) Given an instance, the maximum Nash welfare (MNW) solution chooses a piece of cake W with \(\ell (W)\le \alpha\) such that the product \(\prod _{i\in N}u_i(W)\) is maximized. It then assigns \(W_i = W\cap A_i\) for all \(i\in N\).
The following example illustrates some of our definitions.
Example 2.4
Let \(\alpha = 1/2\). Consider an instance with two agents whose utility functions are given as follows:
A possible piece W selected by both leximin and MNW is \(W = [1/8, 5/8]\).3 Then, agent 1 has access to the piece \(W_1 = W \cap A_1 = [1/8, 1/2]\) while agent 2 has access to the piece \(W_2 = W \cap A_2 = [1/4, 5/8]\). Both agents receive utility 3/8.
×
Since both leximin and MNW always choose \(W_i = W\cap A_i\) for all \(i\in N\), we can represent an allocation \({\mathcal {W}}\) simply by the set W when we discuss these mechanisms. Note that \(u_i(W_i) = \ell (W_i\cap A_i) = \ell (W\cap A_i) = u_i(W)\), so it also suffices to consider the agents’ utilities with respect to W. 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 W 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 \(\alpha > 0\) and \(\ell (A_i) > 0\) for every i, all MNW allocations and leximin allocations give every agent a strictly positive utility.
In order to perform meaningful interpersonal comparisons of utilities, we normalize4 the utility of each agent for the entire cake to 1. Specifically, for each \(i\in N\), we let \({\widehat{u}}_i\) be the normalized utility function of agent i, where \({\widehat{u}}_i(S):= u_i(S)/u_i([0,1])\) for any piece of cake S; note that \({\widehat{u}}_i([0,1]) = 1\). We sometimes refer to \(u_i\) as the unnormalized utility function of agent i.
To build some intuition on normalization, observe that the rule that chooses an allocation W maximizing the normalized utilitarian welfare (i.e., the sum of all agents’ normalized utilities) and sets \(W_i = W\cap A_i\) for all \(i\in N\) is not excludably truthful. To see this, consider three agents with \(A_1 = [0,1/2]\), \(A_2 = A_3 = [1/2,1]\), and \(\alpha = 1/2\). The normalized utilitarian rule chooses \(W = [1/2,1]\), leaving agent 1 with utility 0. This agent can then manipulate by reporting \(A_1 = [0, 1/6]\), in which case the interval [0, 1/6] will be contained in the chosen piece W as well as in \(W_1\). On the other hand, one can check that the rule that chooses an allocation W maximizing the unnormalized utilitarian welfare (i.e., the sum of all agents’ unnormalized utilities) is truthful even without blocking. However, this rule may still leave an agent empty-handed—for example, it also chooses \(W = [1/2,1]\) in the instance above, leaving agent 1 with utility 0.
Note that while a version of leximin defined using normalized utilities is different from the one using unnormalized utilities (Definition 2.2), both versions of MNW coincide.
3 Leximin solution
In this section, we consider the leximin solution (defined based on unnormalized utilities). 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. Recall that for the leximin solution, it suffices to consider the set W instead of the entire allocation \({\mathcal {W}}\).
Proposition 3.1
Given any instance, for each agent i, the utility that i receives is the same in all leximin allocations.
Proof
Assume for contradiction that two leximin allocations, W and \(W'\), give some agent different utilities. Let \(W''\) be an allocation such that for each pair of consecutive breakpoints, the amount of cake between those breakpoints included in \(W''\) is the average of the corresponding amounts for W and \(W'\). By linearity, \(W''\) is a feasible allocation, and \(u_i(W'') = \frac{1}{2}(u_i(W) + u_i(W'))\) for every \(i\in N\).
Since the leximin ordering is a total order, the multiset of utilities that the n agents receive in W must be the same as the corresponding multiset in \(W'\). Let j be an agent with the smallest \(\min \{u_j(W), u_j(W')\}\) such that \(u_j(W)\ne u_j(W')\), and assume without loss of generality that \(u_j(W) < u_j(W')\). All agents k with \(\min \{u_k(W), u_k(W')\} < \min \{u_j(W), u_j(W')\}\) have \(u_k(W) = u_k(W')\), and this latter quantity is also equal to \(u_k(W'')\). On the other hand, we have \(u_j(W'') = \frac{1}{2}(u_j(W) + u_j(W')) > u_j(W)\), which means that the number of agents who receive utility exactly \(u_j(W)\) in \(W''\) is strictly less than the corresponding numbers for W and \(W'\). Hence, \(W''\) is a better allocation with respect to the leximin ordering than W and \(W'\), a contradiction. \(\square\)
Next, we show that a leximin allocation can be computed efficiently via a linear programming-based approach similar to the one used in Algorithm 1 of Airiau et al. (2023) in the context of portioning. Recall that in our setting, the utility functions of the agents can be described explicitly by the sets \(A_i\).
Proposition 3.2
There exists an algorithm that computes a leximin allocation in time polynomial in the input size.
Proof
First, we divide the cake into a set M of intervals \(I_1,\ldots ,I_m\) using all breakpoints, so each interval is either desired in its entirety or not desired at all by each agent. Let \(x_j\) denote the length of the interval \(I_j\) that we include in our allocation. Thus, the utility of agent i can be written as \(\sum _{j=1}^m {\textbf{1}}_{I_j\subseteq A_i}x_j\), where \({\textbf{1}}_X\) denotes the indicator variable for event X.
We proceed by formulating linear programs. Initially, the set \(N'\) of agents whose utility we have already fixed is empty. We determine the smallest utility in a leximin allocation by solving for the maximum \(t^*\) such that the utility of every agent is at least \(t^*\). We then determine an agent who receives utility \(t^*\) in a leximin allocation—to this end, for each agent, we solve for the maximum \(\varepsilon\) such that this agent receives utility at least \(t^*+\varepsilon\) and every other agent receives utility at least \(t^*\). We choose an agent \(i'\) who returns \(\varepsilon = 0\), fix the utility of this agent by setting \(t_{i'} = t^*\), and continue by finding the next smallest utility among the remaining agents. The pseudocode of our algorithm is given as Algorithm 1.
Algorithm 1
Computing a leximin allocation
×
Since our algorithm requires solving \(O(n^2)\) linear programs, it runs in polynomial time.5 We now establish its correctness. Consider the first iteration of the while-loop, and the returned value \(t^*\) of the first linear program. We claim that for at least one \(i'\in N\), the linear program for \(i'\) returns \(\varepsilon = 0\). Indeed, if this is not the case, then for every \(i'\), there is a feasible allocation that gives \(i'\) a utility strictly greater than \(t^*\) and gives every other agent a utility of at least \(t^*\); by taking the “average” of all such allocations similarly to the proof of Proposition 3.1, we obtain a feasible allocation that gives every agent strictly greater than \(t^*\), contradicting the definition of \(t^*\). For \(i'\) such that \(\varepsilon = 0\), we therefore have that the utility of \(i'\) is equal to \(t^*\) in every leximin allocation. We then apply a similar argument for the remaining \(n-1\) iterations to conclude that the utility of each agent in the allocation that the algorithm returns is equal to the corresponding utility in every leximin allocation. It therefore follows that the returned allocation is a leximin allocation. \(\square\)
We now come to our main result of this section, which establishes the excludable truthfulness of the leximin solution. Since tie-breaking is unimportant due to Proposition 3.1, we assume that ties are broken in any consistent manner.
Theorem 3.3
The leximin solution is excludably 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 \(\varepsilon\)-change, a useful concept in our proof.
Definition 3.4
(\(\varepsilon\)-change) Given two vectors of real numbers \({\textbf{x}} = (x_1, x_2, \ldots , x_n)\) and \({\textbf{x}}' = (x_1', x_2', \ldots , x_n')\), an \(\varepsilon\)-change from \({\textbf{x}}\) towards \({\textbf{x}}'\) refers to the following continuous operation: for each \(i \in \{1, 2, \ldots , n\}\), \(x_i\) changes linearly to \(x_i'':= x_i + \varepsilon (x_i'-x_i)\), where \(\varepsilon\) is sufficiently small so that if \(x_i < x_j\), then \(x_i'' < x_j''\).
For ease of expression, we will also use an \(\varepsilon\)-change to refer to the outcome of such an operation, i.e., the vector \({\textbf{x}}''\). When we discuss \(\varepsilon\)-changes, we will not specify the exact value of \(\varepsilon\): any \(\varepsilon\) satisfying the above condition works. The following lemma establishes a useful property of \(\varepsilon\)-changes.
Lemma 3.5
Given two vectors \({\textbf{x}}\) and \({\textbf{y}}\), if \({\textbf{y}}\) is a better vector with respect to the leximin ordering than \({\textbf{x}}\), then an \(\varepsilon\)-change from \({\textbf{x}}\) to \({\textbf{y}}\) is also a leximin improvement.
Proof
Sort the numbers of \({\textbf{x}}\) in non-descending order and group them into buckets so that numbers within each bucket are the same and those in different buckets are different. Observe that an \(\varepsilon\)-change improves \({\textbf{x}}\) with respect to the leximin ordering if and only if for the lowest bucket where there is a change, some number increases and no number decreases.
Consider an \(\varepsilon\)-change from \({\textbf{x}}\) towards a better leximin vector \({\textbf{y}}\). If some number in the lowest bucket of \({\textbf{x}}\) decreases, then \({\textbf{y}}\) would not be a leximin improvement of \({\textbf{x}}\), so no number in this bucket decreases. If some number in this bucket increases, we are done by the above observation. Else, there is no change in this bucket, and we move on to the next bucket and repeat the same argument. Because \({\textbf{x}}\) and \({\textbf{y}}\) are different, there must be a change in at least one bucket, which gives our desired conclusion. \(\square\)
We now extend the definition of an \(\varepsilon\)-change to allocations. Given two allocations W and \(W'\), an \(\varepsilon\)-change from W towards \(W'\) can be captured by dividing the cake into intervals according to the breakpoints and changing W towards \(W'\) so that the length of cake included in the allocation in each interval changes linearly. Note that when we perform an \(\varepsilon\)-change from W towards \(W'\), by linearity, we also obtain a corresponding \(\varepsilon\)-change from the vector \((u_1(W),\ldots ,u_n(W))\) towards \((u_1(W'),\ldots ,u_n(W'))\), and any allocation obtained during the process is feasible.
Next, we present auxiliary lemmas used for proving the excludable truthfulness of the 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 \(A_1,\ldots ,A_n\) (resp., \(A_1',\ldots ,A_n'\)). We write \(\text {Lex}(R)\) to denote the leximin allocation in instance R, and \(W\succ _R W'\) to mean that W is a strictly better allocation with respect to the leximin ordering than \(W'\) in R (subject to our consistent tie-breaking). Further, we write \(u_i(W; R)\) to denote agent i’s utility for W in R.
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 still receives the same portion in the new instance.
Lemma 3.6
Given an instance R and the allocation \(W = Lex (R)\), let \(R'\) be an instance such that \(W\cap A_i \subseteq A_i' \subseteq A_i\) for an agent \(i \in N\) and \(A_j' = A_j\) for all \(j \in N {\setminus } \{i\}\). Then, \(W = Lex (R')\).
Proof
Suppose for contradiction that \(W \ne \text {Lex}(R')\). Let \(W' = \text {Lex}(R')\). Since \(A_i'\subseteq A_i\), we have \(u_i(W'; R') = \ell (W' \cap A_i') \le \ell (W' \cap A_i) = u_i(W'; R)\). Moreover, for every agent \(j\ne i\), since \(A_j' = A_j\), it holds that \(u_j(W'; R') = \ell (W' \cap A_j') = \ell (W' \cap A_j) = u_j(W'; R)\). On the other hand, since \(W\cap A_i \subseteq A_i'\subseteq A_i\), we have \(W\cap A_i = W\cap A_i'\), and therefore \(u_i(W;R') = \ell (W\cap A_i') = \ell (W\cap A_i) = u_i(W;R)\). Moreover, for every agent \(j\ne i\), since \(A_j' = A_j\), it holds that \(u_j(W; R') = \ell (W \cap A_j') = \ell (W \cap A_j) = u_j(W; R)\).
From the previous paragraph, we know that the vector
when \(R'\) is changed to R, the ith number increases or stays the same while the remaining \(n-1\) numbers stay the same. Since \(W'\succ _{R'} W\) by our assumption, we must also have \(W'\succ _{R} W\), contradicting \(W = \text {Lex}(R)\). \(\square\)
Our second lemma says that when an agent shrinks her desired piece, under leximin she does not get a higher utility than before.
Lemma 3.7
Given an instance R and the allocation \(W = Lex (R)\), let \(R'\) be an instance such that \(A_i' \subseteq A_i\) for an agent \(i \in N\) and \(A_j' = A_j\) for all \(j \in N {\setminus } \{i\}\). Let \(W' = Lex (R')\). Then, \(\ell (W'\cap A_i') \le \ell (W\cap A_i)\).
Proof
Suppose for contradiction that \(\ell (W'\cap A_i') > \ell (W\cap A_i)\); let \(x'\) and x denote the former and latter quantities, respectively. See Fig. 1 for an illustration. Note that \(\ell (W'\cap A_i') = u_i(W'; R') = x'\) and \(\ell (W\cap A_i) = u_i(W; R) = x\).
Since \(A_i'\subseteq A_i\), it holds that \(u_i(W'; R) \ge u_i(W'; R') = x'\). Since \(u_i(W; R) = x\), when changing from \(W'\) to W with respect to R, the utility of agent i decreases from at least \(x'\) to x. However, because \(W = \text {Lex}(R)\), this change is in fact a leximin improvement.6 Hence, even if the utility of agent i started at exactly \(x'\) and decreased to x, the change would still be a leximin improvement.7
Now, consider the agents’ utilities with respect to \(R'\). We have \(u_i(W';R') = x'\), and since \(A_i'\subseteq A_i\), it holds that \(u_i(W;R') \le u_i(W;R) = x\). Hence, when changing from \(W'\) to W, the utility of agent i with respect to \(R'\) decreases from \(x'\) to at most x. For every agent \(j\ne i\), since \(A'_j = A_j\), we have \(u_j(W';R') = u_j(W';R)\) and \(u_j(W;R') = u_j(W;R)\). This means that when changing from \(W'\) to W in \(R'\), agent i’s utility starts at \(x'\) and decreases, while the change in every other agent’s utility is the same as the corresponding change in the last sentence of the previous paragraph. We know that the change in that sentence is a leximin improvement. By Lemma 3.5, an \(\varepsilon\)-change from \(W'\) towards W in \(R'\) is also a leximin improvement. This contradicts the assumption that \(W' = \text {Lex}(R')\). \(\square\)
Our third lemma says that if an agent is already getting her entire desired piece, then whenever she shrinks her desired piece, she is still at maximum utility.
Lemma 3.8
Given an instance R and the allocation \(W = Lex (R)\) such that \(A_i\subseteq W\) for an agent \(i\in N\), let \(R'\) be an instance such that \(A_i' \subseteq A_i\) and \(A_j' = A_j\) for all \(j \in N {\setminus } \{i\}\). Let \(W' = Lex (R')\). Then, \(A_i'\subseteq W'\).
Proof
Suppose for contradiction that \(W'\) does not contain the entire \(A_i'\), and let \(x' = \ell (W'\cap A_i') = u_i(W'; R') < \ell (A_i')\). See Fig. 2 for an illustration.
Since \(W = \text {Lex}(R)\), we have that \(W \succ _R W'\).8 By Lemma 3.5, an \(\varepsilon\)-change from \(W'\) towards W is also a leximin improvement with respect to R, so by the characterization of \(\varepsilon\)-change improvements in the proof of the lemma, in the lowest bucket where there is a change, some number increases and no number decreases. Since \(A_i'\subseteq A_i\), in this \(\varepsilon\)-change, the utility of agent iincreases from at least \(x'\) towards \(\ell (A_i)\).
Now, consider the same \(\varepsilon\)-change from \(W'\) towards W, but with respect to \(R'\). Since \(A_i'\subseteq A_i\), the utility of agent iincreases from exactly \(x'\) towards \(\ell (A_i')\), and since \(A_j' = A_j\) for all \(j\ne i\), the utilities of other agents change in the same way as before. Since agent i’s utility starts no higher than before and still increases, one can see that in the lowest bucket where there is a change, again some number increases and no number decreases. Hence, the characterization of \(\varepsilon\)-change improvements implies that the change is also a leximin improvement with respect to \(R'\). This contradicts the assumption that \(W' = \text {Lex}(R')\). \(\square\)
With these lemmas in hand, we are now ready to prove Theorem 3.3.
Proof
(Proof of Theorem 3.3) Suppose for contradiction that the leximin solution is not excludably truthful. This means that there exists an instance R with \(W = \text {Lex}(R)\) such that if agent i reports \({\widehat{A}}_i\) instead of \(A_i\), the new instance \({\widehat{R}}\) with \({\widehat{W}} = \text {Lex}({\widehat{R}})\) satisfies \(\ell ({\widehat{W}}\cap {\widehat{A}}_i\cap A_i) > \ell (W\cap A_i)\). See Fig. 3 for an illustration. We will keep the desired pieces \(A_j\) of agents \(j\in N\setminus \{i\}\) unchanged throughout this proof.
First, consider an instance \({\widehat{R}}'\) where \({\widehat{A}}_i' = {\widehat{A}}_i\cap {\widehat{W}}\). By Lemma 3.6 applied to \({\widehat{R}}\) and \({\widehat{R}}'\), \({\widehat{W}}\) is also the leximin allocation for \({\widehat{R}}'\).
Next, consider an instance \({\widehat{R}}''\) in which \({\widehat{A}}_i'' = {\widehat{A}}_i\cap {\widehat{W}}\cap A_i = {\widehat{A}}_i'\cap A_i\). Since \({\widehat{A}}_i'\subseteq {\widehat{W}}\), by Lemma 3.8 applied to \({\widehat{R}}'\) and \({\widehat{R}}''\), the leximin allocation for \({\widehat{R}}''\) must contain the entire \({\widehat{A}}_i''\). Recall that \(\ell ({\widehat{A}}_i'') > \ell (W\cap A_i)\).
Finally, consider the instances R and \({\widehat{R}}''\). From the former to the latter, agent i’s desired piece shrinks from \(A_i\) to \({\widehat{A}}_i''\subseteq A_i\). By Lemma 3.7, the agent should not get a higher utility through this shrinking. However, the agent’s utility is \(\ell (W\cap A_i)\) before the shrinking, and \(\ell ({\widehat{A}}_i'')\) afterwards. This is a contradiction. \(\square\)
As we discussed at the end of Sect. 2, the leximin solution defined based on normalized utilities is different from the one based on unnormalized utilities that we have studied in this section. We remark here that normalized leximin is not excludably truthful. To see this, consider two agents with \(A_1 = [0, 1/3]\) and \(A_2 = [1/3, 2/3]\), and let \(\alpha = 1/3\). In this instance, normalized leximin gives each agent length 1/6 of the cake. However, if agent 2 misreports that \(A_2 = [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.
4 Guaranteed normalized egalitarian welfare
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 \(\alpha\). However, this may leave certain agents with zero utility, a patently unfair outcome. To measure fairness, we consider the minimum among the utilities of all agents. In order to compare different agents’ utilities in a meaningful way, we use the normalized utilities in the following definition.
Definition 4.1
(GNEW) Given an instance R and an allocation \({\mathcal {W}}\), the normalized egalitarian welfare (NEW) of \({\mathcal {W}}\) is defined as
For a mechanism \({\mathcal {M}}\) and parameters n and \(\alpha\), the guaranteed normalized egalitarian welfare (GNEW) of \({\mathcal {M}}\) with respect to n and \(\alpha\) is defined as
where the infimum is taken over all instances with n agents and parameter \(\alpha\).
In other words, the GNEW of \({\mathcal {M}}\) with respect to n and \(\alpha\) is the smallest normalized utility of an agent for her piece allocated by \({\mathcal {M}}\), taken over all instances with parameters n and \(\alpha\). For example, if a mechanism always allocates a fixed piece of length \(\alpha\) regardless of the agents’ utility functions, then its GNEW with respect to any n and \(\alpha \in (0,1)\) is 0. We first present a tight upper bound on the GNEW.
for any mechanism \({\mathcal {M}}\). Moreover, for each inequality, there exists a mechanism \({\mathcal {M}}\) such that the inequality is tight.
Proof
The lower bound of 0 holds trivially, and is achieved by the mechanism discussed before the proposition.
For the upper bound, note that if some agent i values the whole cake (i.e., \(A_i = [0, 1]\)), then \(u_i([0,1]) = 1\) and \(u_i(W_i) \le \alpha\), so no mechanism can achieve GNEW larger than \(\alpha\). The tightness follows from a mechanism that, given any instance, divides the cake into intervals using all breakpoints, chooses an (arbitrary) \(\alpha\) fraction from each interval, and sets \(W_i = W\) for all i—this results in \({\widehat{u}}_i(W_i)=\alpha\) for all i. \(\square\)
Our next result gives the precise GNEW of the leximin solution.
For the upper bound, consider the instance R with \(A_i = [(i-1)\alpha /n,i\alpha /n]\) for \(i=1,\ldots ,n-1\), and \(A_n = [(n-1)\alpha /n,1]\). Every leximin allocation W gives a desired cake of length \(\alpha /n\) to every agent, so
We now prove the lower bound. Since the mechanism can allocate length \(\alpha\) of the cake and there are n agents, it can give every agent i a utility of at least \(\min \{\alpha /n, \ell (A_i)\}\). Hence, all leximin allocations give each agent i at least this much utility. If an agent has \(\ell (A_i)\le 1 - (n-1)\alpha /n\), the normalized utility of this agent is at least \(\frac{\alpha /n}{1-(n-1)\alpha /n} = \frac{\alpha }{n-(n-1)\alpha }\). Else, suppose that \(\ell (A_i) = 1 - (n-1)\alpha /n + x\) for some \(x > 0\). In this case, no matter how the mechanism allocates length \(\alpha\) of the cake, the (unnormalized) utility of this agent is at least
where the inequality follows from the fact that the expression on the left-hand side is non-decreasing for \(x\in [0,\infty )\). \(\square\)
Theorem 4.3 shows that the leximin solution achieves a non-trivial GNEW. However, it is unclear how good this GNEW is compared to that of other excludably truthful mechanisms. We will therefore show that the solution attains the highest possible GNEW among all excludably truthful mechanisms satisfying a natural condition. Given a vector of piecewise uniform density functions \({\textbf{f}} = (f_1,\ldots ,f_n)\), let \(L_{\textbf{f}}\) be a vector with \(2^n\) 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 \(L_{\textbf{f}}\) 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 \(\emptyset\), \(\{1\}\), \(\{2\}\), and \(\{1, 2\}\), respectively.
Definition 4.5
(Position obliviousness) A mechanism \({\mathcal {M}}\) is position oblivious if the following holds:
Let \({\textbf{f}}\) and \({\textbf{f}}'\) be any vectors of density functions such that \(L_{\textbf{f}} = L_{{\textbf{f}}'}\), and let R and \(R'\) be instances represented by these respective vectors and a given parameter \(\alpha\). If \({\mathcal {M}}(R) = (W,W_1,\ldots ,W_n)\) and \({\mathcal {M}}(R') = (W',W_1',\ldots ,W_n')\), then \(u_i(W_i) = u_i'(W_i')\) for every \(i\in N\).
Position obliviousness has previously been studied by Bei et al. (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.9 We provide two examples of mechanisms that are truthful (even without blocking) but not position oblivious:
A mechanism that returns a fixed piece of cake of length \(\alpha\), for example the piece \([0,\alpha ]\);
A mechanism that considers \(B: = A_1\cup A_2\cup \dots \cup A_n\), returns B if \(\ell (B) \le \alpha\), and returns the leftmost subset of B of length \(\alpha\) otherwise.
Theorem 4.6
Let \({\mathcal {M}}\) be an excludably truthful and position oblivious mechanism. Then, for all \(n\ge 1\) and \(\alpha \in (0,1)\),
Assume for the sake of contradiction that there exists an excludably truthful and position oblivious mechanism \({\mathcal {M}}\) with \(\text {GNEW}_{n,\alpha }({\mathcal {M}}) = \frac{\alpha }{n - (n-1)\alpha } + \delta\) for some \(\delta > 0\). For each \(i \in N\), let \(C_i\) be a piece of length \(\ell (C_i) = \alpha /n + \varepsilon\) such that \(C_i \cap C_j = \emptyset\) for every pair \(i, j \in N\), where \(\varepsilon > 0\) is such that
Consider an instance R where \(A_i = C_i\) for all \(i \in N\). Since \({\mathcal {M}}\) can allocate length at most \(\alpha\) of the cake, it must return an allocation for which some agent receives utility at most \(\alpha / n\). Assume without loss of generality that \({\mathcal {M}}\) returns an allocation \({\mathcal {W}}\) with \(u_1(W_1) \le \alpha / n\). See Fig. 4 for an illustration.
Fig. 4
Illustration for the proof of Theorem 4.6 with \(n = 3\)
×
Next, consider an instance \(R'\) where \(A_i' = C_i\) for all \(i \in N {\setminus } \{1\}\) and \(A_1' = [0, 1] {\setminus } \bigcup _{i \in N {\setminus } \{1\}} C_i\). (We use the notation \(A_i'\) for instance \(R'\) to distinguish from \(A_i\) for instance R.) For this instance, we have \(\ell (A_1') = 1 - (n-1) \cdot (\alpha / n + \varepsilon )\). Let \({\mathcal {W}}' = {\mathcal {M}}(R')\), and let \(Y = W_1' \cap A_1'\). By the definition of GNEW, we have \(u_1(W_1') / u_1([0, 1]) \ge \text {GNEW}_{n,\alpha }({\mathcal {M}})\), where \(u_1\) here is defined according to \(R'\). Equivalently,
which is strictly larger than \(\alpha /n\) by our choice of \(\varepsilon\).
Finally, consider an instance \(R''\) where \(A_i''=C_i\) for all \(i \in N {\setminus } \{1\}\), while \(A_1''\) is a subset of \([0, 1] {\setminus } \bigcup _{i \in N {\setminus } \{1\}} C_i\) of length \(\ell (A_1'') = \alpha / n + \varepsilon\) such that \(\ell (A_1''\cap Y) > \alpha /n\). Since \({\mathcal {M}}\) is position oblivious, by comparing instances \(R''\) with R, agent 1 must also get a utility of at most \(\alpha / n\) in instance \(R''\). However, if the agent reports \([0, 1] {\setminus } \bigcup _{i \in N {\setminus } \{1\}} C_i\) as in \(R'\), she gets a utility of \(\ell (A_1''\cap Y) > \alpha /n\). This means that \({\mathcal {M}}\) is not excludably truthful and yields the desired contradiction. \(\square\)
Comparing this ratio with the highest possible ratio of \(\alpha\) without the excludable truthfulness condition (Proposition 4.2),10 one can see that adding the excludable truthfulness requirement incurs a (multiplicative) “price” of \(n - (n-1)\alpha\) on the best GNEW. This price can be as large as n when \(\alpha\) is close to 0, and decreases to 1 as \(\alpha\) approaches 1.
An interesting question is whether Theorem 4.6 holds even without position obliviousness.
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.
Proof
We proceed in a similar manner as in the proof of Proposition 3.1. Assume for contradiction that two MNW allocations, W and \(W'\), give some agent different utilities. Since the utility of every agent in an MNW allocation is strictly positive, we have \(u_i(W), u_i(W') > 0\) for all \(i\in N\). Let \(W''\) be an allocation such that for each pair of consecutive breakpoints, the amount of cake between those breakpoints included in \(W''\) is the average of the corresponding amounts for W and \(W'\). By linearity, \(W''\) is a feasible allocation, and \(u_i(W'') = \frac{1}{2}(u_i(W) + u_i(W'))\) for every \(i\in N\).
Recall that by the arithmetic–geometric mean inequality, it holds that \(\frac{x+y}{2}\ge \sqrt{xy}\) for all positive real numbers x, y, with equality if and only if \(x = y\). We therefore have
where the inequality is strict because \(u_i(W)\ne u_i(W')\) for at least one i. Since \(\prod _{i\in N}u_i(W) = \prod _{i\in N}u_i(W')\), this implies that \(W''\) has a higher Nash welfare than both W and \(W'\), yielding the desired contradiction. \(\square\)
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 \(\alpha\) 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.
Proof
Fix an instance with two agents, and let \(X = A_1\cap A_2\) and \(x=\ell (X)\). If \(x \ge \alpha\), then an allocation W is leximin if and only if \(W\subseteq X\), and the same holds for MNW. Similarly, if \(\ell (A_1 \cup A_2) \le \alpha\), the relevant condition for both leximin and MNW is \(A_1\cup A_2\subseteq W\).
Assume now that \(x< \alpha < \ell (A_1 \cup A_2)\). Since both the leximin and MNW solutions satisfy Pareto optimality, we must have \(\ell (W) = \alpha\) and \(X \subseteq W\) in any leximin or MNW allocation W. In other words, the entire intersection of length x must be allocated, along with a further length \(\alpha -x\) of the cake. Let \(\Delta _1 = A_1{\setminus } A_2\) and \(\Delta _2 = A_2{\setminus } A_1\), and consider two cases.
Case 1: \(\min \{\ell (\Delta _1), \ell (\Delta _2)\} \ge (\alpha -x)/2\). In this case, for both leximin and MNW, the length \(\alpha -x\) must be split equally between \(\Delta _1\) and \(\Delta _2\)—otherwise the allocation can be improved with respect to both the leximin ordering and the Nash welfare by splitting the length equally. Conversely, any allocation that splits the length \(\alpha -x\) equally between \(\Delta _1\) and \(\Delta _2\) is both leximin and MNW.
Case 2: \(\min \{\ell (\Delta _1), \ell (\Delta _2)\} < (\alpha -x)/2\). Assume without loss of generality that \(\ell (\Delta _1) < (\alpha -x)/2\). Since
we have \(\ell (\Delta _2) > (\alpha -x)/2\). In this case, the entire \(\Delta _1\) must be allocated—otherwise the allocation W can be improved with respect to both the leximin ordering and the Nash welfare by allocating \(\varepsilon\) more of \(\Delta _1\) and \(\varepsilon\) less of \(\Delta _2\), for any \(0< \varepsilon < \ell (\Delta _1{\setminus } W)\). Conversely, any allocation that allocates the entire \(\Delta _1\) and length \(\alpha -x-\ell (\Delta _1)\) of \(\Delta _2\) is both leximin and MNW.
The desired conclusion follows from the two cases. \(\square\)
Theorems 3.3 and 5.2 together imply the following corollary. Since tie-breaking is unimportant due to Proposition 5.1, we assume that ties are broken in any consistent manner.
Corollary 5.3
For two agents, the MNW solution is excludably truthful.
When \(n\ge 3\), the two mechanisms are no longer equivalent. This can be seen from the instance with \(A_1=[0,1/2]\) and \(A_i=[1/2,1]\) for all \(2\le i\le n\), and \(\alpha = 1/2\). The leximin solution selects length 1/4 from each half of the cake, while MNW selects length \(\frac{1}{2n}\) from the first half and \(\frac{n-1}{2n}\) from the second half. For our main result of this section, we demonstrate that the MNW solution is not excludably truthful even when an agent is only allowed to report a subset of her true desired piece—as discussed in Sect. 1.1, this strengthens the corresponding result of Aziz et al. (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 excludably truthful under subset reporting.
Proof
Assume for convenience that the cake is represented by the interval [0, 8]; this can be trivially scaled back down to [0, 1]. In our original instance, there are six agents whose utility functions are given as follows:
First, observe that in this instance, every (non-integer) point is valued by exactly three agents. Hence, for any subset W of the cake with \(\ell (W)\le 2\), we have \(\sum _{i=1}^6 u_i(W)\le 6\). By the inequality of arithmetic and geometric means (AM-GM), it holds that \(\prod _{i=1}^6 u_i(W) \le 1\). By choosing \(W=[0,2]\), we obtain \(u_i(W)= 1\) for each i, so this choice of W maximizes the Nash welfare as \(\ell (W) = 2\) and \(\prod _{i=1}^{6} u_i(W_i) = 1\), and gives agent 1 a utility of 1. By Proposition 5.1, agent 1 receives utility 1 in every MNW allocation.
Next, consider a modified instance where agent 1 reports \(A_1 = [2,8]\), which is a strict subset of the true \(A_1\). Consider an MNW allocation W for this instance, and let \(x:=\ell (W\cap [2,8])\), \(y:= \ell (W\cap [1,2])\), and \(z:=\ell (W\cap [0,1])\), so \(x+y+z\le 2\). Let \(W'\) be an allocation such that \(\ell (W'\cap [0,1]) = 2-x-y\ge z\), \(\ell (W'\cap [1,2]) = y\), and \(|W'\cap [j,j+1]| = x/6\) for \(j\in \{2,3,\ldots ,7\}\). Notice that \(\ell (W') = 2\), so \(W'\) is a feasible allocation. We claim that \(\prod _{i=1}^6 u_i(W') \ge \prod _{i=1}^6 u_i(W)\). Indeed, letting \(\tau := \ell (W\cap [2,5])\), we have
where the first inequality follows from the AM-GM inequality. Similarly, letting \(\theta := \ell (W\cap ([2,3]\cup [5,6]))\) and \(\rho := \ell (W\cap ([3,4]\cup [6,7]))\), it holds that
Moreover, since \(u_1(W) = u_1(W') = x\), it follows that \(\prod _{i=1}^6 u_i(W') \ge \prod _{i=1}^6 u_i(W)\), as claimed. This means that \(W'\) is also an MNW allocation. The Nash welfare of \(W'\) is
In order to show that MNW is not excludably truthful regardless of tie-breaking, by Proposition 5.1, it suffices to show that the maximum of this expression in the domain \(x,y\ge 0, x+y\in [0,2]\) is attained when \(x > 1\), since this would imply that agent 1 has a profitable deviation.
Let \(g(x,y):= x\left( 2-\frac{x}{2}-y\right) ^2\left( y+\frac{x}{3}\right) ^3\), where \(x,y\ge 0\) and \(x+y\le 2\). We have \(g(1.5,0.5) = 0.84375\). Now, from the AM-GM inequality,
The derivative of the last expression is \(\left( \frac{6-3x}{5}\right) \left( \frac{6-x/2}{5}\right) ^4\), which is nonnegative for \(0\le x\le 2\). This means that for \(x\le 1\), we have
so \(g(x,y)\le \frac{4}{9}\cdot (1.1)^5< 0.72 < g(1.5,0.5)\). It follows that the maximum of g(x, y) is attained when \(x > 1\), as desired. \(\square\)
We remark here that even if we allow the MNW solution to choose any \(W_i\) such that \(W\cap A_i\subseteq W_i\subseteq W\) instead of always choosing \(W_i = W\cap A_i\) (that is, the mechanism may give agent i some parts of W that she does not value, along with all parts of W that she values), our example in Theorem 5.4 still shows that any resulting mechanism is not excludably truthful under subset reporting.
From the fairness perspective, we show later in Theorem 7.6 that the MNW solution achieves the same GNEW as the leximin solution (and the two solutions also share a common worst-case instance). However, the fact that the MNW solution is prone to a particularly simple form of manipulation makes it an unsuitable choice when truthfulness is essential.
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 most of 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. In this section, we consider mechanisms without the blocking ability. When no blocking is allowed, given an input instance, a mechanism \({\mathcal {M}}\) simply chooses a piece of cake W with \(\ell (W) \le \alpha\), and each agent i receives a utility of \(u_i(W) = \ell (W \cap A_i)\).
First, we observe that while the leximin solution is excludably truthful (Theorem 3.3), it is not truthful in the absence of blocking.
Example 6.1
(Leximin is not truthful without blocking) Let \(\alpha = 1/2\). First, consider an instance R with two agents whose utility functions are given as follows:
Assume without loss of generality that the tie-breaking rule chooses \(W = [1/4, 3/4]\). Next, consider an instance \(R'\) with the following utility functions:
Agent 1 receives a utility of 3/8 in every leximin allocation for \(R'\). However, if agent 1 misreports that \(A_1 = [0, 1/2]\), the instance becomes the same as R, and agent 1 receives a utility of 1/2 from the allocation W.
Our main result of this section shows that Example 6.1 is in fact not a coincidence.
Theorem 6.2
Without blocking, for every \(\alpha \in (0, 1)\), no truthful, Pareto optimal, and position oblivious mechanism can achieve a positive GNEW even in the case of two agents.
We assume for contradiction that there exists some \(\alpha \in (0, 1)\) and a truthful, Pareto optimal, and position oblivious mechanism \({\mathcal {M}}\) with \(\text {GNEW}_{2,\alpha }({\mathcal {M}}) > 0\). We consider a sequence of instances with two agents, which we illustrate in Fig. 6. 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 \({\mathcal {M}}\) must allocate length exactly \(\alpha\) of the cake.
Instance \(R^1\): \(A^1_1 = [0, 0.5], A^1_2 = [0.5, 1]\). Let \({\mathcal {M}}(R^1) = W^1\). Because \(\alpha < 1\), at least one of the agents will not obtain her maximum utility of 0.5. Assume without loss of generality that \(\ell (A^1_1 \cap W^1) = x < 0.5\); in other words, \(A^1_1 \setminus W^1\) is nonempty. Since \({\mathcal {M}}\) has a positive GNEW, it must hold that \(0< x < \alpha\).
Instance \(R^2\): \(A^2_1 = [0, 0.5], A^2_2 = W^1 \cup [0.5, 1]\). Let \({\mathcal {M}}(R^2) = W^2\). We must have \(W^2 \subseteq A^2_2\); in other words, agent 2 will receive utility \(\alpha\). This is because otherwise, agent 2 can benefit by reporting \({A^2_2}' = [0.5, 1]\) and the instance becomes \(R^1\), in which case agent 2 will receive utility \(\alpha\) from the output allocation \(W^1\). Note that because \(W^2\) is contained entirely in \(A^2_2\), we still have \(\ell (A^2_1 \cap W^2) \le x\).
Instance \(R^3\): \(A^3_1 = [0, 0.5] \setminus W^1, A^3_2 = W^1 \cup [0.5, 1]\). Let \({\mathcal {M}}(R^3) = W^3\). By the positive GNEW, we have \(\ell (A^3_1 \cap W^3) = y > 0\).
Instance \(R^4\): \(A^4_1 = \left( [0, 0.5] \setminus W^1\right) \cup B, A^4_2 = W^1 \cup [0.5, 1]\), where B is an interval of length x contained in \(A^3_2\) with the largest intersection with \(W^3\). That is,
if \(\ell (A^4_2 \cap W^3) \ge x\), let B be any subset of \(A^4_2 \cap W^3\) of length x;
if \(\ell (A^4_2 \cap W^3) < x\), let B be any interval of length x that contains \(A^4_2 \cap W^3\).
Let \({\mathcal {M}}(R^4) = W^4\). In this instance, we must have \(u_1(W^4) > x\). This is because otherwise, agent 1 can benefit by reporting \({A^4_1}' = [0, 0.5] \setminus W^1\) and the instance becomes \(R^3\), in which case agent 1 will obtain a utility of \(x + y\) (when \(\ell (A^4_2 \cap W^3) \ge x\)) or a utility of \(\alpha\) (when \(\ell (A^4_2 \cap W^3) < x\)). In both cases this value is strictly larger than x.
Finally, observe that instances \(R^2\) and \(R^4\) have the same \(L_{\textbf{f}}\) vector. In particular, we have \(\ell (A^2_1) = \ell (A^4_1) = 1/2\), \(\ell (A^2_2) = \ell (A^4_2) = 1/2+x\), and \(\ell (A^2_1 \cap A^2_2) = \ell (A^4_1 \cap A^4_2) = x\). This means that each agent should receive the same utility in these two instances from our position oblivious mechanism \({\mathcal {M}}\). However, agent 1 receives utility at most x in \(R^2\) and utility strictly larger than x in \(R^4\). We have reached a contradiction. \(\square\)
Interestingly, a recent result by Brandl et al. (2021) in the fair mixing setting implies that position obliviousness can be dropped from Theorem 6.2 if there are \(n\ge 6\) agents. More specifically, Brandl et al. showed that no rule satisfies Pareto optimality, truthfulness, and “positive share”—the last condition is essentially the same as the GNEW being positive. By using the connection between fair mixing and cake sharing outlined in Sect. 1.2, we obtain the following corollary.
Corollary 6.3
(Brandl et al. 2021) Without blocking, no truthful and Pareto optimal mechanism can achieve a positive GNEW if there are \(n\ge 6\) agents.
Nevertheless, our Theorem 6.2 maintains two key advantages over Corollary 6.3:
Theorem 6.2 already holds for the most basic case of \(n = 2\) agents, while Corollary 6.3 requires \(n\ge 6\). Moreover, Brandl et al. noted that the bound \(n\ge 6\) is tight for their result; in other words, their impossibility turns into a possibility if \(n\le 5\). This means that our result for \(n = 2\) (as well as any result for \(n\le 5\)) cannot be implied by a corresponding result from fair mixing.
Brandl et al.’s proof is extremely long and requires inspecting 386 instances. By contrast, our proof of Theorem 6.2 is much shorter and involves only 4 instances, thereby making it considerably easier to understand and verify by hand.
While position obliviousness can be dropped from Theorem 6.2 (if we assume \(n\ge 6\)), truthfulness cannot: leximin is Pareto optimal, position oblivious, and has a positive GNEW. We do not know whether Pareto optimality is necessary for the theorem to hold.
7 Justified representation notions
In multiwinner voting, where the goal is to choose a certain number of candidates from the available candidates (Faliszewski et al. 2017; Lackner and Skowron 2023), a desideratum that has received significant attention in recent years is justified representation (JR) (Aziz et al. 2017). If there are n agents with approval preferences over the candidates and k candidates are to be chosen, JR demands that whenever at least n/k agents approve a common candidate, at least one of these agents is represented in the selected set of candidates (usually referred to as a committee). Two important strengthenings of JR have been proposed:
A committee is said to provide proportional justified representation (PJR) (Sánchez-Fernández et al. 2017) if for every positive integer r and every set of agents \(N^*\subseteq N\) such that \(|N^*| \ge r\cdot n/k\) and the agents in \(N^*\) commonly approve r candidates, at least r candidates in the committee are approved by at least one of these agents.
A committee is said to provide extended justified representation (EJR) (Aziz et al. 2017) if for every positive integer r and every set of agents \(N^*\subseteq N\) such that \(|N^*| \ge r\cdot n/k\) and the agents in \(N^*\) commonly approve r candidates, some agent in \(N^*\) has at least r approved candidates in the committee.
It follows directly from the definitions that EJR implies PJR, which in turn implies JR. Aziz et al. (2017) showed that a committee providing EJR (and therefore PJR and JR) always exists.
In this section, we discuss how these notions can be adapted to our cake sharing setting, and how leximin and MNW perform with respect to the resulting notions. First, observe that since there is no discrete unit of candidate in our setting, JR does not have a clear analog in cake sharing. By contrast, both PJR and EJR admit natural adaptations. Since we do not address truthfulness in this section, we ignore the issue of blocking and assume that an allocation is simply a piece of cake W with \(\ell (W) \le \alpha\).
Definition 7.1
(PJR) Given an instance, an allocation W with \(\ell (W) \le \alpha\) is said to provide proportional justified representation (PJR) if for every positive real number t and every set of agents \(N^*\subseteq N\) such that \(|N^*| \ge t\cdot n/\alpha\) and \(\ell \left( \bigcap _{i \in N^*} A_i\right) \ge t\), it holds that \(\ell \left( W \cap \left( \bigcup _{i \in N^*} A_i \right) \right) \ge t\).
Definition 7.2
(EJR) Given an instance, an allocation W with \(\ell (W) \le \alpha\) is said to provide extended justified representation (EJR) if for every positive real number t and every set of agents \(N^*\subseteq N\) such that \(|N^*| \ge t\cdot n/\alpha\) and \(\ell \left( \bigcap _{i \in N^*} A_i\right) \ge t\), it holds that \(\ell (W\cap A_{j}) \ge t\) for some \(j \in N^*\).
As in the discrete setting, it is clear that EJR implies PJR. A mechanism is said to satisfy PJR (resp., EJR) if it outputs an allocation that provides PJR (resp., EJR) for every instance.
Since leximin ignores the size of the support of any particular preference, it can be easily shown to violate both axioms.
Proposition 7.3
The leximin solution satisfies neither PJR nor EJR.
Proof
Since PJR is implied by EJR, it suffices to prove the statement for PJR. Let \(n\ge 3\), and consider an instance with \(A_1 = [0, 1/2]\) and \(A_i = [1/2, 1]\) for all \(2 \le i \le n\). The leximin solution selects length \(\alpha / 2\) from each half of the cake. Choose t such that
this choice is always possible as \(\alpha \in (0,1)\). Since \(n - 1 \ge t \cdot n/\alpha\) and agents \(2,\ldots ,n\) commonly approve a piece of cake of length \(1/2 \ge t\), PJR dictates that a piece of length at least t must be selected from [1/2, 1]. However, leximin selects length \(\alpha /2 < t\) from this interval. \(\square\)
Next, we show that MNW satisfies both of the representation notions. This result can be seen as a continuous analog of Aziz et al. (2017)’s result that the Proportional Approval Voting (PAV) rule satisfies EJR in the discrete setting. Indeed, PAV assigns a utility of \(1 + \frac{1}{2}+\dots + \frac{1}{j} \approx \ln j\) to an agent whenever the agent approves j candidates in the committee, and chooses a committee that maximizes the sum of the agents’ utilities. Since maximizing a product is equivalent to maximizing the sum of the logarithms of its terms, PAV in multiwinner voting is closely related to MNW in cake sharing.
To aid the presentation of our proof, we introduce some definitions.
Definition 7.4
Given an instance and an allocation W, for every point x that is not included in W and is not a breakpoint, we define its Nash addition marginal as
where \(W_{\text {add}}\) is obtained by adding to W a piece of cake of length \(\varepsilon\) adjacent to the point x. Analogously, for every point x that is included in W and is not a breakpoint, we define its Nash removal marginal as
where \(W_{\text {remove}}\) is obtained by removing from W a piece of cake of length \(\varepsilon\) adjacent to the point x.
Intuitively, the Nash addition marginal is the rate of change of (the logarithm of) the Nash welfare when we add cake adjacent to a certain point. We do not define the Nash addition marginal for breakpoints because adding cake to the left and to the right of a breakpoint may yield different marginals. Similar statements hold for the Nash removal marginal.
Theorem 7.5
The MNW solution satisfies EJR and PJR.
Proof
Since EJR implies PJR, it suffices to establish the statement for EJR. Suppose for contradiction that MNW violates EJR for some instance with parameter \(\alpha\), and consider a value t and a set of agents \(N^*\) with \(|N^*| \ge t \cdot n/\alpha\) who commonly approve a piece of cake S with \(\ell (S) \ge t\) such that Definition 7.2 is not satisfied. Let W be the piece of cake chosen by MNW, and assume without loss of generality11 that \(\ell (W) = \alpha\). Since Definition 7.2 is violated, we have \(u_i(W) < t\) for all \(i\in N^*\).
Suppose that W is a disjoint union of the intervals \(I_1,\ldots ,I_m\), where each interval \(I_j\) is valued either entirely or not at all by each agent. We have that \(\ell (S) \ge t\), \(u_i(W) < t\) for every \(i\in N^*\), and all agents in \(N^*\) approve the entire piece of cake S. In particular, not all of S is contained in W. Let z be a point in \(S\setminus W\) that is not a breakpoint. The contribution of each agent \(i \in N^*\) to the Nash addition marginal at point z is \((\ln u_i(W))' = 1 / u_i(W)\). Thus,
note that when we take integrals, we can safely ignore breakpoints because they form a set of measure zero. Since \(\ell (W) = \alpha\), there exists a point \(y\in W\) whose Nash removal marginal is at most \(n/\alpha\). In particular, the Nash addition marginal at z is strictly greater than the Nash removal marginal at y. Hence, by adding a piece of cake of sufficiently small length \(\varepsilon > 0\) adjacent to z and removing a piece of cake of the same length adjacent to y, we obtain an allocation with a larger Nash welfare than W. This yields the desired contradiction. \(\square\)
Theorem 7.5 allows us to determine the GNEW of the MNW solution, which turns out to be the same as that of the leximin solution (Theorem 4.3).
For the upper bound, consider the same instance R as in Theorem 4.3: \(A_i = [(i-1)\alpha /n,i\alpha /n]\) for \(i=1,\ldots ,n-1\), and \(A_n = [(n-1)\alpha /n,1]\). By the inequality of arithmetic and geometric means, every MNW allocation W gives a desired cake of length \(\alpha /n\) to every agent, so
For the lower bound, as in the proof of Theorem 4.3, it suffices to show that MNW guarantees each agent \(i \in N\) a utility of at least \(\min \{\alpha /n, \ell (A_i)\}\). To this end, we fix an agent i and let \(t = \min \{\alpha /n, \ell (A_i)\}\). We have \(|\{i\}| = \frac{\alpha }{n} \cdot \frac{n}{\alpha } \ge t \cdot \frac{n}{\alpha }\) and \(\ell (A_i) \ge t\). Since the MNW solution satisfies EJR by Theorem 7.5, agent i must receive utility at least \(t = \min \{\alpha /n, \ell (A_i)\}\), as desired. \(\square\)
Next, we show that the MNW solution is the unique rule within a family of welfare-maximizer rules that satisfies either PJR or EJR.12
Definition 7.7
Let \(f:[0, 1] \rightarrow [-\infty , \infty )\) be a strictly increasing function which is differentiable in (0, 1). Given an instance, the f-welfare-maximizer rule chooses a piece of cake W with \(\ell (W)\le \alpha\) whose f-welfare, defined as the sum \(\sum _{i \in N} f(u_i(W))\), is maximized.
Note that the f-welfare-maximizer rule with \(f(x) = \ln x\) is equivalent to the MNW solution; the same is true for \(f(x) = c\ln x + d\) for any real constants \(c > 0\) and d. For all of these functions f, it holds that \(f'(x) = c/x\) for some constant c.
Theorem 7.8
Let \(f:[0, 1] \rightarrow [-\infty , \infty )\) be a strictly increasing function which is differentiable in (0, 1). If the f-welfare-maximizer rule satisfies PJR, then there exists a constant c such that \(f'(x) = c/x\) for all \(x\in (0,1)\). The same statement holds for EJR.
Proof
Since PJR is implied by EJR, it suffices to prove the theorem for PJR. Let f be such that the f-welfare-maximizer rule satisfies PJR.
First, we show that for all \(x,y > 0\) with \(x + y < 1\), it holds that
Suppose for contradiction that \(\frac{f'(x)}{f'(y)} \ne \frac{y}{x}\) for some such x, y. Assume without loss of generality that \(\frac{f'(x)}{f'(y)} > \frac{y}{x}\); otherwise, we can switch the roles of x and y. Let \(n_x\) and \(n_y\) be positive integers such that
We construct an instance as follows. Let \(\alpha = x + y < 1\). The cake is a union of two disjoint intervals: \(S_x\) with length \(\ell (S_x) = 1 - y > x\), and \(S_y\) with length \(\ell (S_y) = y\). The set of agents N is composed of two disjoint sets \(N_x\) and \(N_y\) with \(|N_x| = n_x\) and \(|N_y| = n_y\) (so \(n = n_x + n_y\)) such that the agents in \(N_x\) (resp., \(N_y\)) only approve the piece of cake \(S_x\) (resp., \(S_y\)). Since
$$\begin{aligned} |N_y| = n_y > y \cdot \frac{n_x + n_y}{x + y} = y \cdot \frac{n}{\alpha } \end{aligned}$$
and all agents in \(N_y\) approve a common piece of cake of length y, by the PJR condition, an allocation W chosen by the f-welfare-maximizer rule must include the entire piece \(S_y\). In addition, as \(\ell (S_x) > x\), W cannot include the entire piece \(S_x\). However, since \(n_x \cdot f'(x) > n_y \cdot f'(y)\), the f-welfare of W can be improved by including an \(\varepsilon\)-length more of \(S_x\) and an \(\varepsilon\)-length less of \(S_y\), for some sufficiently small \(\varepsilon > 0\). This contradicts the assumption that W maximizes the f-welfare among all allocations of length at most \(\alpha\), and therefore establishes (1).
Next, we extend (1) by showing that \(\frac{f'(x)}{f'(y)} = \frac{y}{x}\) for all \(x,y\in (0,1)\). Fix \(x,y\in (0,1)\), and let \(\varepsilon > 0\) be such that \(x + \varepsilon < 1\) and \(y + \varepsilon < 1\). From (1), we have \(\frac{f'(x)}{f'(\varepsilon )} = \frac{\varepsilon }{x}\) and \(\frac{f'(y)}{f'(\varepsilon )} = \frac{\varepsilon }{y}\). Dividing the first relation by the second yields \(\frac{f'(x)}{f'(y)} = \frac{y}{x}\).
Finally, we show that there exists a constant c such that \(f'(x) = c/x\) for all \(x\in (0,1)\). Fix \(b\in (0,1)\). For any \(x\in (0,1)\), we have \(\frac{f'(x)}{f'(b)} = \frac{b}{x}\), and so
Thus, we can take \(c = b \cdot f'(b)\). This completes the proof of the theorem. \(\square\)
To end this section, we strengthen Theorem 7.5 by adapting a fairness notion due to Aziz et al. (2020).
Definition 7.9
(AFS) Given an instance, an allocation W with \(\ell (W) \le \alpha\) is said to provide average fair share (AFS) if for every positive real number t and every set of agents \(N^*\subseteq N\) such that \(|N^*| \ge t\cdot n/\alpha\) and \(\ell \left( \bigcap _{i \in N^*} A_i\right) \ge t\), it holds that \(\sum _{i\in N^*} u_i(W) \ge |N^*|\cdot t\).
Since \(\sum _{i\in N^*} u_i(W) \ge |N^*|\cdot t\) implies that \(u_j(W) \ge t\) for at least one \(j\in N^*\), AFS is a strengthening of EJR. As with EJR and PJR, we say that a mechanism satisfies AFS if it outputs an allocation that provides AFS for every instance.
Theorem 7.10
The MNW solution satisfies AFS.
Proof
The proof is very similar to that of Theorem 7.5. Suppose for contradiction that MNW violates AFS for some instance with parameter \(\alpha\), and consider a value t and a set of agents \(N^*\) with \(|N^*| \ge t \cdot n/\alpha\) who commonly approve a piece of cake S with \(\ell (S) \ge t\) such that Definition 7.9 is not satisfied. Let W be the piece of cake chosen by MNW, and assume without loss of generality that \(\ell (W) = \alpha\). Since Definition 7.9 is violated, we have \(\sum _{i\in N^*}u_i(W) < |N^*|\cdot t\).
Suppose that W is a disjoint union of the intervals \(I_1,\ldots ,I_m\), where each interval \(I_j\) is valued either entirely or not at all by each agent. We have that \(\ell (S) \ge t\), \(\sum _{i\in N^*}u_i(W) < |N^*|\cdot t\), and all agents in \(N^*\) approve the entire piece of cake S. In particular, not all of S is contained in W. Let z be a point in \(S\setminus W\) that is not a breakpoint. The contribution of each agent \(i \in N^*\) to the Nash addition marginal at point z is \((\ln u_i(W))' = 1 / u_i(W)\). Thus,
where for the second inequality we apply the inequality of arithmetic and harmonic means. On the other hand, as in the proof of Theorem 7.5, there exists a point \(y\in W\) whose Nash removal marginal is at most \(n/\alpha\). In particular, the Nash addition marginal at z is strictly greater than the Nash removal marginal at y. Hence, by adding a piece of cake of sufficiently small length \(\varepsilon > 0\) adjacent to z and removing a piece of cake of the same length adjacent to y, we obtain an allocation with a larger Nash welfare than W. This yields the desired contradiction. \(\square\)
8 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 establish the leximin solution as an attractive mechanism due to its excludable truthfulness and its optimal guaranteed normalized egalitarian welfare (GNEW) among all excludably truthful and position oblivious mechanisms. On the other hand, we constructed an intricate example showing that the maximum Nash welfare (MNW) solution, which often exhibits desirable properties in other settings, fails to yield excludable 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 GNEW even in the case of two agents—in particular, this implies that the leximin solution is not truthful without blocking. Besides the properties that we have investigated, one could consider other desirable properties, e.g., from the multiwinner voting literature (Lackner and Skowron 2023).
In future research, it would be interesting to extend our cake sharing model to capture other practical scenarios.13 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 Appendix A, we show that a natural generalization of the leximin solution is still excludably truthful and achieves the optimal GNEW 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).14 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; Aumann and Dombb 2015; Bei et al. 2021)—are equally relevant and worthy of exploration in cake sharing as well.
Acknowledgements
This work was partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG23/20), by ARC Laureate Project FL200100204 on “Trustworthy AI”, by the Singapore Ministry of Education under grant number MOE-T2EP20221-0001, 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 Haris Aziz for suggesting Definition 7.9 and Theorem 7.10, Ilya Bogdanov for help with the proof of Theorem 5.4, and the anonymous reviewers of AAAI 2022 and Social Choice and Welfare for their valuable feedback.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
In this section, we consider an extension of our model where the cost of selecting the cake may be non-uniform. Specifically, there is a (public) cost function\(c:[0,1]\rightarrow {\mathbb {R}}_{\ge 0}\), which captures the cost for different parts of the cake. We assume that the cost function is piecewise constant, and without loss of generality that \(\int _0^1 c \mathop {}\!\textrm{d}x = 1\) (if the whole cake has cost 0, the mechanism can simply always choose the whole cake). Note that the main model of our paper corresponds to the cost function being the constant 1 over the entire cake. We still consider piecewise uniform utility functions of the agents, and allow the mechanism to choose a piece of cake with cost at most a given parameter \(\alpha \in (0,1)\).
First, we observe that in this more general setting, the leximin solution has a GNEW of 0.
Example A.1
Let \(\varepsilon \in (0, 1/2)\). Consider an instance R with \(\alpha = 1/2\), two agents such that \(A_1 = [0, \varepsilon ]\) and \(A_2 = [\varepsilon , 1]\), and the cost function c as follows:
In particular, the total cost of the interval \([0,\varepsilon ]\) is 1/2; the same is true for \([\varepsilon , 1]\).
In this instance, the leximin solution must choose an allocation W that includes the same length from each of \(A_1\) and \(A_2\)—this length y satisfies \(y\cdot \frac{1}{2\varepsilon } + y\cdot \frac{1}{2(1-\varepsilon )} = \frac{1}{2}\), i.e., \(y = \varepsilon (1-\varepsilon )\). Hence, the GNEW of leximin (for \(n = 2\) and \(\alpha = 1/2\)) is at most \(\frac{u_2(W)}{u_2([0,1])} = \frac{\varepsilon (1-\varepsilon )}{1-\varepsilon } = \varepsilon\). Since \(\varepsilon\) can be arbitrarily small, the GNEW is necessarily 0.
In spite of this negative example, we can adapt the leximin solution while maintaining both excludable truthfulness and the GNEW as follows. First, consider all breakpoints of the cost function, where the breakpoints are defined in the same way as for the utility functions. Then, for each piece of cake between two consecutive breakpoints, we choose a fraction of at most \(\alpha\) of this cake by implementing the canonical leximin solution with the same \(\alpha\). The adapted leximin solution then returns the union of the chosen cake. By linearity, the chosen cake has cost at most \(\alpha\).
Theorem A.2
For all \(n\ge 1\) and \(\alpha \in (0,1)\), when the cost function is piecewise constant, the adapted leximin solution is excludably truthful and has a GNEW of \(\frac{\alpha }{n-(n-1)\alpha }.\)
Proof
We first establish excludable truthfulness. The cost function is public and its breakpoints cannot be controlled by the agents, so we can consider the piece of cake between each pair of consecutive breakpoints separately. By Theorem 3.3, for each piece, reporting the utility function truthfully yields the highest utility to each agent. Since the utility for the whole cake is simply the sum of the utilities for different pieces, the mechanism is truthful.
The upper bound of the GNEW follows from Theorem 4.3 since the cost function in the current theorem is more general. For the lower bound, observe that by Theorem 4.3, for the piece of cake between each pair of consecutive breakpoints, each agent receives a utility of at least a fraction \(\frac{\alpha }{n-(n-1)\alpha }\) of her utility for this entire piece of cake. The desired bound then follows by linearity. \(\square\)
We remark that since we consider more general cost functions in this section, the GNEW of \(\frac{\alpha }{n-(n-1)\alpha }\) is still optimal by Theorem 4.6. However, unlike the canonical leximin solution, the adapted version is no longer Pareto optimal, since it may be possible to improve the utility of all agents by choosing more than an \(\alpha\) fraction in certain parts of the cake and less in other parts. An interesting question is therefore whether we can obtain Pareto optimality while preserving excludable truthfulness and the GNEW.
Alternatively, the constraint may be in terms of time instead of cache memory—imagine that the agents are choosing the parts of a 10-h TV series or soccer highlights to watch together at a 2-h party.
It follows from known results that the values \(t_i\) are of polynomial size; see the proof of Theorem 1 of Airiau et al. (2023) for a discussion of this point.
Note that this must be a strict leximin improvement in terms of utilities (i.e., not just due to tie-breaking). Indeed, Proposition 3.1 implies that agent i receives the same utility in all leximin allocations, whereas here we have \(u_i(W'; R) > u_i(W; R)\).
For example, the change from the vector (7, 2) to (3, 6) is a leximin improvement, so the change from (5, 2) to (3, 6) must also be a leximin improvement. Indeed, we have \((3,6)\succ (7,2)\succ (5,2)\).
If \(\ell (W) < \alpha\), this means that \(\ell \left( \bigcup _{i\in N}A_i\right) < \alpha\), and any allocation returned by the MNW solution trivially provides EJR.
After the conference version of our work was published, Lu et al. (2023) extended our model to an “(approval-based) voting with mixed goods” model, where the resource to be shared may consist of both cake and discrete goods.
A 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 \(\alpha\) is very close to 1, one of the agents will necessarily receive utility 0.