PaperlayerView exact revision on arXiv

Source-linked AI summary

The Core of the Participatory Budgeting Problem

Brandon Fain, Ashish Goel, Kamesh Munagala

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

TL;DR

Participatory budgeting requires fairly aggregating community preferences when funded projects benefit everyone simultaneously. The paper characterizes Lindahl equilibrium to compute core allocations and reports efficient exact computation for non-satiating utilities, alongside an empirical coincidence between core and welfare.

  • Problem

    How can community preferences be fairly aggregated into project funding when projects are public goods benefiting all users simultaneously?

    Source: §1 · p. 1

  • Method

    The paper characterizes Lindahl equilibrium using common allocation variables, computes the core through convex programming, and adapts the exponential mechanism for approximate truthfulness.

    Source: §1.4 · p. 6, §4 · p. 14, §5 · p. 18

  • Results

    The paper gives an efficient exact core algorithm for non-satiating utilities and reports that the core empirically coincides with welfare.

    Source: §1.4 · p. 6, §3.3 · p. 14

  • Takeaways & Limitations

    The observed core–welfare coincidence is notable because core allocations can differ when a significant minority has orthogonal preferences.

    Source: §3.3 · p. 14

    The computational complexity for more general utility functions, especially without the non-satiating assumption, remains unresolved.

    Source: §5 · p. 18

Abstract

from arXiv · show

In participatory budgeting, communities collectively decide on the allocation of public tax dollars for local public projects. In this work, we consider the question of fairly aggregating the preferences of community members to determine an allocation of funds to projects. This problem is different from standard fair resource allocation because of public goods: The allocated goods benefit all users simultaneously. Fairness is crucial in participatory decision making, since generating equitable outcomes is an important goal of these processes. We argue that the classic game theoretic notion of core captures fairness in the setting. To compute the core, we first develop a novel characterization of a public goods market equilibrium called the Lindahl equilibrium, which is always a core solution. We then provide the first (to our knowledge) polynomial time algorithm for computing such an equilibrium for a broad set of utility functions; our algorithm also generalizes (in a non-trivial way) the well-known concept of proportional fairness. We use our theoretical insights to perform experiments on real participatory budgeting voting data. We empirically show that the core can be efficiently computed for utility functions that naturally model our practical setting, and examine the relation of the core with the familiar welfare objective. Finally, we address concerns of incentives and mechanism design by developing a randomized approximately dominant-strategy truthful mechanism building on the exponential mechanism from differential privacy.

1 Introduction

Participatory budgeting must allocate public goods that benefit voters simultaneously, making fairness central to turning community preferences into funding plans. The paper studies core allocations, their computation, their behavior on real voting data, and incentive-compatible mechanisms.

1 Introduction

  • The core rules out a group using its proportional budget share to make every member better off; it captures group sharing incentives for public goods.For a single voter, this also captures the sharing incentive that they receive at least the utility attainable with their own B/n budget.Source: §1 · p. 2

1.1 Utility Functions

  • Scalar-separable utilities naturally convert scalar-valued preferences such as approval votes into cardinal utilities; saturating utilities also model project budgets and limited project selections.In the experiments, project costs set the saturation amounts, while approval votes determine which projects each voter values.Source: §1.1 · pp. 3–4

1.2 Computing Core Solutions via the Lindahl Equilibrium

  • In the public-goods Lindahl equilibrium, each voter optimizes at per-voter prices within budget B/n, while the allocation maximizes aggregate-price profit; such an equilibrium lies in the core.The prices are hypothetical, and the authors eliminate them from their equilibrium characterization.Source: §1.2 · p. 5

1.3 Truthfulness and Mechanisms

  • Core outcomes can be manipulated through free riding, and incentives to misreport need not vanish as the voter population grows.The paper therefore studies the stronger dominant-strategy notion rather than strategy-proofness in the large, which assumes knowledge of a preference distribution.Source: §1.3 · pp. 5–6

1.4 Our Results

  • The allocation-variable Lindahl characterization supports exact core computation for non-satiating utilities, real-data heuristics for saturating utilities, and an approximately truthful mechanism for homogeneous utilities.The paper presents these as answers to its computational and incentive questions, alongside empirical evaluation on Stanford participatory-budgeting data.Source: §1 · p. 3, §1.4 · pp. 6–7
  • For homogeneous utilities, proportional fairness computes the Lindahl equilibrium, and quadratic voting can elicit the gradient of its objective.For more general utilities, the paper views its potential function as a regularized proportional-fairness objective on a nonlinear utility transform.Source: §1.4 · p. 6
  • On real participatory-budgeting data, the heuristic efficiently computes exact core allocations whose outcomes match welfare-optimal solutions on the same utility functions.The data are modeled with saturating utility functions.Source: §1.4 · p. 6

1.5 Related Work

  • Unlike prior proportional-fairness work for linear utilities, this paper treats scalar-separable utilities and seeks dominant-strategy truthful public-good allocation without payments.The authors distinguish this goal from related work focused on social welfare and mechanisms using payments.Source: §1.5 · p. 7

2 Non-Satiating Utilities: Characterization and Computation

For scalar separable concave utilities, the section characterizes Lindahl equilibrium without prices and gives a convex-programming route to computing it under non-satiation. It connects this approach to proportional fairness for homogeneous utilities and identifies where that connection does not extend straightforwardly.

2 Non-Satiating Utilities: Characterization and Computation

  • The model uses utilities U_i(x) = Σ_j u_ij f_j(x_j), with smooth, non-decreasing, concave f_j and nonnegative u_ij.Allocations are nonnegative and subject to the overall budget B.Source: §2 · pp. 7–8

