Category Archives: voting

A hybrid voting system for scheduling

I was thinking recently about the problem of scheduling a group outing (e.g. for a meal). Using something like Doodle you can all vote on a day, and the day with the most votes wins. It’s basically Approval Voting or, if you allow the “if needs be”, option, range voting.

But this runs into a problem I’ve pointed out with voting on group meals before: If you do it often, you consistently make the same sort of choices over and over again, excluding the same people each time. If the group is mostly fine with Wednesday or Thursdays but has a slight Thursday preference, if I can never do Thursdays then I’m out of luck.

As in the previous lunch post, random ballot solves this: It gives you proportional representation of interests over time.

But while this worked reasonably well for lunch places, it doesn’t work so well for scheduling: Typical scheduling problems have any given person being genuinely indifferent between four or five options. Why force them to express a strict preference for one of those options, especially when it may be that some of those days work much better for some people than others?

So for scheduling it seems like approval voting is in fact very well suited. But is there a system that combines the benefits of both?

There is! It’s in fact an extremely direct hybrid of the two, but weirdly not one I’ve seen before.

  1. Everyone casts a vote as in approval voting. That is, they specify a list of acceptable options.
  2. When tallying, you pick a random voter and restrict the set of possible winners to the ones on their ballot.
  3. Amongst that restricted set, votes are tallied as per normal approval voting, picking the one that the largest number of people approve of.

And that’s all there is to it. It satisfies the proportionality criterion that any voting block will on average get an acceptable answer at least in proportion to the size of the bloc (they may get it much more than that, but that’s intrinsic to the problem: e.g. the set of people who are happy with every answer will get an acceptable answer 100% of the time), while still being broadly majoritarian because of the approval voting component.

You can also add a threshold if you like. Because each person votes for multiple options, doing so is much simpler than in normal random ballot, and much more reasonable, so you could quite easily decide to e.g. exclude any options from the schedule that fewer than half of the people can go to (or even more complicated criterion like e.g. it being at least some fixed fraction of the approval winning outcome). The result is that you only end up excluding people who really can’t make any day that most other people in the group can. Which is fair enough really, though a bit unfortunate.

Is this applicable to non-scheduling problems? I don’t know. It might be! I think it adds a strong centrist bias to random ballot, which can be both good and bad.

The properties of scheduling which matter here are I think:

  • Every voter typically has many acceptable options
  • It’s something done often enough that the randomness tends to balance out
  • It’s something where despite that consensus is probably more important than true proportionality.

It also has the nice property that experimenting with voting systems for scheduling is rather low impact. I’d want to do a more formal analysis of this before proposing it for anything more serious, but I suspect it might still have some nice properties that make it worth considering.

This entry was posted in voting on by .

An untapped family of board game mechanics

Have you noticed how board games are in dire need of electoral reform?

No, wait, seriously. Hear me out. This makes sense.

In most board games, through a series of events, you acquire points (votes), where each point (vote) goes to at most one player, and then at the end the person with the most points (votes) wins outright, regardless of how narrow their margin is.

It’s literally plurality voting, and it leads to a number of the same problems.

One of those problems is that it amplifies small leads quite substantially. e.g. take Scrabble. I play a lot of Scrabble because it’s more or less our family game. I also win a lot of Scrabble. Sometimes comfortably if I managed to get that second bingo out, but often by fairly small margins – 10-20 points in a 300-400 point game is not a large victory, but with plurality victory that doesn’t matter, it’s still a victory.

It also creates spoiler effects, where you have players who obviously can’t win but still participate in pile-ons to people in the lead. e.g. if you’ve ever played a Steve Jackson game (Munchkin, Illuminati, etc) you’ve probably seen this in action – “They’re about to win! Get them!”.

Certainly not all games match this description: e.g. you get a lot of games where rather than scoring points there is a defined victory condition – war games where you take a rather different view of politics and must kill all your opponents (e.g. Risk), or hidden mission games where you must achieve some specific goal unknown to the others (e.g. Chrononauts). I’ll consider that sort of game out of scope here.

Some games you play until someone has hit some defined score and then they immediately win (e.g. Love Letter). This is a bit like majoritarian vote systems (where you only win if you get more than 50% of the vote), but not really.

