关键词：吉本–萨特思韦特定理；投票规则；定量
摘 要：We prove a quantitative version of the Gibbard-Satterthwaite 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 $\epsilon$-far from the family of nonmanipulable functions, a uniformly chosen voter profile is manipulable with probability at least inverse polynomial in $n$, $k$, and $\epsilon^{-1}$.Removing the neutrality assumption of previous theorems is important for multiple reasons. For one, it is known that there is a conflict between anonymity and neutrality, and since most common voting rules are anonymous, they cannot always be neutral. Second, virtual elections are used in many applications in artificial intelligence, where there are often restrictions on the outcome of the election, and so neutrality is not a natural assumption in these situations.