Impartial selection with additive approximation guarantees

DOI10.1007/978-3-030-30473-7_18MaRDI QIDQ5919368zbMATH OpenOpenAlexFDO

Authors I. Caragiannis, George Christodoulou, Nicos Protopapas

Publication date 4 February 2020

Published in Algorithmic Game Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.00135, https://rd.springer.com/content/pdf/10.1007%2F978-3-030-30473-7_18.pdf

zbMATH Keywords

impartial selectionmechanism designvoting

Mathematics Subject Classification ID

Applications of graph theory (05C90) Mechanism design theory (91B03) Voting theory (91B12) Social choice (91B14)

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(sqrtn)$ and $Theta(n^{2/3}l{n}^{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(sqrtn)$ for their deterministic and randomized variants respectively. Finally, we present a general lower bound of $2$ for all deterministic impartial mechanisms.

Recommendations

• Impartial selection with additive approximation guarantees
• Impartial Selection and the Power of up to Two Choices
• Optimal impartial selection
• A near-optimal mechanism for impartial selection
• Impartial nominations for a prize

Cited in

(8)

• On fair selection in the presence of implicit and differential variance
• Incentive compatible mechanism for influential agent selection
• A near-optimal mechanism for impartial selection
• Optimal impartial selection
• Impartial Selection and the Power of up to Two Choices
• Impartial selection with additive approximation guarantees
• Optimal impartial correspondences
• Impartial selection with additive guarantees via iterated deletion

This page was built for publication: Impartial selection with additive approximation guarantees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5919368)