Fair Cake Division Under Monotone Likelihood Ratios

Introduction

Cake division is a quintessential model in the study of fair division. This setup captures the allocation of a divisible resource (metaphorically, the cake) among agents with equal entitlements, but distinct preferences. Over the past several decades, a significant body of work in mathematics, economics, and computer science has been devoted to cake cutting; see [BT96, RW98, Pro15] for excellent expositions and motivating applications (e.g., border negotiations and divorce settlements) of this framework.

Some of the central solution concepts and axiomatic characterizations in the fair-division literature stem from the cake-cutting context [Mou04]. Indeed, the work of Steinhaus, Banach, and Knaster [Ste48]—which lays the mathematical foundations of fair division—addresses cake division. The notion of envy-freeness was also mathematically formalized in this setup [GS58, Fol67]. This well-studied notion deems a cake division to be fair if every agent prefers the piece assigned to her over that of any other agent, i.e., if no agent is envious of others.

This work focuses on a standard formulation of cake division in which every agent must receive a contiguous piece of the cake. That is, the goal is to partition the cake $$into exactly$n$disjoint intervals (connected pieces) and assign them among the$n$participating agents. This connectivity requirement is naturally motivated by settings in which a contiguous part of the resource needs to be allocated to every agent [BT96]; consider, e.g., division of land, transmission spectrum, or processing time on a machine. Note that a partition of the cake$$into intervals$I_{1},I_{2},\ldots,I_{n}$—wherein interval$I_{i}$is assigned to agent$i\in[n]$—is said to be envy-free iff$v_{i}(I_{i})\geq v_{i}(I_{j})$(i.e., iff$\int_{I_{i}}f_{i}\geq\int_{I_{j}}f_{i}$) for all agents$i$and$j$.

The appeal of envy-freeness is substantiated by strong existential results: under mild assumptions, a contiguous envy-free cake division always exists [Str80, Sim80, Su99]. While these results are built upon interesting mathematical connections,For instance, the proof by Su [Su99] invokes Sperner’s lemma. they are, however, nonconstructive. In fact, Stromquist [Str08] has shown that there does not exist a finite-time algorithm for finding envy-free cake divisions with connected pieces; this result holds in a setup wherein the valuations are provided through an (adversarial) oracle. In addition, the work of Deng et al. [DQS12] establishes PPAD-hardness of finding envy-free cake divisions with contiguous pieces, under ordinal valuations.

Algorithms for envy-free cake division remain elusive even if we relinquish the contiguity requirement. It was not until the work of Brams and Taylor [BT95] that a bounded-time algorithm was obtained for noncontiguous envy-free cake division. In general, the best-known result for this problem is by Aziz and Mackenzie [AM16], who develop a hyper-exponential time algorithm for finding envy-free divisions with noncontiguous pieces.The problem of finding an approximate envy-free division (not necessarily with connected pieces) admits a fully-polynomial time approximation scheme [LMMS04].

In light of these algorithmic barriers, identification of computationally-tractable instances in the cake-cutting context stands as a meaningful direction of work. The current paper addresses this consideration and, in particular, identifies an encompassing property—called the monotone likelihood ratio property—which enables the development of efficient algorithms for fair cake-cutting (with connected pieces).

In the cake-division context, we will say that an ordered collection $(f_{i})_{i\in[n]}$ of value densities (of the $n$ agents) satisfies the monotone likelihood ratio property iff for each $i\in[n-1]$, the likelihood ratio $\nicefrac{{f_{i+1}(x)}}{{f_{i}(x)}}$ is nondecreasing in $x\in$. That is, the agents are indexed with the property that consecutive likelihood ratios bear MLRP. This property is transitive and, hence, in cake-division instances with MLRP, value densities $f_{i}$ and $f_{j}$ satisfy MLRP for all $i<j$.

Many distribution families are also known to bear MLRP [LM+01, CB02]. In particular, this property holds if all the value densities belong to any one of the following families: Gaussian distributions (with the same variance but different means), Poisson distributions, binomial distributions, and single-parameter exponentials; see Appendix C for details. Furthermore, it is known that linear translations of any log-concave function satisfy MLRP [SW14]. In particular, linear translations of the following (log-concave) distributions also satisfy this property: Laplace, uniform, multivariate Gaussian, gamma, beta, Subbotin, chi-square, Dirichlet, and logistic. Hence, the current work obtains novel results for many distribution families in a unified manner.

MLRP is a common assumption on agents’ utilities and type distributions in many economic contexts; see [Jew91] for a survey. As a stylized application of MLRP in cake division, consider a setting wherein each agent $i$ has a most preferred point $\mu_{i}$ on the divisible resource (cake) and $i$’s valuation density decreases as a Gaussian function (with a variance parameter that is common across the agents) of the distance from $\mu_{i}$. Indeed, the distance here can be geographical (as in case of land division), temporal (i.e., wait time), or it can be an abstract metric.

Considering similar single-peaked preferences, but with a linear drop in value densities, Wang and Wu [WW19] developed an efficient algorithm for noncontiguous cake division. Note that while linear densities bear MLRP, this property does not hold for piecewise linear densities. Hence our results do not directly address the setting considered in [WW19]. However, in absence of the contiguity requirement (as is the case in [WW19]) one can find a fair cake division by first partitioning the cake into intervals, in each of which the agents’ value densities are linear, and then applying the MLRP result separately.Recall that, in contrast to such a result, our focus is on finding cake divisions in which each agent receives a contiguous piece of the cake.

We focus on cake-division instances with MLRP and develop algorithmic results for almost all the standard notions of fairness and economic efficiency. Our algorithms only require oracle access to the valuations. In particular, the developed algorithms operate under the standard Robertson-Webb model [RW98], wherein we have access to the agents’ valuations through eval and cut queries; see Section 2 for details. MLRP implies that these cut and eval queries (functions) are $\lambda$-Lipschitz (Appendix A.3).

