Algorithms to Live By

August 12th, 2017 by Potato

I recently read Algoirthms to Live By: the Computer Science of Human Decisions and enjoyed it. It takes a few important problems for which algorithms are used in computer science, explains what they do and some of the challenges associated with them, and then relates that back to everyday life.

This is the sort of book where I am clearly the intended audience: the authors do a decent job of making everything understandable and relatable, and there’s some humour… but you’re going to have to have some interest in the foundational problems or you will likely lose interest. That’s not to say that you have to have a math or computer science background, they do explain it all, you should just come to this with some interest and not just my recommendation.

To give you an idea, they spend the first chapter on the Secretary Problem. They explain the problem (you want to hire the best possible secretary, but have to balance that against not wanting to spend forever interviewing; oh, and after you interview and reject someone you can’t go back to them), and how this might crop up in different situations in your life (if you want the best tomatoes at the grocery store might be one example of a secretary-like problem in action). Then some practical insights from the solutions in computer science — in this case, the optimal answer is likely 1/e, or about a third. That is, if you have 100 candidates for your job, you may want to interview the first 30-40 or so with no intention of hiring them just to get an idea of the quality of the field, then after that hire the first one that’s better than any of those previous ones.

A great take-away is from the chapter on caching. In particular, the least recently used (LRU) algorithm is the scientific justification for why your desk is covered in papers where the only organizational principle is that you dropped them there, and the ones you need more are in the pile closer to your keyboard. “What might appear to others to be an unorganized mess is, in fact, a self-organizing mess.”

I also really liked the description of thrashing and context-switching in the discussion on scheduling tasks. This is not unique to this book — lots of time-management books and articles talk about having set times to handle tasks (“interrupt coalescing”), and to turn off your phone and email notifications to handle time-intensive tasks. But for some reason this one resonated a bit more for me — when I read their description of a processor thrashing I was like “this is happening to me right now.” Of course, that’s likely idiosyncratic to me and the fact that at the time I read it, I was struggling with low productivity because I had a large number of small, equally urgent tasks (vs. the usual case of having one big important project on my plate to balance with a few smaller fires) and had to keep dropping something to…

A neat new term I came across in the book to apply to some aspects of the housing bubble is “information cascade.”

“[…] under the right circumstances, this mixing of private and public data can prove toxic.

Imagine the bidders are doubtful about their own estimations of the value of an auction lot—say, the right to drill for oil in some part of the ocean. As University College London game theorist Ken Binmore notes, “the amount of oil in a tract is the same for everybody, but the buyers’ estimates of how much oil is likely to be in a tract will depend on their differing geological surveys. Such surveys aren’t only expensive, but notoriously unreliable.” In such a situation, it seems natural to look closely at your opponents’ bids, to augment your own meager private information with the public information.

But this public information might not be nearly as informative as it seems. You don’t actually get to know the other bidders’ beliefs — only their actions. And it is entirely possible that their behavior is based on your own, just as your behavior is being influenced by theirs. […]

Just as with the tragedy of the commons, this failure is not necessarily the players’ fault. An enormously influential paper by the economists Sushil Bikhchandani, David Hirshleifer, and Ivo Welch has demonstrated that under the right circumstances, a group of agents who are all behaving perfectly rationally and perfectly appropriately can nonetheless fall prey to what is effectively infinite misinformation. This has come to be known as an “information cascade.”

[…] imagine there are ten companies that might bid on the rights for a given tract. One of them has a geological survey suggesting the tract is rich with oil; another’s survey is inconclusive; the reconnaissance of the other eight suggests it’s barren. But being competitors, of course, the companies do not share their survey results with each other, and instead can only watch each other’s actions. When the auction begins, the first company, with the promising report, makes a high initial bid. The second company, encouraged by this bid to take an optimistic view of their own ambiguous survey, bids even higher. The third company has a weak survey but now doesn’t trust it in light of what they take to be two independent surveys that suggest it’s a gold mine, so they make a new high bid. The fourth company, which also has a lackluster survey, is now even more strongly inclined to disregard it, as it seems like three of their competitors all think it’s a winner. So they bid too. The “consensus” unglues from reality. A cascade has formed.

No single bidder has acted irrationally, yet the net result is catastrophe.”

This immediately reminded me of bidding wars in Toronto, where a common algorithm is to count the number of noses at the table and multiply by some constant, say $10,000, and add that to the phony asking price. An extra bidder (or 10) should not in any way affect your perception of value for the house, yet there are many instances where this sort of bidding strategy is reported.

The quotation above also shows the one caveat — it is a slightly academic style, with references and names dropped throughout (though quite readable despite that). This is great for being authoritative, but can slow the read down.

Leave a Reply