A canonical problem in voting theory is: which voting rule should we use to aggregate voters' preferences into a collective decision over alternatives? When applying the axiomatic approach to evaluate and compare voting rules, we are faced with prohibitive impossibilities. However, these impossibilities occur under the assumption that voters' preferences (collectively called a profile) will be worst-case with respect to the desired criterion. In this paper, we study the axiomatic approach slightly \emph{beyond} the worst-case: we present and apply a "smoothed" model of the voting setting, which assumes that while inputs (profiles) may be worst-case, all inputs will be perturbed by a small amount of noise. In defining and analyzing our noise model, we do not aim to substantially technically innovate on Lirong Xia's recently-proposed smoothed model of social choice; rather, we offer an alternative model and approach to analyzing it that aims to strike a different balance of simplicity and technical generality, and to correspond closely to Spielman and Teng's (2004) original work on smoothed analysis. Within our model, we then give simple proofs of smoothed-satisfaction or smoothed-violation of several axioms and paradoxes, including most of those studied by Xia as well as some previously unstudied. Novel results include smoothed analysis of Arrow's theorem and analyses of the axioms Consistency and Independence of Irrelevant Alternatives. In independent work from a recent paper by Xia (2022), we also show the smoothed-satisfaction of coalition-based notions of Strategy-Proofness, Monotonocity, and Participation. A final, central component of our contributions are the high-level insights and future directions we identify based on this work, which we describe in detail to maximally facilitate additional research in this area.
翻译:投票理论的典型问题是:我们应使用哪种投票规则来将选民的偏好归结为集体决定的替代方案?当我们应用不言而喻的方法来评估和比较投票规则时,我们面对着令人望而生畏的无望。然而,这些不可理喻的假设是,选民的偏好(统称为剖面)在理想标准方面将是最糟糕的。在本文中,我们研究的不言而喻方法略微超越了最坏的情况:我们提出并应用了投票环境的“mooded”模式,这个模式假定投入(说明)可能是最坏的情况,而所有投入都将受到少量噪音的干扰。在界定和分析我们的噪音模型时,我们并不试图对里昂·夏最新提出的社会选择模式进行实质性创新;相反,我们提供了一个替代模式和方法来分析它的基础,目的是实现不同的简单和技术一般性平衡,然后将未来与Spielman和Teng(2004年)的原始参与分析紧密性进行。在以往分析中,我们以平淡的深度分析方式展示了我们最平淡的自我分析。