So the analogy isn’t perfect, but I think it has enough merit for the games it applies to to be worth exploring how things can be different. If nothing else it might be an untapped source of interesting game mechanics.

Even within the scope of games which look like elections if you squint at them hard enough there’s some variation.

For example, I’m aware of at least one game which uses random ballot: Killer Bunnies and the Quest for the Magic Carrot.

In this game you acquire carrots (votes), then at the end of the game a winning carrot (vote) is drawn at random and the person who owns that carrot (had that vote cast for them) wins (is elected). So if you own 60% of the carrots then you have a 60% chance of winning.

Given that I’m generally really rather keen on random ballot it may come as some surprise that I think this is a terrible game mechanic.

The problem with random ballot in this context is both that Random Ballot isn’t great for presidential style single winner elections, and also that in the context of a game players (politicians) matter more than carrots (voters). Voters have a right to be well represented in the decision of which politician eats them, carrots don’t.

If the game were very short it would probably be OK, but getting to the end of a long game and then having victory be decided by quite such a large amount of luck is rather frustrating. I think there are ways to fix it and make random ballot a fun game mechanism, but I also worry that it’s a bit too close to existing scoring mechanisms and where it produces different answers players will mostly find it frustrating.

So instead I’d like to look at how you could use an entirely different class of electoral system to produce this effect: Condorcet systems.

The idea of a Condorcet system is that instead of focusing on point scoring you focus on pairwise victories: Which player beats which other player. If there is a player who beats every other player in a one on one victory, they are the Condorcet winner and win outright.

Depending on who you ask, electing the Condorcet winner is either a terrible or a great idea (my personal biases are “It depends what you’re electing them for but all else being equal the Condorcet winner is probably a pretty good choice”), but that doesn’t actually matter here, because the question is not whether it’s a great election system but whether it leads to an interesting game design!

And I think it does.

When there is no Condorcet winner interesting things happen where you get rock-paper-scissors like events where the majority prefers A to B, B to C and C to A. These are called Condorcet cycles. In this case you need some sort of alternate rule to decide which player is most like the Condorcet winner (this can also happen if you get candidates who are tied because an equal number of people prefer each to the other, but you can avoid this possibility by just having an odd number of voters).

There are a wide variety of systems for deciding who the “most Condorcet” candidate is when there is no true Condorcet winner. These range from the very simple to the very complicated, but there’s a particularly simple Condorcet system that I think is very suitable for game design.

It works as follows: You pick an incumbent (usually at random). Then every other candidate (player) challenges the incumbent in some order (usually random). If the majority strictly prefers them (they beat them according to some as of yet unspecified mechanism) then the incumbent drops out and the challenger becomes the incumbent, else the challenger drops out. Once all but one candidate has dropped out, the remaining incumbent is the winner.

There are a number of free variables in how you could turn this into a game mechanic:

  1. Who gets to be starting incumbent?
  2. What determines who wins in a head on head fight?
  3. What order do people challenge in?
  4. Who wins ties?

However you pick these free variables though, I think it’s most interesting if you do this in such a way that allows the possibility of Condorcet cycles (if you don’t it’s really just another scoring system). In order to do this you need something that looks like at least three voters.

The easiest way to do this is might be something like the following:

The game consists of resource acquisition in some manner. You have three resources and treat each as a vote. Each resource is claimed by whichever of the two players owns strictly more of it. If either player claims more resources than the other, that player wins. Otherwise, apply some tie breaking procedure.

Starting from that concept, you can elaborate itinto a full game. The following is a toy game that might work well (but probably would need significant refining through play testing) based this. It’s called “The King is Dead!”

The king is on his death bed and has no natural heir. He has named one, but the nobles are competing to change his mind, and regardless of who he chooses they might not last long enough to take the throne.

There are a few key nobles who might win, but their chances of victory are slim without the support of the two key factions of the kingdom: The peasants, and the clergy. The nobles must use their influence at court to curry favour with these two factions, but be careful! If you use all your influence outside the court, there may be no-one left to support you when you fall afoul of court intrigue.

Game setup:

  • An heir is picked at random from the players.
  • Three cards per player are drawn from a larger deck and are shuffled together to form the issue deck.
  • Each player is given twelve influence tokens.

Each issue card has a number of clergy points and a number of peasant points on it. It may also have a crown on it