The time complexities of our algorithms depend polynomially on the the bit complexity of this Lipschitz constant $\lambda\geq 1$. Such a runtime dependency on $\log\lambda$ is unavoidable (Appendix D): there exist cake-division instances (with $\lambda$-Lipschitz cut and eval queries) wherein for all the agents the value of the cake is almost entirely concentrated in an interval $L$ of length ${1}/{\lambda}$. Here, an envy-free cake division can be obtained only by finely partitioning $L$ among the agents. In particular, the cut points that induce an envy-free allocation (and, hence, correspond to the output of a fair-division algorithm) must be $1/\lambda$ close to each other, i.e., the bit complexity of the output has to be ${\Omega}\left(\log\lambda\right)$. In fact, one can construct instances in which a contiguous envy-free division can be obtained only by cutting the cake at irrational points (Appendix D). Hence, in general, (and even under MLRP) one cannot expect an efficient algorithm that outputs an exact envy-free division, with contiguous pieces.Indeed, the bit complexity of a computationally-bounded algorithm is bounded as well. Therefore, when considering efficient algorithms for cake division, a precision loss in the output is inevitable. However, our algorithms ensure that this precision loss in value, $\eta$, is arbitrarily small; specifically, the developed algorithms run in time $\mathcal{O}\left({\rm poly}\left(n,\log\lambda,\log\frac{1}{\eta}\right)\right)$ and, hence, the precision parameter $\eta$ can be driven exponentially close to zero in polynomial (in the bit complexity of $\eta$) time. Note that this bit-precision issue is akin to the one faced in the convex-optimization problems (where again the optimal solutions can be irrational) and our runtime bound, with respect to the precision parameter $\eta$, is analogous to the one obtained by the ellipsoid method [GLS12].

Our Results and Techniques: Next, we summarize our results for various notions of fairness and (economic) efficiency.

Envy-Freeness: We prove that, given a cake-division instance (in the Robertson-Webb query model) with MLRP, an envy-free allocation can be computed, up to an arbitrary precision, in time that is polynomial in the number of agents and $\log\lambda$; here $\lambda$ is the Lipschitz constant of the Robertson-Webb (cut and eval) queries.

To establish this result, we define a class of divisions, referred to as ripple divisions (Definition 1), and prove that, under MLRP, every ripple division induces a contiguous envy-free cake division (Theorem 6). Specifically, a collection of points $x_{0}=0\leq x_{1}\leq x_{2}\leq x_{n-1}\leq x_{n}=1$ (in the cake $$) is said to form a ripple division of the cake if, for each$i\in[n-1]$, agent$i$is indifferent between the consecutive intervals$[x_{i-1},x_{i}]$and$[x_{i},x_{i+1}]$, i.e.,$v_{i}(x_{i-1},x_{i})=v_{i}(x_{i},x_{i+1})$. Note that a ripple division induces a contiguous cake division—by assigning interval$[x_{i-1},x_{i}]$to agent$i$—with the property that agent$i$does not envy agent$i+1$. That is, in and of itself, a ripple division mandates absence of envy only between consecutive agents, and not between all pairs of agents. We will show that, interestingly, under MLRP this relaxation suffices–the cake division induced by a ripple division is guaranteed to be envy free (Theorem 6). Recall that the agents are indexed following the MLRP order: for each$i\in[n-1]$, the likelihood ratio$f_{i+1}/f_{i}$is nondecreasing. Hence, allocating$[x_{i-1},x_{i}]$to agent$i\in[n]$ ensures that the intervals are assigned (left to right on the cake) in accordance with the MLRP order.

We establish the universal existence of ripple divisions through the intermediate value theorem, i.e., a one-dimensional fixed-point argument (Lemma 3). Since one can use binary search to find fixed points in the one-dimensional setting, this proof in fact leads to an algorithm for finding ripple divisions and, hence, envy-free divisions. Indeed, the notion of ripple divisions and their connection with envy-freeness, under MLRP, are two key contributions of this work.

Pareto Optimality: We show that in cake-division instances with MLRP, Pareto optimal cake divisions, with connected pieces, conform to the MLRP order (Lemma 5). This structural result implies that for maximizing welfare we can restrict attention to allocations wherein the intervals are assigned (left to right on the cake) in accordance with the MLRP order. Intuitively, this leads us to a welfare-maximizing algorithm—specifically, a dynamic program—that recursively finds optimal allocations for intervals placed at the left end of the cake (i.e., for intervals of the form $[0,x]$).

We also establish an extension of Weller’s theorem in the MLRP context. Weller’s theorem [Wel85] asserts that there always exists some cake division—though, not necessarily with connected pieces—which is both envy-free (fair) and Pareto optimal. While this theorem holds in general,Weller’s theorem applies even in the absence of MLRP. it does not guarantee that envy-freeness and Pareto optimality can be achieved together through contiguous cake divisions. We show that, by contrast, under MLRP every contiguous envy-free division is Pareto optimal (Theorem 2). Therefore, given a cake-division instance with MLRP, the allocation computed by our algorithm is not only envy-free but also Pareto optimal, up to an arbitrary precision.

Social Welfare: Social (utilitarian/Benthamite) welfare is a standard measure of collective value. For a cake division $\{I_{1},I_{2},\ldots,I_{n}\}$ it is defined to be the sum of the values that the division generates among the agents, $\sum_{i}v_{i}(I_{i})$. Maximizing social welfare is a well-studied objective in resource-allocation contexts. In the cake-cutting setup, this maximization problem is known to be APX-hard under general valuations [ABKR19]. Complementarily, if the value densities bear MLRP, then we can find (up to an arbitrary precision) a social welfare maximizing division with connected pieces in $\mathcal{O}\left({\rm poly}\left(n,\log\lambda\right)\right)$ time (Theorem 3). As mentioned previously, our algorithm for this problem is based on a dynamic program.

Egalitarian Welfare: The egalitarian (Rawlsian) welfare of a cake division $\{I_{1},\ldots,I_{n}\}$ is defined as the value of the least well-off agent, i.e., $\min_{i}\ v_{i}(I_{i})$. From a welfarist perspective, maximizing this minimum value among cake divisions with connected pieces is an important fairness objective. However, no nontrivial approximation guarantees are known for this problem under general valuations; the work of Aumann et al. [ADH13] shows that maximizing egalitarian welfare across all contiguous cake divisions is APX-hard. Complementing this hardness result, we develop an algorithm that, under MLRP, maximizes egalitarian welfare (up to an arbitrary precision) and runs in $\mathcal{O}\left({\rm poly}\left(n,\log\lambda\right)\right)$ time (Theorem 4).

Our algorithm for maximizing egalitarian welfare is based on a “moving-knife” procedure. This procedure, for a given a target value $\tau>0$, iteratively selects points $x_{0}=0,x_{1},x_{2},\ldots,x_{n}\leq 1$ such that the each interval $[x_{i-1},x_{i}]$ is of value $\tau$ to agent $i\in[n]$. Let $\tau^{*}$ denote the optimal egalitarian welfare in the given cake-division instance. The useful observation here is that this moving-knife procedure will succeed for all $\tau\leq\tau^{*}$. This follows from the fact that here the intervals are assigned (left to right) in the MLRP orderNote that the agents are indexed accordingly. and this ordering is also satisfied by an egalitarian welfare maximizing (in particular, a Pareto optimal) division. Therefore, by performing a binary search with $\tau$, we can find a contiguous division with egalitarian welfare arbitrarily close to the optimal.

Nash Social Welfare: A balance between social and egalitarian welfare is obtained by considering the Nash social welfare [NJ50, KN79]. This welfare objective is defined as the geometric mean of the agents’ values. It is known that, in general, it is APX-hard to find a contiguous cake division that maximizes Nash social welfare [ABKR19]. Under MLRP, however, the problem of maximizing Nash social welfare admits a fully polynomial-time approximation scheme (Theorem 5). We obtain this result via a dynamic program that considers the agents in the MLRP order.

Additional Related Work: Recently, approximation algorithms—with both additive [HGS19] and multiplicative [ABKR19] approximation guarantees—have been developed for finding contiguous envy-free cake divisions. The work of Brânzei and Nisan [BN17] develops query complexity upper and lower bounds for computing approximately envy-free allocations. In contrast to these results, the current work focuses on cake-division instances with MLRP and shows that in such settings arbitrarily low envy can be achieved among the agents.

The work of Bei et al. [BCH+12] also studies contiguous cake division and provides computational results for maximizing social welfare subject to proportional fairness. Under this fairness constraint each agent $i\in[n]$ must receive an interval of value at least $1/n$ times $i$’s total value for the cake. Bei et al. [BCH+12] show that, if the value densities are linear, then this problem admits a fully polynomial-time approximation scheme (FPTAS). We note that every pair of linear densities bear MLRP and, hence, such value-density functions fall within the purview of the current work. However, our algorithm is incomparable to the FPTAS of Bei et al. [BCH+12]–we focus on maximizing social welfare without the fairness constraints. Also, envy-freeness is not addressed in [BCH+12].

Another well-studied fairness notion is that of equitability. Specifically, a cake division $\{I_{1},I_{2},\ldots,I_{n}\}$ is said to be equitable iff all the agents derive the same value from the intervals assigned to them, $v_{i}(I_{i})=v_{j}(I_{j})$ for all $i$ and $j$ [DS61, Alo87]. In other words, equitability ensures that all the agents are equally well-off. Cechlárová and Pillárová [CP12] consider the computation of equitable cake divisions with connected pieces. They showed that—given access to “reverse” cutting queries—such divisions can be efficiently computed, up to an arbitrary precision. We note that value densities that satisfy MLRP have, by definition, full support over the cake. In such a case, the reverse cutting queries can be simulated by standard (cut) queries in the Robertson-Webb model. Hence, under MLRP, strong algorithmic results hold for equitability as well.

Cake-division algorithms for specific classes of valuations have been studied in [CLPP11] and [KLP13]. The work of Kurokawa et al. [KLP13] provides a query-efficient algorithm for envy-free, noncontiguous cake division under piecewise linear densities. Cohler et al. [CLPP11] also address the noncontiguous version of the problem, and for piecewise constant densities they develop a polynomial-time algorithm that computes an envy-free division with optimal social welfare. In contrast to these results our focus is on contiguous cake division.

Notation and Preliminaries

This work studies the problem of dividing a cake $$among$n$agents. Throughout, we will focus on a well-studied formulation of cake cutting which requires that each agent should receive a contiguous piece of the cake, i.e., the goal is to partition the cake$$into$n$pairwise disjoint intervals and assign them among the$n$ agents in a fair/efficient manner.

We additionally assume that the valuations are normalized such that the value of the entire cake is equal to one for every agent $i\in[n]$, i.e., $\int_{0}^{1}f_{i}(x)dx=v_{i}(0,1)=1$. Hence, the value-densities $f_{i}$s constitute probability density functions over the cake $$. We note that this is a standard assumption in the cake-cutting framework and we conform to it for the purpose of brevity. All of our results hold true, even otherwise.

For an allocation $\mathcal{I}=\{I_{1},\ldots,I_{n}\}$, the endpoints of the constituent intervals will be referred to as the cut points of $\mathcal{I}$, i.e., if $I_{i}=[x_{i-1},x_{i}]$ for $1\leq i\leq n$, then the cut-points are $\{x_{0}=0,x_{1},\ldots,x_{n}=1\}$.

We will throughout use the term allocation to specifically refer to partitions of the cake in which each agent receives a connected piece, i.e., receives exactly one interval. More generally, a cake division will be used to denote partitions of the cake $\mathcal{D}=\{D_{1},D_{2},\ldots,D_{n}\}$ in which agent $i$ receives $D_{i}$, a finite collection of intervals. Here, the bundles $D_{i}$s are pairwise disjoint and their union covers the entire cake $$.

In this work we develop algorithmic results for the following notions of fairness and economic efficiency.

Envy-Freeness: For a cake-division instance $\mathcal{C}$, an allocation $\mathcal{I}=\{I_{1},\ldots,I_{n}\}$ is said to be envy-free iif each agent prefers its own interval over that of any other agent, $v_{i}(I_{i})\geq v_{i}(I_{j})$ for all agents $i,j\in[n]$.

Pareto Optimality: Given a cake-division instance $\mathcal{C}$, a division $\mathcal{D}=\{D_{1},\ldots,D_{n}\}$ is said to Pareto dominate another division $\mathcal{C}=\{C_{1},\ldots,C_{n}\}$ iff $v_{i}(D_{i})\geq v_{i}(C_{i})$ for all agents $i\in[n]$ and, there exists at least one agent $k\in[n]$ such that $v_{k}(D_{k})>v_{k}(C_{k})$. Consequently, a cake division is said to be Pareto optimal iff it is not Pareto dominated by any other division.

Recall that a cake division refers to a partition of the cake in which agent receives a finite collection of intervals. By contrast, in an allocation each agent receives a single interval. The algorithms developed in this work compute allocations. Interestingly, though, the Pareto optimality guarantees achieved by our algorithms are stronger in the sense that optimality holds across all cake divisions; specifically, under MLRP, we establish that particular allocations are Pareto optimal not only among the set of all allocations but also among all cake divisions.

Finding allocations that maximize the above-mentioned welfare notions is known to be APX-hard, in general; see, e.g., [ADH13, ABKR19]. Complementing these negative results, a key contribution of this work is to identify a broad class of cake-division instances that admit strong algorithmic results for these welfare objectives and envy-freeness. Specifically, we focus on value densities (distributions) that satisfy the monotone likelihood ratio property (MLRP). We will next define this property and note that our results hold for multiple distribution families that satisfy MLRP.

