← all experiments

Whoever's Left Standing

Experiment № 108 · November 2, 2026

Boyer and Moore's 1981 majority vote reads a stream of ballots holding just two numbers: a candidate and a count. A ballot for the candidate adds one. Any other ballot cancels one of the candidate's, and an arc joins the pair. If some party has more than half, it can't all be cancelled, so it's who's left standing. A second pass checks.

Ballots

Order they arrive in

ballots read— candidate— count— pairs cancelled— memory used2 numbers
recount: candidate's votes— needed for a majority— verdict—

The whole algorithm

candidate = none, count = 0for each ballot x: if count == 0: candidate = x, count = 1 elif x == candidate: count += 1 else: count -= 1 // a pair cancelspass 2: count candidate's ballotsmajority only if that's > n / 2

The true totals (never kept)

Each arc joins a ballot to the one that cancelled it. The count is really a stack of identical tokens, so a newcomer always cancels the most recent survivor, and the arcs nest inside each other without ever crossing. The bars under the line are the count after every ballot.

Click a ballot to change its party · drag across ballots to repaint them · right-click goes the other way · space plays · S steps · F finishes · R counts again · N new ballots · H hides panels

Experiment № 108 · The story

Whoever's Left Standing

Why I picked it

The collection already has two ways to deal with a stream you can't store: HyperLogLog counting distinct visitors and reservoir sampling keeping a fair handful. The majority vote is the third, and the oddest. Robert Boyer and J Strother Moore came up with it around 1980, while they were building a theorem prover, and they used that prover to check a version of it. The algorithm fits in four lines. By their own account the write-up struggled to find a journal and only came out properly in 1991, a decade after their 1981 report, probably because it looked too small to be a result. I wanted to give those four lines a picture, because the idea underneath is so physical. Pair every ballot off against one from a different party and throw both away. A party with more than half of the ballots runs out of opponents before it runs out of ballots.

What I enjoy about it

The arcs. I expected a scribble and got something orderly. The count only ever holds ballots for one party, so you can treat it as a pile of identical tokens: a match goes on top, and a mismatch cancels the top one. Cancelling the most recent survivor means pairs nest like brackets, and the arcs never cross, whatever order the ballots come in. Try Violet first and you get one huge rainbow, as the rest of the field wears violet's lead down from the far end. Try Alternating and every arc shrinks to a stitch. The other thing I enjoy is how badly it fails when it's allowed to. Drop violet's share to 40%, pick Violet first, and the survivor is often a party that came nowhere near winning. Pass one never claims a winner. It names the only party that could have won, and pass two settles it.

Something you might take away

You don't always need to know the score to know who could be winning. Two numbers are enough to rule out every party but one, whatever the order and however many parties there are, and a full tally would need a counter for each. The catch is that it only tells you something if a majority exists, and the algorithm can't tell you whether one does. Last one standing is a claim, and you check it with a recount. That holds outside streams too: a quick method that's only right under some condition still needs a cheap way to test the condition.