SpringerLink
Log in

Auditing for Core Stability in Participatory Budgeting

  • Conference paper
  • First Online:
Web and Internet Economics (WINE 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13778))

Included in the following conference series:

Abstract

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 \(\frac{k}{n}\), so that a subset S of voters can pay for a committee of size at most \(|S| \cdot \frac{k}{n}\). 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.

Supported by NSF grant CCF-2113798.

K. Wang—This work was done while Kangning Wang was at Duke University.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 64.19
Price includes VAT (France)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 79.11
Price includes VAT (France)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. The Stanford Participatory Budgeting Platform. https://pbstanford.org

  2. Aziz, H., Brandt, F., Elkind, E., Skowron, P.: Computational social choice: the first ten years and beyond. In: Steffen, B., Woeginger, G. (eds.) Computing and Software Science. LNCS, vol. 10000, pp. 48–65. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-91908-9_4

    Chapter  MATH  Google Scholar 

  3. Aziz, H., Brill, M., Conitzer, V., Elkind, E., Freeman, R., Walsh, T.: Justified representation in approval-based committee voting. Soc. Choice Welfare 48(2), 461–485 (2017). https://doi.org/10.1007/s00355-016-1019-3

    Article  MathSciNet  MATH  Google Scholar 

  4. Aziz, H., Elkind, E., Huang, S., Lackner, M., Fernández, L.S., Skowron, P.: On the complexity of extended and proportional justified representation. In: AAAI, pp. 902–909 (2018)

    Google Scholar 

  5. Aziz, H., Lang, J., Monnot, J.: Computing Pareto optimal committees. In: Kambhampati, S. (ed.) IJCAI, pp. 60–66 (2016)

    Google Scholar 

  6. Aziz, H., Shah, N.: Participatory budgeting: models and approaches. In: Rudas, T., Péli, G. (eds.) Pathways Between Social Science and Computational Social Science. CSS, pp. 215–236. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-54936-7_10

    Chapter  Google Scholar 

  7. Brainard, W.C., Scarf, H.E.: How to compute equilibrium prices in 1891. Am. J. Econ. Sociol. 64(1), 57–83 (2005)

    Article  Google Scholar 

  8. Brams, S.J., Kilgour, D.M., Sanver, M.R.: A minimax procedure for electing committees. Public Choice 132(3), 401–420 (2007). https://doi.org/10.1007/s11127-007-9165-x

    Article  Google Scholar 

  9. Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D.: Handbook of Computational Social Choice, 1st edn. Cambridge University Press, Cambridge (2016)

    Book  MATH  Google Scholar 

  10. Brill, M., Freeman, R., Janson, S., Lackner, M.: Phragmén’s voting methods and justified representation. In: AAAI, pp. 406–413 (2017)

    Google Scholar 

  11. Brill, M., Gölz, P., Peters, D., Schmidt-Kraepelin, U., Wilker, K.: Approval-based apportionment. In: AAAI, pp. 1854–1861 (2020)

    Google Scholar 

  12. Cabannes, Y.: Participatory budgeting: a significant contribution to participatory democracy. Environ. Urban. 16(1), 27–46 (2004)

    Article  Google Scholar 

  13. Carr, R.D., Fleischer, L.K., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: SODA, pp. 106–115 (2000)

    Google Scholar 

  14. Chamberlin, J.R., Courant, P.N.: Representative deliberations and representative decisions: proportional representation and the Borda rule. Am. Polit. Sci. Rev. 77(3), 718–733 (1983)

    Article  Google Scholar 

  15. Charikar, M.: Greedy approximation algorithms for finding dense components in a graph. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol. 1913, pp. 84–95. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44436-X_10

    Chapter  MATH  Google Scholar 

  16. Chen, X., Fain, B., Lyu, L., Munagala, K.: Proportionally fair clustering. In: ICML, pp. 1032–1041 (2019)

    Google Scholar 

  17. Droop, H.R.: On methods of electing representatives. J. Stat. Soc. Lond. 44(2), 141–202 (1881)

    Article  Google Scholar 

  18. Endriss, U.: Trends in Computational Social Choice. Lulu.com (2017)

    Google Scholar 

  19. Fain, B., Goel, A., Munagala, K.: The core of the participatory budgeting problem. In: Cai, Y., Vetta, A. (eds.) WINE 2016. LNCS, vol. 10123, pp. 384–399. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-54110-4_27

    Chapter  Google Scholar 

  20. Fain, B., Munagala, K., Shah, N.: Fair allocation of indivisible public goods. In: EC (2018)

    Google Scholar 

  21. Feige, U.: A threshold of ln n for approximating set cover. J. ACM (JACM) 45(4), 634–652 (1998)

    Article  MATH  Google Scholar 

  22. Fernández, L.S., et al.: Proportional justified representation. In: AAAI, pp. 670–676 (2017)

    Google Scholar 

  23. Foley, D.K.: Lindahl’s solution and the core of an economy with public goods. Econometrica J. Econometric Soc. 38(1), 66–72 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  24. Goel, A., Krishnaswamy, A.K., Sakshuwong, S., Aitamurto, T.: Knapsack voting for participatory budgeting. ACM Trans. Econ. Comput. 7(2), 1–27 (2019)

    Article  MathSciNet  Google Scholar 

  25. Jiang, Z., Munagala, K., Wang, K.: Approximately stable committee selection. In: STOC, pp. 463–472 (2020)

    Google Scholar 

  26. Kearns, M., Neel, S., Roth, A., Wu, Z.S.: Preventing fairness gerrymandering: auditing and learning for subgroup fairness. In: ICML, pp. 2564–2572 (2018)

    Google Scholar 

  27. Khot, S.: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36(4), 1025–1071 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  28. Kolliopoulos, S.G., Young, N.E.: Approximation algorithms for covering/packing integer programs. J. Comput. Syst. Sci. 71(4), 495–505 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  29. Lindahl, E.: Just taxation-a positive solution. In: Classics in the Theory of Public Finance, pp. 168–176 (1958)

    Google Scholar 

  30. Monroe, B.L.: Fully proportional representation. Am. Polit. Sci. Rev. 89(4), 925–940 (1995)

    Article  Google Scholar 

  31. Munagala, K., Shen, Y., Wang, K.: Auditing for core stability in participatory budgeting (2022). https://doi.org/10.48550/ARXIV.2209.14468. https://arxiv.org/abs/2209.14468

  32. Munagala, K., Shen, Y., Wang, K., Wang, Z.: Approximate core for committee selection via multilinear extension and market clearing. In: SODA, pp. 2229–2252 (2022)

    Google Scholar 

  33. Peters, D., Pierczyński, G., Shah, N., Skowron, P.: Market-based explanations of collective decisions. In: AAAI, vol. 35, no. 6, pp. 5656–5663 (2021)

    Google Scholar 

  34. Peters, D., Skowron, P.: Proportionality and the limits of welfarism. In: EC, pp. 793–794 (2020)

    Google Scholar 

  35. Scarf, H.E.: The core of an N person game. Econometrica 35(1), 50–69 (1967)

    Article  MathSciNet  MATH  Google Scholar 

  36. Thiele, T.N.: Om flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger 1895, 415–441 (1895)

    Google Scholar 

  37. Varian, H.R.: Two problems in the theory of fairness. J. Public Econ. 5(3), 249–260 (1976)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Duke University, Durham, NC, 27708-0129, USA

    Kamesh Munagala & Yiheng Shen

  2. Simons Institute for the Theory of Computing, Berkeley, CA, 94720-2190, USA

    Kangning Wang

Authors
  1. Kamesh Munagala
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yiheng Shen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kangning Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kamesh Munagala .

Editor information

Editors and Affiliations

  1. Aarhus University, Aarhus, Denmark

    Kristoffer Arnsfelt Hansen

  2. Tsinghua University, Bei**g, China

    Tracy **ao Liu

  3. Rotman School of Management, University of Toronto, Toronto, ON, Canada

    Azarakhsh Malekian

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Munagala, K., Shen, Y., Wang, K. (2022). Auditing for Core Stability in Participatory Budgeting. In: Hansen, K.A., Liu, T.X., Malekian, A. (eds) Web and Internet Economics. WINE 2022. Lecture Notes in Computer Science, vol 13778. Springer, Cham. https://doi.org/10.1007/978-3-031-22832-2_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-22832-2_17

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-22831-5

  • Online ISBN: 978-3-031-22832-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation