Source-linked AI summary
A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
Haris Aziz, Herve Moulin, Fedor Sandomirskiy
TL;DR
Whether a Pareto-optimal and PROP1 allocation exists, and can be computed, remained open when utilities may be negative. The algorithm modifies an fPO allocation while preserving fPO, retaining only agents with highest weighted utility for each item. For mixed utilities, an integral allocation satisfying weighted PROP1 and fPO exists, and a strongly polynomial-time algorithm in n + m returns one; Algorithm 1 returns a weighted PROP1 allocation in O(n2m2(n + m)).
Problem
Whether a Pareto-optimal and PROP1 allocation exists, and can be computed, remained open when utilities may be negative.
Source: §1 · p. 1Method
The algorithm modifies an fPO allocation while preserving fPO, retaining only agents with highest weighted utility for each item.
Source: §3 · p. 6Results
For mixed utilities, an integral allocation satisfying weighted PROP1 and fPO exists, and a strongly polynomial-time algorithm in n + m returns one; Algorithm 1 returns a weighted PROP1 allocation in O(n2m2(n + m)).
Source: §3 · pp. 4, 6Takeaways & Limitations
The result establishes existence and efficient computation of an fPO and weighted PROP1 allocation for mixed utilities, without fixing the number of agents or items.
Source: §3 · p. 6Computing a utilitarian-maximal allocation within the set of PROP1 allocations is NP-hard.
Source: §4 · p. 9
Abstract
from arXiv · showhide
We consider fair allocation of indivisible items under additive utilities. When the utilities can be negative, the existence and complexity of an allocation that satisfies Pareto optimality and proportionality up to one item (PROP1) is an open problem. We show that there exists a strongly polynomial-time algorithm that always computes an allocation satisfying Pareto optimality and proportionality up to one item even if the utilities are mixed and the agents have asymmetric weights. We point out that the result does not hold if either of Pareto optimality or PROP1 is replaced with slightly stronger concepts.
1. Introduction
The paper addresses the open problem of finding Pareto-optimal and PROP1 allocations when utilities may be negative. It gives a strongly polynomial-time algorithm for mixed utilities and asymmetric weights, using a rounding approach that avoids equilibrium prices.
Motivation
- Existence and complexity of Pareto-optimal and PROP1 allocations remained open for mixed or negative utilities.For goods, earlier work established existence and a strongly polynomial-time algorithm; for chores, a weighted result applied when the number of agents or items was fixed.Source: §1 · p. 2
Contribution
- A strongly polynomial-time algorithm finds an fPO and PROP1 allocation for mixed utilities, any number of agents or items, and asymmetric weights.The result also implies several recent results for goods, chores, or weaker requirements.Source: §1 · p. 2
2. Preliminaries
The preliminaries define fractional and integral allocations, additive utilities with possibly mixed signs, and the weighted proportionality and consumption-graph concepts used in the paper.
Allocations
- A fractional allocation assigns item fractions, while an integral allocation assigns each item fully to one agent.Each item is allocated fully; an integral allocation is denoted by π, with π_i the set assigned to agent i.Source: §2 · p. 3
Utilities and efficiency
- Utilities are additive and may be positive, negative, or zero; an allocation is fPO if no fractional allocation Pareto-improves it.An integral allocation is PO if no integral allocation improves it, and every fPO integral allocation is PO.Source: §2 · p. 3
Proportionality
- Weighted PROP requires each agent i to receive utility at least u_i(O)b_i, and equal weights make weighted PROP1 equivalent to PROP1.The supplied definition of weighted PROP1 is incomplete.Source: §2 · p. 3
Consumption graph
- The consumption graph is bipartite, with agents and items as vertices and an edge when an agent receives a positive fraction of an item.Source: §2 · p. 3
3. Algorithm
The algorithm improves a fractional proportional allocation to an acyclic fractional Pareto-optimal allocation, then rounds it to an integral allocation. For mixed utilities and weighted agents, it guarantees weighted PROP1 and fPO in strongly polynomial time.
3. Algorithm
- The algorithm starts with a fractional proportional allocation, finds a Pareto-improving fPO allocation with an acyclic consumption graph, and rounds shared items to agents’ advantage.The acyclic graph forms trees; goods go to the active agent, while chores go to an agent sharing them, with the procedure continuing through the tree.Source: §3 · pp. 4–5
- The rounding terminates with no shared items, and the at-most-one-predecessor property yields weighted PROP1.The algorithm reallocates at least one shared item per outer iteration.Source: §3 · p. 5
- The rounding preserves fPO because it keeps each item with agents who have the highest weighted utility for that item, retaining the same weighted-welfare maximum.An fPO allocation maximizes weighted welfare for some strictly positive agent weights.Source: §3 · p. 6
- Different exploration choices can produce different fPO PROP1 allocations; choosing the best among them is left open.Breadth-first search and tie-breaking choices may be varied while preserving the stated properties.Source: §3 · p. 6
- For mixed utilities, an integral allocation satisfying weighted PROP1 and fPO always exists and can be found by a strongly polynomial-time algorithm in n + m.fPO is stronger than Pareto optimality.Source: §3 · p. 6
- The theorem recovers strongly polynomial-time results for two agents with mixed utilities, goods, and chores with a fixed number of agents or items.The respective guarantees are PO and PROP1, fPO and PROP1, and PO and weighted PROP1.Source: §3 · pp. 6–7
4. Discussion
The discussion contrasts prior maximin-share work on goods or chores with this paper’s mixed-utility setting and weighted PROP1 guarantee. It also describes a self-contained LP alternative and boundaries on strengthening the fairness or welfare guarantees.
4. Discussion
- Earlier maximin-share approaches address goods or chores, whereas this work considers mixed utilities and uses weighted PROP1, a relaxation of traditional proportionality.The discussion also notes that the earlier approaches target asymmetric agents.Source: §4 · pp. 7–8
- Algorithm 2 maximizes total utility subject to proportionality to obtain an fPO proportional allocation, then removes cycles through utility-preserving edge deletion.The cycle-removal argument preserves agents’ utilities while making the consumption graph acyclic.Source: §4 · p. 8
- Because Algorithm 2 uses linear programming, it guarantees only weakly polynomial time, unlike the paper’s strongly polynomial main algorithm.The main algorithm relies in Step 2 on the algorithm of Sandomirskiy and Segal-Halevi [14].Source: §4 · p. 8
- The simplex alternative can return a basic feasible solution, but may take exponential time in the worst case despite working well in practice.A basic feasible solution is an extreme point of the feasible set.Source: §4 · pp. 8–9
- Whether EF1 and Pareto optimality can coexist remains open, even for chores; replacing PROP1 with PROPX can fail even for goods.The discussion separately reports NP-hardness of computing a utilitarian-maximal allocation among PROP1 allocations [4].Source: §4 · p. 9
Appendix A. Examples
The examples show that a Pareto improvement can destroy PROP1, including in goods and chores settings. They also show that PROPX may fail to exist even for goods.
Appendix A. Examples
- The initial allocation in the 31-item example is PROP1: agent 1 has utility 0.2 and would reach 0.5 by additionally receiving item A.Source: Appendix A · p. 11
- In the chores example, the initial allocation is PROP1, but the Pareto-improved allocation is not PROP1.The instance has 3 agents and 12 items.Source: Appendix A · pp. 11–12
- A Pareto-improved allocation in the goods example fails PROP1: agent 1 remains at −0.36, below −1/3, even after removing a small A item.The example starts from a PROP1 allocation in a 31-item instance.Source: Appendix A · pp. 11–12
- In the goods example, PROPX is not satisfied: even with the small item, the last agent falls short of the proportionality value 13/3 > 4.The passage states this holds in any most balanced allocation.Source: Appendix A · p. 12