The game is played in rounds which proceed as follows:

  1. A card from the top of the deck is revealed.
  2. The card is now auctioned off with an English auction: The heir bids zero on the card and then play proceeds clockwise, with each player either placing a higher bid or dropping out. Once everyone has dropped out except for the last bidder, that bidder gets that card, places it in front of them, and puts their bid in the centre temporarily.
  3. If the card had a crown on it, the person who won it now becomes heir.
  4. The bid is now redistributed amongst the players: One token at a time, starting from the heir (the new one if it changed places!) and proceeding clockwise until all the tokens have been redistributed

This process completes until the deck is out of cards. The king then dies, and a swift but bloody war of succession occurs.

Starting to the left of the current heir and proceeding clockwise, each player (not counting the player who was heir when the king died) gets the opportunity to challenge the current heir.

A challenge pits the two players against each other as follows:

Each player accrues a victory on each of three scores: Their total support from the peasantry, their total support from the clergy, and their total influence. If one player has a higher score than the other on each of these, they get a victory.

If one of the two has more victories than the other, that player wins. If they are tied, the current heir wins.

Whichever player won is now the new heir. If there are any more challengers left, the next challenger steps up and challenges the heir, otherwise they win and are crowned. Long live the king!

This game definitely needs play-testing and will almost certainly have a number of problems with it, but I think it’s an interesting corner of game design that I haven’t seen anything much like before.

The thing I like about it is also that it creates a much more interesting victory dynamic in most cases: In the case where someone wins really decisively then they still cream everybody else, but the back and forth between the three resources more or less guarantees that nobody will be a Condorcet winner unless everyone else played really badly – the more they spent to get that faction support, the more influence they gave to other players that they could use to claim some other support. This makes things tense right up until the end game.

More generally, I think there’s a rich seam of game design ideas in electoral theory that hasn’t been tapped much. There’s a theorem that says that almost any voting system admits tactical voting. For electoral system design this is a real pain, because systems which encourage tactical voting have a number of problems, but for game design it’s perfect because it means that there’s this giant body of well studied and powerful mechanics that are full of opportunities for tactical play.

(Like my writing? Want to see more of it? Support me on Patreon! Patreon subscribers saw this posts months ago, because all my drafts get posted there when they’re ready)

This entry was posted in Games, voting on by .

How likely are Condorcet cycles in supermajorities?

You can use a supermajority rule to eliminate the possibility of Condorcet cycles. e.g. if you require a \(\frac{2}{3}\) supermajority there is no possibility of creating a Condorcet triple with the majority strictly preferring A to B, B to C and C to A.

Unfortunately that’s only the three candidate case. If you consider the \(N\) candidate case you need a supermajority of \(1 – \frac{1}{N}\) to achieve the same result (just consider the \(N\) cyclic permutations of the candidates and you get a generalisation of the Condorcet example where every candidate beats every other this fraction of the time).

So there is no supermajority rule that in general prevents Condorcet cycles.

In “The Probability of Condorcet Cycles and Super Majority Rules”, Yves Balasko and Hervé Crès show the following asymptotic result: If you consider a profile of votes chosen uniformly at random on the set \(\{p \in \mathbb{R}^{n!}: p \geq 0, \sum p = 1\}\), then the probability of there being a Condorcet cycle in that set with a supermajority of \(\tau\) is bounded above by \(n! \left( \frac{1 –  \tau}{0.4714}\right)^{n!}\).

From this they conclude that the critical threshold for a supermajority is around 54%, because this goes very rapidly towards zero.  e.g. with the 54% threshold the probability of a cycle in \(7\) candidates is \(< 10^{-52}\), which we can probably treat as adequately safe.

They also say “Within our setup, this makes the Condorcet cycles a theoretical curiosity without any practical bearing for super majority rules that exceed the threshold value of 53%”.

Unfortunately this conclusion is totally wrong (the bound is probably correct, but I’ll confess to not having fully followed the rather complicated calculations), because it neglects the fact that \(n\) can be small as well as large.

e.g. for \(n=3\), their upper bound isn’t even smaller than \(1\). It’s about 5.18. It then grows before dropping – at 4 it’s 13.34, at 5 it’s 6.36, and then finally at 6 is becomes small and is 1.6e-5.

