Gibbard-Satterthwaite Theorem

In Gibbard (1973) Gibbard first proved a theorem in game theory, then used that theorem to prove Gibbard-Satterthwaite as a corollary. Quoting Gibbard:

Page 587, Introduction, first paragraph:

… any non-dictatorial voting scheme with at least three possible outcomes is subject to individual manipulation. By a "voting scheme," I mean any scheme which makes a community’s choice depend entirely on individuals’ professed preferences among the alternatives. An individual “manipulates” the voting scheme if, by misrepresenting his preferences, he secures an outcome he prefers to the “honest” outcome—the choice the community would make if he expressed his true preferences.

Page 587, Introduction, second paragraph:

… Let a game form be any scheme which makes an outcome depend on individual actions of some specified sort, which I shall call strategies. A voting scheme, then, is a game form in whicha strategy is a profession of preferences, but many game forms are not voting schemes. Call a strategy dominant for someone if, whatever anyone else does, it achieves his goals at least as well as would any alternative strategy. Only trivial game forms, I shall show, ensure that each individual, no matter what his preferences are, will have available a dominant strategy. Hence in particular, no non-trivial voting scheme guarantees that honest expression of preferences is a dominant strategy. …

Page 589, third full paragraph through page 590, second full paragraph:

For game forms alone, however, there is no such thing as manipulation. To manipulate a system, a voter must misrepresent his preferences. Nothing in the structure of a game form tells us what strategy "honestly" represents any given preference ordering, and hence which strategies would misrepresent it. To talk of manipulation, then, we must specify not only a game form, but for each voter and preference ordering P, we must specify the strategy which "honestly represents" P. Only then can we apply the definition of manipulation as securing an outcome one prefers by selecting a strategy other than the one that honestly represents one’s preferences.

Manipulability, then, is a property of a game form \(g(s_1,\ldotsc,s_n)\) plus n functions \(\sigma_1,\ldotsc, \sigma_n\), where for each individual k and preference ordering P, \(\sigma_k(P)\) is the strategy for k which honestly represents P. Formally, then, where Z is the set of all alternatives open to the community, each \(\sigma_k\) is a function whose arguments are all orderings of Z and_whose values are strategies open to k. Manipulability is a property of a game form in conjunction with an n-tuple \(\langle\sigma_1,\ldotsc, \sigma_n\rangle\) of such functions.

