Impartial selection with additive guarantees via iterated deletion

Javier Cembrano, Felix Fischer, David Hannon and Max Klimm

Games and Economic Behavior, 2024, vol. 144, issue C, 203-224

Abstract: Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. For this problem, we give a deterministic mechanism with an additive performance guarantee of O(n(1+κ)/2) in a setting with n individuals where each individual casts O(nκ) nominations, where κ∈[0,1]. This bound is O(n) for κ=0 and O(n) for κ=1. The latter is trivial, as even a mechanism that never selects provides an additive guarantee of n−1. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.

Keywords: Voting; Impartial selection; Additive approximation (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899825624000095
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:144:y:2024:i:c:p:203-224

DOI: 10.1016/j.geb.2024.01.008

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().