District-Fair Participatory Budgeting
Authors: D Ellis Hershkowitz, Anson Kahng, Dominik Peters, Ariel D. Procaccia5464-5471
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We first show that it is NP-complete to compute an allocation that is welfare-maximizing subject to district fairness. This result holds even for the case of approval votes and proportional budgets, and therefore the generality of our model only strengthens our positive (algorithmic) results without weakening the main negative (hardness) result. We design polynomial-time algorithms that work when we relax or approximate some of the following: (1) the achieved social welfare; (2) the spent budget; (3) the fairness of the solution; and (4) the absence of randomization. We first relax (4) by considering distributions over outcomes, a.k.a. lotteries . We show that using a multiplicative-weights-type algorithm, one can efficiently find a lottery that guarantees budget feasibility (ex post), optimum social welfare (ex post), and district-fairness in expectation up to an ε (ex ante). Our main result for the lottery setting is an ε-DF lottery which always achieves the optimal social welfare subject to district fairness. |
| Researcher Affiliation | Academia | D Ellis Hershkowitz,1 Anson Kahng,1 Dominik Peters,2 Ariel D. Procaccia2 1 Carnegie Mellon University 2 Harvard University dhershko@cs.cmu.edu, akahng@cs.cmu.edu, dpeters@seas.harvard.edu, arielpro@seas.harvard.edu |
| Pseudocode | No | The paper describes algorithms in numbered steps within a paragraph, such as the multiplicative weights algorithm under "Optimal District-Fair Lottery", but it does not provide formal pseudocode blocks or algorithms explicitly labeled as such. |
| Open Source Code | No | The paper does not mention providing open-source code for the described methodology. |
| Open Datasets | No | The paper defines a formal problem setting with parameters but does not use or refer to any specific public datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments, so no training, validation, or test dataset splits are mentioned. |
| Hardware Specification | No | The paper is theoretical and does not discuss running experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any implemented software or list dependencies with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and proofs. It does not provide details on experimental setup such as hyperparameters or system-level training settings. |