In the cake-division context, we will say that a given collection $\{f_{i}\}_{i\in[n]}$ of value-density functions satisfies the monotone likelihood ratio property iff there exists an order $\pi\mathrel{\mathop{\mathchar 58\relax}}[n]\rightarrow[n]$, among the $f_{i}$s, such that, for all $i\in[n-1]$, the consecutive likelihood ratios $\frac{f_{\pi(i+1)}\ (x)}{f_{\pi(i)}\ (x)}$ are non-decreasing in $x\in$. That is, for each $i\in[n-1]$, the densities $f_{\pi(i)}$ and $f_{\pi(i+1)}$ bear MLRP over $$.

We will refer to this order $\pi$ as the MLRP order of the value densities. Lemma 9 (in Appendix A.2) shows that, given a cake-division instance in the Robertson-Webb query model, with the promise that the underlying value densities satisfy MLRP (i.e., given a promise problem), one can efficiently find the MLRP order $\pi$. Hence, without loss of generality, we will throughout assume that the $n$ agents are indexed such that $\pi$ is the identity permutation, i.e., for all $i\in[n-1]$, the likelihood ratio $\frac{f_{i+1}(x)}{f_{i}(x)}$ is non-decreasing in $x\in$.

It is relevant to note that, to be well defined, MLRP requires the value densities $f_{i}$s to be strictly positive over the cake $$. Hence, for cake-division instances$\langle[n],\{f_{i}\}_{i\in[n]}\rangle$with MLRP, we have$f_{i}(x)>0$for all$i\in[n]$and$x\in$.

Instantiations of MLRP: MLRP induces a total order on linear value densities $f_{i}(x)=a_{i}x+b_{i}$; see Appendix C for details. Hence, our results imply that if, in a cake-division instance, the value densities of all the agents are linear, then an envy-free (or welfare-maximizing) allocation can be computed efficiently.

Many other distribution families are also known to bear MLRP, e.g., Gaussian distributions (with the same variance), Poisson distributions, and single-parameter exponentials. Therefore, our algorithmic results address, in particular, cake-division instances wherein all the agents have Gaussian value densities with the same variance, but different means.

These instantiations substantiate the applicability of our algorithmic results which, through MLRP, address a wide range of cake-division instances.

Lipschitz Constant of Cut and Eval Queries: We say that the cut and eval queries in a cake-division instance are $\lambda$-Lipschitz iff the following inequalities hold for each agent $i\in[n]$:

It is worth pointing out that besides MLRP (and, hence, the positivity of the value densities), all the other assumptions made in this work are standard.

The time complexities of our algorithms depend polynomially on the the bit complexity of the Lipschitz constant $\lambda\geq 1$.In the case of linear value densities, $f_{i}(x)=a_{i}x+b_{i}$, the bit complexity of the Lipschitz constant $\lambda$ is proportional to the bit complexity of the coefficients $a_{i}$s and $b_{i}$s (Proposition 3). Hence, if linear densities are explicitly given as input, then we have a polynomial (in the input size) runtime bound. As mentioned previously, in general, such a runtime dependency on $\log\lambda$ is unavoidable; Appendix D provides an illustrative examples. Furthermore, it is possible—even with rational and MLRP value densities—that the exact envy-free/welfare-maximizing allocations are induced by irrational cuts (Appendix D). That is, in general, one cannot expect an efficient algorithm that outputs an exact envy-free (or welfare-maximizing) allocation. Therefore, when considering efficient algorithms for cake division, a precision loss is inevitable. However, our algorithms ensure that this loss is arbitrarily small. Specifically, given a cake-division instance $\mathcal{C}$ in which the value densities satisfy MLRP, we can find, in time that is polynomial in $\log(1/\eta)$ (along with $n$ and $\log\lambda$), an envy-free allocation $\mathcal{I}=\{I_{1},\ldots,I_{n}\}$ such that, $v_{i}(I_{i})\geq v_{i}(I_{j})-\eta$ for all agents $i,j\in[n]$. Since the precision parameter $\eta$ can be driven exponentially close to zero in polynomial (in the bit complexity of $\eta$) time, we will say that an envy-free allocation can be computed up to an arbitrary precision.

Similarly, in the context of maximizing welfare (social or egalitarian) welfare, given a cake-division instance wherein the value densities bear MLRP, we can find—in time that is polynomial in $\log(1/\eta)$—an allocation with the (social or egalitarian) welfare $\eta$ (additively) close to the optimal. Hence, as in the case of envy-freeness, we assert that a welfare-maximizing allocation can be computed efficiently, up to an arbitrary precision.

Main Results

This section presents the statements of our key results.

Envy-Freeness: In Section 5 we prove that for cake-division instances, in which the value densities satisfy MLRP, the problem of finding an envy-free allocation essentially admits a polynomial-time algorithm.

Recall that, under MLRP, the cut and eval queries are necessarily $\lambda$-Lipschitz (Proposition 3).

Pareto Optimality: Weller’s theorem [Wel85] asserts that there always exists some cake division (though, not necessarily with connected pieces) which is both envy-free and Pareto optimal (among all cake divisions, with or without connected pieces). We show that, in the context of MLRP, every envy-free allocation is in fact Pareto optimal (among all cake divisions). Therefore, for cake-division instances with MLRP, the allocation computed by our algorithm is not only envy-free (fair) but also Pareto optimal, up to an arbitrary precision.

Let $\mathcal{C}$ be a cake-division instance wherein the value-density functions satisfy the monotone likelihood ratio property. Then, every envy-free allocation in $\mathcal{C}$ is also Pareto optimal (over the set of all cake divisions).

Social Welfare: In Section 7 we show that, up to an arbitrary precision, a social welfare maximizing allocation can be computed efficiency under MLRP.

Egalitarian Welfare: Section 8 addresses the problem of maximizing egalitarian welfare. Specifically, we prove that, in cake-division instances with MLRP, an allocation with egalitarian welfare arbitrarily close to the optimal can be computed efficiently.

Nash Social Welfare: In Section 9 we show that, under MLRP, the problem of maximizing Nash social welfare admits a fully polynomial-time approximation scheme (FPTAS).

Implications of the Monotone Likelihood Ratio Property

This section provides useful implications of MLRP (Lemma 1). This result will be used in subsequent sections towards the analysis of our algorithms.

Let $f_{i}$ and $f_{j}$ be two (ordered) value-density functions that bear MLRP i.e., the likelihood ratios satisfy $\frac{f_{j}(b)}{f_{i}(b)}\leq\frac{f_{j}(c)}{f_{i}(c)}$ for all $0\leq b\leq c\leq 1$. Then, $f_{i}$ and $f_{j}$ satisfy the following two properties

