SU\G(𝔸)/K·U
Sign Up for free Log In

Beyond Cake Cutting: Allocating Homogeneous Divisible Goods

Authors

Ioannis Caragiannis, Vasilis Gkatzelis, Alexandros Psomas, Daniel Schoepflin
Type: Preprint
Publication Date: 2022-01-01
Citations: 0
DOI: https://doi.org/10.48550/arxiv.2201.04662

Abstract

The problem of fair division known as "cake cutting" has been the focus of multiple papers spanning several decades. The most prominent problem in this line of work has been to bound the query complexity of computing an envy-free outcome in the Robertson-Webb query model. However, the root of this problem's complexity is somewhat artificial: the agents' values are assumed to be additive across different pieces of the "cake" but infinitely complicated within each piece. This is unrealistic in most of the motivating examples, where the cake represents a finite collection of homogeneous goods. We address this issue by introducing a fair division model that more accurately captures these applications: the value that an agent gains from a given good depends only on the amount of the good they receive, yet it can be an arbitrary function of this amount, allowing the agents to express preferences that go beyond standard cake cutting. In this model, we study the query complexity of computing allocations that are not just envy-free, but also approximately Pareto optimal among all envy-free allocations. Using a novel flow-based approach, we show that we can encode the ex-post feasibility of randomized allocations via a polynomial number of constraints, which reduces our problem to solving a linear program.

Locations

  • arXiv (Cornell University)
    View
  • DataCite API
    View

Ask a Question About This Paper

Summary

Login to see paper summary

Fair and Efficient Cake Division with Connected Pieces

2019-01-01
Eshwar Ram Arunachaleswaran , Siddharth Barman , Rachitesh Kumar +1 more
The classic cake-cutting problem provides a model for addressing fair and efficient allocation of a divisible, heterogeneous resource (metaphorically, the cake) among agents with distinct preferences. Focusing on a standard … The classic cake-cutting problem provides a model for addressing fair and efficient allocation of a divisible, heterogeneous resource (metaphorically, the cake) among agents with distinct preferences. Focusing on a standard formulation of cake cutting, in which each agent must receive a contiguous piece of the cake, this work establishes algorithmic and hardness results for multiple fairness/efficiency measures. First, we consider the well-studied notion of envy-freeness and develop an efficient algorithm that finds a cake division (with connected pieces) wherein the envy is multiplicatively within a factor of 2+o(1). The same algorithm in fact achieves an approximation ratio of 3+o(1) for the problem of finding cake divisions with as large a Nash social welfare (NSW) as possible. NSW is another standard measure of fairness and this work also establishes a connection between envy-freeness and NSW: approximately envy-free cake divisions (with connected pieces) always have near-optimal Nash social welfare. Furthermore, we develop an approximation algorithm for maximizing the $\rho$-mean welfare--this unifying objective, with different values of $\rho$, interpolates between notions of fairness (NSW) and efficiency (average social welfare). Finally, we complement these algorithmic results by proving that maximizing NSW (and, in general, the $\rho$-mean welfare) is APX-hard in the cake-division context.
View PDF Chat

Fair and Efficient Cake Division with Connected Pieces

2019-07-25
Eshwar Ram Arunachaleswaran , Siddharth Barman , Rachitesh Kumar +1 more
The classic cake-cutting problem provides a model for addressing fair and efficient allocation of a divisible, heterogeneous resource (metaphorically, the cake) among agents with distinct preferences. Focusing on a standard … The classic cake-cutting problem provides a model for addressing fair and efficient allocation of a divisible, heterogeneous resource (metaphorically, the cake) among agents with distinct preferences. Focusing on a standard formulation of cake cutting, in which each agent must receive a contiguous piece of the cake, this work establishes algorithmic and hardness results for multiple fairness/efficiency measures. First, we consider the well-studied notion of envy-freeness and develop an efficient algorithm that finds a cake division (with connected pieces) wherein the envy is multiplicatively within a factor of 2+o(1). The same algorithm in fact achieves an approximation ratio of 3+o(1) for the problem of finding cake divisions with as large a Nash social welfare (NSW) as possible. NSW is another standard measure of fairness and this work also establishes a connection between envy-freeness and NSW: approximately envy-free cake divisions (with connected pieces) always have near-optimal Nash social welfare. Furthermore, we develop an approximation algorithm for maximizing the $\rho$-mean welfare--this unifying objective, with different values of $\rho$, interpolates between notions of fairness (NSW) and efficiency (average social welfare). Finally, we complement these algorithmic results by proving that maximizing NSW (and, in general, the $\rho$-mean welfare) is APX-hard in the cake-division context.

