PaperlayerView exact revision on arXiv

Source-linked AI summary

Fair Allocation of Indivisible Public Goods

Brandon Fain, Kamesh Munagala, Nisarg Shah

arXiv:1805.03164v2cs.GTcs.CYcs.DScs.MA

TL;DR

Individual-agent fairness can miss groupwise concerns in indivisible public-good allocation. The paper develops efficient algorithms for approximate core outcomes, with a (0, 2)-core guarantee for matroid bases and computable constant-δ guarantees for matchings.

  • Problem

    Individual-agent fairness axioms can treat allocations giving some agents zero utility as equally good, while groupwise core fairness is sought for indivisible public goods.

    Source: §1 · p. 2

  • Method

    The authors develop efficient algorithms for integral core approximations using variants of the Nash welfare objective.

    Source: §2.1 · p. 9, §6 · p. 22

  • Results

    For matroid bases, a (0, 2)-core outcome is guaranteed; for matchings, a (δ, 8 + 6/δ)-core outcome is computable for constant δ ∈ (0, 1].

    Source: §1.5 · p. 5

  • Takeaways & Limitations

    These algorithms establish nontrivial existence of integral core approximations and achieve exact Pareto efficiency under matroid and matching constraints.

    Source: §6 · p. 22

    For packing constraints, whether any (δ, α)-core exists for constant δ > 0 and α = O(1) remains open.

    Source: §6 · p. 22

Abstract

from arXiv · show

We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume that agents have additive utilities across elements. Our model generalizes existing frameworks such as fair public decision making and participatory budgeting. We study a groupwise fairness notion called the core, which generalizes well-studied notions of proportionality and Pareto efficiency, and requires that each subset of agents must receive an outcome that is fair relative to its size. In contrast to the case of divisible public goods (where fractional allocations are permitted), the core is not guaranteed to exist when allocating indivisible public goods. Our primary contributions are the notion of an additive approximation to the core (with a tiny multiplicative loss), and polynomial time algorithms that achieve a small additive approximation, where the additive factor is relative to the largest utility of an agent for an element. If the feasibility constraints define a matroid, we show an additive approximation of 2. A similar approach yields a constant additive bound when the feasibility constraints define a matching. More generally, if the feasibility constraints define an arbitrary packing polytope with mild restrictions, we show an additive guarantee that is logarithmic in the width of the polytope. Our algorithms are based on variants of the convex program for maximizing the Nash social welfare, but differ significantly from previous work in how it is used. Our guarantees are meaningful even when there are fewer elements than the number of agents. As far as we are aware, our work is the first to approximate the core in indivisible settings.

1 Introduction

The paper studies fair choices among public goods, where every agent shares the chosen outcome and individual proportionality can miss whether large groups are represented. It defines an approximate core and gives polynomial-time algorithms for several feasibility constraints.

1 Introduction

  • The core addresses cases where vote tallying may ignore a large minority, unlike individual fairness criteria that can treat every allocation as equally good.The motivating example contrasts funding the two most popular projects with a compromise that reflects larger groups' preferences.Source: §1 · pp. 1–2

1.1 Public Goods Model

  • The model represents public goods as feasible subsets of elements, with additive agent utilities, and includes issue choices and resource-packing constraints.Its constraint settings include matroids, matchings, and packing constraints; public decision making corresponds to a partition matroid.Source: §1.1 · p. 2, Matching Constraints · pp. 2–3, Matroid Constraints · p. 2

1.2 Prior Work: Fairness Properties

  • Integral outcomes may fail even approximate proportionality, while proportionality up to one issue is vacuous when issues are fewer than agents.The paper asks for a stronger group-level fairness notion because individual guarantees may not reflect large groups' wishes.Source: §1.2 · pp. 3–4

1.3 Summary of Contributions

  • The paper studies the core for integer allocations and extends it with additive and multiplicative relaxation parameters to provide guarantees for coalitions of every size.The core combines proportionality and Pareto efficiency, and its additive guarantee is scaled to the maximum utility from one element.Source: §1.4 · p. 4, Approximate Core · pp. 4–5

