Hands-on Tutorials

A Better Way To Vote

A Markovian Method To Quantify Collective Preferences From Individuals’ Ranked Choices

Image by author

What’s For Dinner?

The other day my family of four had to make a critical decision: what to get for dinner. The options on the table were sushi, fried chicken, Indian, or pizza. We could have done what we’d always done before: each person votes for their top choice and the option with the highest votes wins. But, I had been thinking about how to more accurately model collective preferences, and we decided to give that a whirl. So each of us ranked the 4 options from the most preferred to the least. Here’s how we voted (preserving anonymity to protect the innocent):

Vote 1: sushi, fried chicken, pizza, Indian
Vote 2: sushi, fried chicken, pizza, Indian
Vote 3: fried chicken, sushi, pizza, Indian
Vote 4: pizza, fried chicken, Indian, sushi

The typical top-choice voting method would have had a clear winner: sushi. But shouldn’t the antipathy of voter 4 towards sushi count for something? I crunched the votes through a model that accounted for all the preferences expressed in the votes, not just the top choices. And that model came up with a different winner: fried chicken. It made sense. Wouldn’t the group be happier overall if each individual got something in their top 2 choices (as was the case with fried chicken) than if 1 out of 4 had to suffer through their last choice (sushi)?

The model went further than just picking a winner: it ranked the options. Turns out that my family as a whole preferred (at that moment) fried chicken, then sushi, followed by pizza, and lastly Indian.

Not only did the model rank the options, but it also revealed the relative ratios of preference between the options:

fried-chicken:sushi:pizza:Indian as 44:37:16:3

It was a close race between fried chicken and sushi, with the former edging the latter out. Pizza was a distant third. And the family was just not in the mood for Indian that evening.

How did we get these results? Read on and I’ll explain in detail. But before that, a clarification. I hope the non-seriousness of the what’s-for-dinner problem has not lulled you into thinking that this just fun and games. In fact, it’s deadly serious business. Collectives at all levels (family, company, community, state) value the opinions of their members (or at least they should). And often the group decisions boil down to how to allocate a finite resource (e.g. power or money) across a set of competing priorities. That’s where this method shines. It quantitatively determines the relative preference among a set of options, which can then be used to allocate a budget in accordance with the will of the people.

The Method

I’ll illustrate the method for determining the collective relative preference among a set of options from individuals’ ranked choices, using the above example of what’s-for-dinner. Represent one person’s ranked-choice between two cuisines as a directed graph in which each cuisine is a node (vertex) and an edge (link/arrow) is directed from the less preferred cuisine to the more preferred one.

A graph representing a person’s preference for sushi over pizza (image by author)

A convenient, concise, and consistent way for an individual to express their relative preferences among the cuisines is to rank the cuisines by listing them from the most preferred to the least. For example, vote 2 (sushi, fried chicken, pizza, Indian) indicated that sushi was the top choice for that person, then fried chicken, followed by pizza, and lastly Indian. This encapsulated 6 pairwise comparisons:

1. sushi preferred to fried chicken
2. sushi preferred to pizza
3. sushi preferred to Indian
4. fried chicken preferred to pizza
5. fried chicken preferred to Indian
6. pizza preferred to Indian

Represent the vote by a graph with 6 directed edges, one for each of those comparisons.

A graph representing the decreasing ranked vote “sushi, fried chicken, pizza, Indian” (image by author)

Aggregate the votes by adding together the graphs for the votes. What does it mean to add together graphs? It means that each edge in the summed graph is assigned a weight that is a count of how many of the graphs being summed have that edge. Here’s the sum of the 4 graphs for the 4 votes in the example:

Graph aggregation of 4 votes (image by author)

In the aggregated votes graph, the edge from pizza to sushi with the weight 3 denotes that in 3 of the votes sushi was preferred to pizza. A particular cuisine is compared to every other cuisine in each vote. So the number of pairwise comparisons expressed for one cuisine in one vote is one less than the number of cuisines, or 3 in this example with 4 cuisines. For 4 total votes, the number of pairwise comparisons expressed for one cuisine is 4 x 3 or 12. Given the total number of pairwise preferences expressed for each cuisine, transform the aggregated graph by adding a self-edge to each node with a weight equal to the number of preferences in which the cuisine was preferred to other cuisines. This weight is the sum of the weights of the incoming edges to the node. Or, equivalently, it is the difference between the total number of preferences for a node (12 in the example) and the sum of the weights of the outgoing edges from the node. Here’s the transformed aggregated graph with self-edges:

Aggregated votes with self-edges (image by author)

