Author Archives: david

A small tactical voting example

Another “small election exhibiting some obscure feature” post. I hope you’re not bored of these yet (but if you are I recommend you just don’t read them).

Consider the following election:

  • 1, 2, 3, 4
  • 2, 1, 4, 3
  • 3, 4, 1, 2

The Kemeny-Young winner for this election is 1, as that is the unique Condorcet winner.

But if the second voter wants to vote tactically and changes their vote from 2, 1, 4, 3 to 2, 3, 4, 1 so the votes are now as follows:

  • 1, 2, 3, 4
  • 2, 3, 4, 1
  • 3, 4, 1, 2

There is no longer a Condorcet winner. The majority preferences go 1 > 2 > 3 > 4 > 1 so there is a cycle.

However there is still an unambiguous Kemeny-Young winner (you’ll have to trust me on this one or work it out yourself. It’s a little hard to show the working). The new Kemeny-Young winner is 2, which our tactical voter strictly prefers to 1, so they should make that change.

The Gibbard-Sattherthwaite theorem guarantees that an election like this must exist, but I was pleasantly surprised at how simple the example was.

This entry was posted in Uncategorized on by .

Should you join Google?

I’ve had a few people who were thinking of applying to Google ask me if the fact that I’m leaving is a sign that they shouldn’t.

There’s a short answer is a long answer.

The short answer is: No, you should absolutely still apply.

The long answer is that you should absolutely still apply, but I would offer you the following advice:

  • Understand that the exciting thing you’re really keen to find out how they manage to do is probably going to be pretty disappointing when you find out and if that’s your primary reason for joining, maybe don’t.
  • Before you accept an offer, make sure you know the team you’ll be joining and have realistic expectations as to what working on it is likely to be like.
  • Understand the trade-offs you’re making by working for Google and make sure you are prepared to accept them.

Honestly I think this is good advice wherever you’re applying, but it’s both particularly important to do at Google and somehow feels particularly hard to do when you’re applying there.

If you have specific questions about joining Google and why I left feel free to email me, but bear in mind I am of course under a confidentiality agreement and once I no longer work there there won’t be anyone I can ask whether I can tell you something, so I’ll have to be a bit careful about what I say to you. You may well be better off finding someone who still works there and asking them to have a frank discussion with you.

This entry was posted in Uncategorized on by .

Some more small elections

A follow on from the last post with some more small elections.

Here are some small examples of elections demonstrating some preferential voting systems (two popular and one a little obscure) are not Condorcet. I can easily add more if you want me to add your favourite preferential voting system to this, but there seem to be a sparsity of interesting non Condorcet preferential voting systems.

Each of these are minimal amongst examples I’ve been able to find. Where minimal is taken under the lexicographic order of number of candidates then number of votes. (i.e. if one election has fewer candidates it’s regarded as smaller. If they have the same number of candidates the one with fewer voters is smaller). I’ve no idea if they’re minimal in absolute terms, but I’ve made a reasonable attempt to find smaller ones and I think it likely that they are. In particular they’re all locally minimal in the sense that they will no longer demonstrate the desired behaviour if you drop a candidate or drop fewer than two votes from them, but it’s possible some smaller subset does demonstrate the desired behaviour.

Borda count

  • 2, 3, 1
  • 2, 3, 1
  • 2, 3, 1
  • 3, 1, 2
  • 3, 1, 2

The Borda winner is 3 but the Condorcet winner is 2.

IRV and Contingent vote

  • 1, 2, 3
  • 1, 2, 3
  • 2, 1, 3
  • 3, 2, 1
  • 3, 2, 1

The IRV winner is 1 but the Condorcet winner is 2. The contingent vote winner for this is also 1 (unsurprisingly because the two will always agree when there are only three candidates).

Coombs

Coombs is basically the reverse of IRV: At each step you remove the candidate who the most voters have ranked last of the remaining candidates and rerun until you only have one candidate left.

  • 1, 3, 2
  • 2, 1, 3
  • 2, 1, 3
  • 2, 3, 1
  • 2, 3, 1
  • 3, 1, 2
  • 3, 1, 2

The Coombs winner is 3 but the Condorcet winner is 2.

Borda-majority judgment

This is Majority Judgement applied to the Borda scores. i.e. a preferential ranking is implicitly assigning a grade of n to its highest candidate, n – 1 to its second highest, etc. This isn’t my invention – it’s from the standard text on the subject – but I’m not aware of this being a system that anyone actually uses.

  • 1, 2, 3
  • 1, 2, 3
  • 2, 1, 3
  • 2, 1, 3
  • 2, 3, 1
  • 3, 1, 2
  • 3, 1, 2

The Borda-majority judgment winner is 2 but the Condorcet winner is 1.

This entry was posted in Uncategorized on by .

An interesting hypothetical election

Here is an election:

  • 1, 4, 2, 3, 5
  • 2, 3, 5, 4, 1
  • 2, 5, 4, 1, 3
  • 3, 2, 5, 1, 4
  • 3, 5, 2, 1, 4
  • 3, 5, 2, 4, 1
  • 4, 1, 3, 2, 5
  • 4, 2, 5, 3, 1
  • 4, 3, 2, 5, 1
  • 5, 4, 1, 2, 3
  • 5, 4, 2, 1, 3