1.5 Our Results

  • Polynomial-time algorithms achieve a (0, 2 + ε)-core for matroid constraints and a (δ, 8 + 6/δ)-core for matchings, for constant δ in (0, 1].For public decision making, private goods, and multi-winner elections, every coalition receives a guarantee close to the individual guarantee of Conitzer et al..Source: §1.5 · p. 5
  • For packing constraints, the additive guarantee depends on width ρ and improves as constraints become easier; the stated theorem assumes b_k = ω(log K).The paper also extends its techniques to an endowment-based core for packing constraints, but gives no efficient algorithm for that model.Source: Matching Constraints · p. 3, §1.5 · pp. 5–6

1.6 Related Work

  • The approach connects smooth Nash-welfare local search to core approximations, alongside related fractional-core and endowment-based work; strategic incentives are outside the paper's scope.For matroid and matching constraints, the authors modify the integer Nash-welfare objective and use polynomial-time local search.Source: §1.6 · pp. 6–8

2 Prelude: Nash Social Welfare

The section motivates Nash social welfare as a fairness-oriented objective, then shows why integer and fractional variants behave differently for the core. It introduces smoothing for indivisible outcomes and uses fractional MNW to establish core guarantees.

2 Prelude: Nash Social Welfare

  • Nash social welfare, the sum of log utilities, balances utilitarian and egalitarian objectives, is scale invariant, and generally favors more equal utility distributions.The integer MNW solution can prioritize the largest set of agents receiving nonzero utility before maximizing their product of utilities.Source: §2 · p. 8, §2.1 · p. 8

2.1 Integer Nash Welfare and Smooth Variants

  • Integer MNW can fail to approximate the core even in public decision making, while a different outcome in the example is a (0, 1)-core outcome.The example also shows that proportionality or proportionality up to one issue can hold without yielding a reasonable core approximation.Source: §2.1 · pp. 8–9
  • Smoothing adds a parameter ℓ to each agent's utility inside the log objective; ℓ=0 recovers Nash welfare, while ℓ=1 is NP-hard to optimize.The paper motivates smoothing by the Nash welfare objective's sensitivity to zero utility.Source: §2.1 · p. 9
  • For matroid constraints, local search on smooth Nash welfare yields a (0, 2)-core outcome; for matching constraints, it yields a core outcome with a stated additive guarantee.The matching guarantee's numeric bound is incomplete in the supplied passage.Source: §2.1 · p. 9

2.2 Fractional Max Nash Welfare Solution

  • The fractional MNW solution lies in the core, but can be irrational with rational inputs; the section also states a polynomial-time theorem for computing a fractional approximate core outcome.The paper says an approximately utility-preserving fractional solution suffices for its approximation results.Source: §2.2 · pp. 9–10

3 Matroid Constraints

For matroid constraints, smooth Nash welfare gives an additive core approximation, and local search computes a slightly weaker guarantee in polynomial time. The analysis also establishes limits on stronger guarantees and a stronger result for private goods.

3 Matroid Constraints

  • The smooth Nash welfare optimum gives a (0, 2)-core outcome, while local search gives a (0, 2 + ǫ)-core outcome in polynomial time.The local search starts from a matroid basis and repeatedly performs feasible one-element swaps that improve its objective.Source: §3 · p. 10, §3.2 · p. 10, §3.1 · p. 10

3.2 Analysis

  • The local-search analysis rules out a blocking coalition for its (0, 2 + ǫ)-core guarantee by showing that such a deviation would imply an improving feasible basis swap.The corresponding global-optimum argument establishes the (0, 2)-core guarantee.Source: §3.2 · p. 11
  • For matroid constraints, a (0, 1 − ǫ)-core outcome is not guaranteed for any ǫ > 0, so the (0, 2) guarantee is tight up to a unit additive relaxation.Whether a (0, 1)-core outcome always exists under matroid constraints remains open.Source: §3.2 · p. 12
  • For private goods, maximizing smooth Nash welfare with ℓ=1 returns a (0, 1)-core outcome.This is a stronger guarantee than the general matroid result stated in the section.Source: §3.2 · p. 12

4 Matching Constraints

For matching constraints, local search over bounded-size augmentations yields a polynomial-time approximate core outcome. The section also gives a lower bound showing that additive approximation below 1 is not guaranteed, even with multiplicative relaxation.

