Distributed Agreement in the Arrovian Framework
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913566829838336 |
|---|---|
| author | Wood, Kenan Mendes, Hammurabi Pulaj, Jonad |
| author_facet | Wood, Kenan Mendes, Hammurabi Pulaj, Jonad |
| contents | Preference aggregation is a fundamental problem in voting theory, in which public input rankings of a set of alternatives (called preferences) must be aggregated into a single preference that satisfies certain soundness properties. The celebrated Arrow Impossibility Theorem is equivalent to a distributed task in a synchronous fault-free system that satisfies properties such as respecting unanimous preferences, maintaining independence of irrelevant alternatives (IIA), and non-dictatorship, along with consensus since only one preference can be decided.
In this work, we study a weaker distributed task in which crash faults are introduced, IIA is not required, and the consensus property is relaxed to either $k$-set agreement or $ε$-approximate agreement using any metric on the set of preferences. In particular, we prove several novel impossibility results for both of these tasks in both synchronous and asynchronous distributed systems. We additionally show that the impossibility for our $ε$-approximate agreement task using the Kendall tau or Spearman footrule metrics holds under extremely weak assumptions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_04685 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distributed Agreement in the Arrovian Framework Wood, Kenan Mendes, Hammurabi Pulaj, Jonad Distributed, Parallel, and Cluster Computing Computer Science and Game Theory Preference aggregation is a fundamental problem in voting theory, in which public input rankings of a set of alternatives (called preferences) must be aggregated into a single preference that satisfies certain soundness properties. The celebrated Arrow Impossibility Theorem is equivalent to a distributed task in a synchronous fault-free system that satisfies properties such as respecting unanimous preferences, maintaining independence of irrelevant alternatives (IIA), and non-dictatorship, along with consensus since only one preference can be decided. In this work, we study a weaker distributed task in which crash faults are introduced, IIA is not required, and the consensus property is relaxed to either $k$-set agreement or $ε$-approximate agreement using any metric on the set of preferences. In particular, we prove several novel impossibility results for both of these tasks in both synchronous and asynchronous distributed systems. We additionally show that the impossibility for our $ε$-approximate agreement task using the Kendall tau or Spearman footrule metrics holds under extremely weak assumptions. |
| title | Distributed Agreement in the Arrovian Framework |
| topic | Distributed, Parallel, and Cluster Computing Computer Science and Game Theory |
| url | https://arxiv.org/abs/2409.04685 |