Author Archives: david

Consider the tournament

Due to reasons, I found myself thinking about the following problem:

We have a two-player game with players \(1, \ldots, n\). Player \(i\) beats player \(j\) with probability \(A_{ij}\) ( so \(A_{ij} = 1 – A_{ji}\)).

We wish to run a tournament with these players. The tournament is played as a sequence of games between pairs. The loser of the two drops out, and we choose another pair from the remainder until there is only one left (assume that a player winning any game they participate in is not affected by previous games they’ve played).

My question is this: How much can we influence the result of the tournament by changing which pairs play against eachother?

The short answer is “a lot”. There are clear upper and lower bounds on a given player winning (the upper bound on player \(i\) winning is \(\max\limits_{j} A_{ij}\) – they don’t play until the very end and then play against the player they are most likely to beat – while the lower bound is \(\prod\limits_{j} A_{ij}\) – they play against every other player\), but there’s a lot of variation in there and these bounds won’t be achievable for all tournaments.

So how to resolve this question? Well, I wrote some code. Have ye a nice little python module for calculating how to rig tournaments.

(Well, it doesn’t actually tell you how to rig tournaments, though it could easily be modified to do so. Instead it tells you the probability of victory under various strategies. Some of those strategies are “recursively maximize this function”).

I’m going to explore this more later, but if I write any more on this right now I’ll be late to work, so in the meantime this is just a “Here’s some code! If you’re interested in this question, feel free to play around with it”.

Chicken breasts in red wine and caramelized onion sauce

I made this the other day. It was improvised but turned out to be really good, and I’ve been eating leftovers for it since and not feeling put out by this at all.

A pack of thick bacon. I used about half of it for something else, but reused the frying pan with the bacon fat in it as well as some of the bacom
8 small red onions, sliced
About 50g butter
About a tbsp dark brown sugar
A fair bit of salt (I’ve no idea how much. “to taste”)
About half a bottle of dry red wine
8 chicken breasts

Equipment needed: Food processor, frying pan, small baking tray

First fry the bacon quite thoroughly, then take it out and put it aside. Add the butter to the fat in the pan, let it melt, then add the onions, salt and sugar. Put on a high heat and cook for bloody ages until the onions are properly caramelized (no “put on high heat for 10 minutes” nonsense. Caramelising onions properly takes most of an hour). Slice the bacon quite thinly, add it to the onions, fry for a few more minutes then add about half the wine and some water so that the onions are just covered. Lower the heat a bit and simmer, stirring occasionally, until you’ve got a thick reduction. Add the rest of the wine and a fair bit more water and simmer for another half hour or so.

Once this is cooked, transfer to the blender and blend until you’ve got a smooth, thick sauce.

Place the chicken breasts in your baking tray and cover with the sauce.

Now bake in the oven at 160C until the chicken is tender and easily comes apart when you poke it with a fork (I think this took a little over an hour, but I forgot to time).

This should probably be part of a larger meal, but I’ve mostly just been eating it with bread. The sauce is amazing, so you definitely want something that soaks it up.

When reheating it I’ve been slicing the chicken, spooning on extra sauce and frying it in a bit of butter.

It’s like Intrade meets OKCupid

As someone who spends most of their time single, it’s pretty much inevitable that every now and then I overcome my mild disinterest in the subject, decide it might be nice to try that not being single thing again for a change and reactivate one or more of my various online dating accounts.

This basically starts a cycle which lasts a few months and a dozen or so dates and ends up with me stopping using online dating again, frustrated at what an unpleasant experience it is. It definitely works for some people, but not really for me, and my frustrations with it definitely don’t seem to be unusual.

Naturally as someone who is interested in technical solutions to social problems and can’t resist a good problem when it’s sitting in front of me what then happens is that I design my own online dating site. I quickly remember that this isn’t an industry I want to get into and that the idea of bootstrapping it sounds hellish, but the result is that I have a lot of shelved ideas for how I’d do an online dating site if I took leave of my senses and decided to make one.

Which meant that when the latest wave of outrage about someone having done something terrible on the internet passed by, and when it was basically about online dating where you bribe people to go on dates with you, I was well primed.

My quip in response to it was “but of course this is a good idea. You see, markets are efficient, so everyone is going to end up with the best date”.

Unfortunately my second thought in response to that was “Wait hang on there’s something there”.

For those of you lucky enough not to have used OKCupid or similar, one of its key features is the compatibility score. It gives you a percentage score for how likely someone is to be a good match to you.

They’re a bit rubbish. I mean, a low score is a pretty good indicator that someone is going to be a dreadful match for you, but a high score at best indicates that you probably won’t hate them and everything they stand for (and there are plenty of people on the site you will hate everything they stand for).

One of the things I often wonder is why it doesn’t do complicated learning off the other info you’re providing to the site – you provide a lot of text which it could train classifiers off, why not learn what you’re looking for in a profile and use that? I suspect the short answer is because it’s hard. There’s a lot of nuance that it’s hard for a computer to extract from the profiles.

On the other hand, people are quite good at extracting that info from the profiles. Natural language processing is sortof our thing. If you could get people to provide you with compatibility scores that’d probably work rather well…

And markets are a decent way of soliciting information from people.

Of course, the idea of people bidding to go on dates with someone is revolting. Of all the things I don’t want online dating to do, reinforcing a commodity model of dating is pretty high up there. But with a twist, you can easily avoid this problem. You’re not bidding on going on dates with someone. You’re bidding on the chances of two other people going on a date.

i.e. you’re running a prediction market to get peoples’ compatibility scores.

I think I would describe this idea as “compellingly awful”. Amongst all the online dating sites I’m not going to build, I’m most not going to build this one. But it’s got into my head and I’ve accidentally designed the whole thing, so now I’m going to tell you about it to get the damn idea out of my head.

Here’s how it works: You use a fairly constrained prediction market based off a fake currency. Because the name amuses me I’m going to call this currency “dating dollars”.

Dating dollars can be bought for real money. They can never be redeemed for real money. Their worth is created by the fact that you must pay dating dollars to use features of the site. In particular it costs dating dollars to message someone for the first time (if they’ve already messaged you you get a discount but still have to pay some). You can also spend dating dollars for things like “promote me in search results” or “prioritise finding me some matches”.

As well as by spending real money you can get small amounts of dating dollars for providing feedback to the site. If someone messages you and you aren’t interested, clicking the “I’m sorry I’m not interested” button will give you a little bit of dating dollars. Once you’ve started talking to someone you can tell it if you’re going on a date or not. As long as your answer to that question agrees with the answer the other person gives you get rewarded. Also once you’ve been on a date it will ask you if that date went well. It will reward you either way for this one (so people don’t have an incentive to lie if they think the other person is mistaken). Basically the site is saying “Thanks!” for providing useful feedback it can use (and also it will nag you if you don’t provide that feedback).

And then there’s the third way, which is the actual point of the site: The prediction market.

This is a game you can play. What it does is it shows you two profiles side by side and asks you to the following question: With this payoff, would you pay one dating dollar to bet that if one of these two messages the other then they will go on a date and report that it went well?

If you say yes you pay the dollar and the bet is recorded. The following then happens:

If at any point the two of them go on a date and both report it went well you get the pay-off
If at any point they indicate that they’re not going to go on a date (e.g. by rejecting a message, by explicitly clicking “No we’re not going to go on a date”, etc) you lose the bet and are informed of such
If after one week neither has shown any sign of interest or disinterest in the other, you get your dollar back and a dollar is deducted from the payoff. The bet remains active though, so you still have the potential to gain or lose money.

The profiles you are betting on are out of your control. You get shown them one after the other picked mostly at random (people can pay to appear more often in these). It probably makes sense to only vary one member of the pair at a time to reduce cognitive burden.

This game is then used to determine the “market rate” for a pair. This is 1 over the lowest value that most people will pay for the pair. This gives you your compatibility score. Peoples’ bet that a date between the two of you would be successful. You can then see your most compatible voters.

I suspect displaying the actual compatibility score would be… depressing. Assuming the prediction market is actually broadly accurate, most dates end in failure so most scores are going to be quite low. You’d almost certainly want to show the order + maybe a “great/good/eh/NOPE” badge based on where you lie in the global market for pairs.

You might need some protection against market manipulation. Hellbanning people who manipulate is probably a good way to do this (not necessarily from the site over all, but not counting their bets as contributing to the market price). You might also want to get people to predict only for pairs which are far away from them.

