Proximately Envy-Free and Efficient Allocation of Mixed Manna
Siddharth Barman, Paritosh Verma · 2025
Read Proximately Envy-Free and Efficient Allocation of Mixed Manna by Siddharth Barman, Paritosh Verma (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-18673.txt.
Introduction
Fair division asks how to split items so no one envies another's share, while waste stays low. Siddharth Barman and Paritosh Verma study that pairing for mixed manna in this 2025 paper. Mixed manna means a pool holding both goods people want and chores people shun. For goods alone and chores alone, fairness up to one item can pair with efficiency. For the mixed case, a recent result says they clash.
The pair restore the pairing by softening the fairness rule in two principled ways. One rule lets an agent erase envy by adding an item to its own bundle, or by dropping one from it. The other lets envy be checked by adjusting the other's bundle instead. They prove efficient allocations exist under both rules with additive values. The proofs lean on a classic fixed-point theorem. The results also yield a fresh proof for the divisible case.
Catalog record
| CREATOR | Siddharth Barman, Paritosh Verma |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-18673
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Proximately Envy-Free and Efficient Allocation of Mixed Manna Siddharth Barman, Paritosh Verma Abstract The existence of fair and efficient allocations of indivisible items is a central problem in fair division. For indivisible goods, the existence of Pareto efficient ( PO \mathrm{PO} ) and envy free up to one item ( EF 1 \mathrm{EF}1 ) allocations was established by [ 2 ] . In a recent breakthrough, [ 4 ] established the existence of PO \mathrm{PO} and EF 1 \mathrm{EF}1 allocations for indivisible chores. However, the existence of PO \mathrm{PO} and EF 1 \mathrm{EF}1 allocations of mixed manna remains an intriguing open problem. In this paper we make significant progress in this direction. We establish the existence of allocations that are PO \mathrm{PO} and introspective envy free up to one item ( IEF 1 \mathrm{IEF}1 ) for mixed manna. In an IEF 1 \mathrm{IEF}1 allocation, each agent can eliminate its envy towards all the other agents, by either adding an item or removing an item from its own bundle. The notion of IEF 1 \mathrm{IEF}1 coincides with EF 1 \mathrm{EF}1 for indivisible chores, and hence, our existence result generalizes the aforementioned result of [ 4 ] . 1 Introduction Fair division of limited resources is ubiquitous problem that has been extensively studied by mathematicians, economists, philosophers, and political theorists, among others. The existence of fair and economically efficient allocations is a fundamental problem in fair division. This paper studies this problem for indivisible resources (which cannot be fractionally assigned) and additive preferences. For the case of indivisible goods, i.e., weakly desirable items, [ 2 ] established the existence of Pareto efficient (\mathrm{PO}) and envy free up to one item ( \mathrm{EF}1 ) allocations by showing that maximizing the Nash welfare objective (geometric mean of utilities) results in such allocations. This approach however does not work for indivisible chores (weakly undesirable items), and the corresponding problem was open for around a decade. Recently, [ 4 ] resolved this open problem by establishing the existence of \mathrm{PO} and \mathrm{IEF}1 allocation for indivisible chores via a combination of a fixed point and a combinatorial argument. Despite this, the problem of the existence of \mathrm{PO} and \mathrm{EF}1 allocation remains open for indivisible mixed manna, where each item can be a good for some agents and a chore for other agents. This work focuses on the mixed manna setting. We establish the existence of \mathrm{PO} and introspective envy free up to one item , \mathrm{IEF}1 allocations ( Theorem 1 ). In an \mathrm{IEF}1 allocation, each agent can eliminate its envy towards all the other agents by either adding or removing one item from its bundle (the items allocated to it); see Section 2 for a formal definition. The notion of \mathrm{IEF}1 is closely related to the popular notion of \mathrm{EF}1 . For indivisible chores, \mathrm{IEF}1 and \mathrm{EF}1 are exactly the same. For indivisible goods, although they are quite similar, \mathrm{EF}1 implies \mathrm{IEF}1 . Since, \mathrm{IEF}1 is same as \mathrm{EF}1 for indivisible chores, our Theorem 1 generalizes the existence result of \mathrm{PO} and \mathrm{EF}1 allocations of indivisible chores by [ 4 ] . In a recent work [ 1 ] consider the mixed manna setting and establish the existence of \mathrm{PO} and \mathrm{EFR} - (n-1) allocations, where \mathrm{EFR} - (n-1) entails the existence of n-1 items such that each agent can become envy free by reallocation them. Our Theorem 1 generalizes this result since the notion of \mathrm{IEF}1 is strictly stronger than \mathrm{EFR} - (n-1) . The existence result of both [ 4 ; 1 ] crucially relies on the KKM fixed point theorem. 2 Preliminaries Fair Division Instance. A fair division instance \mathcal{I} is denoted by a triple \mathcal{I}=\langle[n],[m],\{v_{i}\}_{i=1}^{n}\rangle where n,m\geq 2 are integers. The set [n]\coloneqq\{1,2,\ldots,n\} denotes a set of n agents indexed by integers 1 to n . The set [m]\coloneqq\{1,2,\ldots,m\} denotes the set of items that are to be allocated to the n agents. The value of each item j\in[m] for each agent i\in[n] is denoted by v_{i}(j)\in\mathbb{R} . The values of all the items [m] for each agent i\in[n] is collectively denoted by v_{i} . We assume that all the agents have additive valuation, i.e., the total value of a set of items S\subseteq[m] , referred as a bundle , is v_{i}(S)\coloneqq\sum_{t\in S}v_{i}(t) , i.e., the sum of values of all items in S . We will assume that v_{i}(\emptyset)=0 for all i\in[n] . Allocation. An allocation \mathcal{A}=(A_{1},A_{2},\ldots,A_{n}) is a partition of the set of items [m] into n disjoint parts, i.e., A_{i}\cap A_{j}=\emptyset for all i,j\in[n] . An allocation is called complete if \cup_{i=1}^{n}A_{i}=[m] and partial if \cup_{i=1}^{n}A_{i}\subsetneq[m] ; we will simply use allocation to refer to a complete allocation. The set of all complete allocations of [m] among n agents will be denoted by \Pi_{n}([m]) . Fairness and Efficiency. Next we define the main fairness and efficiency notion used in our paper. Definition 1 ( \mathrm{IEF}1 ) . An allocation \mathcal{A}=(A_{1},A_{2},\ldots,A_{n})\in\Pi_{n}([m]) is called introspective envy free up to one item or \mathrm{IEF}1 for an instance \mathcal{I}=\langle[n],[m],\{v_{i}\}_{i=1}^{n}\rangle if for each agent i\in[n] there exists a subset S\subseteq[m] containing at most one item, |S|\leq 1 such that v_{i}(A_{i}\Delta S)\geq max_{j=1}^{n}v_{i}(A_{j}) . 1 1 1 Here \Delta denotes the symmetric set difference, i.e., for any two sets A,B\subseteq[m] , A\Delta B=(A\setminus B)\cup(B\setminus A) . In other words, each agent i\in[n] either doesn’t envy any other agent, or its envy towards all the agents can be simlultaneously eliminated by removing or adding one item to its bundle. Notably unlike the standard notion of \mathrm{EF}1 , the thought-experiment of agent i in \mathrm{IEF}1 , which is aimed towards eliminating its envy towards everyone else, only concerns its own bundle, i.e., it is introspective in nature. Given an instance \mathcal{I}=\langle[n],[m],\{v_{i}\}_{i=1}^{n}\rangle , an allocation \mathcal{B}=(B_{1},B_{2},\ldots,B_{n}) Pareto dominates another allocation \mathcal{A}=(A_{1},A_{2},\ldots,A_{n}) if v_{i}(B_{i})\geq v_{i}(A_{i}) for all i\in[n] and v_{j}(B_{j})>v_{j}(A_{j}) for some j\in[n] . Definition 2 ( \mathrm{PO} ) . An allocation \mathcal{A}=(A_{1},A_{2},\ldots,A_{n})\in\Pi_{n}([m]) is called Pareto efficient for the instance \mathcal{I}=\langle[n],[m],\{v_{i}\}_{i=1}^{n}\rangle , if there is no allocation \mathcal{B}\in\Pi_{n}([m]) that Pareto dominates it. Item Types. Without loss of generality, we will assume that all the items in [m] are of three types. An item j\in[m] is a good if v_{i}(j)>0 for all i\in[n] . An item j\in[m] is a chore if v_{i}(j)<0 for all i\in[n] . An item is nonnegatively-valued if v_{i}(j)\geq 0 for all i\in[n] , v_{a}(j)>0 for some a\in[n] , and v_{b}(j)=0 for some b\in[n] . This assumption is without loss of generality given our goal is to compute Pareto efficient (and fair) allocations. In particular, if there is an item k that is positively-valued by some agent and negatively-valued by another agent, then, in any Pareto efficient allocation, item k will never be allocated to an agent having a negative value for it. Hence, we can assume that any agent who values item k negatively, values it at zero instead; this leads to the aforementioned item types. An instance where we have both positively and negatively valued items is said to be an instance with mixed manna . Other Notations. We will use \Delta_{n-1} to denote the n-1 -dimensional simplex, i.e., \Delta_{n-1}\coloneqq\{x\in\mathbb{R}^{n}\mid\sum_{i=1}^{n}x_{i}=1\text{ and }x_{i}\geq 0\text{ for all }i\in[n]\} . For