4 Matching Constraints

  • The search tests bounded-size matching augmentations, replacing the currently matched edges that touch the augmentation with its edges.The analysis constructs a multiset of augmentations from the symmetric difference of the current and comparison matchings.Source: Algorithm · p. 13, Analysis · p. 14
  • A polynomial-time local search for matching constraints returns a (δ, 8 + 3κ)-core outcome, with κ = 2/δ.For constant δ, the analysis bounds the number of iterations by O(m^2/δ), with each iteration checking augmentations of size at most κ.Source: Analysis · pp. 13–14, Algorithm · p. 13
  • No (δ, α)-core outcome is guaranteed for matching constraints when δ ≥ 0 and α < 1.In the K2,2 example, one agent has zero utility in every outcome and can deviate to obtain utility 2.Source: Analysis · p. 15

5 General Packing Constraints

This section develops and analyzes a polynomial-time rounding approach to approximate the core under general packing constraints, including conditions under which a solution satisfies a (δ, α)-core guarantee.

5.1 Maximal Proportionally Fair Outcome

  • An MPF outcome minimizes the proportional-fairness factor r, and its value R satisfies R ≤ min(Vmax, n, ρ); an MPF outcome is computable in polynomial time.An r-PF outcome gives each agent an r fraction of its maximum feasible utility after a unit additive relaxation.Source: §5.1 · p. 16

5.2 Result and Proof Idea

  • Theorem 5 establishes a polynomial-time computable (δ, α)-core outcome under its packing assumptions.The proof bounds utility deviations and then uses the resulting guarantees to establish the approximate-core condition.Source: §5.2 · p. 17
  • The proof idea adds a small amount of an MPF outcome to the fractional core before randomized rounding, because preserving every agent’s core utility directly can require a large additive loss.The passage notes that the MPF outcome gives each agent substantial utility but can differ substantially from a core outcome.Source: §5.2 · pp. 17–18

5.3 Algorithm

  • The algorithm combines an approximate fractional-core solution with an MPF outcome, scales their mixture, and independently rounds elements into an integral outcome.The analysis states that the algorithm runs in expected polynomial time and has constant probability of returning a feasible outcome satisfying Theorem 5’s guarantee.Source: §5.2 · p. 18, §5.3 · p. 18, §5.4 · p. 18

5.4 Analysis

  • The analysis scales down before rounding so packing constraints hold with probability at least 0.99, and the core guarantee holds with probability at least 1/6.Together these events yield a constant probability of a feasible outcome satisfying the guarantee.Source: §5.4 · p. 18

5.4.1 Grouping Agents

  • Agents are partitioned into exponentially decreasing utility groups: heavy-group agents receive an MPF utility guarantee, while the light group may receive none.The grouping is based on each agent’s maximum feasible utility Vi.Source: §5.4.1 · pp. 18–19

5.4.2 Bounding Violations of Utility Preservation

  • Theorem 6 bounds utility-preservation violations across the heavy and light groups, with both stated inequalities holding simultaneously with probability at least 1/6.The heavy-group analysis uses the MPF utility guarantee; the light-group analysis allows additive as well as multiplicative approximation.Source: §5.4.2 · pp. 19–20

5.4.3 Approximate Core

  • Theorem 7 uses the preserved-utility agents to show that every coalition and alternative outcome has an agent satisfying the approximate-core condition.The proof handles coalitions with many preserved agents using fractional-core optimality, and those with fewer by bounding deviating utility among agents outside that set.Source: §5.4.3 · pp. 20–21
  • A solution satisfying Theorem 6 is a (δ, α)-core solution for every α > α∗, given the existence of such an agent.This completes the proof of Theorem 5.Source: §5.4.3 · p. 22

6 Conclusion

The paper establishes integral outcomes that approximate the core, with exact Pareto efficiency for globally optimized smooth-Nash-welfare algorithms under matroid and matching constraints. It leaves tighter bounds and packing-constraint existence guarantees open, while linking core approximation to single-agent utility maximization.

6 Conclusion

  • For matroid and matching constraints, globally optimizing smooth Nash welfare achieves exact Pareto efficiency alongside approximate-core guarantees.The paper also establishes efficient algorithms producing constant or near-constant core approximations.Source: §6 · p. 22
  • For general packing constraints, it remains open whether a constant-additive approximate-core outcome exists, even without computation limits.The paper also leaves open whether a (0, 1)-core outcome always exists for matroid or matching constraints.Source: §6 · p. 22
  • The work connects multi-agent core approximation to single-agent utility maximization, including short augmenting paths from fast PRAM matching algorithms.This connection suggests a possible deeper link between efficiency and existence results.Source: §6 · p. 22

A Impossibility Examples