Finally, transform the graph to normalize all the weights so that the sum of the weights of all outgoing edges from a node is 1. Then, the normalized weight of the edge from pizza to sushi denotes the fraction of the pairwise preferences (expressed in the votes) that preferred sushi to pizza. The weights can now be thought of as the empirical probabilities of transitioning between different collectively preferred cuisines. Here’s the normalized graph for the example, obtained by dividing each weight by 12 (which is the total number of comparisons of one cuisine with other cuisines in the 4 votes cast):

Aggregated votes with self-edges and normalized weights (image by author)

Now you’re ready to determine the result of the votes. Start with an ad hoc initial assumption of the group’s relative preference among the cuisines. For example, all cuisines are equally preferred:

fried-chicken:sushi:pizza:Indian as 1:1:1:1

Apply the probabilistic transitions (encoded in the transformed aggregated votes graph) to the initial preference to obtain the revised collective preference after one iteration. How? From the graph, you know that Indian has an 8% chance of remaining preferred, a 33% chance of losing to pizza, another 33% chance of losing to fried chicken, and a 25% chance of losing to sushi. So the Indian part of the initial preference transitions to 8% Indian, 33% pizza, 33% fried-chicken, and 25% sushi. Apply the same process to the other cuisines components, and you get the new ratios of:

fried-chicken:sushi:pizza:Indian as 38:33:25:4

If applying the transitions seems tedious, worry not, linear algebra can help. Construct a 4 by 4 matrix in which the first column consists of the probabilities of fried-chicken transitioning to fried-chicken, sushi, pizza and Indian, the second column consists of the transition probabilities out of sushi, and so on.

Transition Probability Matrix T (image by author)

Then, represent the relative preferences as a vector of relative probabilities. So the initial unbiased preference, v₀, has the components 0.25, 025, 0.25, 0.25 for the equal relative probabilities between the 4 cuisines. Multiply the preference vector by the transition matrix to get the revised preference vector after one iteration. Keep iterating until the preference stabilizes to the actual preference of the voters.

Relative preference transitions until stable (image by author)

In this example, the stable relative preference turns out to be:

fried-chicken:sushi:pizza:Indian as 44:37:16:3

As you saw at the beginning of this article, fried chicken is the winner, edging out sushi by a slim margin.

The Underlying Theory

If this method of computing relatively weighted preferences from individuals’ ranked-choices seems a bit like pulling a rabbit out of a hat, rest assured that it has a solid mathematical foundation. If you’re mathematically inclined, I’ll sketch the theory here. Otherwise, feel free to skip this section.

The problem maps to a Markov chain, making its full mathematical machinery available. A Markov chain is a sequence of events in which the probability of each event depends only on the current state (without regard to any past states or history). The normalized aggregated graph of individuals’ ranked choices described a 4-state Markov chain. A state is a node in the graph (or a mixture of nodes), which in our example represented the voters’ preferred weights for the cuisines. An event is a change in the state i.e. a change in the relative weights between cuisines. The empirical transition probabilities determined from the votes defined a stochastic matrix (or more precisely a left stochastic matrix in which each column summed to 1). Such a matrix is guaranteed to have an eigenvector with eigenvalue 1. That eigenvector is the steady-state of the Markov chain since it remains stable under the probabilistic transitions. And, if the matrix is positive (i.e. no entry is 0), then any initial state is guaranteed to converge to the steady-state. It turned out that our preference transition matrix was indeed positive. That’s why you could have started with any initial relative preference and reached the stable collective preference.

Given this theoretical base, let’s christen the method the Markovian method.

How Can You Try It?

In my family, each of us has strong opinions on everything, ranging from what we should have for dinner to what activity we should do to make full use of a Seattle sun break. Manually going through all the steps of the Markovian method is quite tedious and error-prone. But it's a simple matter to have a computer do it for us. I have a prototype web implementation at https://vishesh-khemani.github.io/collective-preference that you can play with. Just input the options and the votes on those options and it spits out the relative weights preferred by the voters, as well as the transition probability graph. You can see the code here: https://github.com/vishesh-khemani/vishesh-khemani.github.io/tree/main/collective-preference.

Here’s a screenshot of a run for the what’s-for-dinner example:

https://vishesh-khemani.github.io/collective-preference/ (image by author)

How Is It Useful?

Better Ranked-Choice Voting

In US political elections, third-party candidates often play the spoiler. For example, in the 2000 presidential election, Al Gore lost to George W. Bush by ~500 votes in Florida, a deficit that would have been comfortably overcome had Ralph Nader not garnered ~97,000 votes. This leads to the voter’s dilemma of whether to vote for their most preferred candidate or their somewhat preferred candidate who has a better shot at winning. What if the voters could rank their choices instead of voting for just one candidate? Countries like Australia and US states like Maine already do this. However, their tallying methodology is deficient (since it only considers lower-ranked choices of those ballots whose higher-ranked choices were eliminated in previous rounds of tallying).

