Source-linked AI summary
Fair Public Decision Making
Vincent Conitzer, Rupert Freeman, Nisarg Shah
TL;DR
The paper asks how to guarantee fairness when several public decisions must be made and each decision can benefit multiple players. It formalizes this setting, introduces three relaxations of proportionality, and studies their relationships with Nash welfare, Pareto optimality, algorithms, and hardness. MNW satisfies or approximates the relaxations, while the paper establishes both polynomial-time and hardness results for achieving them with or without Pareto optimality.
Problem
Fairness notions for private goods do not directly capture simultaneous public decisions, where a chosen alternative can provide positive utility to multiple players and proportionality is not always guaranteeable.
Method
The paper models outcomes as one chosen alternative per issue with additive utilities, then introduces Prop1, RRS, and PPS and analyzes mechanisms, Pareto optimality, and computational complexity.
Results
MNW satisfies Prop1 and Pareto optimality while providing a 1/n approximation to RRS and PPS in public decision making; for private goods, it completely satisfies PPS and gives an n/(2n−1) > 1/2 approximation to RRS.
Takeaways & Limitations
The three relaxations extend proportionality to public decisions, and MNW provides fairness and efficiency guarantees across both public decisions and private-goods division.
Takeaways & Limitations
The paper leaves open the existence and complexity of mechanisms satisfying RRS, Prop1, and PO, as well as whether MNW admits a constant RRS approximation better than 1/2.
Abstract
from arXiv · showhide
We generalize the classic problem of fairly allocating indivisible goods to the problem of \emph{fair public decision making}, in which a decision must be made on several social issues simultaneously, and, unlike the classic setting, a decision can provide positive utility to multiple players. We extend the popular fairness notion of proportionality (which is not guaranteeable) to our more general setting, and introduce three novel relaxations --- \emph{proportionality up to one issue, round robin share, and pessimistic proportional share} --- that are also interesting in the classic goods allocation setting. We show that the Maximum Nash Welfare solution, which is known to satisfy appealing fairness properties in the classic setting, satisfies or approximates all three relaxations in our framework. We also provide polynomial time algorithms and hardness results for finding allocations satisfying these axioms, with or without insisting on Pareto optimality.
1 Introduction
The paper generalizes fair division from private goods to simultaneous public decisions, where alternatives can benefit multiple players. It introduces proportionality relaxations and studies their compatibility with efficiency, computability, and established mechanisms.
- Motivation: The framework generalizes private-goods allocation, but envy is less meaningful when all players receive the same public decisions.Proportionality instead compares each player’s utility with the value of receiving her favorite alternative on every issue, divided by n.
- Model: Public decision making selects one alternative for each of several issues, with each player’s outcome utility equal to the sum across chosen alternatives.The model remains non-trivial despite independent issues and additive utilities.
- Fairness relaxations: Prop1, RRS, and PPS relax proportionality by allowing one favorable issue change, using a round-robin guarantee, or protecting against adversarially selected issues.RRS is based on receiving the utility guaranteed when a player is last in the round-robin ordering; PPS uses favorite alternatives on approximately a 1/n fraction of adversarially chosen issues.
- Mechanisms and efficiency: With Pareto optimality required, leximin satisfies RRS, PPS, and PO, while MNW satisfies Prop1 and PO and provides 1/n approximations to RRS and PPS for public decisions.For private goods, MNW completely satisfies PPS and gives an n/(2n−1) > 1/2 approximation to RRS.
- Complexity and open questions: Finding MNW or leximin outcomes is NP-hard; under P ≠ NP, public decisions have no polynomial-time method satisfying PPS or RRS together with PO, whereas private goods admit one for PPS and PO.The paper also identifies open questions about stronger guarantees and the complexity of satisfying additional axiom combinations.
2 Model
The paper models public decision making as choosing one alternative per issue, with additive utilities that may benefit multiple players, and adapts fairness concepts from private-goods division. It introduces proportionality relaxations motivated by one-issue changes and round-robin guarantees, alongside Pareto optimality.
- Public decision making: A public decision problem has m issues, one chosen alternative per issue, and n players with utilities for each issue’s alternatives.An outcome selects an alternative for every issue, and each player’s total utility is additive across the selected alternatives.
- Public decision making: Unlike private goods, a single public alternative can provide positive utility to multiple players.This distinguishes public decisions from allocations where players derive utility only from goods they receive.
- Connection to private goods: Public decision making generalizes private-goods division by representing each good as an issue whose alternatives allocate utility to individual players.Choosing the alternative associated with player i is equivalent to allocating good g to player i in the constructed instance.
- Efficiency and computational focus: The paper studies Pareto optimality, requiring that no alternative outcome improve one player without making another player worse off, together with the fairness axioms.It examines whether these properties can be satisfied jointly and notes that round robin satisfies Prop1 and RRS but not Pareto optimality.
- Fairness axioms: Proportionality requires each player’s outcome utility to reach 1/n of the maximum utility she could obtain across all issues, while Prop1 permits changing one issue in her favor.The paper defines α-proportionality by requiring ui(c) ≥ α · Propi and specializes α = 1 to Prop and Prop1.
- Fairness axioms: Round robin share captures utility from controlling issues in turn, while pessimistic proportional share values a proportional number of issues selected pessimistically.The round-robin guarantee is based on the player being last in the ordering; p = ⌊m/n⌋ issues underlies PPS.
3 (Approximate) Satisfiability of Axioms
The section studies which fairness guarantees can be achieved together with Pareto optimality. Round robin achieves several guarantees without efficiency, while leximin and MNW recover different combinations with Pareto optimality and approximation trade-offs.
- The round robin mechanism satisfies RRS, PPS, and Prop1 in polynomial time, but its outcome need not be Pareto optimal.Its lack of efficiency can arise when compromise alternatives make multiple players better off than issue-by-issue favorite choices.
- The leximin mechanism satisfies RRS, PO, and (1/2)-Prop1.The (1/2)-Prop1 guarantee follows from the lemma that RRS implies (1/2)-Prop1.
- The MNW solution satisfies Prop1 and PO.The proof establishes Pareto optimality by considering whether an improvement benefits a player outside the positive-utility set or increases utility within it.
- The MNW solution satisfies 1/n-RRS and 1/n-PPS, with both approximations tight up to a factor of O(log n).The result concerns the public decision-making setting, where MNW approximates RRS and PPS rather than satisfying them exactly.
- For private goods, EF1 implies PPS and n/(2n −1)-RRS but does not imply n/(2n −2)-RRS.Because MNW satisfies EF1, these implications provide corresponding lower bounds for MNW in private-goods division.
- For private goods, MNW satisfies PPS and n/(2n −1)-RRS, but for every ε > 0 it does not satisfy (2/3 + ε)-RRS.The section therefore leaves open whether MNW achieves a constant RRS approximation better than 1/2.
4 Computational Complexity
The section characterizes the computational trade-offs among fairness guarantees and Pareto optimality. It establishes hardness results for public decisions, a polynomial-time result for private goods, and the reductions supporting these claims.
- Hardness results: For public decision making, finding an outcome satisfying PPS and PO is NP-hard.The proof reduces from X33C, an NP-complete exact triple-cover problem.
- Reduction: The reduction’s exact-triple-cover construction uses replicated vertex groups and added sets to encode an X3C instance.The source problem asks whether q sets cover every vertex exactly once, while X33C requires each vertex to be covered exactly three times.
- Reduction: The X33C reduction creates one player and one issue per vertex, with alternatives encoding individual preferences and 3-sets.Each player’s PPS is 1 − ε, and the construction links Pareto-optimal PPS outcomes to exact triple-covers.
- Hardness results: For public decision making, finding an outcome satisfying RRS and PO is NP-hard.This follows from the relationship between RRS and PPS established in the hardness construction.
- Polynomial-time results: For private goods division, PPS and PO can be satisfied in polynomial time.The algorithm assigns at least floor(m/n) goods to every player and maximizes weighted utilitarian welfare, implying PPS and PO.
5 Discussion
The discussion places the framework between fair division and voting theory and considers randomized outcomes. It also identifies open questions about stronger fairness notions and computational guarantees.
- Open questions: Open questions include improving MNW’s approximation to RRS and finding mechanisms satisfying RRS, Prop1, and PO.The paper also leaves several existence and complexity questions unresolved.
- Randomization: Randomized MNW outcomes satisfy Prop, RRS, PPS, and Prop1 in expected utilities.The argument interprets issue-selection frequencies as randomized weights and uses Prop1 for deterministic outcomes.
- Open questions: The discussion asks whether a stronger public-decision fairness notion could generalize envy-freeness from private-goods division.The paper notes that deterministic mechanisms may not satisfy such a notion, while randomized mechanisms or relaxations might.
- Connections: The framework connects fair division theory and voting theory through collective outcomes based on individual preferences.Fair division typically uses cardinal utilities over private goods, whereas voting commonly aggregates preferences over alternatives.
- Randomization: A realized randomized outcome may fail Prop even though the lottery is fair under expected utilities.This distinction applies when fairness is evaluated over the lottery rather than a particular realization.
A Relationships Among Fairness Axioms
This section analyzes relationships among Prop1, RRS, and PPS. It shows that Prop1 does not approximate RRS or PPS in general, while RRS implies a 1/2-approximation to Prop1 for public decisions and has sharper private-goods behavior.
- General relationships: Prop1 provides no approximation to RRS or PPS for either public decisions or private goods.Instances exist where a player receives zero utility, satisfies Prop1, and nevertheless has non-zero PPS share.
- Public decisions: For public decisions, RRS implies 1/2-Prop1.Thus an RRS allocation guarantees at least half of the proportional-share benchmark after the one-issue relaxation.
- Private goods: For private goods, RRS implies Prop1 if and only if m ≤ 4n − 2.The theorem gives both sufficiency and necessity for this item-to-player threshold.
- Private goods: For m > 4n − 2, an allocation can satisfy RRS while failing Prop1.The construction gives player 1 only her most valuable good and shows that adding one good remains insufficient for proportionality.
- Private goods: When a player receiving her RRS share lacks proportionality, adding one suitable good can make her reach proportional share.The proof considers the most valuable unallocated good or the player’s tth most valuable good, depending on the allocation.
B Proof of Lemma 5
The proof develops a feasible-set exchange argument. Starting from a feasible set with a minimum entry above the threshold, it constructs another feasible set with improved product structure while preserving feasibility.
- Feasibility: A set of n non-negative numbers is feasible when its total is at least 1 − δ.The proof also derives a bound on the sum of individual deficits below 1.
- Exchange argument: The proof selects the minimum entry and then the second-lowest entry to construct a new feasible set.This ordering identifies where mass can be redistributed while maintaining the feasibility condition.
- Exchange argument: The constructed set leaves all entries except the selected ones unchanged and adjusts the selected entries to preserve feasibility.The proof checks feasibility through the resulting deficit terms.
- Boundary case: The argument completes by handling feasible sets whose smallest entry equals 1 − δ.This boundary case is needed to establish the claimed product-improvement property for all feasible sets.
C Proof of Theorem 14
The proof establishes that Algorithm 1 terminates and outputs an allocation satisfying PPS and PO. It preserves weighted-social-welfare optimality while using bounded inner-loop transfers and an outer-loop progress measure.
- Algorithm 1 produces an allocation satisfying PPS and PO by ensuring every player receives at least p goods and preserving weighted-social-welfare optimality.Property (A) implies PPS, while property (B) implies PO.
- Weighted-social-welfare optimality is preserved because goods are allocated to players maximizing wi · ui(g), and weight reductions stop at the first tie.The allocation changes also preserve optimality because the second inner loop transfers goods under the algorithm’s prescribed conditions.
- The first inner loop terminates after O(n) iterations because each iteration adds one player to DEC.Weights of players already in DEC are reduced, while a new player outside DEC joins the set.
- The second inner loop terminates in O(n) iterations while transferring goods to players in LS, maintaining goods for EQ players, and removing goods from GT players.Tracing back through prior DEC additions prevents indefinite continuation.
- The outer loop executes O(m) times because each iteration decreases the deficit metric by at least 1, from an initial value at most p · n ≤ m.Each iteration gives an additional good to a player in LS without adding new players to LS.
- The resulting asymptotic running time is determined by O(n · m) arg min computations inside the inner loops, together with O(m) outer-loop iterations.The bottleneck searches across goods owned by DEC players and players outside DEC.