I think the main obstacle to this is market liquidity. On the one hand the fact that the seller is the computer and is powered by a fiat currency helps a lot, but you still need to get people to actually bid, and getting people to bid on enough pairs might be challenging. Or it might not – enough people might really enjoy the game of matchmaking that they’re happy to devote loads of time to it. I suspect work could be done to make this compelling. It might not be enough though – you probably need at least three offers for each pair, and there are order \(n^2\) pairs (actually it’s not that bad because localisation) and order \(n\) people.

You’d also have to watch the money supply – if you’re offering bids that are too generous then people will be flush with dating dollars and no one will pay you real money for them. If on the other hand you offer bids that are too stingy then no one will bid and play your game and your source of information will dry up. You could solve this with a bid and ask system, but I think the market is unlikely to be sufficiently liquid to support that. Though if it were you could support more complicated trading of instruments… e.g. predictions that at least one person from one group would go on a successful date with at least one person from another. Bundling assets together. etc. No. Argh. Bad David.

In short, I think that as well as being a ludicrous idea this is probably actually a bad one. The problems of keeping it balanced are probably too great. Which is good because I’m not going to be making it. Really.

Examining bias in non-majoritarian random pair

One of the nice features of using random ballot for electing representatives is the strong proportionality property: The expected fraction of parliament made up by some group is the fraction of people who vote for someone from that group.

I’d like to consider how this looks in the following voting system:

Pick two random members of the populace
Everyone votes for one of them without the possibility of abstention.
A candidate wins with probability equal to the fraction of people who voted for them

This isn’t the majoritarian random pair in which the candidate of the two with the majority vote wins. Why? Well partly because it’s just easier to reason about this one, but partly also because hard cutoffs like that create a vastly more biased system.

The proportionality property here is a bit more complicated. There are two factors that determine what the probability of electing someone from a specific group are. We’ll call them \(g\) and \(e\). \(g\) is the probability of a random person belonging to the group (i.e. the fraction of the population who do). \(e\) is the probability that given a randomly chosen member of that group and a randomly chosen member not of that group a randomly chosen voter, they will vote for the in-group member. Call the probability that a member of the group is elected \(r\).

\(e\) might need a bit of elaboration. It basically measures how much the populace likes that group – if \(e = 1\) then they’ll always vote for that group, if \(e = 0\) they will never vote for that group, if \(e = \frac{1}{2}\) they don’t really care whether you’re a member of that group or not.

What is the probability of a member of the group being elected? Well, consider first whether they were picked. If both of the chosen candidates are group members, one must be elected. If neither are then one is not elected, and if it’s mixed with one in-group and one out-group then a group member is elected with probability \(e\)

This means that \(r= g^2 + 2g(1-g)e\).

Lets start with the \(e = \frac{1}{2}\) case. This means that the probability is \(g^2 + g – g^2 = g\). So for any group where there is no popular opinion pro or against the group, you get representation proportional to its presence in the populace.

By considering \(e = 0\) and \(e = 1\) we can get some general bounds: \(g^2 \leq r \leq 1 – (1 – g)^2 = 2g – g^2\). This means that no matter how much everyone else hates them, any group with a reasonable representation in the populace will get representation. For comparison, if we’re trying to elect a house of \(650\) out of a populace of \(63\) million as in the UK, any group with about 250 thousand members expects to get a representative regardless of how much people hate them.

An example where this is relevant is race. Currently just shy of 80% of the UK population are white. Unfortunately just shy of 96% of our MPs are white. The lower bound this would put on the percentage of non-white MPs (in probability anyway) is 4% (this is suspiciously close to the actual percentage, but that’s just a coincidence). So even in the circumstance where our country was so profoundly racist that every single one of us only ever voted for white people (I’d like to think we’re a bit better than this) we would still not be doing worse than the status quo. This is however an example of this system doing worse than sortition – a sortition will elect in proportion to the population, regardless of the prevailing biases.

This lower bound is probably not realistic. In general it seems unlikely that any group will be so hated that no-one will vote for them, because when this happens that group will tend to close ranks and vote for in-group members. So the more common lower bound is likely to be that \(e = g\). This gives us \(r = g^2 + 2g^2(1-g) = 3g^2 – 2g^3\). At the \(g = 0.2\) mark this gives us about \(10\%\) of the house. For much smaller \(g\), which will correspond to fringe groups (e.g. racist groups like the EDL), \(g^3\) is small enough as to be negligible this doubles the base probability. It’s also worth noting that this sort of effect means that although the lower bound makes this better than random ballot in principle, in practice under random ballot many people would likely be voting in-group and thus get much the same benefit.