So in order to find what the appropriate super majority threshold is for making the probability of a cycle adequately small (say under 1 in 1000) we need to manually check the cases of 3, 4 and 5.

Fortunately it’s easy to do that by direct simulation, so I wrote some code, and the 54% threshold is indeed the wrong one and fails to handle the three candidate case well.

About 6% of elections on three candidates have majority cycles, and of those about a quarter would still have a cycle with a 54% supermajority. The 99.9% mark is a 59% supermajority: Above that, fewer than one in a thousand profiles have a cycle. For four candidates, the 99.9% mark is 57%.

If we take the higher requirement of one in a million (which is well into the region where my simulation does not have sufficient fidelity to actually give a good answer) the thresholds become 64% and 61%.

That leaves the n=5 case. My simulation is a bit too inefficient (it has an O(n!) componetn in it) to run in reasonable time for n=5, but fortunately it doesn’t have to. The upper bound for the supermajorities the lower n required is now adequately low: For a 59% supermajority it’s 6e-6, for a 60% supermajority it’s 3e-7, so goes below the one in a million mark too.

So, in conclusion, if you require a 60% supermajority, and not just a 54% one, you are probably free of Condorcet cycles. If you go for the full 2/3 supermajority (which probably makes a lot of sense for serious cases) you’re almost certainly safe – you’re provably safe at n=3 and, provably have vanishingly low probability for n >= 5, and for n=4 a simulation says there’s well under a one in a million chance of getting a cycle.

Unless of course your population is drawn from a model that isn’t well represented by a uniform distribution (i.e. all populations ever) or the candidates are adversarially chosen to manipulate the electorate (i.e. all candidates ever). In those edge cases you might still have some problems.

This entry was posted in voting on by .

Adding a threshold to random ballot

Content warning: Democracy.

I make no secret of the fact that I like random ballot.

One of the first things almost everyone who doesn’t instantly reject the idea suggests is that they’d be more comfortable with random ballot if it had a threshold to keep the really fringe people out – say anyone who would lose their deposit under the current UK system because  they have fewer than 5% of the vote is disqualified and can’t elected. The idea being that although it’s a low-probability event, you’re going to still get a sizable minority of MPs elected with less than 5% of the vote (about \(\frac{1}{20}\) of them in fact, so in the UK around 32.5), which is pretty unfair to those constituents (in a way that apparently getting elected with only 25% of the vote is not).

My major problems with this proposal are:

  1. It distorts the proportionality properties of random ballot
  2. It disenfranchises anyone who votes for someone who failed to reach threshold – which may be a lot more than that fraction of the population if there are multiple minority candidates!
  3. It takes a tactics free voting system and reintroduces something that looks like a pretty classic spoiler vote

How much I care about each of these points varies:

  1. I don’t really have a problem with this as long as the threshold is low enough (and 5% is) – proportional representation is probably better when you restrict the candidates to the subset of the possible representatives that aren’t universally reviled.
  2. This is bad and to be avoided to the greatest degree possible.
  3. Eh, if I’m going to insist on tactics free voting my options are pretty limited. It would be nice to reduce the amount of tactical voting though.

I think I’ve figured out a patch which fixes the second and mitigates the third. The result is a curious hybrid system that is somewhere between random ballot, approval voting and instant runoff voting, but I actually think it works pretty well and, complexity aside, might be strictly better than random ballot for a lot of use cases.

The key idea is this: We make it a ranked system, where your ranked vote is interpreted to mean that you wish your vote to be cast for the highest ranked candidate on your ballot that has not been disqualified for failing to clear the threshold. Voters neither can nor should rank every candidate – the only candidates that appear on their ballots should be ones they’d be happy to vote for.

We then arrange a set of qualified candidates so that every candidate who qualifies has at least a threshold worth of votes cast for them under the above interpretation.

The system works as follows.

Once the ballots have been counted, the threshold is calculated as a number of ballots. This is now fixed and does not get updated throughout the process.

Each candidate is marked as either “uncertain”, “disqualified”, or “eligible”. Every candidate starts as uncertain. Each ballot is marked as either “available”, “withdrawn” or cast”. Every ballot starts as available.

