Voting Theory Exercises


Exercise 4

  • $N = 10$, $A$ - set of candidates
  • define a relation $a \ B \ b$ as "$a$ is better than $b$"
  • if this relation transitive and can it have cycles?

Exercise 4.1

Define $a \ B \ b$ as

  • $a \ B \ b \iff n_{ab} \geqslant 6$ where $n_{ab}$ is the number of people who rank $a$ before $b$ (like in Condorcet's Rule)

This voting system is very similar to the Condorcet's Rule

We can show that it means to be transitive:

  • ex-transitivity.png
  • i.e. if there exists a loop then there can be no transitivity
  • so it suffices to show that there can be cycles and it will answer both questions

Consider the following ranking:

  • $3: a > b > c$
  • $3: b > c > a$
  • $4: c > a > b$

Now calculate the $B$ relationship:

  • $a \ B \ b$ since $n_{ab} = 7$
  • $b \ B \ c$ since $n_{bc} = 6$
  • $c \ B \ a$ since $n_{ca} = 7$

We have a cycle:

  • condorcet-monotonicity-2.png


Exercise 4.1

Define $a \ B \ b$ as

  • $a \ B \ b \iff n_{ab} \geqslant 7$ where $n_{ab}$ is the number of people who rank $a$ before $b$

In this case $B$ also is not always transitive.

Consider the following example:

  • $4: a > b > c$
  • $3: b > c > a$
  • $3: c > a > b$
  • in this case there are not enough votes to have an edge $c \to a$
  • ex-not-completeness.png
  • note that his shows that the relation $B$ is not complete (this can also be the case for the previous exercise)

And there can be no cycles: too few voters for this

  • consider the case with 3 candidates: $A = \{a, b, c\}$
  • there are 6 possible individual rankings for elements from $A$: there are 3! permutations of $A$
    • $R_1: a < b < c$ -- $n_1$ voters
    • $R_2: a < c < b$ -- $n_2$ voters
    • $R_3: b < a < b$ -- $n_3$ voters
    • $R_4: b < c < a$ -- $n_4$ voters
    • $R_5: c < a < b$ -- $n_5$ voters
    • $R_6: c < b < a$ -- $n_6$ voters
    • $n_i$ - the number of voters with ranking $R_i$
  • to have a cycle we need to have:
    • $n_{ab} = n_1 + n_2 + n_6 \geqslant 7$
    • $n_{ba} = n_1 + n_3 + n_4 \geqslant 7$
    • $n_{ca} = n_4 + n_5 + n_6 \geqslant 7$
  • let's sum up these
    • $2 \cdot n_1 + n_2 + n_3 + 2 \cdot n_4 + n_5 + 2 \cdot n_6 \geqslant 21$ (1)
  • recall that we have only 10 voters:
    • $n_1 + n_2 + n_3 + n_4 + n_5 + n_6 = 10$ (2)
  • now let's calculate (1) - (2):
    • $n_1 + n_4 + n_6 \geqslant 11$
    • this cannot happen: we have only 10 voters
  • contradiction


Sources