Existence and Computation of Fair Allocations under Constraints

Siddharth Barman, Ioannis Caragiannis, Sudarshan Shyam · 2026

Read Existence and Computation of Fair Allocations under Constraints by Siddharth Barman, Ioannis Caragiannis, Sudarshan Shyam (2026) 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-2603-00411.txt.

Introduction

Barman, Caragiannis, and Shyam study fair sharing of divisible goods when each person values items differently and faces a size budget, so some goods may go unassigned. They place leftovers with a charity construct and study feasible envy freeness, which judges envy only over budget feasible bundles. The team extends known existence results, shows the feasible set is non convex, and proves fair plus Pareto optimal sharing always exists. They also confirm no method can add truthfulness to both at once, though truthfulness pairs with each alone.

Catalog record

CREATORSiddharth Barman, Ioannis Caragiannis, Sudarshan Shyam
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50781
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.00411

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Existence and Computation of Fair Allocations under Constraints Siddharth Barman, Ioannis Caragiannis, Sudarshan Shyam Abstract We study fair division of divisible goods under generalized assignment constraints. Here, each good has an agent-specific value and size, and every agent has a budget constraint that limits the total size of the goods she can receive. Since it may not always be feasible to assign all goods to the agents while respecting the budget constraints, we use the construct of charity to accommodate the unassigned goods. In this constrained setting with charity, we obtain several new existential and computational results for feasible envy-freeness ( 𝖥𝖤𝖥 \mathsf{FEF} ); this fairness notion requires that agents are envy-free, considering only budget-feasible subsets. First, we simplify and extend known existential results for 𝖥𝖤𝖥 \mathsf{FEF} allocations. Then, we show that the space of 𝖥𝖤𝖥 \mathsf{FEF} allocations has a non-convex structure. Next, using a fixed-point argument, we establish a novel guarantee that 𝖥𝖤𝖥 \mathsf{FEF} can always be achieved with Pareto-optimality. Furthermore, we give an alternative proof of the fact that one cannot additionally obtain truthfulness in this context: There does not exist a mechanism that is simultaneously truthful, fair, and Pareto-optimal. On the positive side, we show that truthfulness is compatible with each of 𝖥𝖤𝖥 \mathsf{FEF} and Pareto-optimality, individually. 1 Introduction Dividing items fairly among agents with individual preferences is a central requirement in many domains. Problems ranging from distributing land among communities to allocating computing resources among organizational groups can all be addressed using fair division frameworks. Motivated by such considerations, over the past seventy years, research efforts in the economics, computer science, and mathematics literature have resulted in significant developments in fair division [ 16 , 4 , 1 ] . Classic work focused on the fair division of a single divisible and heterogeneous resource, referred to as a cake [ 18 ] . Starting with this cake cutting setup, the fairness notion that has been predominantly studied in the literature is envy-freeness [ 11 , 22 ] . An allocation is said to be envy-free if no agent values the bundle of any other agent higher than her own. Another desired property when dividing resources is economic efficiency. A standard way of formalizing this desideratum is Pareto-optimality. Specifically, an allocation is said to be Pareto-optimal if we cannot increase the value of any agent, via reallocations, without reducing that of someone else. Notably, in the divisible-goods setting, fairness and efficiency—formalized through envy-freeness and Pareto-optimality, respectively—can be achieved together [ 22 ] . Specifically, it is known that an allocation that maximizes the Nash social welfare (the geometric mean of agents’ valuations) is both envy-free and Pareto-optimal. Furthermore, one can maximize the Nash social welfare by solving the well-known convex program of Eisenberg and Gale [ 8 ] . Hence, in the current context of divisible goods, fair and efficient allocations can, in fact, be computed in polynomial time. The interplay of fairness and efficiency is a central theme in fair division literature and has been studied in various other contexts, including in the setting of indivisible goods [ 6 ] . However, most existing fair division results (with or without efficiency considerations) assume that the agents have no restrictions on the goods they can receive. This assumption does not always capture real-world scenarios. For instance, in fair land division, a natural requirement is to ensure that each agent receives a connected plot [ 19 ] . Motivated by such considerations, recent works have considered fair division under allocation constraints [ 20 ] . The current work contributes to this active thread of research and establishes fairness and efficiency guarantees under generalized assignment constraints. These constraints capture the allocation requirements inherent in numerous real-world domains; see multiple applications surveyed in [ 17 ] . Here, each divisible good has an agent-specific size and value, and each agent has a budget which constrains the size of her bundle. Also, note that, in such a constraint setting, it may not always be feasible to assign all goods to the agents while respecting the budget constraints. Hence, as in recent works (see, e.g., [ 3 ] ), we conform to the construct of charity to denote the set of unassigned goods. In this constrained setting with charity, our work establishes fairness guarantees considering a notion called feasible envy-freeness (FEF) [ 7 , 23 , 3 ] . This notion extends envy-freeness and is formulated with the idea that it is unreasonable to expect two agents, with significantly different budgets, to receive bundles of comparable value. Hence, FEF requires that agents are envy-free, considering only budget-feasible subsets. Specifically, an allocation is said to be feasibly envy-free (FEF) if and only if each agent i values her bundle over every budget-feasible subset 1 1 1 For ease of exposition, even for divisible goods, we use the term subset to denote fractional assignments of the goods. within any other agent’s bundle; an analogous guarantee is required against the charity. 1.1 Our Results and Contributions This section details our fairness, efficiency, and truthfulness results for allocating divisible goods among agents with additive valuations and under generalized assignment constraints. Our contribution is summarized pictorially in the triangle below. Fairness: Prior work [ 3 ] has shown that, under generalized assignment constraints, \mathsf{FEF} allocations of divisible goods always exist and can be found efficiently. We develop an alternate proof of the existence for \mathsf{FEF} allocations. Our result, in fact, generalizes the previously known existential guarantee by encapsulating a more general class of constraints and valuations (Theorem 3.4 in Section 3 ). Our proof here is non-constructive and, hence, does not directly lead to an algorithm. We also present a fair division instance with simple constraints, in which the space of \mathsf{FEF} allocations is not convex (Theorem 4.1 in Section 4 ). This comes in contrast to the unconstrained setting where envy-free allocations can be easily characterized by a set of linear inequalities. This places in context the earlier algorithm of 3 , which employs a series of parameterized linear programs in the computation of an \mathsf{FEF} allocation. Fairness and Efficiency: We establish (in Section 5 ) that, under generalized assignment constraints, there always exists an \mathsf{FEF} allocation that is also Pareto-optimal (among all feasible allocations). This fairness plus efficiency guarantee resolves, in the positive, an open question posed in [ 3 ] . Furthermore, our proof implies the PPAD-membership of computing \mathsf{FEF} and Pareto-optimal (PO) allocations. It is relevant to note that a special case of this computational problem is already known to be PPAD-hard [ 21 ] . Fairness, Efficiency, and Truthfulness: Finally, we show (in Section 6 ) that one cannot additionally achieve truthfulness in this context: There does not exist a truthful mechanism for finding \mathsf{FEF} and PO allocations. Interestingly, our impossibility result is not confined to the constrained setting, i.e., it also holds in the standard, unconstrained setup. This instantiation to the unconstrained context is interesting in and of itself, 2 2 2 In particular, this negative result implies that one cannot extend the classic work of Varian [ 22 ] to include truthfulness. and we would not be surprised if it is a folklore result; still, to the best of our

Read the complete text