Mathematical elections

    3 minutes read | 493 words by Ruben Berenguel

Image from Flickr

Arrow’s impossibility theorem and related results

Background: Let K={A,B,C…} be a finite set of alternatives (maybe political parties), with more than 3 items. Let’s call transitive preference a way to sort all these elements, with draws possible. It’s just a funny name for a vote, in the more general sense as we can split our vote (Let A have 0.5, B 0.25 and C 0.25 of our vote). Now consider a set of N electors, each one with a transitive preference, i.e. a vote. We will call constitution (according to the naming in the theorem) a function which assigns each set of electors-votes a certain outcome: the final election, the people’s choice. As a matter of notaton, A>(n)B means that the elector n decides A is a better election than B.

There are certain properties which a “good” constitution should verify:

  • Transitivity: Assume an outcome is given, and the constitution says A>B. The constitution will be transitive if JUST a voter changes his vote A>(n)B for B>(n)A, then the constitutional output will be either no change, or A gets dropped. This assumption is used so that voting isn’t harmful for the voted party.
  • Unanimity: If everyone votes A>B, the constitution should result in A>B.
  • Independence of irrelevant alternatives: If the fact of A being above B in the constitution is only a result of A being above B in the individual votes.

We say a constitution is a dictatorship if there is an elector n such that the constitution puts A>B whenever n puts A above B.

Arrow’s impossibility theorem: Every constitution satisfying all three properties above is a dictatorship.

This theorem establishes compositions in a legislative chamber, for instance. And there is not a clear-cut way to do so, the theorem says. What happens if the constitution just selects, without order, a subset of candidates?

Duggan-Schwartz’s theorem: A constitution to select a subset of candidates from a set of more than 3 always satisfies:

  • The system is not anonymous, thus the vote of certain electors has a bigger impact than others.

  • The system pre-imposes that certain candidates never win.

  • The preferred candidate amongst all electors is in the subset of electees.

  • The election is manipulable.

And what if we just need to choose one winner, a president?

Gibbard-Satterthwaite’s theorem: A constitution to choose just one candidate amongs more than 3 candidates verifies one of the following:

  • It is a dictatorship,
  • The system pre-imposes that certain candidates never win.
  • The election is manipulable.

What means that the election is manipulable? There are different ways it could be manipulated. For instance, knowing how the system works, and certain voting trends, the vote of a number of individuals can change the outcome of the election. A typical example, the slightly extreme leftists voting moderate leftists, knowing that more extreme leftists won’t get representation in the election.

This, of course, doesn’t mean you should not vote… just think a little before doing so.