A quantitative Gobbard-Satterthwaite theorem without neutrality (Q343234): Difference between revisions

From the authors' abstract: Quantitative versions of the Gibbard-Satterthwaite theorem have already been proven for \(k=3\) alternatives and for neutral functions on \(k\geq 4\) alternatives. Here we prove a quantitative version of the theorem for general social choice functions for any number \(k\geq 3\) of alternatives. In particular we show that for a social choice function \(f\) on \(k\geq 3\) alternatives and \(n\) voters, which is \(\varepsilon\)-far from the family of nonmanipulable functions, a uniformly chosen voter profile is manipulable with probability at least inverse polynomial in \(n\), \(k\), and \(\varepsilon^{-1}\). Ours is a unified proof which covers all previous cases established before. The proof crucially uses reverse hypercontractivity in addition to several ideas from the two previous proofs. Much of the work is devoted to understanding functions of a single voter, and in particular we also prove a quantitative Gibbard-Satterthwaite theorem for one voter.