I don’t know how to design websites, but I know when I like one. To make this website, the one you’re on right now, I built tools to ask myself the same question over and over: “Which one do I like more, this one or that one?” In this post I’ll show you nine increasingly fancy ways to go from pairwise votes (“A beats B, A beats C, …”) to a ranked list (“A > B > C”). Elo rating is probably the most famous of these.

Choosing between designs for this website. I liked both of these but they are so bold and colorful! I was too shy 🫣
I’ll start with the simplest possible method, then we’ll see what’s wrong with it. Then we’ll fix it, leading us to the next method, and so on. By the end of this post, you’ll understand the kinds of things that Elo rating does well, its failure modes, and how to fix them. There are fun connections to modern ML methods. (For example, the Elo update is a single step of a stochastic gradient descent with a logistic loss function. And pairwise comparisons by humans are often used to rank responses for RLHF.)
Everyone has a different top 5 Miyazaki movies list, and everyone is right in their own way. That will be my running example in this post. Studio Ghibli holds the copyright to the movie stills I’ve used here. I’m grateful to them for providing these images under the delightfully-phrased condition, “Please use them freely, within the bounds of common sense.”
It’s too hard to rank things, just let me pick the best of two.
We begin by supposing that it is just Too Hard for me to rank things. It is too much to ask for. The best I can manage is, Which of these is better? We’d like to turn my answers into a ranking. If my preferences are self-consistent, then my votes must have the property that if A > B and B > C then A > C (transitivity).
Method 1: Topological sort on the graph of votes
Assuming my votes do have this property, we can do topological sort to find the ranking. Each movie is a node and each vote is an edge between two nodes that says, This is better than that.
At any point during the process, there will be some movies that are definitely known to be better than some other ones, and others where we cannot say which is better.
For example, if I vote that Totoro is better than Ponyo, and Ponyo better than Porco Rosso, then we know that Totoro must be better than Porco Rosso. That much is uncontroversial. But given just those two votes, we cannot tell whether Spirited Away is better than Porco Rosso. How silly!
Here’s a demo:
Did you run into a cycle? The problem is Rock-Paper-Scissors cycles. I cannot help but contradict myself, and this kind of exact algorithm chokes immediately on even a single contradictory input.
But what if I contradict myself?
We need a method that will tolerate noisy votes. The classic solution is Elo rating, used to rate chess players.
Method 2: Elo rating
Each player has a rating, which is a single number. Suppose there’s a match between Player 1 and Player 2. The probability that Player 1 wins is a function of the difference in their ratings. (The function is a logistic curve with inputs scaled so that ratings are around 1-2k). If the stronger player wins the match then there’s only a small update to their ratings, because this outcome was expected: the strong player gains a little, the weak player loses a little. But if the weaker player wins, then the strong player’s rating goes down by a lot, and the weak player’s rating goes up by a lot, because the outcome was a surprise. You can look up the update formula on Wikipedia.
I think the right way to think about this is as an optimization problem: given all the match outcomes between all players, assign a rating to each player such that a loss is minimized. The loss function is the negative log-likelihood of each match. But to actually solve this problem you need to know all matches that have ever happened. Instead, the Elo system performs an update after each match that corresponds to a single step of stochastic gradient descent, on just the two players involved, and a judiciously chosen step size. Everyone starts with a rating of 1500.
Here’s a demo. As you vote, it also runs Method 1, topological sort. You’ll notice that Elo handles contradictory votes just fine. But movies can be in the top 5 despite never having won a match.
When Elo rating is good, and its two key weaknesses
Elo is great for the problem it was invented to solve: there’s no single authority who knows all the matches that have been played. You just want to update the ratings of the two players who had a match, and also it would be nice to not have to do a lot of complicated calculations. There are lots of matches happening all the time, and no central computer with all the data.
However, it has problems. First, the ratings have no uncertainty. A beginner might have a rating of 1500 because they haven’t played many games yet, while another player might have a rating of 1500 after a hundred matches. The second number is a much better indicator of the player’s true strength, but Elo doesn’t track that.
Second, suppose that A beats B early on, when they’re both rated about 1500. A’s rating goes up a little. Then B beats a bunch of Grandmasters the next day. B’s rating shoots up. But because Elo updates ratings in order after each match, A’s rating remains unchanged, even though it should rise because A defeated what turned out to be a strong player.
If lots of matches are being played this isn’t a big deal. A’s true strength will soon reveal itself. But we’re leaving information on the table.
But what if I want each match to update all the strengths?
Method 3: A Gaussian for each movie, fitted to all votes
This is where framing it as an optimization problem is helpful. Instead of doing a single SGD step after each match, let’s just refit all the strengths to the entire set of cast votes. With a human casting votes there simply isn’t that much data. It’s better to spend compute to get more use out of the data. Here, each movie’s strength is modeled as an independent Gaussian. So we’re throwing away correlations but we get a simple model that’s easy to interpret.
This is better than Elo because it updates our beliefs about every movie’s strength in light of new evidence. But, like Elo, this model simply accepts whichever matches have been played and updates accordingly. The matches themselves are random. You can click away for a long time and still not find the best Miyazaki movie.
But what if I only care about the best movies?
Instead of proposing random matches, we want to propose matches that focus on discovering the best movie. This is where having an uncertainty for each strength pays off.
Suppose there have been a bunch of votes. After the fit, we have a Gaussian for each movie, each with its own mean and variance. Suppose we wanted to know the very best Miyazaki movie, based on the votes so far. How do we answer that question?
A reasonable naive answer would be: the best movie is simply the movie with the highest mean strength. This isn’t a terrible answer, but it’s overconfident. What if the movie with the second-highest mean has a big variance? We’re ignoring the very real possibility that actually the best movie is the one with second-highest mean, or some other one.
A better answer is to sample from each movie’s Gaussian, and return the movie whose sample is biggest. If every movie has a very tight variance around its mean, then this method and the naive one behave the same. But if the movies’ distributions overlap a lot, each movie has a chance of being the best in a way that reflects that overlap.
Perhaps unintuitively, the highest-mean movie is not necessarily the one that’s returned the most often! Example: if one movie has a tiny lead and a tight variance, while many others are close behind with large variance.
This is called “sampling from the posterior”. We’re answering a question we care about, and we’d like the answer to reflect the uncertainty in our model and data, so we sample the posterior and compute the answer on that sample.
(Later we’ll want many samples from the posterior. This lets us answer questions like, “How likely is it that Spirited Away is the best Miyazaki movie?”.)
The key insight is that we can use this idea to propose good matches.
Method 4: Top-two Thompson sampling
Take two samples from the posterior. If they disagree on what the best movie is, then that’s a real match worth proposing to the voter. Asking them to vote on that matchup settles a real disagreement that arose naturally from the model. I like to think of these as two alternate worlds, both drawn from the posterior of the model, so if they disagree then it’s worth spending a vote to figure out which world is right.
Two samples disagreeing about the best movie. Each sample assigns a specific strength to each movie, drawn from that movie’s Gaussian.
This idea is adapted from Daniel Russo, “Simple Bayesian Algorithms for Best-Arm Identification”, Operations Research 68(6):1625–1647, 2020.
Here’s a demo. The dots in each row show where the two samples placed each movie. The two red dots are the lead movies in the two samples. Even though we spend most votes asking about the top few movies, the ones at the bottom still have a chance to show their strength!
You’ll notice that the matchups now concentrate on figuring out the very best movie, while leaving every other movie unresolved. That’s weird! Even if Spirited Away is best, it’s weird for Mononoke to be at the bottom.
But what if I care about the top 5, not just the best movie?
What matches should be proposed if we want to figure out the top 5 movies? We can extend the idea above: draw two plausible worlds (samples) from the posterior, and propose a match that settles a disagreement between them.
Each sample assigns a strength to each movie, so there’s an ordered list of top 5 movies in each sample.
Take 2 samples from the posterior and walk down their top 5 in order. The first time they disagree, propose a match between those movies. Like with top-two Thompson sampling, if the second sample has exactly the same top 5 in the same order, keep drawing until you get something different.
Method 5: MCMC to find the top 5 and their order
That’s cool but how can we draw samples from this posterior? You can’t just write down a formula for it. The answer is MCMC sampling. In this kind of algorithm, we do a random walk in the space of strength vectors that spends time in each region proportional to that region’s posterior probability. It can do this without actually needing to compute the actual posterior probability (which is usually intractable, because the denominator is a difficult integral). You just need to be able to calculate the likelihood of each vote, given a sample. I won’t say any more here on how this works but it’s a beautiful and fascinating topic.
The rest of the methods here will use MCMC to sample from the posterior. The posterior probability distribution will be represented simply by the collection of samples. Anything we want to know about the distribution can be approximated by computing an average of the collection of samples.
Here’s a demo. It shows several samples, the top 5 in each one, and the first place where they disagree. That’s the match.
You’ll notice that it spends a lot of energy resolving not just which movies are in the top 5 but also their relative order.
But what if I just care about the set of top 5 movies, not their order?
Intuitively, we need fewer votes to figure this out since it’s a strict subset of the information in the previous method. Here’s how: draw two samples and compare the set of top 5 movies in each. If the sets are different, propose a match between two movies where the two disagree, that is, movies that are in one sample’s top 5 set but not the other’s.
This idea is adapted from Algorithm 3 of You, Qin, Wang and Yang, “Information-Directed Selection for Top-Two Algorithms” (COLT 2023).
Method 6: MCMC to find the top 5 as a set
Here’s a demo:
You’ll notice that this method proposes matches whose outcome is nearly certain. Surely that’s a waste?
But what if I don’t want to cast votes whose outcome is already quite certain?
Our posterior distribution, in the form of the samples, already tells us how likely the outcome of a vote is. We can use this to be more efficient in the matches proposed. Let p_i be the probability that the ith movie is in the top 5. Then define a loss function that’s the sum of p_i(1-p_i) over all movies. This loss function rewards when a movie is certain to be in the top 5 or certain to be out of it. We want to propose a match that, in expectation, reduces this loss the most. In other words, propose the match whose outcome most pushes movies either into the top 5 or out of it, in expectation.
Method 7: Propose the matchup that gives the most information
This is called one-step or myopic lookahead: we’re comparing all possible pairs and evaluating the two possible outcomes. You can imagine making a tree of possible outcomes going several votes into the future, to make even better decisions. But it gets expensive real fast.
Demo time!
But does it really need to be so complicated?
Here’s a simpler rule that works even better than the fancy information thing from before. Of all the movies in the top 5, one of them is least likely to be in the top 5. And of all the movies not in the top 5, one of them is most likely to be in the top 5. Propose a match between those two.
Method 8: Propose a match between the two movies that are closest to moving between being in and out of the top 5
This rule is simple, cheap to evaluate, easy to debug, and works well in practice. I like it!
This idea is from Kalyanakrishnan et al., “PAC Subset Selection in Stochastic Multi-armed Bandits”, ICML 2012.
How I like to think about match proposals
You’ll notice that each demo has a stopping condition. For example, the demo in Method 8 stops when the 5 highest P(top 5) are each ≥ 0.9. Separately, each method has its own heuristic for proposing matches. The key insight is that these two are, or should be, connected. Matches should be proposed such that, in expectation, we reach the stopping condition after the fewest votes. But this is a very difficult problem to solve exactly. Tree search can do it but you still need to cut it off after some point. Hence all the heuristics.
Bonus technique: MEGALIKE!
Right now we get a single bit of information from each vote: which movie is better. But sometimes a match is very lopsided. I like Totoro a LOT more than I like Porco Rosso. By allowing the voter to register a strong preference, we can get to convergence faster. There are several ways to model this. One hack is to count a MEGALIKE as just several ordinary votes. Another way is to treat a MEGALIKE as saying, “The difference between the true strengths is bigger than d”.
To make this a valid probability model, a regular vote now actually means something like “the difference between their true strengths is positive but less than d”. So if two movies are far apart, a regular vote might actually bring them closer together. You can think of the model as learning, “They could have MEGALIKEd but they didn’t, so actually these movies aren’t so far apart”.
Here’s a demo!
Bye!