This a voting mechanism from Voting Theory.

The main idea:

- all candidates are compared in pairs
- prefer the candidate who are preferred by the majority in pair-wise comparison

We say that a voting system (procedure) is *fair* when

- if we choose a candidate $x$ then
- $x$ can beat every other candidate in a pair-wise election
- in this case $x$ is called
*the Condorcet winner*

If $x$ wins the election but it loses in pairwise comparison

- then the Condorcet fairness criteria is not satisfied

Many other Voting Theory methods do not satisfy this criterion:

But the *Condorcet Voting System* (discussed below) does satisfy it.

Idea:

- all candidates from the set $A$ are compared in pairs
- there are $N$ voters
- $n_{ij}$ is the number of voters that prefer $i$ to $j$ (i.e. they say $i > j$)
- $n_{ij} + n_{ji} = N$

$i$ is preferred globally to $j$ $\iff n_{ij} > \cfrac{N}{2}$

Preference Graph:

- we depict all preferences in a graph
- each candidate is a node
- an edge between two nodes $a$ and $b$ means "$a$ is preferred over $b$" ($a > b$)

We find the winner by looking for an node that has no incoming edges

- it means that this candidate is preferred to all other candidates

Individual rankings:

- $a > b > c$ - 11 voters
- $b > a > c$ - 8 voters
- $c > b > a$ - 2 voters

Pair-wise comparisons:

- $a \text{ vs } b$: $n_{ab} = 11, n_{ba} = 10 \Rightarrow a > b$
- $a \text{ vs } c$: $n_{ac} = 19, n_{ca} = 2 \Rightarrow a > c$
- $b \text{ vs } c$: $n_{bc} = 19, n_{cb} = 2 \Rightarrow b > c$

The Preference Graph for this example is

The Condorcet winner does not always exist - this is called *the Condorcet Paradox*.

- when there's a cycle in the Preference Graph - there is no winner

$A = \{x, y, z\}, N = 60$

Individual rankings:

- 23: $x > y > z$
- 17: $y > z > x$
- 2: $y > x > z$
- 10: $z > x > y$
- 8: $z > y > x$

The preference graph has a cycle:

This rule satisfies:

- Condorcet's Fairness Criteria
- Separability

Does not satisfy:

- Monotonicity
- Solution Existence (see Condorcet Paradox)

Suppose we have the following ranting:

- 1 vote: $a > b > c$
- 1 vote: $b > c > a$
- 1 vote: $a > c > b$

Let's build the preference graph:

- $a$ vs $b$: $n_{ab} = 2, n_{ba} = 1 \Rightarrow a > b$
- $a$ vs $c$: $n_{ac} = 2, n_{ca} = 1 \Rightarrow a > c$
- $b$ vs $c$: $n_{bc} = 2, n_{cb} = 1 \Rightarrow b > c$

Suppose now $c$ improves his position:

- 1 vote: $a > b > c$
- 1 vote: $b > c > a$
- 1 vote: ${\color{blue}{c > a}} > b$

We have the following preference graph:

- $a$ vs $b$: $n_{ab} = 2, n_{ba} = 1 \Rightarrow a > b$
- $a$ vs $c$: $n_{ac} = 1, n_{ca} = 2 \Rightarrow {\color{blue}{c > a}}$
- $b$ vs $c$: $n_{bc} = 2, n_{cb} = 1 \Rightarrow b > c$
- no one is the winner now - there is no solution

So by improving his position $c$ should stay in at least the same position

- but now he is not - everybody loses

Say we have two regions $A$ and $B$, and $A \cup B = V$.

- suppose for both $A$ and $B$ we have same ranking: $a$ is preferred to $b$
- $n^A_{ab} > n^A_{ba}$ for $A$ and $n^B_{ab} > n^B_{ba}$ for $B$

- if we run the election in $V$ we will get:
- $n_{ab} = n^A_{ab} + n^B_{ab}$, $n_{ba} = n^A_{ba} + n^B_{ba}$
- $n^A_{ab} > n^A_{ba} \land n^B_{ab} > n^B_{ba} \Rightarrow n_{ab} > n_{ba}$

- so $a$ is preferred over $b$ in the whole region $V$ as well

Thus, Separability is respected.

- Decision Engineering (ULB)
- Mathematics of Voting, slides [[1]]
- Voting Fairness Criteria [2]