The Condorcet criterion (CC) is a classical and well-accepted criterion for voting. Unfortunately, it is incompatible with many other desiderata including participation (Par), half-way monotonicity (HM), Maskin monotonicity (MM), and strategy-proofness (SP). Such incompatibilities are often known as impossibility theorems, and are proved by worst-case analysis. Previous work has investigated the likelihood for these impossibilities to occur under certain models, which are often criticized of being unrealistic. We strengthen previous work by proving the first set of semi-random impossibilities for voting rules to satisfy CC and the more general, group versions of the four desiderata: for any sufficiently large number of voters $n$, any size of the group $1\le B\le \sqrt n$, any voting rule $r$, and under a large class of {\em semi-random} models that include Impartial Culture, the likelihood for $r$ to satisfy CC and Par, CC and HM, CC and MM, or CC and SP is $1-\Omega(\frac{B}{\sqrt n})$. This matches existing lower bounds for CC and Par ($B=1$) and CC and SP ($B\le \sqrt n$), showing that many commonly-studied voting rules are already asymptotically optimal in such cases.
翻译:康多尔塞特标准(CCC)是典型和公认的投票标准。 不幸的是,它与许多其他标准不相容,包括参与(Par),半途单调(HM),中途单调(MMM),以及战略防守(SP)等。 这种不兼容性通常被称为不可能的定理,并通过最坏情况分析加以证明。 先前的工作调查了在某些模式下出现这些不协调性的可能性,这些模式往往被批评为不现实。 我们强化了先前的工作,通过证明第一组半兰地投票规则的半兰地不易性以满足CC,以及更一般的四度偏差的集团版本:对于足够多的选民来说,任何规模的1美元,Ble\le\ sqrt n美元,任何投票规则$rr;在包括不偏心文化在内的大型类半兰特制模式下,美元用于满足CC和Par、CC和H、CC和Par_BRial 和MRM_BR) 常规显示的美元和SP-BRames。