The Query Complexity of Cake Cutting

2017-01-01
Simina Brânzei , Noam Nisan
We study the query complexity of cake cutting and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower … We study the query complexity of cake cutting and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower bounds are tight for computing connected envy-free allocations among n=3 players and for computing perfect and equitable allocations with minimum number of cuts between n=2 players. We also formalize moving knife procedures and show that a large subclass of this family, which captures all the known moving knife procedures, can be simulated efficiently with arbitrarily small error in the Robertson-Webb query model.
View PDF Chat

Fair Cake Division Under Monotone Likelihood Ratios

2020-01-01
Siddharth Barman , Nidhi Rathi
This work develops algorithmic results for the classic cake-cutting problem in which a divisible, heterogeneous resource (modeled as a cake) needs to be partitioned among agents with distinct preferences. We … This work develops algorithmic results for the classic cake-cutting problem in which a divisible, heterogeneous resource (modeled as a cake) needs to be partitioned among agents with distinct preferences. We focus on a standard formulation of cake cutting wherein each agent must receive a contiguous piece of the cake. While multiple hardness results exist in this setup for finding fair/efficient cake divisions, we show that, if the value densities of the agents satisfy the monotone likelihood ratio property (MLRP), then strong algorithmic results hold for various notions of fairness and economic efficiency. Addressing cake-cutting instances with MLRP, first we develop an algorithm that finds cake divisions (with connected pieces) that are envy-free, up to an arbitrary precision. The time complexity of our algorithm is polynomial in the number of agents and the bit complexity of an underlying Lipschitz constant. We obtain similar positive results for maximizing social (utilitarian) and egalitarian welfare. In addition, we show that, under MLRP, the problem of maximizing Nash social welfare admits a fully polynomial-time approximation scheme (FPTAS). Many distribution families bear MLRP. In particular, this property holds if all the value densities belong to any one of the following families: Gaussian (with the same variance), linear, binomial, Poisson, and exponential distributions. Furthermore, it is known that linear translations of any log-concave function satisfy MLRP. Therefore, our results also hold when the value densities of the agents are linear translations of the following (log-concave) distributions: Laplace, gamma, beta, Subbotin, chi-square, Dirichlet, and logistic. Hence, through MLRP, the current work obtains novel cake-cutting algorithms for multiple distribution families.
View PDF Chat

Fair Cake Division Under Monotone Likelihood Ratios

2020-05-31
Siddharth Barman , Nidhi Rathi
This work develops algorithmic results for the classic cake-cutting problem in which a divisible, heterogeneous resource (modeled as a cake) needs to be partitioned among agents with distinct preferences. We … This work develops algorithmic results for the classic cake-cutting problem in which a divisible, heterogeneous resource (modeled as a cake) needs to be partitioned among agents with distinct preferences. We focus on a standard formulation of cake cutting wherein each agent must receive a contiguous piece of the cake. While multiple hardness results exist in this setup for finding fair/efficient cake divisions, we show that, if the value densities of the agents satisfy the monotone likelihood ratio property (MLRP), then strong algorithmic results hold for various notions of fairness and economic efficiency. Addressing cake-cutting instances with MLRP, first we develop an algorithm that finds cake divisions (with connected pieces) that are envy-free, up to an arbitrary precision. The time complexity of our algorithm is polynomial in the number of agents and the bit complexity of an underlying Lipschitz constant. We obtain similar positive results for maximizing social (utilitarian) and egalitarian welfare. In addition, we show that, under MLRP, the problem of maximizing Nash social welfare admits a fully polynomial-time approximation scheme (FPTAS). Many distribution families bear MLRP. In particular, this property holds if all the value densities belong to any one of the following families: Gaussian (with the same variance), linear, binomial, Poisson, and exponential distributions. Furthermore, it is known that linear translations of any log-concave function satisfy MLRP. Therefore, our results also hold when the value densities of the agents are linear translations of the following (log-concave) distributions: Laplace, gamma, beta, Subbotin, chi-square, Dirichlet, and logistic. Hence, through MLRP, the current work obtains novel cake-cutting algorithms for multiple distribution families.

Approximation Algorithms for Envy-Free Cake Division with Connected Pieces