The values of the intervals satisfy $\frac{\int\limits_{a}^{b}f_{j}}{\int\limits_{a}^{b}f_{i}}\leq\frac{\int\limits_{c}^{d}f_{j}}{\int\limits_{c}^{d}f_{i}}$ for all $[a,b],[c,d]\subseteq$ with $b\leq c$.

The (normalized) values satisfy $\frac{\int\limits_{x}^{b}f_{i}}{\int\limits_{a}^{b}f_{i}}\leq\frac{\int\limits_{x}^{b}f_{j}}{\int\limits_{a}^{b}f_{j}}$ for all intervals $[a,b]\subseteq$ and all $x\in[a,b]$.

Moreover, properties (i) and (ii) are equivalent.

Here, if the likelihood ratio $\frac{f_{j}(x)}{f_{i}(x)}$ is strictly increasing, then we have a strict inequality in the corresponding implications.

The proof of this lemma is delegated to Appendix A.1. Note that, in terms of the agents’ valuations $v_{i}$ and $v_{j}$, property (i) in Lemma 1 can be expressed as $\frac{v_{j}(a,b)}{v_{i}(a,b)}\leq\frac{v_{j}(c,d)}{v_{i}(c,d)}$ for all $[a,b],[c,d]\subseteq$ with $b\leq c$. Similarly, property (ii) corresponds to $\frac{v_{i}(x,b)}{v_{i}(a,b)}\leq\frac{v_{j}(x,b)}{v_{j}(a,b)}$ for all $[a,b]\subseteq$ and all $x\in[a,b]$.

It is well-known that MLRP implies first-order stochastic dominance (see Lemma 8). Interestingly, property (ii) provides a strengthening: over any interval $[a,b]$, the normalized (by $v_{j}(a,b)$) values of agent $j$ stochastically dominate the normalized (by $v_{i}(a,b)$) values of agent $i$.

Envy-Freeness

In this section we develop an efficient algorithm for finding envy-free allocations in cake division instances with MLRP (Theorem 1). Towards this goal, we define a class of cake divisions, referred to as ripple divisions (Definition 1), and prove that, under MLRP, every ripple division induces an envy-free allocation (Theorem 6). Existential and computational guarantees for ripple divisions are established in Section 5.1 (Lemma 3) and Section 5.2 (Lemma 4), respectively. Section 5.4 builds upon these results to prove our main result (Theorem 1) for envy-freeness.

We establish the universal existence of ripple divisions through the intermediate value theorem, i.e., a one-dimensional fixed-point argument (Lemma 3). Consequentially, for cake-division instances with MLRP, we develop an alternate proof of existence of envy-free allocations. Since one can use binary search to find fixed points in the one-dimensional setting, this proof in fact leads to an algorithm for finding ripple divisions and, hence, envy-free divisions.

Given a cake-division instance $\mathcal{C}=\langle[n],\{f_{i}\}_{i}\rangle$, a collection of points $x^{*}_{0}=0\leq x^{*}_{1}\leq\dots\leq x^{*}_{n-1}\leq x^{*}_{n}=1$ is said to form a ripple division of the cake iff

For establishing existence of ripple divisions, we first consider a relaxation of Definition 1 wherein do not enforce the last cut point (i.e., $x^{*}_{n}$) to be equal to one. Under this relaxation, the intervals $\{[x_{i-1},x_{i}]\}_{i=1}^{n}$ do not cover the entire interval $$(instead, they span$[0,x_{n}]$) and, hence, lead to a partial allocation of the cake.

Also, by convention, the agents are indexed following the MLRP order: for each $i\in[n-1]$, the likelihood ratio $f_{i+1}/f_{i}$ is nondecreasing. Hence, assigning interval $[x_{i-1},x_{i}]$ to agent $i\in[n]$ provides an allocation wherein the intervals are assigned (left to right on the cake) in accordance with the MLRP order. We will show that the (partial) allocation obtained by assigning interval $[x_{i-1},x_{i}]$ to agent $i\in[n]$ is envy-free (Theorem 6).

Given a cake-division instance $\mathcal{C}=\langle[n],\{f_{i}\}_{i}\rangle$, a collection of points $x_{0}=0\leq x_{1}\leq\dots\leq x_{n-1}\leq x_{n}\leq 1$ is said to form a $\delta$-ripple division of the cake iff $x_{n}\geq 1-\delta$ and

Both Definitions 1 and 2 require that, for all $i\in[n-1]$, agent $i$’s value for the $i$th interval ($[x^{*}_{i-1},x^{*}_{i}]$ and $[x_{i-1},x_{i}]$, respectively) is positive. Also, note that a -ripple division is an exact ripple division.

Next we use Lemma 2 and a limit argument ($\delta\to 0$) to establish universal existence of ripple divisions.

Let $\mathcal{C}$ be a cake-division instance in which the cut and eval queries are $\lambda$-Lipschitz. Then, $\mathcal{C}$ necessarily admits a ripple division.

Proof Lemma 2 asserts that, for any $\delta\in(0,1)$, there exists a collection of points $x^{\delta}_{0}=0<x^{\delta}_{1}<\ldots<x^{\delta}_{n-1}<x^{\delta}_{n}=1-\delta$ that form a $\delta$-ripple division. Note that here $x^{\delta}_{n}=1-\delta$. We consider the sequence of these $\delta$-ripple divisions, $\mathcal{S}\coloneqq\left\langle(x^{\delta}_{0},x^{\delta}_{1},\ldots,x^{\delta}_{n})\right\rangle_{\delta\in(0,1)}$.

Since $\mathcal{S}$ is a nonempty and bounded sequence in $^{n}$, the Bolzano-Weierstrass theorem ensures that $\mathcal{S}$ contains a convergent subsequence, say $\left\langle({x}^{\delta_{j}}_{0},{x}^{\delta_{j}}_{1},\dots,{x}^{\delta_{j}}_{n})\right\rangle_{\delta_{j}>0}$. Write $(x^{*}_{0},x^{*}_{1},\dots,x^{*}_{n})\in^{n}$ to denote the limit of this subsequence as $\delta_{j}$ tends to zero. We will show that the points $x^{*}_{0},x^{*}_{1},\ldots,x^{*}_{n}$ form a ripple division in $\mathcal{C}$ (see Definition 1), i.e., establish that $x^{*}_{n}=1$ and $v_{i}(x^{*}_{i-1},x^{*}_{i})=v_{i}(x^{*}_{i},x^{*}_{i+1})>0$ for all agents $i\in[n-1]$.

First, note that $x^{*}_{n}=1$, since the sequence $\langle 1-\delta_{j}\rangle\to 1$ as $\delta_{j}\to 0$. Also, $x^{*}_{0}=0$, since the constant sequence $\langle 0\rangle$ tends to .

We will next prove that $v_{i}(x^{*}_{i-1},x^{*}_{i})=v_{i}(x^{*}_{i},x^{*}_{i+1})$ for all agents $i\in[n-1]$. Given that the collection $\left({x}^{\delta}_{0},{x}^{\delta}_{1},\dots,{x}^{\delta_{j}}_{n}\right)$ forms a $\delta_{j}$-ripple division, we have $v_{i}({x}^{\delta_{j}}_{i-1},{x}^{\delta_{j}}_{i})=v_{i}({x}^{\delta_{j}}_{i},{x}^{\delta_{j}}_{i+1})$, for all $i\in[n-1]$.

2 Computation of Ripple Divisions

Let $\mathcal{C}=\langle[n],\{f_{i}\}_{i}\rangle$ be a cake-division instance in which the cut and eval queries are $\lambda$-Lipschitz. Then, for any $\delta\in(0,1)$ and in the Robertson-Webb query model, a $\delta$-ripple division of $\mathcal{C}$ can be computed in $\mathcal{O}\left({\rm poly}(n,\log\lambda,\log\frac{1}{\delta})\right)$ time.

3 From Ripple Divisions to Envy-Free Allocations

The next theorem establishes the crucial connection between ripple divisions and envy-freeness. In particular, setting $\delta=0$ in this theorem, we obtain that, under MLRP, every (exact) ripple division induces an envy-free allocation.

Let $\mathcal{C}=\langle[n],\{f_{i}\}_{i}\rangle$ be a cake-division instance in which the value densities satisfy the monotone likelihood ratio property and let parameter $\delta\geq 0$. Then, every $\delta$-ripple division, $x_{0}=0\leq x_{1}\leq\dots\leq x_{n-1}\leq x_{n}\leq 1$, in $\mathcal{C}$ induces an envy-free partial allocation $\{I_{i}=[x_{i-1},x_{i}]\}_{i=1}^{n}$.

This theorem asserts that here the partial allocation $\mathcal{I}=\{I_{1},\ldots,I_{n}\}$ (with $I_{i}=[x_{i-1},x_{i}]$) satisfies $v_{i}(I_{i})\geq v_{i}(I_{j})$, for all $i,j\in[n]$, and at most a $\delta$-length piece of the cake (specifically, $[x_{n},1]$) remains unallocated in $\mathcal{I}$.

Proof We will show that if the points $x_{0}=0\leq x_{1}\leq x_{2}\leq\ldots\leq x_{n}\leq 1$ form a $\delta$-ripple division, then the partial allocation $\{I_{i}=[x_{i-1},x_{i}]\}_{i=1}^{n}$ is envy-free. Here, the definition of a $\delta$-ripple division (Definition 2) ensures that, for each agent $i\in[n-1]$, the values the two consecutive intervals $I_{i}$ and $I_{i+1}$ are equal and positive

Recall that the agents are indexed following the MLRP order, i.e., for each $i\in[n-1]$, the likelihood ratio $f_{i+1}/f_{i}$ is nondecreasing. We fix an agent $i\in[n]$ and establish envy-freeness with respect to $i$ by considering two complementary cases (i) for agents to the left of $i$, we prove that $v_{i}(I_{1})\leq v_{i}(I_{2})\leq\ldots\leq v_{i}(I_{i})$ and (ii) for agents to the right of $i$, we prove that $v_{i}(I_{i})\geq v_{i}(I_{i+1})\geq\ldots\geq v_{i}(I_{n})$.

Case (i): Consider any agent $k\in[n]$ such that $k<i$. Given that $f_{k}$ and $f_{i}$ bear MLRP (i.e., $f_{i}/f_{k}$ is non-decreasing), property (i) of Lemma 1, with $a=x_{k-1}$, $b=c=x_{k}$, and $d=x_{k+1}$, gives us $\frac{v_{i}(x_{k-1},x_{k})}{v_{k}(x_{k-1},x_{k})}\leq\frac{v_{i}(x_{k},x_{k+1})}{v_{k}(x_{k},x_{k+1})}$. That is, for the intervals $I_{k}=[x_{k-1},x_{k}]$ and $I_{k+1}=[x_{k},x_{k+1}]$ we have

Instantiating equation (2) for agent $k$, we can simplify inequality (3) to $v_{i}(I_{k})\leq v_{i}(I_{k+1})$. Combining this inequality across all $k<i$, we obtain the desired chain of inequalities for agent $i$, i.e., $v_{i}(I_{1})\leq v_{i}(I_{2})\leq\ldots\leq v_{i}(I_{i})$.

Case (ii): Consider any agent $j\in[n]$ such that $j>i$ Given that $f_{i}$ and $f_{j}$ bear MLRP (i.e., $f_{j}/f_{i}$ is non-decreasing), property (i) of Lemma 1, with $a=x_{j-1}$, $b=c=x_{j}$, and $d=x_{j+1}$, gives us $\frac{v_{j}(x_{j-1},x_{j})}{v_{i}(x_{j-1},x_{j})}\leq\frac{v_{j}(x_{j},x_{j+1})}{v_{i}(x_{j},x_{j+1})}$. That is, for the intervals $I_{j}=[x_{j-1},x_{j}]$ and $I_{j+1}=[x_{j},x_{j+1}]$ we have

Instantiating equation (2) for agent $j$, we can simplify inequality (4) to $v_{i}(I_{j})\geq v_{i}(I_{j+1})$. Combining this inequality across all $j>i$, we obtain the desired chain of inequalities for agent $i$, i.e., $v_{i}(I_{i})\geq v_{i}(I_{i+1})\geq\ldots\geq v_{i}(I_{n})$.

The above two cases establish that agent $i\in[n]$ does not envy any other other agent, i.e., $\mathcal{I}=\{I_{1},\ldots,I_{n}\}$ is an envy-free partial allocation. Indeed, if $\delta=0$, then $\mathcal{I}$ covers the entire cake, i.e., we obtain an envy-free allocation. $\sqcap$$\sqcup$

Notably, Lemma 3 and Theorem 6 (with $\delta=0$) provide a stand-alone proof of existence of envy-free allocations in cake-division instances with MLRP. The next section establishes an algorithmic counterpart of this existential result; specifically, we show that using Lemma 4 one can directly obtain an efficient algorithm for finding envy-free allocations, under MLRP.

4 Proof of Theorem 1

This section restates and proves our main result (Theorem 1) for envy-freeness.

