Skip to main content
Journal cover image

Auditing for Core Stability in Participatory Budgeting

Publication ,  Conference
Munagala, K; Shen, Y; Wang, K
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 2022

We consider the participatory budgeting problem where each of n voters specifies additive utilities over m candidate projects with given sizes, and the goal is to choose a subset of projects (i.e., a committee) with total size at most k. Participatory budgeting mathematically generalizes multiwinner elections, and both have received great attention in computational social choice recently. A well-studied notion of group fairness in this setting is core stability: Each voter is assigned an “entitlement” of kn, so that a subset S of voters can pay for a committee of size at most |S|·kn. A given committee is in the core if no subset of voters can pay for another committee that provides each of them strictly larger utility. This provides proportional representation to all voters in a strong sense. In this paper, we study the following auditing question: Given a committee computed by some preference aggregation method, how close is it to the core? Concretely, how much does the entitlement of each voter need to be scaled down by, so that the core property subsequently holds? As our main contribution, we present computational hardness results for this problem, as well as a logarithmic approximation algorithm via linear program rounding. We show that our analysis is tight against the linear programming bound. Additionally, we consider two related notions of group fairness that have similar audit properties. The first is Lindahl priceability, which audits the closeness of a committee to a market clearing solution. We show that this is related to the linear programming relaxation of auditing the core, leading to efficient exact and approximation algorithms for auditing. The second is a novel weakening of the core that we term the sub-core, and we present computational results for auditing this notion as well.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783031228315

Publication Date

January 1, 2022

Volume

13778 LNCS

Start / End Page

292 / 310

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Munagala, K., Shen, Y., & Wang, K. (2022). Auditing for Core Stability in Participatory Budgeting. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 13778 LNCS, pp. 292–310). https://doi.org/10.1007/978-3-031-22832-2_17
Munagala, K., Y. Shen, and K. Wang. “Auditing for Core Stability in Participatory Budgeting.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 13778 LNCS:292–310, 2022. https://doi.org/10.1007/978-3-031-22832-2_17.
Munagala K, Shen Y, Wang K. Auditing for Core Stability in Participatory Budgeting. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2022. p. 292–310.
Munagala, K., et al. “Auditing for Core Stability in Participatory Budgeting.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13778 LNCS, 2022, pp. 292–310. Scopus, doi:10.1007/978-3-031-22832-2_17.
Munagala K, Shen Y, Wang K. Auditing for Core Stability in Participatory Budgeting. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2022. p. 292–310.
Journal cover image

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783031228315

Publication Date

January 1, 2022

Volume

13778 LNCS

Start / End Page

292 / 310

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences