Approximately Fair and Population Consistent Budget Division via Simple Payment Schemes
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912624314155008 |
|---|---|
| author | Aziz, Haris Lederer, Patrick Lu, Xinhang Suzuki, Mashbat Vollen, Jeremy |
| author_facet | Aziz, Haris Lederer, Patrick Lu, Xinhang Suzuki, Mashbat Vollen, Jeremy |
| contents | In approval-based budget division, a budget needs to be distributed to candidates based on the voters' approval ballots over these candidates. In the pursuit of a simple, consistent, and approximately fair rule for this setting, we introduce the maximum payment rule (MP). Under this rule, each voter controls a part of the budget and, in each step, the corresponding voters allocate their entire budget to the candidate approved by the largest number of voters with non-zero budget. We show that MP meets our criteria as it satisfies monotonicity and a demanding population consistency condition and gives a $2$-approximation to a fairness notion called average fair share (AFS). Moreover, we generalize MP to the class of sequential payment rule and prove that it is the most desirable rule in this class: all sequential payment rules but MP and one other rule fail monotonicity while only allowing for a small improvement in the approximation ratio to AFS. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_02435 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximately Fair and Population Consistent Budget Division via Simple Payment Schemes Aziz, Haris Lederer, Patrick Lu, Xinhang Suzuki, Mashbat Vollen, Jeremy Computer Science and Game Theory Theoretical Economics In approval-based budget division, a budget needs to be distributed to candidates based on the voters' approval ballots over these candidates. In the pursuit of a simple, consistent, and approximately fair rule for this setting, we introduce the maximum payment rule (MP). Under this rule, each voter controls a part of the budget and, in each step, the corresponding voters allocate their entire budget to the candidate approved by the largest number of voters with non-zero budget. We show that MP meets our criteria as it satisfies monotonicity and a demanding population consistency condition and gives a $2$-approximation to a fairness notion called average fair share (AFS). Moreover, we generalize MP to the class of sequential payment rule and prove that it is the most desirable rule in this class: all sequential payment rules but MP and one other rule fail monotonicity while only allowing for a small improvement in the approximation ratio to AFS. |
| title | Approximately Fair and Population Consistent Budget Division via Simple Payment Schemes |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2412.02435 |