The examples show that small packing budgets can preclude approximate core outcomes, and that maximizing smooth Nash welfare need not produce a good core approximation for Knapsack. They also separate this failure from the computational difficulty of single-agent welfare maximization.

A Impossibility Examples

  • For b=1 and width ρ=2, a packing instance has no (δ, m/4)-core outcome for any δ>0.The example demonstrates why Theorem 3 assumes sufficiently large b.Source: A Impossibility Examples · p. 25
  • In a complete bipartite graph example, every feasible outcome gives one of two agents zero utility, while that agent can deviate to obtain scaled utility m/4.Thus, no feasible outcome is (δ, m/4)-core for any δ>0.Source: A Impossibility Examples · p. 25
  • The bipartite-graph example’s failure of core approximation is orthogonal to the computational difficulty of single-agent welfare maximization.The single-agent welfare-maximizing outcome in that example is simple to compute.Source: A Impossibility Examples · p. 25
  • For every ℓ>0, a Knapsack instance makes smooth Nash welfare return an outcome that is not an (O(m^1/2−ε), O(m^3/4−ε))-core, unlike Theorem 5’s constant-δ, logarithmic-α guarantee.The example’s construction selects large elements despite special agents’ incentive to deviate to small elements.Source: A Impossibility Examples · pp. 25–26

B.1 Proof of Theorem 4

The proof turns fractional Nash-welfare maximization into a convex minimization problem whose approximate solutions satisfy the approximate core condition. It uses ellipsoid optimization to compute such a solution efficiently.

B.1 Proof of Theorem 4

  • The objective Q(U) mimics the derivative of Nash social welfare after adding ε′=ε/(1+δ) to its utility terms.The regularization term is what distinguishes the stated objective from the unmodified derivative.Source: §B.1 · p. 26
  • Any utility vector U with Q(U)≤n(1+δ) is a (δ, ε)-core outcome, and the program’s optimum is attained by the fractional smooth Nash-welfare maximizer.That optimum has value n.Source: §B.1 · p. 27
  • The ellipsoid algorithm applies because the objective’s range and feasible-polytope diameter are exponentially bounded and the polytope is efficiently separable.Efficient subgradient computation and convexity are also required.Source: §B.1 · p. 27
  • Q is convex, and its subgradient can be computed by solving a linear program for U′ before differentiating with U′ fixed.The subgradient procedure is described across the proof’s steps.Source: §B.1 · p. 27

B.2 Proof of Lemma 7

The proof invokes a standard Chernoff bound for sums of independent bounded random variables. The supplied steps also state a conditional expectation range involving A, B, and γ.

B.2 Proof of Lemma 7

  • The proof identifies its concentration inequality as the standard Chernoff bound.Source: §B.2 · p. 27
  • The Chernoff theorem is stated for independent random variables X_j in [0,1] and their sum X.The bound is considered for ε∈(0,1).Source: §B.2 · p. 27
  • In the stated case (1−γ)A<B, the proof gives γB≤E[X]≤(1+γ)B.Source: §B.2 · p. 28

C Endowments-Based Core

The section studies a core definition in which a coalition’s available budget scales with its size rather than its utility being scaled. It applies dependent rounding to fractional core outcomes, while noting unresolved computation and existence questions.

C Endowments-Based Core

  • The randomized-rounding approach extends to a slightly different core definition and yields approximation results for Approval Voting and general packing problems.The section states these results for (δ, α)-core outcomes, without giving the complete α bounds in the supplied passages.Source: C Endowments-Based Core · pp. 28–30
  • Under the endowments-based definition, a coalition may use budget B|S|/n without scaling down its utility.This contrasts with the earlier definition, which gives a coalition the full budget but scales its utility by |S|/n.Source: C Endowments-Based Core · p. 28
  • A fractional core outcome is known to exist for Approval Voting, but whether it or an approximate core can be computed in polynomial time remains unknown.Source: C Endowments-Based Core · p. 28
  • Whether an integral core always exists for Approval Voting is open, while a nearby participatory-budgeting setting with nonbinary utilities and unequal item sizes can lack one.Theorem 4 does not apply to this endowments-based definition.Source: C Endowments-Based Core · p. 28
  • Dependent rounding converts a fractional core outcome into an integral one while preserving each element’s selection probability, the budget constraint, and negative correlation.The algorithm is not necessarily polynomial-time because polynomial-time computation of the fractional core outcome is unknown.Source: C Endowments-Based Core · p. 29

Related papers

Loading 1805.03164v2…