A ballot approves a candidate if the candidate appears on the vote’s ballot. A ballot prefers a candidate if it approves them and every candidate it ranks more highly is disqualified.

Ballot counting now proceeds in a number of rounds until there are no more available votes. A round proceeds as follows:

  1. Every uncertain candidate which is preferred by more than a threshold worth of ballots is marked as eligible.
  2. Every available ballot whose preferred candidate is eligible is marked as cast. This includes candidates marked eligible in previous rounds.
  3. Every uncertain candidate that is approved by fewer than a threshold worth of available ballots is marked as disqualified
  4. If no uncertain candidate has changed its state this round (either by being marked eligible or disqualified), the candidate with the fewest approvals is marked as disqualified. In the event of a tie, the candidate that is preferred by fewer available votes drops out. If that is still a tie, break it arbitrarily.
  5. Every available ballot whose approved candidates have all been disqualified is marked as withdrawn.

At the end, we have a set of eligible candidates and every vote is either cast or withdrawn after they could not collaborate with enough other people to get a candidate they liked elected. Random ballot is now performed with the cast ballots, with the preferred candidate of the selected ballot being elected.

Example

Let’s see how this might play out in practice. We’ll use an unrealistically high threshold of 40% so that we can see how it works properly without requiring a large number of candidates.

Suppose we’ve got four candidates: Alex, Charlie, Kim and Pat. The votes go as follows:

  • 40% vote Alex
  • 25% vote Charlie
  • 20% vote Kim, Charlie
  • 10% vote Charlie, Kim
  • 4% vote Pat, Alex
  • 1% vote Pat

The vote proceeds as follows:

  1. Alex is marked as elected and the 40% go to them.
  2. Pat does not have enough approvals to meet the threshold, so drops out.
  3. The 4% Pat, Alex ballots are now cast for Alex who now has 44%
  4. The 1% Pat voters are marked as withdrawn
  5. Both Kim and Charlie have enough approvals to make the threshold, but neither meets the threshold, so the one with the lowest approvals (which is Kim at 30% vs Charlie’s 55%) drops out.
  6. All remaining available votes prefer Charlie, so Charlie is marked as eligible with 55% of the vote.

So at the end, Alex has 44% of the vote, Charlie has 55%, and the remaining 1% of the votes are wasted. This means that Charlie wins with probability \(\frac{55}{99} = \frac{5}{9} \approx 56%\).

Reasoning

The core idea is to select a set of candidates that you can just use normal random ballot on and have everyone automatically clear the threshold. The election procedure is essentially a greedy algorithm to achieve that.

The motivation behind using approval voting for the selection stage is that immediately dropping out all candidates who aren’t approved by at least of threshold is always the correct thing to do: They can no longer get elected (because there aren’t enough votes that could be cast for them to clear the threshold), so having them stay in the game just leaves them as potential spoilers.

Once you have that, using approval voting to decide dropouts is also the obvious thing to do: The candidate that drops out is the one most likely to drop out later anyway. Approval voting is also a much more stable metric to use for deciding dropouts than preferences.

A simpler version of this system might be to simply mark everyone who gets at least a threshold worth of approvals as eligible. The major reasons I don’t like that is that you can get candidates through who have fewer than a threshold of votes cast for them (which isn’t awful but feels non-ideal) and that it brings in additional tactical elements about whether or not to approve candidates (because if you don’t their votes might go to you).

Evaluation

(Note: This is an informal evaluation. I haven’t actually done simulations to verify this yet)

I think this works pretty well. It mostly works out like random ballot with quality control on which candidates actually run.

The only people who are disenfranchised entirely by this system are the people who so hate any candidate that at least the critical threshold of the voting population can tolerate that they can’t bring themselves to vote for that candidate. Note that this is a much smaller set of people than those who merely prefer every such candidate to any mainstream one. I… probably should still have a problem with disenfranchising these people, but I can’t really bring myself to right now. So I’m calling that a win for point 2.

 

So what does tactical voting look like under this system?

I think it’s pretty mild.

First off, there is never any point in ranking candidates in an order other than your true preferences. The only time that your rank order matters between two candidates is when both of them are eligible, so the usual argument for random ballot holds. So the only question of tactics is who to include on your ballot.

There’s also absolutely no reason to ever omit your favourite candidate from your ballot.