2022-01-01
Siddharth Barman , Pooja Kulkarni
Cake cutting is a classic model for studying fair division of a heterogeneous, divisible resource among agents with individual preferences. Addressing cake division under a typical requirement that each agent … Cake cutting is a classic model for studying fair division of a heterogeneous, divisible resource among agents with individual preferences. Addressing cake division under a typical requirement that each agent must receive a connected piece of the cake, we develop approximation algorithms for finding envy-free (fair) cake divisions. In particular, this work improves the state-of-the-art additive approximation bound for this fundamental problem. Our results hold for general cake division instances in which the agents' valuations satisfy basic assumptions and are normalized (to have value $1$ for the cake). Furthermore, the developed algorithms execute in polynomial time under the standard Robertson-Webb query model. Prior work has shown that one can efficiently compute a cake division (with connected pieces) in which the additive envy of any agent is at most $1/3$. An efficient algorithm is also known for finding connected cake divisions that are (almost) $1/2$-multiplicatively envy-free. Improving the additive approximation guarantee and maintaining the multiplicative one, we develop a polynomial-time algorithm that computes a connected cake division that is both $\left(\frac{1}{4} +o(1) \right)$-additively envy-free and $\left(\frac{1}{2} - o(1) \right)$-multiplicatively envy-free. Our algorithm is based on the ideas of interval growing and envy-cycle-elimination. In addition, we study cake division instances in which the number of distinct valuations across the agents is parametrically bounded. We show that such cake division instances admit a fully polynomial-time approximation scheme for connected envy-free cake division.
View PDF Chat

Envy-Free Cake-Cutting for Four Agents

2023-11-06
Alexandros Hollender , Aviad Rubinstein
In the envy-free cake-cutting problem we are given a resource, usually called a cake and represented as the $[0,1]$ interval, and a set of n agents with heterogeneous preferences over … In the envy-free cake-cutting problem we are given a resource, usually called a cake and represented as the $[0,1]$ interval, and a set of n agents with heterogeneous preferences over pieces of the cake. The goal is to divide the cake among the n agents such that no agent is envious of any other agent. Even under a very general preferences model, this fundamental fair division problem is known to always admit an exact solution where each agent obtains a connected piece of the cake; we study the complexity of finding an approximate solution, i.e., a connected $\varepsilon$-envy-free allocation. For monotone valuations of cake pieces, Deng, Qi, and Saberi (2012) gave an efficient (poly $(\log (1 / \varepsilon))$ queries) algorithm for three agents and posed the open problem of four (or more) monotone agents. Even for the special case of additive valuations, Bránzei and Nisan (2022) conjectured an $\Omega(1 / \varepsilon)$ lower bound on the number of queries for four agents. We provide the first efficient algorithm for finding a connected $\varepsilon$-envy-free allocation with four monotone agents. We also prove that as soon as valuations are allowed to be non-monotone, the problem becomes hard: it becomes PPAD-hard, requires poly $(1 / \varepsilon)$ queries in the black-box model, and even poly $(1 / \varepsilon)$ communication complexity. This constitutes, to the best of our knowledge, the first intractability result for any version of the cake-cutting problem in the communication complexity model.
View PDF Chat

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

2020-09-22
Paul W. Goldberg , Alexandros Hollender , Warut Suksompong
We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the … We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems on the existence of envy-free allocations, such as when we fix the ordering of the agents or constrain the positions of certain cuts. In addition, we consider a discretized setting where indivisible items lie on a line and show a number of hardness results extending and strengthening those from prior work. Finally, we investigate connections between approximate and exact envy-freeness, as well as between continuous and discrete cake cutting.
View PDF Chat

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

2020-04-03
Paul W. Goldberg , Alexandros Hollender , Warut Suksompong
We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the … We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems on the existence of envy-free allocations, such as when we fix the ordering of the agents or constrain the positions of certain cuts. In addition, we consider a discretized setting where indivisible items lie on a line and show a number of hardness results strengthening those from prior work.
View PDF Chat

The Query Complexity of Cake Cutting.

2017-05-08
Simina Brânzei , Noam Nisan
We study the query complexity of cake cutting and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower … We study the query complexity of cake cutting and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower bounds are tight for computing connected envy-free allocations among n=3 players and for computing perfect and equitable allocations with minimum number of cuts between n=2 players. We also formalize moving knife procedures and show that a large subclass of this family, which captures all the known moving knife procedures, can be simulated efficiently with arbitrarily small error in the Robertson-Webb query model.

Envy-Free Cake-Cutting for Four Agents

