Gibbard-Satterthwaite theorem

from Wikipedia, the free encyclopedia

The Gibbard-Satterthwaite theorem is a statement in social choice theory about group decisions, especially about the limits of preferential choices . In the case of preferential elections, each group member ranks a number of decision alternatives according to their individual approval.

The theorem states that every preferential election with three or more decision alternatives can be manipulated by strategic voting behavior, provided that it satisfies democratic values, that all persons participate in the process on an equal footing and that every alternative has the chance to be accepted.

Exact formulation

Two definitions are helpful for an exact formulation of the theorem: A procedure is called dictatorial if there is an excellent person whose preference the procedure decides. A procedure is called manipulable if there are situations in which a participant - who knows both the procedure and the voting behavior of all other participants - can improve the chances of an alternative by voting not for this, but for another alternative or that Can worsen chances of an alternative by voting for them. With these definitions the Gibbard-Satterthwaite theorem reads:

If there are three or more alternatives, at least one of the following three conditions is met for each preferential election:

  1. The process is dictatorial.
  2. There is an alternative that can never be accepted.
  3. The procedure can be manipulated.

An example

In the following example, the rules of instant runoff voting apply :

Each voter determines his first, second, ..., last choice among all decision alternatives (options). If an option has the majority of the first places, it is selected. Otherwise, the option with the lowest number of first places will be deleted from all preference orders (voting slips), and the other options will move up to the places that have become free. In particular, the options that took second place behind the deleted one are now considered the first choice of these voters.

You have to choose between four options A, B, C and D. There are four groups of voters, which order the options as follows:

Group 1 (15 people): B> C> D> A
Group 2 (24 people): C> D> A> B
Group 3 (29 people): D> A> C> B
Group 4 (32 people): A> D> C> B

First option B is deleted, then D. Thus, A is collectively preferred with a majority of 61:39. Group 1 would like to prevent candidate A from winning. Since, for ideological reasons, they think they know the preferences of the other groups, they put A in the first position of their preference order:

Group 1 (15 people): A> B> C> D
Group 2 (24 people): C> D> A> B
Group 3 (29 people): D> A> C> B
Group 4 (32 people): A> D> C> B

Due to the new preferences, first B is deleted and then C. Among the remaining candidates A and D, D is collectively preferred with a majority of 53:47.

literature

  • Allan Gibbard: Manipulation of voting schemes. A general result. In: Econometrica . Volume 41, No. 4, 1973.
  • Mark Satterthwaite: Strategy-proofness and Arrow's Conditions. Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions. In: Journal of Economic Theory . Volume 10, 1975.

Web links