Impartial Selection with Additive Guarantees via Iterated Deletion
Impartial Selection with Additive Guarantees via Iterated Deletion
复制标题
通过迭代删除提供附加保证的公正选择
DOI：
10.1145/3490486.3538294
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Cembrano J
中科院分区：
文献类型：
--
作者：
Cembrano J
公平选择是根据群体中其他成员的提名从群体中选择一个人，以这种方式，个人不能影响自己的选择机会。我们给出了一个确定性机制，在n个个体的情况下，每个个体都有O（nκ）个提名，其中κ∈[0，1]，其附加性能保证为O（n（1+κ）/2）。对于κ=0，即当每个人至多投一个常数数量的提名时，这个界限是O（n）。这与最著名的随机机制和单一提名的保证相匹配。对于k =1，边界是O（n）。这是微不足道的，因为即使是从不选择的机制也会提供n-1的附加保证。然而，我们证明，这也是最好的可能性：对于每一个确定性的公正机制，都存在这样一种情况，即某个人被其他每个人提名，该机制要么不选择，要么选择一个没有被任何人提名的人。
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. 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]. For κ=0, i.e. when each individual casts at most a constant number of nominations, this bound is O(√n). This matches the best-known guarantee for randomized mechanisms and a single nomination. For κ=1 the bound is O(n). This 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.
登录
查看更多内容
使用随机化、分区和分配进行策略证明的对等选择
DOI：
10.1016/j.artint.2019.06.004
发表时间：
2016
期刊：
Artif. Intell.
影响因子：
--
作者：
H. Aziz;Omer Lev;Nicholas Mattei;J. Rosenschein;T. Walsh
通讯作者：
T. Walsh
PeerNomination：放松精确性以提高同行选择的准确性
DOI：
10.24963/ijcai.2020/55
发表时间：
2020
期刊：
ArXiv
影响因子：
--
作者：
Nicholas Mattei;P. Turrini;Stanislav Zhydkov
通讯作者：
Stanislav Zhydkov
最优公正选择
DOI：
--
发表时间：
2013
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Felix A. Fischer;Max Klimm
通讯作者：
Max Klimm
公正的选择和最多两种选择的力量
DOI：
10.1145/3107922
发表时间：
2015
期刊：
ACM Transactions on Economics and Computation (TEAC)
影响因子：
--
作者：
S. Tamura
通讯作者：
S. Tamura
影响因子：
0.5
作者：
I. Caragiannis;G. Christodoulou;Nicos Protopapas
通讯作者：
Nicos Protopapas