Proof Given a cake-division instance $\mathcal{C}$, with MLRP, and precision parameter $\eta>0$, we invoke Lemma 4 to find an $\left(\frac{\eta}{\lambda}\right)$-ripple division in $\mathcal{O}\left({\rm poly}(n,\log\lambda,\log\frac{1}{\eta})\right)$ time.

Write $x_{0}=0\leq x_{1}\leq\dots\leq x_{n-1}\leq x_{n}\leq 1$ to denote the computed $\left(\frac{\eta}{\lambda}\right)$-ripple division and let $\mathcal{I}=\{I_{1},\ldots,I_{n}\}$ be the corresponding partial allocation; here $I_{i}=[x_{i-1},x_{i}]$. Theorem 6 ensures that $\mathcal{I}$ is envy-free.

We will show that coalescing the unassigned (in $\mathcal{I}$) piece $[x_{n},1]$ to agent $n$ provides a complete allocation that satisfies envy-freeness, up to $\eta$ precision. Write $\mathcal{I}^{*}\coloneqq\{I^{*}_{1},I^{*}_{2},\ldots,I^{*}_{n-1},I^{*}_{n}\}$ to denote this allocation in which the $n$th agent receives the interval $I^{*}_{n}\coloneqq[x_{n-1},1]$ (equivalently, $I^{*}_{n}=I_{n}\cup[x_{n},1]$) and $I^{*}_{i}=I_{i}$ for the remaining agents $i\in[n-1]$.

Note that against all agents $j\in[n-1]$, envy-freeness of $\mathcal{I}^{*}$ directly follows from the fact that the partial allocation $\mathcal{I}$ is envy-free: $v_{i}(I^{*}_{i})\geq v_{i}(I_{i})\geq v_{i}(I_{j})=v_{i}(I^{*}_{j})$, for all $i\in[n]$ and all $j\in[n-1]$.

Finally, we address envy against agent $n$. Recall that $x_{i}$s form a $\left(\frac{\eta}{\lambda}\right)$-ripple division, hence $x_{n}\geq 1-\frac{\eta}{\lambda}$. In addition, the fact that eval queries are $\lambda$-Lipschitz gives us $v_{i}([x_{n},1])\leq\eta$ for all agents $i\in[n]$. Hence, for all $i\in[n]$ we have

Therefore, $\mathcal{I}^{*}$ satisfies envy-freeness, up to $\eta$ precision: $v_{i}(I^{*}_{i})\geq v_{i}(I^{*}_{j})-\eta$ for all $i,j\in[n]$.

The time complexity obtained via Lemma 4 implies that the parameter $\eta$ can be driven exponentially close to zero, in time that is polynomial in $\log\frac{1}{\eta}$ (i.e., in the bit complexity of $\eta$). Hence, we can find an envy-free allocation, up to arbitrary precision, in $\mathcal{O}\left({\rm poly}(n,\log\lambda)\right)$ time. Theorem 1 now stands proved. $\sqcap$$\sqcup$

Pareto Optimality

This section shows that, with MLRP in hand, one does not loose out on Pareto optimality by imposing the contiguity requirement. That is, under MLRP, there always exist allocations (i.e., cake divisions with connected pieces) that are Pareto optimal among all cake divisions, with or without connected pieces. Moreover, such allocations conform to the MLRP order.

This structural result implies that for maximizing welfare we can restrict attention to allocations wherein the intervals are assigned (left to right on the cake) in accordance with the MLRP order. Intuitively, this leads us to a welfare-maximizing algorithm—specifically, a dynamic program—that recursively finds optimal allocations for intervals placed at the left end of the cake (i.e., for intervals of the form $[0,x]$); see Section 7 and Appendix 9 for details.

Subsequently, Section 6.1 (Theorem 2) establishes a strong connection between fairness and (Pareto) efficiency in the MLRP context: if the value densities bear MLRP, then every envy-free allocation is necessarily Pareto optimal.

Let $\mathcal{C}=\langle[n],(f_{i})_{i}\rangle$ be a cake-division instance in which the value densities satisfy the monotone likelihood ratio property. Then, for every cake division $\mathcal{D}=\{D_{1},\ldots,D_{n}\}$ in $\mathcal{C}$ there exists an allocation $\mathcal{J}=\{J_{1},\ldots,J_{n}\}$ such that $v_{i}(J_{i})\geq v_{i}(D_{i})$, for $1\leq i\leq n$.

Furthermore, for every Pareto optimal allocation $\mathcal{I}=\{I_{1},\ldots,I_{n}\}$ in $\mathcal{C}$, there exists an allocation $\mathcal{I^{\prime}}=\{I^{\prime}_{1},\ldots,I^{\prime}_{n}\}$ with $v_{i}(I^{\prime}_{i})=v_{i}(I_{i})$ that conforms to the MLRP order, i.e., if $\ f_{i+1}/f_{i}$ is nondecreasing in $$, then the interval assigned to agent$i$(i.e.,$I^{\prime}_{i}$) appears to the left of the interval assigned to the agent$i+1$(i.e.,$I^{\prime}_{i+1}$).

Proof Consider a cake division $\mathcal{D}=\{D_{1},\ldots,D_{n}\}$ wherein two consecutive intervals are assigned violating the MLRP order: say, interval $[p,q]$ is assigned to agent $j$ (i.e., this interval is contained in the bundle $D_{j}$), the adjacent interval $[q,r]$ is assigned to agent $i$, and agent $i$ appears before $j$ in the MLRP order ($f_{j}/f_{i}$ is non-decreasing over $$).

We will show that in such a case there always exists a point $q^{\prime}\in[p,r]$ such that $v_{i}(p,q^{\prime})\geq v_{i}(q,r)$ and $v_{j}(q^{\prime},r)\geq v_{j}(p,q)$. That is, one can swap the allocation order between $i$ and $j$ (in the interval $[p,q]\cup[q,r]$) without decreasing the agents’ values. Moreover, we note that, if $f_{j}/f_{i}$ is strictly increasing in the interval $[p,q]\cup[q,r]$, then this update leads to a strict increase in agent $i$’s or agent $j$’s value.

Hence, starting with any cake division $\mathcal{D}=\{D_{1},\ldots,D_{n}\}$, we can repeatedly apply the above-mentioned resolution towards the MLRP order and obtain an allocation $\mathcal{J}=\{J_{1},\ldots,J_{n}\}$ with the desired property, $v_{i}(J_{i})\geq v_{i}(D_{i})$ for all $i\in[n]$.

