Beyond Proportional Individual Guarantees for Binary Perpetual Voting
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_ | 1866914914128363520 |
|---|---|
| author | Gafni, Yotam Golan, Ben |
| author_facet | Gafni, Yotam Golan, Ben |
| contents | Perpetual voting studies fair collective decision-making in settings where many decisions are to be made, and is a natural framework for settings such as parliaments and the running of blockchain Decentralized Autonomous Organizations (DAOs). We focus our attention on the binary case (YES/NO decisions) and \textit{individual} guarantees for each of the participating agents. We introduce a novel notion, inspired by the popular maxi-min-share (MMS) for fair allocation. The agent expects to get as many decisions as if they were to optimally partition the decisions among the agents, with an adversary deciding which of the agents decides on what bundle. We show an online algorithm that guarantees the MMS notion for $n=3$ agents, an offline algorithm for $n=4$ agents, and show that no online algorithm can guarantee the $MMS^{adapt}$ for $n\geq 7$ agents. We also show that the Maximum Nash Welfare (MNW) outcome can only guarantee $O(\frac{1}{n})$ of the MMS notion in the worst case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_08767 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Beyond Proportional Individual Guarantees for Binary Perpetual Voting Gafni, Yotam Golan, Ben Computer Science and Game Theory Perpetual voting studies fair collective decision-making in settings where many decisions are to be made, and is a natural framework for settings such as parliaments and the running of blockchain Decentralized Autonomous Organizations (DAOs). We focus our attention on the binary case (YES/NO decisions) and \textit{individual} guarantees for each of the participating agents. We introduce a novel notion, inspired by the popular maxi-min-share (MMS) for fair allocation. The agent expects to get as many decisions as if they were to optimally partition the decisions among the agents, with an adversary deciding which of the agents decides on what bundle. We show an online algorithm that guarantees the MMS notion for $n=3$ agents, an offline algorithm for $n=4$ agents, and show that no online algorithm can guarantee the $MMS^{adapt}$ for $n\geq 7$ agents. We also show that the Maximum Nash Welfare (MNW) outcome can only guarantee $O(\frac{1}{n})$ of the MMS notion in the worst case. |
| title | Beyond Proportional Individual Guarantees for Binary Perpetual Voting |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2408.08767 |