Gibbard–Satterthwaite Theorem clarification

Question

recently I read about this theorem on math websites which talked about voting systems. since I'm interested in politics and math I'm interested to understand this theorem but it requires higher level math(I'm learning math in high-school last year). I need a help to understand this theorem. 1-is it mentioning that every system of voting with more than two people to be voted for is unjust? any help to understanding it is appreciated.

Answer 1

Your question is very broad, so I'll try to give a general explanation of the theorem, as well as answer the specific question. I also don't really know what kinds of math and notation you'd be familiar with, so please ask if something is unclear.

What is a voting rule?

Within (computational) social choice theory, we model voting as people casting ballots, after which some rule will select a winner. The framework does not require that the winner be at all based on the ballots, though I'm sure you'll agree that we would probably want that.

More mathematically, we have $m$ candidates $C = \{a, b, c, \dots\}$ and $n$ voters $N = \{1, 2, 3, \dots,n\}$, each of which submits some ballot $A_i$ giving their preference over the candidates. All these ballots together, we call a ballot profile, which we denote with a boldface A: $\mathbf{A} = [A_1, A_2, \dots, A_n]$.

A voting rule, then, is some function $f$ which, given a ballot profile $\mathbf{A}$, outputs the winner of the election. What exactly the winner looks like depends on the kind of election we're running. Similarly, we can vary the form of the ballots that the voters are allowed to submit. We're specifically looking at the Gibbar-Satterthwaite theorem, so let's look at what kind of election this theorem applies to.

What kind of election does the GS theorem apply to?

The Gibbard–Satterthwaite theorem applies to voting rules that have the following three properties:

1. Single-winner, which means that we're electing a single candidate (not a committee or parliament or something like that);

2. Resoluteness, which means that ties are not allowed;

3. Ordinal voting, which means that the ballots that the voters submit only have information about which candidates they like more than others. So, they might be able to submit something like $a \succ b \succ d \succ c$ indicating that they prefer $a$ over $b$, which they prefer over $d$, which they prefer over $c$. They cannot, however, indicate more than that. The theorem for example does not apply to voting rules that allow the voters to grade the candidates.

Note here that 1. and 2. together mean that the voting rule always outputs exactly one candidate. So, for any ballot profile $\mathbf{A}$, $f(\mathbf{A}) = c$ such that $c \in C$.

These three properties are indeed satisfied by most presidential elections, as we're electing a single person, and voters can only vote ordinally. For example, in the US one votes for their favorite candidate, and in France one votes for their favored candidate and then for their favorite among the two frontrunners.

What is the Gibbard–Satterthwaite theorem?

Now that we have that out of the way, the Gibbard–Satterthwaite theorem says that every voting rule falls into at least one of the following three categories:

1. Dictatorship: a single voter picks the winner, all other votes are ignored;

2. Only one or two candidates can possibly win;

3. Strategic voting can be beneficial.

The first category is clearly terrible. Indeed, a dictatorship is hardly a voting rule, as it doesn't have much to do with voting.

The second category is equally terrible. This says that, if we have an election with at least three candidates, the voting rule prevents one of them from winning, even if they were to get every single vote.

Most real elections fall in the third category, which is non-strategy-proofness. This means that a voter might be able to get a better result by misrepresenting their preference. For example, voter $1$ submits the following truthful ballot: $A_1 = a \succ b \succ d \succ c$. If we feed the ballot profile with this ballot through the voting rule we get some winner, for example $d$: $f(\mathbf{A}) = d$. However, if instead she lies on her ballot and submits $A_1^* = b \succ a \succ d \succ c$, this might change the outcome of the election in her favor: $f(\mathbf{A}^*) = b$.

A more important example is the US presidential election. Specifically, in 2000 the election was incredibly close. There was lots of controversy around this election, as well as about the outcome, but we'll ignore that and pretend like the official final tally was entirely correct. We'll also ignore every candidate except for the most important three.

As it happens, many people that year preferred the green party candidate (Nader) over both the democrat (Gore) and the republican (Bush). However, most people who liked Nader still preferred Gore over Bush. That is, a very common truthful ballot was $\textit{Nader} \succ \textit{Gore} \succ \textit{Bush}$. Because the election was decided on only a handful of votes, this became very impactful. Bush won, but it is generally considered highly likely that, if these people had voted more strategically by voting for Gore in the first place, Gore would have won, which they would have preferred over Bush.

This symbolises the problem with manipulability. Ideally, people should not have to misrepresent their preferences to be properly represented.

Does that mean every voting rule is unjust?

First off, we should note that unjust is a very broad term. However, if you feel a voting rule that is not strategy-proof is unjust, then the answer is essentially yes. Of course, this theorem only applies to a specific form of voting rule, but there are many of these impossibility theorems for lots of different voting frameworks and lots of different (un)desirable properties. The most famous one is Arrow's theorem, but more get proven all the time (and most don't get a name).

Again, if you have any questions, please feel free to ask.