Optimal impartial selection

DOI10.1137/140995775MaRDI QIDQ3449559zbMATH OpenOpenAlexFDO

Authors Felix Fischer, Max Klimm

Publication date 4 November 2015

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.8631, http://eprints.gla.ac.uk/131323/7/131323.pdf

zbMATH Keywords

approximationimpartial selectionimpartialitysocial choicevoting

Mathematics Subject Classification ID

Approximation algorithms (68W25) Games involving graphs (91A43) Voting theory (91B12) Social choice (91B14)

Abstract: We study the problem of selecting a member of a set of agents based on impartial nominations by agents from that set. The problem was studied previously by Alon et al. and Holzman and Moulin and has important applications in situations where representatives are selected from within a group or where publishing or funding decisions are made based on a process of peer review. Our main result concerns a randomized mechanism that in expectation awards the prize to an agent with at least half the maximum number of nominations. Subject to impartiality, this is best possible.

Recommendations

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

Cites work

• A near-optimal mechanism for impartial selection
• Coin-Flipping Games Immune against Linear-Sized Coalitions
• Competitive auctions
• Competitive generalized auctions
• Fast leader-election protocols with bounded cheaters' edge
• Fast perfect-information leader-election protocols with linear immunity
• Impartial division of a dollar
• Impartial nominations for a prize
• Incentive compatible regression learning
• Manipulation-resistant reputation systems
• Truthful randomized mechanisms for combinatorial auctions

Cited in

(17)

• An axiomatic analysis of the papal conclave
• A new axiomatic approach to the impartial nomination problem
• Incentive compatible mechanism for influential agent selection
• Impartial nominations for a prize
• A near-optimal mechanism for impartial selection
• Indifference-Zone-Free Selection of the Best
• Impartial Selection and the Power of up to Two Choices
• Impartial nomination correspondences
• Sequential voting with confirmation network
• Impartial selection with additive approximation guarantees
• Impartial selection with additive approximation guarantees
• Characterizing minimal impartial rules for awarding prizes
• Selecting a winner with external referees
• Optimal impartial correspondences
• Impartial selection with additive guarantees via iterated deletion
• Deterministic impartial selection with weights
• Optimal impartial correspondences

This page was built for publication: Optimal impartial selection

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