License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.70
URN: urn:nbn:de:0030-drops-181223
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18122/
Go to the corresponding LIPIcs Volume Portal

Goyal, Mohak ; Sakshuwong, Sukolsak ; Sarmasarkar, Sahasrajit ; Goel, Ashish

Low Sample Complexity Participatory Budgeting

pdf-format:
LIPIcs-ICALP-2023-70.pdf (1 MB)

Abstract

We study low sample complexity mechanisms in participatory budgeting (PB), where each voter votes for a preferred allocation of funds to various projects, subject to project costs and total spending constraints. We analyse the distortion that PB mechanisms introduce relative to the minimum-social-cost outcome in expectation. The Random Dictator mechanism for this problem obtains a distortion of 2. In a special case where every voter votes for exactly one project, [Fain et al., 2017] obtain a distortion of 4/3. We show that when PB outcomes are determined as any convex combination of the votes of two voters, the distortion is 2. When three uniformly randomly sampled votes are used, we give a PB mechanism that obtains a distortion of at most 1.66, thus breaking the barrier of 2 with the smallest possible sample complexity.
We give a randomized Nash bargaining scheme where two uniformly randomly chosen voters bargain with the disagreement point as the vote of a voter chosen uniformly at random. This mechanism has a distortion of at most 1.66. We provide a lower bound of 1.38 for the distortion of this scheme. Further, we show that PB mechanisms that output a median of the votes of three voters chosen uniformly at random, have a distortion of at most 1.80.

BibTeX - Entry

@InProceedings{goyal_et_al:LIPIcs.ICALP.2023.70,
  author =	{Goyal, Mohak and Sakshuwong, Sukolsak and Sarmasarkar, Sahasrajit and Goel, Ashish},
  title =	{{Low Sample Complexity Participatory Budgeting}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{70:1--70:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18122},
  URN =		{urn:nbn:de:0030-drops-181223},
  doi =		{10.4230/LIPIcs.ICALP.2023.70},
  annote =	{Keywords: Social Choice, Participatory budgeting, Nash bargaining}
}

Keywords: Social Choice, Participatory budgeting, Nash bargaining
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023
Supplementary Material: Software (Source Code): https://github.com/Sahasrajit123/Low-sample-complexity-PB

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI