Happy new year everyone!

I thought I would cope with my New Year’s hangover through the traditional method: Ibuprofen, coffee and attempting to solve NP hard combinatorial optimisation problems.

(The fact that I am now free to work on these things as my contract with Google has officially expired may have something to do with why I was looking into this today rather than waiting until I was less hungover)

As some of you might be aware I have a perverse interest in the Feedback Arc Set for Tournaments (FAST) problem. This is as follows:

Given an \(n \times n\) matrix \(A\), find an ordering of \(\{1, \ldots, n\}\), say \(\sigma_1, \ldots, \sigma_n\), which minimizes the sum of backwards weights \(w(A, \sigma) = \sum_{i < j} A_{\sigma_j,\sigma_i}\). This sum can be regarded as in a sense the degree to which the ordering gets the pairwise preferences of \(A\) “wrong”.

The classic example of why this is interesting is the Kemeny Young voting method. There are others (I think it’s useful for graph drawing for example) but I don’t know much about them.

Anyway, solving this is super NP hard. We’re not talking “it’s about as hard as the travelling salesman”, we’re talking “You want to solve this optimally for a hundred nodes? Ha ha. Good luck”. As a result one tends to use heuristic orderings for it.

I was wondering whether you could related this back to voting to get a good heuristic order and it turns out you can, and a really rather good one to boot. So this is a report on an experiment I’ve run which uses the Ranked Pairs voting algorithm to give an \(O(n^3)\) heuristic ordering for FAST that appears to produce quite a high quality result.

You can see all the code for this work here.

Evaluation

The metric I am using to evaluate methods is as follows: Let \(A\) be a matrix valued random variable and let \(f\) and \(g\) be functions which take an \(n \times n\) matrix and return a random permutation of \(\{1, \ldots, n\}\). Then \(f\) is better than \(g\) with respect to \(A\) if \(E(f(A)) < E(g(A))\).

Note that this notion of betterness depends very much on the distribution of \(A\). \(f\) is better for \(g\) for every choice of distribution only if for every fixed \(x\), \(E(f(x)) < E(g(x))\), which is a much stronger and hard to test condition.

I focus on one particular choice of \(A\): \(100 \times 100\) matrices are generated such that if \(i < j\) we pick \(A_{ij}\) to be any integer between 0 and 100. If \(i > j\) we pick it to be any integer between 0 and 70. We then shuffle the coordinates so as to prevent systems that are biased towards picking the coordinates in order from having an advantage. This gives us a matrix which has a rough “direction” but is really quite noisy in how well it establishes that direction.

I then generate 100 matrices and compare two methods by using a monte carlo permutation test for the difference of the means when applied to these matrices. Note: I am aware this is a somewhat dubious decision due to the potential difference in the standard deviations. This step could use improving.

Because I am comparing more than two different methods there is a multiple testing problem. I use the Benjamini-Hochberg procedure to control the false discovery rate to 1%. I think this is valid because of the nature of the correlations between the tests (false discoveries should all be positively correlated) but I’m not really sure.

As a calibration I tested adding duplicates of some methods to see if this would confuse the results and it did not. All the existing results remained statistically significant and no false conclusions were drawn about the relations amongst the duplicates.

Basically: The statistics here are kinda dodgy and I don’t really know enough to know how dodgy they are. There’s a reason working on my statistics is one of my plans for the next few months. However the results are all sufficiently convincing that I’m not too worried about the conclusions being wrong even if the methods are.

Methods compared

I compared six different methods, with varying expectations of some of them being any good (actually I compared more than this, but I threw some of them away because they were not any better and were annoyingly slow). These were:

1. Generate a random permutation
2. Generate a random permutation then apply a local kemenization procedure (basically: swapping adjacent elements in the order when this will improve the score). Reverse this and apply the local kemenization procedure again. Pick the best of these two.
3. Sort by the assigning a variable \(i\) the score \(\sum A_{ji}\) (this is basically the weight of evidence that various things are less than \(i\)\) and again apply the local kemenization procedure.
4. A greedy algorithm that builds up the list one element at a time by iterating over the indices in a random order and inserting each element in the optimal location in the already built list.
5. Kwik-sort, which is essentially applying quick sort with a random pivot to the order defined by the matrix and ignoring that that order isn’t actually transitive. This is as defined in this paper. I have not tried their proposed LP version of kwik sort because running the LP on this size of problem turns out to be really slow and I got bored of waiting for it.
6. Ranked pairs. This works by building a transitive order over the elements. We iterate over the pairs of indices in decreasing order of weight (i.e. largest first). If the order of this pair has not been established already we “lock it in” in this order and add all of the other pairs that this + transitivity requires.

Results

Here is the program output:

 Simple shuffle: 210202.81 +/- 3381.47. 1%=204032.12, 50%=209934.00, 99%=218417.48
 Improved shuffle: 204489.03 +/- 2225.88. 1%=199087.83, 50%=204575.50, 99%=209383.01
 Smoothed indegree: 178446.51 +/- 1699.39. 1%=174738.72, 50%=178306.50, 99%=183069.17
 Insertion order: 175407.30 +/- 1965.16. 1%=171059.98, 50%=175226.50, 99%=179597.99
 Kwik Sort: 195279.10 +/- 2923.19. 1%=189704.31, 50%=195339.50, 99%=201568.30
 Ranked pairs: 172922.71 +/- 1431.80. 1%=170204.94, 50%=172847.00, 99%=177180.83<

 Pairwise comparisons:
 Improved shuffle < Simple shuffle (p=0.0020)
 Insertion order < Improved shuffle (p=0.0020)
 Insertion order < Kwik Sort (p=0.0020)
 Insertion order < Simple shuffle (p=0.0020)
 Insertion order < Smoothed indegree (p=0.0020)
 Kwik Sort < Improved shuffle (p=0.0020)
 Kwik Sort < Simple shuffle (p=0.0020)
 Ranked pairs < Improved shuffle (p=0.0020)
 Ranked pairs < Insertion order (p=0.0020)
 Ranked pairs < Kwik Sort (p=0.0020)
 Ranked pairs < Simple shuffle (p=0.0020)
 Ranked pairs < Smoothed indegree (p=0.0020)
 Smoothed indegree < Improved shuffle (p=0.0020)
 Smoothed indegree < Kwik Sort (p=0.0020)
 Smoothed indegree < Simple shuffle (p=0.0020)

(The reason they all have the same p value is that that’s what you get when you never see a result that extreme in 500 random draws in the permutation test)

Ranked Pairs seems to comfortably beat out all the other heuristics by some margin, and the permutation tests agree that this is statistically significant.

As a side note, I wish I’d done this comparison a while ago, because I’m quite surprised to find out how badly kwik sort does. This may be an artifact of the shape of the data. I’m not sure.

I also ran a smaller experiment to compare Ranked Pairs with Schulze voting. It had to be smaller because Schulze voting was too slow to run on the full set of 100 matrices, so the following is a comparison between Schulze and Ranked Pairs on 10 matrices:

Schulze: 176430.30 +/- 1391.75. 1%=174276.96, 50%=176359.00, 99%=178563.24
Simple shuffle: 212209.30 +/- 3389.81. 1%=208202.43, 50%=211704.00, 99%=219189.76
Ranked pairs: 172918.60 +/- 1701.93. 1%=170901.82, 50%=172503.00, 99%=175619.76

Pairwise comparisons:
Ranked pairs < Schulze (p=0.0040)
Ranked pairs < Simple shuffle (p=0.0020)
Schulze < Simple shuffle (p=0.0020)

As Schulze appears to be both dramatically slower and a fair bit worse for this data set, it doesn’t seem worth pursuing as an alternative.

Suppose I run a shop selling water.

Suppose further there’s a crisis on and the municipal water supply goes out.

So, as a sensible trader, I jack up the price to $100/litre and make a boat-load of cash. People pay it because well what’s money next to a little not dying of dehydration? as

I mean, sure, they have to deal with the fact that they burned through a significant chunk of their savings after the crisis has passed, but they made a rational and considered choice to participate in this transaction, therefore it’s valid and fair, right?

My neighbour on the other hand believes that raising their prices would be exploitative and continues selling water at the normal price. As a result the first person who comes along goes “Holy shit, water for cheap!” and buys the whole lot just in case. Nobody else gets any.

Which one of us has improved the situation more?

Well, I’ve certainly made sure a lot more people won’t run out of water than my neighbour has. That’s got to be a good thing, even if I turned a tidy profit in doing so, right?

So why are people so angry at me?

My neighbour in trying to do the “moral” thing just ended up making the situation worse, but people are just tutting a bit and saying he should have been more sensible and making helpful suggestions about rationing.

I mean sure, I was charging a lot of money for that water, but people were willing to spend it therefore the water was worth at least that much to them. Should I have sold it at less? I’m not a charity.

And lets not forget that I’m the one who kept the most people in water!

There’s a meme that I’ve seen a lot recently (probably because I follow a lot of rationalists on tumblr) that people are irrational to get angry at people who provide better options at exploitative rates, because there are two possibilities:

1. Not have any option to fix your major problem
2. Have the option to fix your major problem at an extremely high cost

And the second is obviously better! It gives you options to fix things which you can decide whether they’re worth it.

(Examples of this sort of scenario where this have come up have been PETA’s water thing in Detroit and Uber’s surge pricing. I think there have been a few others).

I have a lot of sympathy for this view. I also think it’s wrong. I think maybe the level of rage is disproportionate, but I think it’s perfectly valid to be angry about these things.

Consider the water sellers above. Raising prices during a crisis is fine. It’s not an unreasonable way to control demand of a limited supply (there are other not unreasonable ways which might be better, but I don’t think it’s intrinsically wrong to treat this as a supply/demand problem given the system we live in). But how high should I raise prices?

Well I could just raise them to what the market could bear.

But the market will bear a lot. People’s alternative is dying. People will pay a lot to not die. As a result I can basically take them for what they’re worth.

In a well-functioning capitalist society (please imagine I said that phrase with a straight face) what would happen is that if I were making an obscene amount of profit someone else would realise that they can basically steal all my customers and still make an only slightly less obscene amount of profit by offering the goods at a lower price. Prices for water would then converge on a sensible value where water sellers still make a profit while people pay a reasonable amount for water that reflects its current scarcity.

But in a crisis we’re not in a well-functioning capitalist society. When this sort of price/value convergence happens it happens over a longish period of time. Crises are happening now and you can’t wait for this price convergence.

And how much will the market bear in a crisis? A lot. When your alternatives are death, major injury, etc. the amount of money you’d be willing to pay is generally very large even if you know it’s going to screw you over later. This means that there is a very large gap between what it will cost to provide your get out of crisis service and what people are willing to pay you for it, and that gap is pure profit.

Is it OK to make a profit here? I mean, sure, I guess. I’m not against people benefiting from helping others – indeed I’m moderately in favour of it because it encourages people to help others.

But by and large I think that if you have a large number of people giving a substantial fraction of their life savings to someone resulting in a very large profit, and you compare it to that person making about half as much profit and people giving about half as much of their life savings, the latter is a much better scenario.

So how do we arrange it so that people don’t exploit crises?

Well, the optimal solution would be to provide good enough crisis support that the opportunity to do so was not there.

But the solution that’s actually available to most of us is to punish people who do by shouting at them, denying them our business, etc. It creates an incentive for people to do better and moves their crisis price point away from the “take them for what we can get” end that it will tend to default to and much closer to the “offer this service which improves matters at a price where we can still make a reasonable profit” end we want them to be at.

So lets do that then. Sure, it’s not the optimal solution, but by adopting the position that anything that improves the situation is better than its absence, you’ve already abdicated the ability to complain about choosing the available solution instead of the optimal one.

So are people improving the situation by offering these options? Generally, yes. Is it OK for us to punish them for this? Yes, because it shifts the incentives so that they will improve the situation more rather than not at all.

(And arguably we should also complain about the fact that we do this, because it makes people think about the motivations and reasoning for this and maybe makes them less likely to punish people who are actually just turning a fairly reasonable profit out of the situation. The recursion never ends)

Note: This is somewhat related to my stance on the correct solution to trolley problems.

I’m relatively unusual amongst my friends in that I actually like my family and enjoy spending Christmas with them.I do however find choosing presents for people very stressful, and I’m not really that interested in receiving them (I’m also really hard to buy for, so I imagine other people find me gifts for me particularly stressful). So, this year my parents and I decided to get each other a great Christmas present: Not having to worry about Christmas presents.

My brother and his girlfriend were out of the country visiting her family for Christmas, so it was just me, my parents, and my sister. My sister opted out of this opting out of presents thing, so basically all the presents under the tree were either to or from her. As a result we basically just had the one round of presents and were done in ten minutes. Normally with 5 of us it takes more than an hour (the present opening algorithm runs in \(O(n^2)\)).

And… you know what? It turns out I missed the experience of us all opening the presents. I really didn’t expect to. It’s not the getting gifts that I missed (I can buy the things I want generally speaking, and I probably tend to spend about as much as I receive), but there’s something pleasant about the shared experience of opening presents together that it felt weird not having.

So, I wondered, how can I combine the lack of stress of not having to buy presents with the enjoyment of giving and getting presents?

And thus I formed a stratagem! Stress can be reduced using tried and tested techniques:

1. Advance planning
2. Constrained options
3. Focusing on my areas of competence

So I have predeclared my intentions for Christmas 2015.

Everyone I buy presents for (which is strictly the set of people present at my family Christmas. Christmas scope creep: Just say no) is getting one of the following:

1. Items of my choosing (parameters accepted) from one of a short list of things I am good at choosing for people: Books, board games, booze, tasty foods.
2. Any extremely specific request they would like me to fulfil (within reasonable price bounds)
3. Socks, if they fail to express a preference amongst the above

In exchange I am of course willing to provide similar parameters to people on request, but will also be sending out a Christmas list at the beginning of October providing a rough “Here is how to buy presents for me if you don’t have any better ideas, but I’m happy to accept anything you want to buy instead” guide.

I have sent out a Google form asking for peoples’ preferences amongst the above (people will be able to edit their responses), and I have created calendar reminders for when to send out my presents guide (October 1st) and when to send people a reminder that they should consider their Christmas preferences and maybe submit/edit them (November 25th).

A slightly belated or extremely premature, yet nevertheless highly organised, Christmas to you all.

I made something delicious last night, but it feels like it was about twice as much work as it should have been and produces results that were about 2/3rds as good as they should have been. Hence this post is notes rather than a recipe. Feel free to experiment on this theme and report back if you come up with a more sensible way to cook it.

The food concept is basically fancy liver and onions with tomato and kale, served with quinoa.

Ingredients list (quantities are so approximate you wouldn’t believe):

• Lots of frozen tomatoes (you can’t buy frozen tomatoes as far as I know. These were from my mother’s garden which she froze back in the summer. I imagine fresh would work fine for this). I think there were about a dozen smallish ones (larger than cherry tomatoes but not too small that I couldn’t close my hand entirely around one).
• A large bunch of kale
• Two medium sized onions
• A small bunch of sage
• About two hands full of chicken liver
• Some flour for coating the liver
• Oh god so much butter
• Four rashers of bacon
• About one and a half cups of quinoa
• Half a lemon
• Some salt

Process:

This is what I did, but it’s pretty far from optimal and could be streamlined a lot. I recommend not following it directly but instead treating it as an inspiration for a better, swifter, means of cooking this.

First roast the tomatoes (I did this in a baking tray with a raised grill). Cut them in half for this (the frozen tomatoes were frozen halved anyway). As they roast, periodically drain off and keep all the liquid. For me this produced about two cups of liquid over the course of the cooking. When most of the liquid has come out of the tomatoes but they’re still quite soft, take them off the roast.

While those are roasting, start cooking the onions. This involved slicing them fairly finely and then cutting the slices in half lengthwise, then putting them in a pan on high heat with lots of butter and some salt (note: This recipe ended up a bit too salty because of this and the bacon. Maybe don’t use too much salt here)

At some point when you have a free moment, finely chop up the sage.

Once the onions are starting to caramelise, chop up the bacon quite finely (it ended up in roughly 2cm by 0.5cm strips for me) and add it to the onions. Continue cooking until the onions are well and truly caramelised, then add the tomatoes and the sage and keep cooking for a bit longer.

At this point it’s time to start cooking the quinoa. Cook this basically as normal – one part quinoa to two parts water – but instead of water use the tomato water we reserved earlier in the cooking process. This probably won’t be quite enough so top it up with enough water to make up the difference.

While all of those are cooking, chop up the kale, removing the stems and slicing the leaves quite finely.

I then transferred the onions, tomatoes and bacon mix out into a serving dish and reused the pan (which was still quite greasy from the previous mix so didn’t need more butter for me but you may wish to add some more) to fry the kale. This should only take a few minutes, you don’t want it overcooked.

While that’s cooking, prepare the liver. Cut it up quite finely (I think I had it at roughly 2cm by 1cm strips) and mix it up with some flour until it’s thoroughly coated.

Once the kale is done, transfer it out to the serving dish. Now it’s time to start cooking the liver.

I made a mistake here, which is that the pan now had lost most of its grease so it needed more butter. I didn’t wait until the butter was hot enough, and as a result the liver did not cook quite as I wanted – you need a good high heat or it tends to boil a bit in its own juices. So don’t do that then.

Anyway, cook the liver until it’s, err, cooked. Then add the things you’ve previously put in the serving dish back to the pan, stir everything together for about another minute or two, and transfer back to the dish.

Hopefully the quinoa is ready at this point. Add the juice of half a lemon to it and mix thoroughly.

Now serve.

I found this made enough food for two people to eat slightly more than they probably should but about as much as they wanted, with not quite enough left over for a third. On the other hand this should be pretty easy to scale up.