Impartial selection with additive guarantees via iterated deletion

• 成果类型: Article
• 署名作者: Cembrano, Javier; Fischer, Felix; Hannon, David; Klimm, Max
• 署名单位: Technical University of Berlin; University of London; Queen Mary University London; Technical University of Berlin
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2024.01.008
• 发表日期: 2024
• 页码: 203-224
• 关键词: Voting; Impartial selection; Additive approximation

摘要

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+kappa)/2)) in a setting with n individuals where each individual casts O(n(kappa)) nominations, where kappa is an element of[0, 1]. This bound is O(root n) for kappa = 0 and O(n) for kappa = 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.