Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2407.17569 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913444766154752 |
|---|---|
| author | Mikšaník, David Schvartzman, Ariel Soukup, Jan |
| author_facet | Mikšaník, David Schvartzman, Ariel Soukup, Jan |
| contents | A tournament organizer must select one of $n$ possible teams as the winner of a competition after observing all $\binom{n}{2}$ matches between them. The organizer would like to find a tournament rule that simultaneously satisfies the following desiderata. It must be Condorcet-consistent (henceforth, CC), meaning it selects as the winner the unique team that beats all other teams (if one exists). It must also be strongly non-manipulable for groups of size $k$ at probability $α$ (henceforth, k-SNM-$α$), meaning that no subset of $\leq k$ teams can fix the matches among themselves in order to increase the chances any of it's members being selected by more than $α$. Our contributions are threefold. First, wee consider a natural generalization of the Randomized Single Elimination Bracket rule from [Schneider et al. 2017] to $d$-ary trees and provide upper bounds to its manipulability. Then, we propose a novel tournament rule that is CC and 3-SNM-1/2, a strict improvement upon the concurrent work of [Dinev and Weinberg, 2022] who proposed a CC and 3-SNM-31/60 rule. Finally, we initiate the study of reductions among tournament rules. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_17569 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Approximately Strategy-Proof Tournament Rules for Collusions of Size at Least Three Mikšaník, David Schvartzman, Ariel Soukup, Jan Computer Science and Game Theory A tournament organizer must select one of $n$ possible teams as the winner of a competition after observing all $\binom{n}{2}$ matches between them. The organizer would like to find a tournament rule that simultaneously satisfies the following desiderata. It must be Condorcet-consistent (henceforth, CC), meaning it selects as the winner the unique team that beats all other teams (if one exists). It must also be strongly non-manipulable for groups of size $k$ at probability $α$ (henceforth, k-SNM-$α$), meaning that no subset of $\leq k$ teams can fix the matches among themselves in order to increase the chances any of it's members being selected by more than $α$. Our contributions are threefold. First, wee consider a natural generalization of the Randomized Single Elimination Bracket rule from [Schneider et al. 2017] to $d$-ary trees and provide upper bounds to its manipulability. Then, we propose a novel tournament rule that is CC and 3-SNM-1/2, a strict improvement upon the concurrent work of [Dinev and Weinberg, 2022] who proposed a CC and 3-SNM-31/60 rule. Finally, we initiate the study of reductions among tournament rules. |
| title | On Approximately Strategy-Proof Tournament Rules for Collusions of Size at Least Three |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2407.17569 |