arXiv:2107.06435

Semi-Random Impossibilities of Condorcet Criterion

Lirong Xia

제출 2021-07-14

원문 초록

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.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.