Caragiannis, Ioannis, Christodoulou, George and Protopapas, Nicos 
ORCID: 0000-0002-6130-3641
(2019)
Impartial Selection with Additive Approximation Guarantees.
In: Symposium on Algorithmic Game Theory (SAGT), 2019-10-1 - 2019-10-3, Athens, Greece.
|
Text
Impartial_Selection_with_Additive_Approximation_Guarantees.pdf - Author Accepted Manuscript Download (314kB) | Preview |
Abstract
Impartial selection has recently received much attention within the multi-agent systems community. The task is, given a directed graph representing nominations to the members of a community by other members, to select the member with the highest number of nominations. This seemingly trivial goal becomes challenging when there is an additional impartiality constraint, requiring that no single member can influence her chance of being selected. Recent progress has identified impartial selection rules with optimal approximation ratios. Moreover, it was noted that worst-case instances are graphs with few vertices. Motivated by this fact, we propose the study of additive approximation, the difference between the highest number of nominations and the number of nominations of the selected member, as an alternative measure of the quality of impartial selection. Our positive results include two randomized impartial selection mechanisms which have additive approximation guarantees of $\Theta(\sqrt{n})$ and $\Theta(n^{2/3}\ln^{1/3}n)$ for the two most studied models in the literature, where $n$ denotes the community size. We complement our positive results by providing negative results for various cases. First, we provide a characterization for the interesting class of strong sample mechanisms, which allows us to obtain lower bounds of $n-2$, and of $\Omega(\sqrt{n})$ for their deterministic and randomized variants respectively. Finally, we present a general lower bound of $2$ for all deterministic impartial mechanisms.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | 18 pages, 7 figures. A preliminary version appeared in SAGT '19. Corrected a minor bug in Theorem 3 and typos. Theory Comput Syst (2022) |
| Uncontrolled Keywords: | Impartial selection, Voting, Mechanism design |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 18 Jul 2019 08:09 |
| Last Modified: | 19 Jan 2023 00:37 |
| DOI: | 10.1007/978-3-030-30473-7_18 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3050062 |
Dimensions
Dimensions
