Sam Gentle.com

Optimisation order

I mentioned before that for many problems you can be sure that you'll find a solution, just not how good the solution is. You have to find the best solution you can by making tradeoffs between the different choices. These are usually called optimisation problems, and there's a lot of research into various classes of optimisation problem and ways to solve them.

I've also said that I think our brains are optimisation machines, sometimes even to their own detriment. For better or worse we seem to do much better on optimisation problems than on, for example, formal reasoning, where we are comparative dunces. I suspect this is because optimisation problems likely fit our evolved capabilities better than formal logic does. But even though we can often find a good solution to difficult problems with lots of constraints, not all good solutions are equal.

The stable marriage problem is a fairly simple but very applicable optimisation problem, which applies to any situation where two groups want to match in pairs, and each member has a list of preferences for the other group. Dating is the canonical example, but also matching medical students and hospitals, job searching, and network management. The canonical algorithm, called Gale–Shapley, is simply that each member of one group asks their first available preference, and the other group accepts the offer if it's the best one they've had so far (bumping a previous offer if necessary). You do this over and over again until everyone is matched.

Gale–Shapley is guaranteed to find a solution such that nobody wants to change; ie, anyone you would rather be with is already with someone they'd prefer more. However, there are often multiple such solutions, and in that case some solutions will result in better outcomes for some people, even though on the whole everyone gets a good enough solution. In fact, Gale–Shapley does guarantee that one group will have the best possible outcome: the group doing the asking. The group that accepts or rejects the offers appears to be in a position of power, but actually receives the worst outcome that is still good enough.

That in its own right is a fairly significant result, given the similarity of Gale-Shapley to many real-world preferential matching algorithms. A job-hunting system where you ask your preferred employers in order for a job will get you the best result. A system where employers ask a pool of candidates in order will get the employers the best result. In dating, too, you want to be the one doing the asking. Being asked perhaps feels more flattering and less risky, but means a less optimal outcome.

It's also worth considering this pattern beyond the stable marriage problem. In every optimisation problem I am familiar with, the order matters. The parameters that go in first are most likely to get the best results, and the ones that go in last get the worst. This is for the simple reason that the earlier parameters can use more information. In the case of the SMP, they choose among all the candidates. Everything that goes afterwards starts by fitting around what's there already. In the event of multiple solutions, this biases the outcome.

The simple advice I would take away from this is to make sure that your optimisation order matches your preferences. If you want to have a good work life, a good home life, and a healthy social life, what order do those go in? Because while you might be able to have all of those things, you are unlikely to have all of those things equally. What you work on first will get the best outcome, and what you work on last will get the okayest outcome.