Tideman Voting Algorithm: A Graph-Based Approach to Elections

Understanding the Tideman Voting Algorithm: A Graph-Based Approach

The Tideman algorithm, also known as "ranked pairs," is a sophisticated voting system that leverages graph theory to determine election winners. By allowing voters to rank candidates in order of preference, it captures more nuanced voter intentions than simple plurality voting systems. This blog post explores the theoretical foundations of the Tideman algorithm, focusing on its graph-based approach and key mechanisms.

The Graph Theory Foundation

At its core, the Tideman algorithm represents an election as a directed graph:

• Nodes represent candidates
• Edges represent preferences of one candidate over another

This approach creates what's called an adjacency matrix where locked preferences between candidates are recorded. In the matrix example shown in the image, "true" values indicate a locked preference (or edge) between candidates.

For example, in the matrix shown, we can see that:

• Candidate 0 is preferred over candidate 1
• Candidate 2 is preferred over candidate 0
• Candidate 2 is preferred over candidate 1

These locked preferences collectively form the final graph that determines the winner.

The Preferences Array

The preferences array is a fundamental data structure in the Tideman algorithm. It records how many voters prefer one candidate over another:

• preferences[i][j] represents the number of voters who prefer candidate i over candidate j

For an election with three candidates (represented as 0, 1, and 2), the preferences array might look like this:

	0	1	2
0		5	3
1	4		6
2	7	2

In this example, 5 voters prefer candidate 0 over candidate 1, 3 voters prefer candidate 0 over candidate 2, and so on. The diagonal cells remain empty because a candidate cannot be compared with themselves.

Recording Voter Preferences with the Ranks Array

Tideman tracks individual voter preferences using a ranks array. For each voter, this array stores their candidate rankings where:

• The index represents the rank (0 being the highest preference)
• The value represents the candidate ID

For example, in an election with Alice (0), Bob (1), Charlie (2), and David (3) as candidates, if a voter prefers Bob most, followed by Alice, then David, and finally Charlie, their ranks array would be:

ranks = 1, ranks[1] = 0, ranks[2] = 3, ranks[3] = 2

This means at rank 0 (highest preference), they chose candidate 1 (Bob), at rank 1 they chose candidate 0 (Alice), and so on.

Sorting Candidate Pairs by Strength of Victory

After collecting all votes, the algorithm creates "pairs" of candidates where one is preferred over another. These pairs are then sorted by strength of preference (how many more voters prefer one candidate over the other).

The algorithm uses merge sort to efficiently organize these pairs, ensuring that the strongest preferences are considered first when building the final graph.

The Lock Pairs Function: Avoiding Cycles

The most crucial part of Tideman is the lock_pairs function, which determines which preferences to "lock in" to the final graph. There are two main approaches to implementing this function:

Method 1: Column Check

A graph remains non-cyclic if at least one column in the adjacency matrix contains all "false" values. This is an observation that requires checking all columns.

Method 2: Cycle Detection

The more sophisticated approach is to check if locking a pair would create a cycle in the graph. A cycle occurs when following the preference edges leads back to the starting candidate.

Cycle Detection in Practice

Let's see how cycle detection works with an example:

Candidates = [a, b, c, d]
Sorted Pairs = [(d, a), (a, b), (b, c), (c, a), (d, b), (d, c)]

1. Looking at pair (d, a): No prior locked pairs, so we can lock this. Graph: d → a
2. Looking at pair (a, b): No cycle created, so we lock it. Graph: d → a → b
3. Looking at pair (b, c): No cycle created, so we lock it. Graph: d → a → b → c
4. Looking at pair (c, a): This would create a cycle c → a → b → c, so we don't lock it.
5. Looking at pair (d, b): No cycle created, so we lock it. Graph now includes d → b
6. Looking at pair (d, c): No cycle created, so we lock it. Final graph includes d → c

The final graph looks like:

		a
	➚	↓
d	➙	b
	➘	↓
		c

The key insight is that we only skipped locking pair (c, a) because it would have created a cycle.

Finding the Winner

After locking all valid pairs, the winner is the candidate with no incoming edges in the final graph - the "source" of the directed graph. This candidate is not beaten by any other candidate according to the locked preferences.

In our example, candidate d has no incoming edges, making it the winner.

Theoretical Significance

The Tideman algorithm elegantly solves several problems in voting theory:

1. It finds a Condorcet winner when one exists (a candidate who would win head-to-head against all others)
2. It provides a reasonable approximation when no Condorcet winner exists
3. It satisfies the Independence of Irrelevant Alternatives criterion better than many other voting systems

By using graph theory to represent voter preferences, Tideman creates a more complete picture of the election results than simpler methods like plurality voting.

Conclusion

The Tideman algorithm represents a sophisticated application of graph theory to voting systems. By considering the full spectrum of voter preferences and carefully constructing a directed graph that avoids cycles, it provides a more nuanced and representative election outcome.

Understanding the theoretical foundations of Tideman - from preference arrays and rank recording to cycle detection and winner determination - gives us insight into how modern voting systems can better capture voter intent and produce fairer election results.