Note that this resolution process also establishes the second part of the theorem, i.e., for every Pareto optimal allocation $\mathcal{I}$, there exists an allocation $\mathcal{I^{\prime}}$ with $v_{i}(I^{\prime}_{i})=v_{i}(I_{i})$ that conforms to the MLRP order.

The remainder of the proof addresses the desired point $q^{\prime}\in[p,r]$. In particular, we will identify $q^{\prime}$ such that assigning interval $[p,q^{\prime}]$ to agent $i$ (instead of $[q,r]$) and assigning $[q^{\prime},r]$ to agent $j$ (instead of $[p,q]$) leads to an increment in values.

Write $\beta_{i}\coloneqq\frac{v_{i}(q,r)}{v_{i}(p,r)}$ to denote the normalized value of agent $i$ under the initial assignment. Define $q^{\prime}\in[p,r]$ to be the point that satisfies

Since the value densities satisfy MLRP, property (ii) of Lemma 1, applied to the interval $[p,r]$ and $q^{\prime}\in[p,r]$, gives us $\frac{v_{i}(q^{\prime},r)}{v_{i}(p,r)}\leq\frac{v_{j}(q^{\prime},r)}{v_{j}(p,r)}$. Simplifying further we obtain $1-\frac{v_{j}(q^{\prime},r)}{v_{j}(p,r)}\leq 1-\frac{v_{i}(q^{\prime},r)}{v_{i}(p,r)}$, i.e.,

Therefore, we obtain a value bound for agent $i$

That is, agent $i$’s value is preserved through the reassignment, $v_{i}(p,q^{\prime})\geq v_{i}(q,r)$.

For agent $j$, via property (ii) of Lemma 1, with interval $[p,r]$ and $q\in[p,r]$, we have

This inequality reduces to $1-\frac{v_{j}(p,q^{\prime})}{v_{j}(p,r)}\geq 1-\frac{v_{j}(q,r)}{v_{j}(p,r)}$. Simplifying we obtain $\frac{v_{j}(p,r)-v_{j}(p,q^{\prime})}{v_{j}(p,r)}\geq\frac{v_{j}(p,r)-v_{j}(q,r)}{v_{j}(p,r)}$. Therefore, we have the desired inequality $v_{j}(q^{\prime},r)\geq v_{j}(p,q)$ and the stated claims follow. $\sqcap$$\sqcup$

Remark. For cake-division instances with MLRP, we can prove that any allocation $\mathcal{K}$ that conforms to the MLRP order is Pareto optimal (over the set of all cake divisions). Write $0=k_{0}<k_{1}<\dots<k_{n}=1$ to denote the cut-points of $\mathcal{K}$. For contradiction, we assume that $\mathcal{K}$ is not Pareto optimal. That is, there exists a cake-division $\mathcal{L}$ that dominates $\mathcal{K}$ and is Pareto optimal. By Lemma 5, we know there exists another Pareto optimal allocation $\mathcal{M}$ with $v_{i}(M_{i})=v_{i}(L_{i})$ for all $i\in[n]$ that conforms to the MLRP order. Write $0=m_{0}<m_{1}<\dots<m_{n}=1$ to denote the cut-points of $\mathcal{M}$. Since, $\mathcal{M}$ Pareto dominates $\mathcal{K}$, we will have $k_{i}\leq m_{i}$ for all $i\in[n]$ with at least one strict inequality. This contradicts the fact that $k_{n}=m_{n}=1$. Therefore, $\mathcal{K}$ is Pareto optimal. $\sqcap$$\sqcup$

Weller’s theorem [Wel85] is a notable result in the cake-cutting literature and it asserts that there always exists some cake division—though, not necessarily with connected pieces—which is both envy-free (fair) and Pareto optimal. While this theorem holds in general, it does not guarantee that envy-freeness and Pareto optimality can be achieved together with allocations. Indeed, there are cake-division instances wherein none of the of envy-free allocations are Pareto optimal.

We show that, by contrast under MLRP, every envy-free allocation is Pareto optimal, among all cake divisions (Theorem 2). Therefore, given a cake-division instance with MLRP, the allocation computed by our algorithm (Algorithm 1) is not only envy-free but also Pareto optimal, up to an arbitrary precision.

Proof Write $\mathcal{I}=\{I_{1},I_{2},\dots,I_{n}\}$ to denote an envy-free allocation in $\mathcal{C}$; here interval $I_{i}$ is assigned to agent $i\in[n]$. We assume, towards a contradiction, that there exists a cake division $\mathcal{D}=\{D_{1},\ldots,D_{n}\}$ that Pareto dominates $\mathcal{I}$. Lemma 5 implies that in such a case there exists an allocation $\mathcal{J}=\{J_{1},\ldots,J_{n}\}$ which also Pareto dominates $\mathcal{I}$. That is, we have $v_{i}(J_{i})\geq v_{i}(D_{i})\geq v_{i}(I_{i})$, for all agents $i\in[n]$, and there exists some agent $k\in[n]$ such that $v_{k}(J_{k})\geq v_{k}(D_{k})>v_{k}(I_{k})$.

Recall that for an allocation the endpoints of all the constituent intervals are referred to as its cut points. We break our analysis into the following two cases depending on whether $\mathcal{I}$ and $\mathcal{J}$ have the same set of cut points.

Case 1: The cut points of the allocations $\mathcal{I}$ and $\mathcal{J}$ are identical. In this case, there must exist a permutation $\sigma\mathrel{\mathop{\mathchar 58\relax}}[n]\mapsto[n]$ such that $I_{\sigma(i)}=J_{i}$ for all $i\in[n]$. Since $\mathcal{I}$ is envy-free, we have $v_{i}(I_{i})\geq v_{i}(I_{\sigma(i)})=v_{i}(J_{i})$ for all agents $i\in[n]$. However, this contradicts the fact that $\mathcal{J}$ Pareto dominates the allocation $\mathcal{I}$.

Case 2: The cut points of $\mathcal{I}$ and $\mathcal{J}$ are not identical. Since both the allocations form a partition of the same cake $$, there must exist some$s,t\in[n]$such that the interval$J_{s}$is a strict subset of the interval$I_{t}$, i.e.,$J_{s}\subset I_{t}$. Envy-freeness of$\mathcal{I}$gives us$v_{s}(I_{s})\geq v_{s}(I_{t})>v_{s}(J_{s})$. The last strict inequality follows from the fact that the value density$f_{s}$of agent$s$has full support over$$and$J_{s}$is a strict subset of$I_{t}$. This bound$v_{s}(I_{s})>v_{s}(J_{s})$contradicts the fact that$\mathcal{J}$Pareto dominates$\mathcal{I}$and completes the proof.$\sqcap$$\sqcup$