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

approximationvotingsocial choiceimpartialityimpartial selection

Mathematics Subject Classification ID

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

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

(16)

• Selecting a winner with external referees
• An axiomatic analysis of the papal conclave
• Impartial Selection and the Power of up to Two Choices
• Impartial nominations for a prize
• Optimal impartial correspondences
• Impartial selection with additive approximation guarantees
• Impartial selection with additive approximation guarantees
• Deterministic impartial selection with weights
• A new axiomatic approach to the impartial nomination problem
• Incentive compatible mechanism for influential agent selection
• Impartial nomination correspondences
• A near-optimal mechanism for impartial selection
• Impartial selection with additive guarantees via iterated deletion
• Characterizing minimal impartial rules for awarding prizes
• scientific article; zbMATH DE number 7450018 (Why is no real title available?)
• Indifference-Zone-Free Selection of the Best

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)