Computational kindness and the revelation principle

In EWD1300, Edsger W. Dijkstra wrote:

even if you have only 60 readers, it pays to spend an hour if by doing so you can save your average reader a minute.

He wrote this as the justification for the mathematical notations that he introduced and as an ode to the art of definition. But any writer should heed this aphorism.^[1] Recently, I finished reading Algorithms to Live By by Brian Christian and Tom Griffiths.^[2] In the conclusion of their book, they gave a unifying name to the sentiment that Dijkstra expresses above: computational kindness.

As computer scientists, we recognise that computation is costly. Processing time is a limited resource. Whenever we interact with others, we are sharing in a joint computational process, and we need to be mindful of when we are not carrying our part of the processing burden. Or worse yet, when we are needlessly increasing that burden and imposing it on our interlocutor. If you are computationally kind then you will be respectful of the cognitive problems that you force others to solve.

I think this is a great observation by Christian and Griffiths. In this post, I want to share with you some examples of how certain systems — at the level of the individual, small group, and society — are computationally kind. And how some are cruel. I will draw on examples from their book, and some of my own. They will include, language, bus stops, and the revelation principle in algorithmic game theory.

George Kingsley Zipf outlines how considerations of computational kindness are embedded in our very language through a conflict between the speaker and listener in how to invest cognitive energies. A speaker hopes to have all concepts expressed by a single simple sound and leave the difficulty of disambiguation to the listener. The listener, on the other hand, wishes for a totally unambiguous language, so the difficulty of picking the right words is on the speaker, and the listener doesn’t need to spend energy on disambiguation.^[3] The former task, of using a longer and more elaborate sequence of sounds to express our meaning, is clearly easier than the latter task of picking out the most consistent of countless interpretations of a terse utterance. Thus, the fact that our words are not extremely overloaded is a testament to our computational kindness towards listeners.

But this doesn’t mean that computational kindness ends at unambiguous words. We can also be more or less kind by what we choose to say. Some of these considerations are at odds with typical concerns of politeness. Suppose that my friend asks where I want to go for dinner tonight. If I reply with “anything’s fine by me, whatever you would like” then under conventional wisdom, I am being polite. I am offering her the freedom to determine dinner plans. However, anybody who has said this in practice (or worse yet, heard it as a response) knows that this is hardly kind. Now, my friend has to not only select something from her extensive list of preferences, but she has to also simulate my preferences to judge which of the options is best at optimising both of our utilities. It is often more difficult for my friend to simulate my preferences than it is for me to examine them for myself.^[4] Thus, my response not only forced her to do all the cognitive work, but I have created a higher amount of total work to be done. The kinder response would be for me to provide a (small) set of concrete options that won’t require her to simulate my preferences.

We can also take this idea from interpersonal settings to a design principle. Suppose that I encounter a bus stop in a new city. Since I don’t know the frequency of the bus schedule, as I wait at the stop, I will have to constantly do three things: (1) remain vigilant, staring into the distance for the bus, and (2) update my beliefs of the expected waiting time based on how long I’ve already waited while^[5] (3) checking this estimate against my utility for prompt arrival and cost of Uber. Instead, if the city posts a digital sign counting down to the next arrival then: I won’t have to stare into the distance, I won’t have to recalculate my estimate of the arrival, and I will only have to check my utility function once.^[6] Not a huge difference in cognitive load for a single person, but a difference that can quickly add up over the transit population.

Finally, let us consider an explicitly computational example from mechanism design: an auction.^[7] In a classic blind auction, a single item is up for auction and each bidder writes down their bid privately on a piece of paper. The auctioneer then looks at all the pieces of paper, giving the item to the bidder with the highest bid and charging them whatever they bid.

Let’s analyse this auction more closely with just two bidders: Alice and Bob. Alice values the item at a and Bob at b. Suppose that in this particular case, a > b. If Alice simply bids her valuation a then she will win, but not gain any value. On the other hand, if she could guess Bob’s bid and make her own bid a penny over b then she’d still win the item and make a profit of a – b. Of course, Bob doesn’t know ahead of time that he is going to lose the auction, so he will be going through a similar internal simulation of what Alice might do. In the end, both will have to spend a lot of effort simulating the other and in most cases will not bid their true valuation. The won’t employ a truthful bidding strategy. In fact, the first-price sealed-bid auction has no dominant bidding strategy.