2.1 Characterization

  • For scalar separable utilities, Lindahl equilibrium is characterized directly through allocation variables, eliminating the price variables.The characterization requires the stated inequality for each item to be tight when its allocation x_j is positive.Source: §2.1 · p. 8, §2 · p. 8

2.2 Efficient Computation

  • Under non-satiation, an approximately optimal convex-program solution yields an approximate core allocation, enabling polynomial-time computation for a broad class of concave functions.The class is bounded by the condition that each f_j grows faster than ln x_j while remaining concave.Source: §2.2 · pp. 8–9

2.3 Connection to Proportional Fairness

  • For degree-one homogeneous utilities, Lindahl equilibrium coincides with the proportional-fair allocation maximizing Σ_i log U_i(x) under the budget constraint.The linear-utility case is included.Source: §2.3 · p. 9
  • For homogeneous utilities, quadratic voting elicits a user’s utility-gradient direction, providing information for stochastic gradient descent to compute a proportionally fair allocation.The elicitation asks the user to maximize utility within an ℓ2-ball around the current allocation; as its radius approaches zero, the resulting direction aligns with the gradient.Source: §2.3 · p. 10
  • For non-homogeneous utilities, the potential uses a nonlinear utility transform and regularization that proportional fairness on transformed inputs does not capture.With disjoint-preference groups and power utilities, core allocations scale with group size, whereas proportional fairness scales with α_j times group size.Source: §2.3 · p. 10

3 Saturating Utilities: Approximation and Experiments

For saturating utilities, the paper gives an efficient approximate-core guarantee and heuristically computes near-exact core solutions on real participatory-budgeting data; core and welfare allocations usually coincide.

3 Saturating Utilities: Approximation and Experiments

  • The experiments use seven elections’ approval-vote data, with 200–3,000 voters and at most 30 projects, modeled using saturating utilities.The data are binary voter-by-project matrices; voters typically select at most four or five projects.Source: §3 · p. 11

3.1 Efficiently Approximating the Core

  • The theorem gives an efficiently computable α-approximate multiplicative core for any ε > 0, with α determined by ε and the ratio of total budget to the smallest project budget.The stated α is (1/ε)(B/s)^ε + 1 − 1/ε, where s is the smallest project budget.Source: §3.1 · p. 11

3.2 Heuristically Computing the Exact Core

  • The heuristic binary-searches allocation and price variables to reduce the largest Lindahl-condition violation, yielding an ε-approximate additive core if the process converges.It repeats this procedure until all item conditions are satisfied to accuracy ε.Source: §3.2 · p. 12
  • The dynamics lack a convergence guarantee and can cycle, but small additive noise to votes empirically restored convergence across the datasets.Figure 3 plots Lindahl-condition error against iterations; the text reports comparable convergence for all seven datasets.Source: §3.2 · p. 12, Figure 3 · p. 12

3.3 Comparing the Core with WELFARE

  • CORE and WELFARE compute the same integer allocations on almost all datasets, and high budget similarity implies that fractional core allocations are almost integral.The Boston example has identical integer allocations under both schemes.Source: §3.3 · pp. 13–14, Figure 4 · p. 13, Figure 5 · p. 13
  • Welfare and core can differ when a significant minority has preferences orthogonal to the majority, despite their observed similarity in these datasets.The authors offer approximately independent random preferences as one possible explanation for the observed similarity.Source: §3.3 · p. 14

4 Homogeneous Utilities: Mechanism Design

For homogeneous utilities in a large market, the paper develops a randomized mechanism based on the exponential mechanism to approximate the core while providing approximate dominant-strategy truthfulness.

4 Homogeneous Utilities: Mechanism Design

  • The mechanism targets approximately core outcomes and approximate dominant-strategy truthfulness for homogeneous degree-one utilities, under the large-market condition k = o(n^1/2).The paper presents the mechanism for linear utilities, noting that it generalizes to degree-one homogeneous functions.Source: §4 · p. 14

4.2 Exponential Mechanism

  • The exponential mechanism samples allocations according to a score for core approximation; the paper states that it can find an approximate core while providing approximate truthfulness.The score is designed for allocation outcomes, rather than directly optimizing the proportional-fairness objective as a separable score.Source: §4 · p. 14, §4.2 · p. 16

4.1 The Scoring Function and its Approximation

  • The scoring approach relates to proportional fairness’s gradient optimality condition and trades score sensitivity against approximation to truthfulness and the core.Its sensitivity to one agent’s report is bounded by 1.Source: §4.1 · p. 15

5 Conclusion

The paper characterizes the Lindahl equilibrium in common allocation variables, enabling core allocations to be computed through a convex program. Experiments find core allocations similar to welfare allocations under saturating utility, while computational questions remain open for more general utilities.

  • The paper expresses the Lindahl equilibrium, and hence the core, using common allocation variables and computes core allocations as solutions to a convex program.Source: §5 · p. 18
  • A randomized adaptation of the exponential mechanism computes approximate core allocations while guaranteeing approximate truthfulness.Source: §5 · p. 18
  • On real data, core allocations are similar to welfare allocations under the saturating utility model.Source: §5 · p. 18
  • The computational complexity for more general utility functions remains unknown, including whether Lindahl equilibria can be computed efficiently without the non-satiation assumption.Source: §5 · p. 18

A Approximate Lindahl Equilibrium

An additive approximation to the Lindahl equilibrium conditions implies an additively approximate core solution. The appendix presents this implication through a theorem and a price-based proof argument.

B Core under Independent Preferences

Under an independent random-users model, the welfare-maximizing project set is an approximate integral core solution when its expected utility exceeds the theorem's stated threshold. Tests on voting data find large groups of correlated projects, so independence alone does not explain the observed similarity between core and welfare outcomes.

Loading 1610.03474v2…