If you’re comfortable that your favourite candidate will be eligible, you can stop there. In general as soon as you’ve ranked a candidate who you’re sure will make threshold there’s no point in going further.

In particular this means that everyone who would under random ballot cast their vote for a candidate who makes it past the threshold of first choices doesn’t need to worry about the rest of the system and can just comfortably cast a single vote as per normal. If every candidate clears the threshold then this system then just reduces to random ballot.

Tactics then consist of essentially jockeying a bit to try to get minority candidates you like who haven’t quite cleared the threshold to get enough votes so that they can be eligible.

There’s no point in omitting a candidate from your ballot when you’re certain they’re going to make threshold on first choice votes before anything else of import has happened. Once a candidate has been made eligible their presence or absence on your ballot has no impact one way or the other. So generally tactical voters will pick a backstop candidate who they’re sure is threshold clearing as their preferred mainstream option if all else fails.

think the same mostly applies for anyone you’re morally certain is going to clear the threshold before anyone you prefer to them. This isn’t perfectly true – it may be in your interests to keep them in the running for longer so you get to keep counting their approvals for candidates you like to stop said candidates dropping out. This is a sufficiently hard to predict move that I don’t expect it to have much practical impact.

So the only real question of tactics is which other fringe candidates you approve. Basically what you want to do is ensure that your lower ranked preferences don’t end up competing with your higher ranked preferences for who gets disqualified.

So, in other words, the easiest tactical vote consists of casting your ballot as follows:

  1. Always rank your favourite candidate first.
  2. Repeatedly add your favourite candidate of the candidates who are “significantly more mainstream” than the ones you’ve added so far.
  3. Keep adding candidates as per above until you’ve added one you are certain will meet threshold.

I would be surprised if many voters bothered to rank more than three candidates – their actual favourite, their second choice who might make threshold, and the mainstreamish candidate (for values of mainstream that mean “have the support of at least 5% of the population”) who they like most.

So essentially the tactical voting creates a bias towards voting for making your subsequent preferences a bit more mainstream than you otherwise would.

But that’s what the system is intended to do anyway. So if that’s genuinely all the tactical bias there is, if anything it’s a feature.

Assuming I’ve not missed some critical flaw under tactical voting, all told I think this is a pretty neat system which nicely balances the proportionality properties of random ballot with a mild mainstream bias.

Applications

This should be applicable most places where random ballot is, assuming the complexity cost is not prohibitive (e.g. you probably don’t want to use this for deciding where to go for lunch).

Where the additional complexity isn’t a problem (e.g. because vote tallying is computerised anyway) I think I might actually just flat out prefer this system to random ballot – it’s a good way to curb some of its variance while still retaining most of its desirable properties.

This is particularly true for cases where random ballot is not currently entirely suitable (because e.g. the stakes are very high and/or the number of repetitions of the vote are quite low) – if you were to push the threshold up to somewhere more in the region of 40% it might even become suitable for more presidential style single winner elections (or, at least, not obviously less suitable than the current systems).

It might also be an interesting procedure for other allocation problems. There’s nothing intrinsic to random ballot for most of it – it’s just a question of how to divide up numbers so that they add up to 100% (in the event that nobody withdraws their vote) and each meet a threshold. You could just as easily use it for e.g. deciding how to distribute money between a number of projects or charities.

This entry was posted in voting on by .

Rigging elections with integer linear programming

No, this isn’t a post about politics, sorry, it’s just a post about voting theory.

As you might have noticed (and if not, this is the post announcing it), I have a book out! It’s called Voting by Example and is about the complexities of voting and why different voting systems might be interesting. You should go buy it.

But this isn’t just an ad post for the book, it’s about something else: How I came up with the examples in this book.

At its core is the following example. We have a student election where there are four candidates are running for class president. Each student casts a vote ranking the four candidates in order of most to least preferred.

The votes are as follows:

  • 32% of students voted Alex, Kim, Charlie, Pat
  • 27% of students voted Charlie, Pat, Kim, Alex
  • 25% of students voted Pat, Charlie, Kim, Alex
  • 16% of students voted Kim, Pat, Alex, Charlie

The point of this example is that each of four different ranked voting systems give a different answer:

It’s also constructed to have a minimal number of voting blocs, though it’s minimum amongst a slightly more specific set of elections than just those satisfying the above conditions.