2023-01-01
Alexandros Hollender , Aviad Rubinstein
In the envy-free cake-cutting problem we are given a resource, usually called a cake and represented as the $[0,1]$ interval, and a set of $n$ agents with heterogeneous preferences over … In the envy-free cake-cutting problem we are given a resource, usually called a cake and represented as the $[0,1]$ interval, and a set of $n$ agents with heterogeneous preferences over pieces of the cake. The goal is to divide the cake among the $n$ agents such that no agent is envious of any other agent. Even under a very general preferences model, this fundamental fair division problem is known to always admit an exact solution where each agent obtains a connected piece of the cake; we study the complexity of finding an approximate solution, i.e., a connected $\varepsilon$-envy-free allocation. For monotone valuations of cake pieces, Deng, Qi, and Saberi (2012) gave an efficient ($\textsf{poly}(\log(1/\varepsilon))$ queries) algorithm for three agents and posed the open problem of four (or more) monotone agents. Even for the special case of additive valuations, Brânzei and Nisan (2022) conjectured an $Ω(1/\varepsilon)$ lower bound on the number of queries for four agents. We provide the first efficient algorithm for finding a connected $\varepsilon$-envy-free allocation with four monotone agents. We also prove that as soon as valuations are allowed to be non-monotone, the problem becomes hard: it becomes PPAD-hard, requires $\textsf{poly}(1/\varepsilon)$ queries in the black-box model, and even $\textsf{poly}(1/\varepsilon)$ communication complexity. This constitutes, to the best of our knowledge, the first intractability result for any version of the cake-cutting problem in the communication complexity model.

Fair Division Beyond Monotone Valuations

2025-01-24
Siddharth Barman , Paritosh Verma
This paper studies the problem of fairly dividing resources -- a cake or indivisible items -- amongst a set of agents with heterogeneous preferences. This problem has been extensively studied … This paper studies the problem of fairly dividing resources -- a cake or indivisible items -- amongst a set of agents with heterogeneous preferences. This problem has been extensively studied in the literature, however, a majority of the existing work has focused on settings wherein the agents' preferenes are monotone, i.e., increasing the quantity of resource doesn't decrease an agent's value for it. Despite this, the study of non-monotone preferences is as motivated as the study of monotone preferences. We focus on fair division beyond monotone valuations. We prove the existence of fair allocations, develop efficient algorithms to compute them, and prove lower bounds on the number of such fair allocations. For the case of indivisible items, we show that EF3 and EQ3 allocations always exist as long as the valuations of all agents are nonnegative. While nonnegativity suffices, we show that it's not required: EF3 allocations exist even if the valuations are (possibly negative) subadditive functions that satisfy a mild condition. In route to obtaining these results, we establish the existence of envy-free cake divisions for burnt cakes when the valuations are subadditive and the entire cake has a nonnegative value. This is in stark contrast to the well-known nonexistence of envy-free allocations for burnt cakes. In addition to the existence results, we develop an FPTAS for computing equitable cake divisions for nonnegative valuations. For indivisible items, we give an efficient algorithm to compute nearly equitable allocations which works when the valuations are nonnegative, or when they are subadditive subject to a mild condition. This result has implications beyond fair division, e.g., in facility, graph partitioning, among others. Finally, we show that such fair allocations are plenty in number, and increase exponentially (polynomially) in the number of agents (items).
View PDF Chat

Fair Cake Division Under Monotone Likelihood Ratios

2021-12-16
Siddharth Barman , Nidhi Rathi
This work develops algorithmic results for the classic cake-cutting problem in which a divisible, heterogeneous resource (modeled as a cake) needs to be partitioned among agents with distinct preferences. We … This work develops algorithmic results for the classic cake-cutting problem in which a divisible, heterogeneous resource (modeled as a cake) needs to be partitioned among agents with distinct preferences. We focus on a standard formulation of cake cutting wherein each agent must receive a contiguous piece of the cake. Although multiple hardness results exist in this setup for finding fair/efficient cake divisions, we show that, if the value densities of the agents satisfy the monotone likelihood ratio property (MLRP), then strong algorithmic results hold for various notions of fairness and economic efficiency. Addressing cake-cutting instances with MLRP, first we develop an algorithm that finds cake divisions (with connected pieces) that are envy free, up to an arbitrary precision. The time complexity of our algorithm is polynomial in the number of agents and the bit complexity of an underlying Lipschitz constant. We obtain similar positive results for maximizing social, egalitarian, and Nash social welfare. Many distribution families bear MLRP. In particular, this property holds if all the value densities belong to any one of the following families: Gaussian (with the same variance), linear, Poisson, and exponential distributions, linear translations of any log-concave function. Hence, through MLRP, the current work obtains novel cake-cutting algorithms for multiple distribution families.
View PDF Chat

An Improved Envy-Free Cake Cutting Protocol for Four Agents

