论文标题
最公平的投票规则
Most Equitable Voting Rules
论文作者
论文摘要
在社会选择理论中，匿名（所有被同样对待的代理人）和中立性（所有被同样对待的替代品）被广泛认为是``最小需求''和````最小需求''''和``毫无争议''公理的公平和公平。但是，ANR的不可能 - 没有能够满足匿名，中立性和共识性（总是选择一个赢家）的投票规则 - 即使在两个替代方案和两个特工的简单环境中也保持不变。如何设计最佳满足匿名性，中立性和共振性的投票规则仍然是一个悬而未决的问题。 我们针对包括排名列表和委员会在内的各种偏好和决策的最佳设计问题。我们的概念性贡献是最公平的改进的新颖而强烈的概念，可最佳地保留满足两个公理的任何不重新统治的匿名性和中立性。我们的技术贡献是双重的。首先，我们表征了不可能在一般设置下保持ANR的条件，尤其是当代理数量较大时。其次，我们提出了最有利的遗产（MFP）抢七局，以计算最公平的改进并设计多项式时间算法，以计算代理人的偏好是完整的排名，以计算MFP。
In social choice theory, anonymity (all agents being treated equally) and neutrality (all alternatives being treated equally) are widely regarded as ``minimal demands'' and ``uncontroversial'' axioms of equity and fairness. However, the ANR impossibility -- there is no voting rule that satisfies anonymity, neutrality, and resolvability (always choosing one winner) -- holds even in the simple setting of two alternatives and two agents. How to design voting rules that optimally satisfy anonymity, neutrality, and resolvability remains an open question. We address the optimal design question for a wide range of preferences and decisions that include ranked lists and committees. Our conceptual contribution is a novel and strong notion of most equitable refinements that optimally preserves anonymity and neutrality for any irresolute rule that satisfies the two axioms. Our technical contributions are twofold. First, we characterize the conditions for the ANR impossibility to hold under general settings, especially when the number of agents is large. Second, we propose the most-favorable-permutation (MFP) tie-breaking to compute a most equitable refinement and design a polynomial-time algorithm to compute MFP when agents' preferences are full rankings.