Where a decision-making system is characterized by functions g, \(σ_1,\ldotsc, σ_n as I have indicated, it is characterized by a voting scheme,\[ v(P_1,\ldotsc, P_n) = g(σ_1(P_1),\ldotsc, σ_n(P_n)). /]

For each n-tuple \(\langle{P_1},\ldotsc, P_n\rangle\), \(v(\langle{P_1},\ldotsc, P_n\rangle\) is the outcome if individuals \(1,\ldotsc,n\) honestly profess preference orderings \(P_1,\ldotsc, P_n\) respectively. Whereas manipulability is not a property of a game form alone, it is a property of a voting scheme alone. Voting scheme v is manipulable if for some k and preference n-tuples \(\langle(P_1),\ldotsc, P_n\rangle\) and \(\langle{P_1^\prime},\ldotsc, P_n^\prime\rangle\), \(P_i=P_i^prime\) except when \(i=k\), and\[ v(P_1^\prime,\ldotsc, P_n^\prime) P_k v(P_i,\ldotsc, P_n). \]

For, then, if \(P_k\) is k’s real preference ordering, given the way the others vote, k prefers the result of expressing preference ordering \(P_k^\prime\), to that of expressing \(P_k\).

Note that to call a voting scheme manipulable is not to say that, given the actual circumstances, someone really is in a position to manipulate it. It is merely to say that, given some possible circumstances, someone could manipulate it. A voting scheme is manipulable, then, unless its structure guarantees that no matter how each person votes, no one will ever be in a position to manipulate the scheme.

Page 591, fourth paragraph:

A game form 1s straightforward if for every player k and preference ordering P of the outcomes, some strategy is dominant for k and P. The theorem on game forms says that no non-trivial game form is straightforward.

Page 595, third full paragraph:

A player k is a dictator for game form g if, for every outcome x, there is a strategy \(s(x)\) for k such that \(g(s) = x\) whenever \(s_k = s(x)\). A game form g is dictatorial if there is a dictator for g.

THEOREM: Every straightforward game form with at least three possible outcomes is dictatorial.

COROLLARY: Every voting scheme with at least three outcomes is either dictatorial or manipulable.

In Satterthwaite (1975) Satterthwaite first proved a variant of the Gibbard-Satterthwaite theorem in which voter preferences are required to be strict, meaning individual voter preference ordering relations do not allow indifference. He then generalized that result to include the possibility of individual voter indifference between alternatives.

(Satterthwaite uses theses symbols of mathematical logic: \(\in\) element of, ⊂ subset of, ⋐ strict subset of, ∪ union of two sets, ∩ intersection of two sets, and \(\thicksim\) not.

Quoting Satterthwaite:

Page 189, first two full paragraphs:

Let a committee be a set \(I_n\) of \(n, n ⩾ 1\), individuals whose task is to select a single alternative from an alternative set \(S_m\) of m elements, \(m ⩾ 3\). Each individual \(i \in I_n\), has preferences \(R_i\), which are a weak order on \(S_m\), i.e., \(R_i\) is reflexive, complete, and transitive. Thus, if \(x, y \in S_m\), and \(i \in I_n\), , then \(x R_i y\) means that individual i either prefers that the committee choose alternative x instead of y or is indifferent concerning which of the two alternatives the committee chooses. Strict preference for x over y on the part of individual i is written as \(x\overline{R_i}y\). Thus, \(x\overline{R_i}y\) is equivalent to writing \(xR_iy\) and \(\thicksim{y}R_ix\). Indifference is written as \(xR_iy\) and \(yR_ix\). Let \(\pi_m\) represent the collection of all possible preferences and let \(\pi_m^n\) represent the n-fold Cartesian product of \(\pi_m\).

The committee makes its selection of a single alternative by voting. Each individual \(i \in I_n\), casts a ballot \(B_i\) which is a weak order on \(S_m\)' i.e., \(B_i \in\pi_m\). The ballots are counted by a voting procedure \(v^{nm}\). Formally, a voting procedure is a single-valued mapping whose argument is the ballot set \(B = (B_1,\ldots, B_n)\in\pi_m^n\) and whose image is the committee’s choice, a single alternative \(x\in{S_m}\). Every voting procedure \(v^{nm}\) has a domain of \(\pi_m^n\) and a range of either \(S_m\), or some nonempty subset of \(S_m\). Let the range be labeled \(T_p\), where \(p, 1\geqslant{p}\geqslant{m}\), is the number of elements contained in \(T_p\). Given these definitions, let the tetrad \(\langle I_n, S_m, v^{nm}, T_p\rangle\) be called the committee’s structure.

Page 190, first full paragraph:

With the basic structure of the committee specified, I can define the concept of a strategy-proof voting procedure. Consider a committee with structure \(\langle I_n, S_m, v^{nm}, T_p\rangle\). Individual \(i\in{I_n}\), can manipulate the voting procedure \(v^{nm}\) at ballot set \(B = (B_1,\ldots,, B_n)\in\pi_m^n\) if and only if a ballot \(B_i^\prime\in\pi_m\) exists such that \[ v^{nm}(B_1 ,..., B_i^\prime,...,B_n) \overline{B_i} v^{nm}(B_1,..., B_i ,..., B_n). \] Thus, \(v^{nm}\) is manipulable at B if an individual \(i\in{I_n}\) can substitute ballot \(B_i^\prime\) for \(B_i\) and secure a more favorable outcome by the standards of the original ballot \(B_i\). The voting procedure \(v^{nm}\) is strategy-proof if and only if no \(B\in{\pi_m^n\) exists at which it is manipulable.

Note: There is a notational issue in the above quote that was a bit confusing to me. Satterthwaite uses \(B_i\) as both a ballot submitted by voter i, and a relation that can be used to compare two different results from the voting procedure \(v^{nm}\). This was not confusing to readers when the paper was originally published because the ballots under consideration then were always preference orders, and thus contained all the information needed to construct a voting procedure. My confusion came from working with approval voting ballots, which do not have that information.

THEOREM 1. (Gibbard-Satterthwaite). Consider a strict committee with structure \(\langle I_{n}, S_{m}, v^{nm}, T_{p} \rangle\), where \(n \geqslant 1\) and \(m \geqslant p \geqslant 3\). The voting procedure \(v^{nm}\) is strategy-proof if and only if it is dictatorial.

THEOREM 1’. Consider a committee \(\langle I_{n}, S_{m}, v^{nm}, T_{p} \rangle\) where \(n \geqslant 2\) and \(m \geqslant p \geqslant 3\). The voting procedure \(v^{nm}\) is strategy-proof only if it is dictatorial.

The Wikipedia article Gibbard–Satterthwaite theorem has a fairly good description of GST:

Informal statement:

[GST] states that for every voting rule, one of the following three things must hold:

1. The rule is dictatorial, i.e. there exists a distinguished voter who can choose the winner; or
2. The rule limits the possible outcomes to two alternatives only; or
3. The rule is susceptible to tactical voting: in certain conditions some voter's sincere ballot may not defend their opinion best.

Formal statement:

Gibbard-Satterthwaite theorem — If a voting rule has at least 3 possible outcomes and if it is non-manipulable, then it is dictatorial.

No, not really. The only sense in which SAVE might be considered a dictatorship is if there is a voter whose preferences are always selected by the system. In a simulation context we occasionally find such voters but they are not dictators in any reasonable sense. Instead they are voters whose preferences are in the median position of the set of electoral preferences. Even though these voters always get their way, the reason is simply that their preferences happen to be near or at the balance point of the full set of electoral preferences. They are not dictators, but are instead voters whose ideals happen to coincide with the electorate's collective preferences.

Yes, or at least it seems to be so. At first glance, SAVE qualifies under GST as a trivial voting system in the sense that in all circumstances the questions SAVE asks voters are all choices between two alternatives, which are the definition of trivial. SAVE manages to select a single winner from among a (possibly increasing) set of alternatives by breaking down the complicated problem into an iterative series of binary decisions. A vote for a non-focus alternative \(A\) states a voter's preference for \(A\) to be in the set from which the next focus could be chosen. A vote for the current focus alternative \(F\) states the voter's acceptance as \(F\) as the final winner.

The basic strategy is for voters to vote for any alternative they think is better than the focus, and to vote for the focus when they are willing to accept that focus as the final winner. In the expected to be rare cases where a voter considers an alternative \(T\) to be equally beneficial as the focus \(F\), that voter should link the vote for \(T\) to the vote for \(F\). Specifically, if the voter is trying to get an alternative better than \(F\), the voter would not be voting to terminate the SAVE loop with \(F\) as the final winner, so should also not vote for \(T\) since \(T\) is neither better nor worse than \(F\). When the voter is willing to accept \(F\), it makes sense to vote for \(T\), since \(T\) is again neither better nor worse, and so should also be acceptable.

This question is a little trickier. In simulations we find the pairwise results between the focus alternative and the alternatives that might replace it tend to be very close. This means if any voter changed their ballot from the basic strategy mentioned above, the round results might well change, which could lead to a different focus for the next round and potentially a different final outcome. But manipulation isn't just whether a voter can have an effect on the outcome. For a voting system to be manipulable it must be possible for a voter to get a subjectively better outcome than what would otherwise occur, which has an implicit requirement to know what would otherwise occur.

There are two views on this manipulability question.