If the item at stake is extremely valuable, you could imagine that Alice would hire a consultant to do the difficult cognitive task of simulating what Bob might bid. Of course, Bob will do the same. What happens if they hire the same consultant? Well then he’d see both bids and just tell Alice to bid a penny over b (or vice-versa with Bob, if b > a). And if they hire different consultants then they will have the difficult task of simulating each other to find this perfect advice. But if you are the auctioneer, why force the participants to waste money hiring consultants? Instead, we can just incorporate the trusted advisor into the bidding process. This is the idea behind the revelation principle. It is a way to transform any game (with some dominant strategy) into one where the truthful strategy is dominant.

In the case of the sealed-bid auction, the auctioneer could simply award the item to the top bid, but make them pay the second top bid. This effectively rolls up the advisor (to whom Alice told her true valuation so that he’d tell her what to bid) into the auction mechanism itself. It saves Alice and Bob the effort of simulation each other (or paying someone else to do that) and allows them to just bid truthfully. This is known as the Vickrey auction — the computationally kind sealed-bid auction. When Google holds auctions for their ads or the US government for swaths of radio frequencies, they use a Vickrey auction and are thus kind to their clients. Instead of wasting the bidder’s resources forcing them to simulate each other, by changing to a well-designed process, the auctioneer can save everybody this needless effort.

What do you think of computational kindness, dear reader? What are some other examples where the world around us can be improved by being more mindful of the computational problems that we pose each other? As an ethical principle, does computational kindness add something beyond the typical concerns of the moral philosopher? I think that opens the door for algorithmic philosophy to make a contribution not only to metaphysics, epistemology, and philosophy of science but also to (meta-)ethics.^[8]

Notes

1. Opening with an endorsement of succinctness puts me in the awkward position of giving you, dear reader, a tempting metric to judge me by. A metric that I often fail to satisfy. The introduction of extensive footnotes in my posts has been part of my way to mitigate my wordiness. You can read the main text, and skip these long notes.

   As a secondary defence, however: terseness is not the only way to be computationally kind. In fact, it can be unkind when parsing the terse code would require running needless loops of thinking.

   Finally, even the unkindness of ambiguity-in-presentation is not necessarily bad. For example, the author might by trying to encouraging active reading, to facilitate a fuller understanding.

2. For full disclosure: this book was mailed to me by a marketing manager for Henry Holt and Company, with the hope that I would review it on this blog. Overall, I enjoyed the book, and there are many to whom I would recommend it. I will write a full review soon highlighting its strengths and shortcomings, and giving a fuller flavour of the content that it covers.
3. Zipf’s tension — and many of the other interpersonal examples in this post — is premised on the assumption that the point of communication is to convey information unambiguously. An assumption that can be questioned.
4. This is not to imply that this hypothetical interchange is worse for the pair taken as a whole. By having to regularly simulate each other’s preferences, and then test our simulations for accuracy — do I frown at her decision or am I excited about it? — we can build intimacy and understanding of each other.

   I am also not implying that the only motivation for an unkind response is trying to conserve my own processing effort. Consider, for example, the Ben Franklin effect: “He that has once done you a kindness will be more ready to do you another than he whom you yourself have obliged.” Building on the previous point, the interlocutors following the unkind strategy in alterations, might help fortify a relationship.

5. Christian & Griffiths consider how we should update our expected waiting time for such cases in their Chapter 6: Bayes’s Rule.
6. I think that computational kindness also helps me understand why I find subways to be less stressful than buses. Not only is the schedule more consistent, but the train will only stop at stations and will stop at every station. Thus, I don’t need to remain constantly vigilant for pulling the stop request, and can only tune in when the vehicle slows down to see if this is my stop.
7. Christian & Griffiths consider this and other examples in their Chapter 11: Game Theory.
8. For practical ethics, computer science already provides us with important considerations. For example, as I discussed in weapons of math destruction and the ethics of big data. But the discussion in that earlier post uses computer science in a very different way than here. My closest prior post in this direction might be on hiding lies in complexity, which — with hindisght — I could re-interpret as an example of computational cruelty in finance.