Existence and Computation of Fair Allocations under Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912932286169088 |
|---|---|
| author | Barman, Siddharth Caragiannis, Ioannis Shyam, Sudarshan |
| author_facet | Barman, Siddharth Caragiannis, Ioannis Shyam, Sudarshan |
| contents | 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 (FEF); this fairness notion requires that agents are envy-free, considering only budget-feasible subsets.
First, we simplify and extend known existential results for FEF allocations. Then, we show that the space of FEF allocations has a non-convex structure. Next, using a fixed-point argument, we establish a novel guarantee that 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 FEF and Pareto-optimality, individually. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_00411 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Existence and Computation of Fair Allocations under Constraints Barman, Siddharth Caragiannis, Ioannis Shyam, Sudarshan Computer Science and Game Theory 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 (FEF); this fairness notion requires that agents are envy-free, considering only budget-feasible subsets. First, we simplify and extend known existential results for FEF allocations. Then, we show that the space of FEF allocations has a non-convex structure. Next, using a fixed-point argument, we establish a novel guarantee that 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 FEF and Pareto-optimality, individually. |
| title | Existence and Computation of Fair Allocations under Constraints |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2603.00411 |