Gender is another interesting example to consider. If we consider the \(g^2\) lower bound, that should give us at least a quarter of our representatives being women. Sadly, that’s actually slightly better than our current representation of women in parliament – it gives us an expected number of \(162.5\) compared to our current \(146\).

And this is a worst-case scenario: It’s only that bad if every single person will always vote for a man over a woman (which is obviously untrue given that we’ve managed to elect 146 female candidates under a first past the post system). With \(g = \frac{1}{2}\) we have \(r = \frac{1}{4} + \frac{1}{2}e\). it’s almost impossible to know what an accurate value for \(e\) is, but if we take \(e = \frac{1}{4}\) as a pessimistic lower bound this gives us \(r = \frac{3}{8}\), which is surprisingly not bad.

Another case worth considering is what you do when a group is really popular outside of all proportion to its membership. For example, if you live in the top 1% of wealth distribution and want electing you can get yourself a pretty decent chance of winning the election against someone who isn’t just by throwing money at advertising and PR (this isn’t strictly true, but it’s about the worst case scenario). The result of this is that they get… about 2% of the seats. That’s not so bad. I had trouble finding salaries for MPs prior to their elections (post election their salary puts them in the top 5%), but I bet a lot more than 13 of them broke £150k. I would also expect this bias to be much stronger in a random ballot system where the set of candidates was unrestricted.

So where am I going with this? I’m not really sure. I just wanted to see how heavily this was distorted compared to a sortition. The conclusion seems to be that it’s bad but not too bad – in biasing the sortition towards what society thinks makes a good candidate we’re naturally biasing towards society’s prejudices, but the randomization of the candidates puts bounds on how badly it can do that. It seems like this might actually be a nice middle ground between sortition and random ballot.

Stating the probabilistic Gibbard-Sattherthwaite Theorem

So as mentioned in an emergency edit, the version of the Gibbard-Sattherthwaite Theorem for non-deterministic voting systems that I mentioned in my last post is wrong. The set of voting systems permitted by it is in fact notably larger than I claimed (I got my version of it from this rangevoting.org post. Ah, trusting third party reporting of science by people with an agenda).

So now I’m reading the original paper. I’m struggling a bunch with the details, but I at least understand the result and think I can see my way towards constructing an alternate proof that makes more sense to me.

Here is the true version of the theorem as near as I can tell:

Consider a voting system under the following setup:

There are N candidates
Each of M voters must submit a ballot consisting of a full ordering of the N candidates
The votes are aggregated in some way to produce a lottery over the N candidates

Further, assume that voters are Von Neumann-Morgenstern rationalists with full preferences over lotteries arising from expected values of utility functions, and that they have strict preferences amongst the candidates (i.e. there are no two candidates to which they assign the same utility).

A voter’s ballot is honest if whenever they rank candidate x better than candidate y their utility function \(U\) has \(U(x) > U(y)\).

A voting system is strategy-proof if there are never circumstances where a single voter can change their vote from an honest one to a dishonest one and get a lottery they strictly prefer in expected utility.

The theorem is that any strategy-proof voting system is a probabilistic mixture of the following types of system (that is, we choose from any number of items of this type with fixed probabilities independently of the votes cast):

Fixed, meaning it always elects a specific candidate
Unilateral, meaning there is a single voter such that any other voter can change their ballot without affecting the outcome
Duple, in the sense that there are only two candidates it can elect (fixed is a special case of this where it can only actually elect one)

Three examples of this are sortition (it is an equal mixture of each of the possible fixed systems), random ballot (it is an equal mixture of each of the unilateral systems which elect the candidate’s top choice) and random pair (it’s an equal mixture of majority vote between each of two possible pairs of candidates).

But these aren’t the only examples. For example, a system which randomly chooses between a fixed voter’s top k choices is unilateral and strategy-free. So is a system which chooses between two fixed candidates, picking a candidate with probability equal to the fraction of people who prefer that candidate. There is a lot of flexibility in terms of how you construct the unilateral and duple systems which is ignored by random ballot and random pair.

How might we prove the theorem? Well… I haven’t quite understood the proof yet, truth be told. I’ve got bits of it lying disassembled in pieces hanging around on the shop floor of my brain, and I’m getting there, but so far I don’t have anything coherent enough to blog about. Once I do I’m hoping to try to slim it down and blog about it. We’ll see. For now though, I just thought it was important to have a correct statement of the theorem online.