Roughly what this means is:

  • Alex has the most first choice votes
  • When compared pairwise with any other candidate, the majority prefer Charlie
  • Pat wins a complicated procedure where people iteratively drop out depending on who is the favourite of the remaining candidates amongst the fewest voters
  • If you give people a score of 3 for each voter who ranks them first, two for each who ranks them second, and one for each who ranks them third, then Kim has the highest score.

If you want to know more than that I recommend the relevant Wikipedia links above, which are all very approachable.

The significance of this is that each of these is a popular (either in practice or amongst electoral theorists) way of saying who should be the winner. So the situation ends up being rather complex to decide.

But this isn’t a post about the significance. This is a post about how I constructed the example.

Historically I’ve generally created example elections with Hypothesis or a similar approach – randomly fuzzing until you get a result you want – but that wasn’t really going to work very well here due to the rather complicated set of constraints that are hard to satisfy by accident.

So I instead turned to my old friend, integer linear programming.

The idea of integer linear programming (ILP) is that we have a number of variables which are forced to take integer values. We can then impose linear constraints between them, and give a linear objective function to optimise for. For example we might have three variables \(v_1, v_2, v_3\) and the following constraints:

  • \(v_1, v_2, v_3 \geq 0\)
  • \(v_1 + 2 v_2 + 3 v_3 \leq 5\)

And then try to maximise \(v_1 + 2 v_2 + 4 v_3\).

Given a problem like this we can feed it to an ILP solver and it will spit out a solution. If we do that, it will tell us that an optimal solution for this problem is \(v_1 = 2, v_2 = 0, v_3 = 1\).

A lot of problems can be nicely turned into ILP problems, and there are some fairly good open source ILP solvers, so it’s often a nice way to solve complex combinatorial problems.

So how do we turn our election rigging problem into an integer linear program?

The key idea is this: 4! isn’t very large. It’s only 24. 24 is tiny from an ILP point of view.

This means that there’s no problem with creating a variable for each of the possible votes that someone could cast, representing the number of people who cast that vote. That is, we create integer variables \(v_p\) indexed by permutations with the constraints:

  • \(\sum v_p = 100\)
  • \(v_p \geq 0\)

Then the value of e.g. \(v_{(0, 1, 2, 3)}\) is the number of people who cast the exact vote \((0, 1, 2, 3)\) (or, by name, Alex,, Charlie, Pat, Kim).

We then use a trick to get nicer examples, which is that we try to minimise the number of non-zero votes. The idea is to create variables which, when minimised, just look like markers that say whether a vote is non-zero or not.

So we create supplementary 0/1 valued integer variables \(u_p\) with the constraints that \(v_p \leq 100 u_p\), and set the objective to minimise \(\sum u_p\). Then \(u_p\) will be set to \(0\) wherever it can be, and the only places where it can’t are where \(v_p\) is non-zero. Thus this minimises the number of voting blocs.

So that’s how we create our basic ILP problem, but right now it will just stick 100 votes on some arbitrary possible ballot. How do we then express the voting conditions?

Well, lets start with the plurality and Borda scores. These are pretty easy, because they constitute just calculating a score for each candidate for each permutation and adding up the scores. This means that the scores are just a linear function of the variables, which is exactly what an ILP is built on.

Victory is then just a simple matter of one candidate’s score exceeding another. You need to set some epsilon for the gap (linear programming can’t express \(<\), only \(\leq\)), but that’s OK – the scores are just integers, so we can just insist on a gap of \(1\).

The following code captures all of the above using Pulp, which is a very pleasant to use Python interface to a variety of ILP solvers:

The idea is that the additive_scores parameter takes a list of scoring functions and a partial list of winners given those functions and returns an election producing those orders.

So if we run this asking for the plurality winners to be (0, 1, 2, 3) and the Borda winners to be (3, 2, 1, 0) we get the following:

>>> build_election(4, 100, [
    (lambda p, c: int(p[0] == c), (0, 1, 2, 3)),
    (lambda p, c: 3 - p.index(c), (3, 2, 1, 0))])
[((0, 3, 1, 2), 35), ((1, 2, 3, 0), 34), ((2, 3, 0, 1), 31)]