Where each is a vote cast for one of 5 candidates, ordered from favourite to least favourite.

Why is it interesting? Because it produces different answers depending on which of three popular Condorcet voting systems you use.

The Smith set for this election is 2, 3, 4, 5. The Kemeny young winner is 4, the Schulze method winner is 2, and the ranked pairs winner is 5.

More in this vein possibly to follow.

This entry was posted in Uncategorized, voting on by .

A patch for quadratic voting

An idea that always appeals to me is the idea of quadratic vote buying. You have some currency system associated with a vote (it doesn’t have to be real money) and you can buy as many votes as you want. However the cost of buying \(n\) votes is proportional to \(n^2\). So buying 2 votes costs 4 times as many as buying one vote, etc. The cost of your vote is then distributed evenly amongst all the other voters.

This has the nice property of letting you put more of your credibility behind things that are important to you, and then redistributes that credibility at the end.

In practice there are a lot of social problems with this and I’m not at all sure it’s a good idea, but that doesn’t stop it having a lot of appeal for me. People who are aware of my tastes will probably find this spectacularly unsurprising.

But one problem I was thinking about earlier is as follows: Suppose you really really don’t want something to pass. So you buy a lot of votes to prevent it from passing, spending a lot of your bank balance, and it turns out it didn’t have much chance of passing and you comfortably overshoot the mark. It seems a little unfair that you’ve wasted all that money.

It occurred to me that you can solve this with a sort of Vickrey auction. You run the vote as normal, but in the end you only pay enough to buy out the next best option. e.g. in the two outcome case if the vote is won 100 to 80, then the winning voters only pay for 80 votes and the losing voters don’t pay anything.

But how do you actually do this? Those votes aren’t just single bids – they’re the sum of a number of bids from a number of individuals. How do you choose which voter pays what?

I’d argue that the most equitable arrangement of votes is the one that minimizes the total amount spent. This seems both fairest and makes it safer to bid high values to achieve your desired result. I haven’t checked the details too carefully, but I’m pretty sure the correct way to do this is to find the smallest threshold \(t\) such that everyone who bought more than \(t\) votes only buys \(t\) votes and everyone who bought under buys their maximum amount while still achieving the desired number of votes.

You can find this optimal threshold as follows: Iterate over the votes from smallest to largest. Calculate the threshold you would have if every smaller vote were to pay full price. This is the amount of required votes remaining divided by the number of voters remaining. If this threshold is smaller than the current vote, congratulations you’ve found the threshold. If it’s larger than the current vote, deduct the current vote from the amount remaining and keep going.

Here is some python code to implement this:

Note that this requires arbitrary fractional currencies for anyone who is left in at the end. If you’re using a currency that doesn’t support this (e.g. real money) then this is easy to solve: You have n people left paying and are required to pay an amount A as an integer multiple of the smallest currency unit (it’s an integer because the total we’re originally setting out to achieve is an integer, and at each stage we removed a set of votes all of which were themselves integers). We can write this as \(A = pm + r\) with \(r < n\). Then every one in the remainder set pays \(p\) and additionally \(r\) of them selected at random pay an additional one. This is still within their willingness to pay band because they were each willing to pay an integer amount greater than \(\frac{A}{n}\).

I have not checked any sort of voting or game theory for this idea and as such it may be a terrible one, but intuitively it seems to behave nicely.

Generalising to more than two alternatives

It’s interesting to consider how this would work with more than two options. If your vote is just to pick a single candidate then there’s no issue at all – it works exactly as designed – but one thing that appeals to me in quadratic voting is that you can use it to construct a sort of range voting. If you prefer A to B to C you might as well stick a few secondary votes on B because they’re a lot cheaper than piling more votes onto A. However in this system that has some unfortunate results, because if the end result is A vs B you’ve driven up your price!

I think you can solve this with what is essentially instant runoff voting to reduce the n alternative case to the two alternative case:

Your vote is a ranked subset of the alternatives. You also associate a number of votes with each alternative. These are probably not required to be in the same order – i.e. you could vote A over B over C but assign 1 to A, 0 to B and 2 to C if you really wanted. This might be a good strategy if e.g. you had two candidates who you both really hated but had a strong preference as to which would win amongst the two of them. So your vote might be something like “A-10, B-1, C-1, D-10, E-0″ – you really don’t want it to get as far as D, but you’re hedging your bets in case it does. (Note: You could also simplify this by only allowing a single weight for the whole thing)

You then run the election as follows:

  1. If you only have two alternatives left, everyone votes for their preferred choice amongst those remaining with the weight they assigned to it. This is resolved as above.
  2. If you have more than two alternatives left, tally up the weights each person has assigned their most preferred choice amongst the remainder. The alternative with the lowest score drops out.
  3. Repeat the process from 1

The result is that you are never bidding against yourself when it comes to spending actual money – the auction at the end occurs between two options and you’re only bidding on one of those options.

I’m even less sure this is a good idea. It probably isn’t. It definitely has weird tactical voting properties that would probably give people a headache (I’m quite concerned about the possibility of distorting the results with high cost votes that you know will drop out before you have to pay them. This can be mitigated by requiring a full ranking of all the candidates and a single weight for your vote, but I’m not sure it’s worth it). It’s an interesting one though. I’ll have to think about it some more.

This entry was posted in Uncategorized on by .