Smallest tournaments not realizable by frac23{frac{2}{3}}-majority voting

摘要

Define the predictability number α(T) of a tournament T to be the largest supermajority threshold src="/content/y582q21482542x03/355_2009_375_Article_IEq2.gif" alt="$${frac{1}{2} 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.