So this is already looking quite close to our starting example.

Creating a Condorcet winner is similarly easy: Whether the majority prefers a candidate to another is again just an additive score. So we just need to add the requisite \(N\) constraint that our desired Condorcet candidate wins.

if condorcet_winner is not None:
    victories = {
        (i, j): lpsum(
            v for p, v in variables if p.index(i) > p.index(j) )
            for i in candidates
            for j in candidates
    }
    for c in candidates:
        if c != condorcet_winner:
            problem.addConstraint( victories[(condorcet_winner, c)] >=
                victories[(c, condorcet_winner)] + 1
            )

If we run this to force the Condorcet winner to be \(1\) we now get the following:

>>> build_election(4, 100, [
    (lambda p, c: int(p[0] == c), (0, 1, 2, 3)),
    (lambda p, c: 3 - p.index(c), (3, 2, 1, 0))],
    condorcet_winner=1,
)
[((0, 3, 1, 2), 28),
 ((1, 2, 3, 0), 27),
 ((2, 1, 3, 0), 24),
 ((3, 2, 0, 1), 21)]

This is pretty close to the desired result. We just need to figure out how to set the IRV winner.

This is a bit more fiddly because IRV isn’t a simple additive procedure, so we can’t simply set up scores for who wins it.

But where it is a simple additive procedure is to determine who drops out given who has already dropped out, because that’s simply a matter of calculating a modified plurality score with some of the candidates ignored.

So what we can do is specify the exact dropout order: This means we know who has dropped out at any point, so we can calculate the scores for who should drop out next and add the appropriate constraints.

The following code achieves this:

    if irv_dropout_order is not None:
        remaining_candidates = set(candidates)
        for i in irv_dropout_order:
            if len(remaining_candidates) <= 1:
                break
            assert i in remaining_candidates
            allocations = {j: [] for j in remaining_candidates}
            for p, v in variables:
                for c in p:
                    if c in remaining_candidates:
                        allocations[c].append(v)
                        break
            loser_allocations = sum(allocations.pop(i))
            remaining_candidates.remove(i)
            for vs in allocations.values():
                problem.addConstraint(loser_allocations + 1 <= sum(vs))

And running this we get the following:

>>> build_election(4, 100, [
    (lambda p, c: int(p[0] == c), (0, 1, 2, 3)),
    (lambda p, c: 3 - p.index(c), (3, 2, 1, 0))
], condorcet_winner=1, irv_dropout_order=(3, 1, 0, 2))
[((0, 3, 1, 2), 31),
 ((1, 2, 3, 0), 27),
 ((2, 1, 3, 0), 25),
 ((3, 2, 0, 1), 17)]

This isn’t quite the same example in the book (the first bloc has one fewer vote which the last bloc got in this), because the book example had a bit more code for optimizing it into a canonical form, but that code isn’t very interesting so we’ll skip it.

Here’s the full code:

I’m constantly surprised how nice integer linear programming ends up being for constructing examples. I knew I could do the Borda and plurality scores – that’s in fact the example that motivated me trying this out at all – but although I find it obvious in retrospect that you can also fix the Condorcet winner it definitely wasn’t a priori. The fact that it’s easy to also calculate the IRV dropout order was genuinely surprising.

This is also a nice example of how much fun small n programming can be. This isn’t just an O(n!) solution – it generates a problem of size O(n!) and then feeds it to a solver for an NP-hard problem! in principle that should be catastrophic. In practice, n is 4, so who cares? (n=4 is about the limit for this too – it just about works for n=5, and for n=6 it doesn’t really).

I also find it somewhat surprising how much freedom there is to get different results from different voting systems. I was motivated to do some of this by The ultimate of chaos resulting from weighted voting systems, so I knew there was a fair bit of freedom, but I was somewhat expecting that to be a pathology of weighted voting systems, so I’m still a little surprised. I guess there’s just quite a lot of room to play around with in a 24-dimensional simplex.

Which brings me to my final point: When you’re trying to understand what is possible in a domain, this sort of example generation focused programming is very useful for exploring the limits of the possible and building your intuition. I feel like this isn’t a thing people do enough, and I think we should all do more of it.

I also think you should buy my book.

(Or support my writing on Patreon)

This entry was posted in programming, Python, voting on by .