Consider an election with 3 candidates: X, MX, and M. X is an extreme candidate, a polarizing figure who is either loved or loathed. MX is a moderate version of X. M is a moderate candidate on the other side of the political spectrum from X and MX. Supporters of X would likely rank M at the bottom. Supporters of MX or M will likely rank X at the bottom (since X is either loved or loathed). Consider the following votes:

Vote 1: X, MX, M
Vote 2: X, MX, M
Vote 3: MX, M, X
Vote 4: M, MX, X
Vote 5: M, MX, X

In a conventional plurality election, the result would be a tie between M and X. X would be a spoiler for MX’s chances.

In a conventional ranked-choice election (as it is implemented in Maine), MX would be eliminated in the first round of tallying. Then vote 3 would contribute a vote to its second choice M, pushing M to victory over X. Again X would be a spoiler for MX.

What happens in the Markovian method? Here’s a screenshot:

Image by author

An entirely different result: MX wins! Supporters of X were still able to have their voices heard for MX as their second choice. X was not a spoiler. And isn’t that the fairest outcome? MX was the first or second choice for all the voters. Both X and M were least preferred by a substantial fraction of the voters. Voters can vote according to their true preferences without worrying about siphoning votes away from a more popular candidate. And, candidates are incentivized to be less polarizing, lest the antipathy of the supporters of their opponents derails their chances.

Tournament Ranking And Predictions

Here’s a scenario that does not involve voting but rather predictions. Why am I talking about predictions? Well, the modeling of pairwise preferences applies equally well to any pairwise comparison among a set of entities. For example, in a tournament, we can input the result of past games into the model and it will predict the relative likelihood of each competitor winning.

I tried this out for a recently completed tournament: a cricket league that involved 8 teams with each team playing every other team twice. After the 56 games, the top 4 teams advanced to the playoffs. I entered the data for the first 28 games (half-way through the league stage, after each team had played every other team once) to see what the model would predict for the next 28 games. Here’s the result:

Image by author

Image by author

How well did the model’s prediction do?

1. The model predicted the top 4 teams (those who would qualify for the playoffs) completely accurately.
2. The model’s ranking would require 5 pairwise swaps (denoted by the crossings between the red and green lines in the figure above) to exactly match the actual ranking. If the model had been as wrong as possible by predicting a ranking in the opposite order of the actual ranking, it would have required 28 pairwise swaps. So, here’s one measure of how accurate the predicted ranking was: (1–5/28) or 0.82 (where 1 would be perfect accuracy and 0 would be the worst accuracy). That’s quite a high accuracy score.
3. Maybe you think that this is all overkill and you could have simply tracked the win/loss record for each team after 28 games and come up with a similarly accurate prediction. But that’s just not true. The win/loss record after 28 games would be rife with inaccuracies and other issues. For example, each of Bangalore, Mumbai, and Delhi had a 5:2 record and Bangalore beat Mumbai who beat Delhi who beat Bangalore. So it’s not clear what the relative ranking should be between these 3 teams. Kolkata won more games than Hyderabad and also beat Hyderabad, so you would think that it should be ranked higher than Hyderabad. However, the Markovian model placed Hyderabad higher, mainly because they beat some other top teams, a prediction that bore out in reality.

Summary

1. If a set of entities (e.g. candidates in an election, or teams in a tournament) is compared pairwise (e.g. a voter prefers candidate A to candidate B, or team A beat team B in a recent game), with each pairwise comparison occurring any number of times (e.g. different voters’ preferences between two candidates, or different game results between two teams), then you can determine the relative weights between the entities that fully encapsulate the pairwise comparisons (e.g. the voters prefer candidate A over candidate B by 3:2, or team A has a 5:3 odds of beating team B).
2. The computation method is based on mapping the pairwise comparisons among entities into empirical transition probabilities between the entities. How? Represent a pairwise comparison as a graph in which each compared entity is a node with a directed edge from the “loser” to the “winner” entity. Combine all the comparison graphs into an aggregated graph in which each edge has a weight equal to the number of occurrences of that edge in the pairwise comparisons. Normalize the weights so that the weight of the edge from entity A to entity B is the fraction of comparisons between A and B that had B as the winner. This fraction is the empirical transition probability of B winning against A. Now the graph represents a Markov chain for winning transitions between the compared entities. Starting with any initial win ratios between the entities, and repeatedly applying the transition probabilities, the Markov chain stabilizes to a steady-state of win ratios.
3. The method is widely applicable, from deciding which cuisine will best satisfy the disparate tastes among friends/family, to what the relative winning odds are of competitors in a tournament, to which candidate is truly the most preferred choice of the voters, to how to allocate a fixed budget across competing projects, and so on.
4. You can play with this Markovian method for your own set of entities and comparisons using a prototype web implementation at https://vishesh-khemani.github.io/collective-preference. And if you come up with an interesting result, I’d love it if you could leave a comment.