Smallest tournaments not realizable by $${\frac{2}{3}}$$-majority voting |
| |
Authors: | Dylan Shepardson Craig A Tovey |
| |
Institution: | (1) H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, 765 Ferst Drive, Atlanta, GA 30332-0205, USA |
| |
Abstract: | Define the predictability number α(T) of a tournament T to be the largest supermajority threshold for which T could represent the pairwise voting outcomes from some population of voter preference orders. We establish that the predictability
number always exists and is rational. Only acyclic tournaments have predictability 1; the Condorcet voting paradox tournament
has predictability ; Gilboa has found a tournament on 54 alternatives (i.e. vertices) that has predictability less than , and has asked whether a smaller such tournament exists. We exhibit an 8-vertex tournament that has predictability , and prove that it is the smallest tournament with predictability < . Our methodology is to formulate the problem as a finite set of two-person zero-sum games, employ the minimax duality and
linear programming basic solution theorems, and solve using rational arithmetic.
D. Shepardson was supported by a NSF Graduate Research Fellowship during the course of this work. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|