Improved Bounds for Single-Nomination Impartial Selection
Improved Bounds for Single-Nomination Impartial Selection
复制标题
改进单一提名公正选择的界限
DOI：
10.1145/3580507.3597693
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Cembrano J
中科院分区：
文献类型：
--
作者：
Cembrano J
我们给出了公平选择的单一提名模型的新界限，这是Holzman和Moulin提出的问题（Econometrica，2013）。一个选择机制，可以是随机的，从一组成员中选择一个人;如果一个人的选择是独立的提名，那么这个机制就是公正的，如果在任何情况下，被选中的个人收到的提名的预期数量至少是任何个人收到的提名的两倍，那么这个机制就是最优的。在多提名模型中，个人可以投任意数量的提名，所谓的置换机制是最优的，这是最好的可能。在单一提名模型中，每个人只投一个提名，置换机制做得更好，在此之前，已知是最优的，但不比最优的好。我们表明，它实际上是最佳的所有。这一结果是通过严格的界限上的性能的机制，最大程度的图形，对于任何，我们证明使用对抗性的论点。然后，我们表明，置换机制是不是最好的可能性，事实上，通过结合置换机制，另一种机制称为多元化亚军，和一些新的想法，-最优性可以实现所有。最后给出了任意最优公平机制的上界。他们改善了现有的上限为alland意味着，没有公正的机制可以比最优的所有，他们不排除存在一个最优的公正机制arbitraryifis大。
We give new bounds for the single-nomination model of impartial selection, a problem proposed by Holzman and Moulin (Econometrica, 2013). A selection mechanism, which may be randomized, selects one individual from a group ofbased on nominations among members of the group; a mechanism is impartial if the selection of an individual is independent of nominations cast by that individual, and-optimal if under any circumstance the expected number of nominations received by the selected individual is at leasttimes that received by any individual. In a many-nominations model, where individuals may cast an arbitrary number of nominations, the so-called permutation mechanism is-optimal, and this is best possible. In the single-nomination model, where each individual casts exactly one nomination, the permutation mechanism does better and prior to this work was known to be-optimal but no better than-optimal. We show that it is in fact-optimal for all. This result is obtained via tight bounds on the performance of the mechanism for graphs with maximum degree, for any, which we prove using an adversarial argument. We then show that the permutation mechanism is not best possible; indeed, by combining the permutation mechanism, another mechanism called plurality with runner-up, and some new ideas,-optimality can be achieved for all. We finally give new upper bounds onfor any-optimal impartial mechanism. They improve on the existing upper bounds for alland imply that no impartial mechanism can be better than-optimal for all; they do not preclude the existence of a-optimal impartial mechanism for arbitraryifis large.
登录
查看更多内容
最优公正选择
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
通过迭代删除提供附加保证的公正选择
DOI：
10.1145/3490486.3538294
发表时间：
2022
期刊：
--
影响因子：
--
作者：
Cembrano J
通讯作者：
Cembrano J
对研究“历史因果关系”的思考
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
Matsumoto;K.;Arakawa;A.;Yasuda Y.;Asao;I.;Matsushima K.;Okura;T
通讯作者：
T