2018-07-01
Georgios Amanatidis , George Christodoulou , John Fearnley +3 more
We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents, so … We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents, so that every agent finds her piece at least as valuable as every other agent's piece. The problem has had an interesting history so far. Although the case of three agents is solvable with less than 15 queries, for four agents no bounded procedure was known until the recent breakthroughs of Aziz and Mackenzie (STOC 2016, FOCS 2016). The main drawback of these new algorithms, however, is that they are quite complicated and with a very high query complexity. With four agents, the number of queries required is close to 600. In this work we provide an improved algorithm for four agents, which reduces the current complexity by a factor of 3.4. Our algorithm builds on the approach of Aziz and Mackenzie (STOC 2016) by incorporating new insights and simplifying several steps. Overall, this yields an easier to grasp procedure with lower complexity.

An Improved Envy-Free Cake Cutting Protocol for Four Agents

2018-01-01
Georgios Amanatidis , George N. Christodoulou , John Fearnley +3 more
We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents, so … We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents, so that every agent finds her piece at least as valuable as every other agent's piece. The problem has had an interesting history so far. Although the case of three agents is solvable with less than 15 queries, for four agents no bounded procedure was known until the recent breakthroughs of Aziz and Mackenzie (STOC 2016, FOCS 2016). The main drawback of these new algorithms, however, is that they are quite complicated and with a very high query complexity. With four agents, the number of queries required is close to 600. In this work we provide an improved algorithm for four agents, which reduces the current complexity by a factor of 3.4. Our algorithm builds on the approach of Aziz and Mackenzie (STOC 2016) by incorporating new insights and simplifying several steps. Overall, this yields an easier to grasp procedure with lower complexity.
View PDF Chat

Envy-Free Cake Cutting with Graph Constraints

2022-01-01
Ganesh Ghalme , Xin Huang , Nidhi Rathi
We study the classic problem of fairly dividing a heterogeneous and divisible resource -- represented by a cake, $[0,1]$ -- among $n$ agents. This work considers an interesting variant of … We study the classic problem of fairly dividing a heterogeneous and divisible resource -- represented by a cake, $[0,1]$ -- among $n$ agents. This work considers an interesting variant of the problem where agents are embedded on a graph. The graphical constraint entails that each agent evaluates her allocated share only against her neighbor's share. Given a graph, the goal is to efficiently find a locally envy-free allocation where every agent values her share to be at least as much as any of her neighbor's share. The best known algorithm (by Aziz and Mackenzie) for finding envy-free cake divisions has a hyper-exponential query complexity. One of the key technical contributions of this work is to identify a non-trivial graph structure -- tree graphs with depth at-most two (Depth2Tree) -- on $n$ agents that admits a query efficient cake-cutting protocol (under the Robertson-Webb query model). In particular, we develop a discrete protocol that finds a locally envy-free allocation among $n$ agents on depth-two trees with at-most $O(n^3 \log(n))$ cuts on the cake. For the special case of Depth2Tree where every non-root agent is connected to at-most two agents (2-Star), we show that $O(n^2)$ queries suffice. We complement our algorithmic results with establishing a lower bound of $\Omega(n^2)$ (evaluation) queries for finding a locally envy-free allocation among $n$ agents on a 1-Star graph (under the assumption that the root agent partitions the cake into $n$ connected pieces).

The Complexity of Cake Cutting with Unequal Shares

2020-06-06
Ágnes Cseh , Tamás Fleiner
An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among … An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this article, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands, which delivers a proportional solution in fewer queries than all known protocols. By giving a matching lower bound, we then show that our protocol is asymptotically the fastest possible. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.
View PDF Chat

The complexity of cake cutting with unequal shares

2017-09-10
Ágnes Cseh , Tamás Fleiner
An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among … An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among $n$ players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this paper, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands that delivers a proportional solution in fewer queries than all known algorithms. Then we show that our protocol is asymptotically the fastest possible by giving a matching lower bound. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.

The complexity of cake cutting with unequal shares

2017-01-01
Ágnes Cseh , Tamás Fleiner
An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among … An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among $n$ players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this paper, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands that delivers a proportional solution in fewer queries than all known algorithms. Then we show that our protocol is asymptotically the fastest possible by giving a matching lower bound. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.
View PDF Chat

Almost envy-freeness with general valuations

2018-01-07
Benjamin Plaut , Tim Roughgarden
The goal of division is to distribute resources among competing players in a fair way. Envy-freeness is the most extensively studied fairness notion in division. Envy-free allocations do not always … The goal of division is to distribute resources among competing players in a fair way. Envy-freeness is the most extensively studied fairness notion in division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the division of indivisible goods with different classes of player valuations.