You are currently browsing the monthly archive for January 2011.

It’s eight months already since I got my ipad and I haven’t boasted about it here yet. (But I did try to piss everyone off by constantly playing with it during the summer game theory workshops, with a considerable success.) Well, everything you’ve heard is true, the pad is awesome. I will pour more detailed praise in another post, but first I have a complaint to register: There is no Dvorak layout option for the software keyboard.

If you don’t know what is Dvorak, then the keyboard layout you work with is the one invented million years ago. The hunter gatherers who were roaming the earth at that time were typing their papers using a mechanical device called typewriter which was something between a keyboard and a printer: When you press a key it would squirt ink onto a paper. Since the typewriter would jam when two keys were pressed together rapidly, the layout of the keys was designed to slow down the typing. That’s why the vowels in your qwerty keyboard are all over the place and you have to move your fingers a long distance from one letter to another when you type. I, on the other hand, and other members of the exclusive club of dvorak users, rarely move our fingers from the middle row in our keyboard, which reads, from left to right, AOEU ID HTNS. Notice how your favorite letters are all there. make sense, no ?



How come Dvorak didn’t conquer the world already ? Well, some people view this as a market failure. Other, especially those who believe `market failure’ is a logical contradiction, view this as a proof that the dvorak layout is actually no more efficient and that the story about the qwerty layout being designed for inefficiency is a crock. Other say we are in a transition stage between one equilibrium to another: Just wait another million years and everybody will be using dvorak.

As for me, I know that the dvorak layout doesn’t improve my writing speed since, dvorak or no dvorak, it takes me so much longer to think what I want to write than to actually type it, that even if the letters will randomly permute after every key i press the impact on my writing speed will be negligible. Also, I usually take a couple of days break after every sentence I write (my exasperated co-authors could elaborate on this point), so again — the bottleneck is definitely not in the keyboard layout.

Why then am I using dvorak ? Because it’s a status symbol, because it’s cool, because I will enjoy seeing your face when you try to type on my notebook and get gibberish, because i am an avid consumer of useless gadgets. In short, I am using dvorak for the same reasons I am using ipad. So how come the ipad’s operating system doesn’t support dvorak layout ?

Ok, just in case you missed the subtext of this post, let me make it explicit: I have an ipad ! it’s awesome ! i am totally smug about it !

I thought I’d use the bully pulpit, such as it is, to advertise, in a non-traditional way, a paper by Mallesh Pai and myself. To view the advertisement, see below. At most 4 minutes and 10 seconds of your life will be consumed.  Mallesh and I hope that others will be inspired to advertise their own work in similar fashion.

(Edited January 14; My thanks to Patricia L. for pointing out how to embed the video directly in the post)

Vodpod videos no longer available.

If one were dictator, how should one organize one’s rule to maximize one’s benefit (once one starts `oneing’ one must continue `oneing’ until the end of one’s sentence)? My instinct says one should essentially set up a free market (except perhaps in media) and tax the returns (presumably choose the optimal tax). In short, the optimal dictator stays out of commerce. However, this is not the way most dictators do it. Many of them decide to run their own commercial enterprises and use their monopoly on violence to hinder the competition. Why?

My colleague Daniel Diermeier suggests that it may have to do with the ability to tax. If tax collection is inefficient, the dictator would prefer direct control over the means of production. Yet another colleague, Mark Satterthwaite, suggests overreach. Dictators by their nature are prone to place more confidence in their own abilities than is warranted. A third explanation, from Roger Myerson, by way of Tim Feddersen, is that Dictators have henchman who must be rewarded for their loyalty. These rewards take the form of ownership of assets (although its not clear why you can’t just pay to keep the goons to stay in their barracks until needed).

Perhaps, we have examples of dictators of the variety I have in mind: Lee Kuan Yew. If so, why not more of them? That is, why do many of them choose to emulate Uncle Joe instead? Could the PRC be an example of a country moving to this form of dictatorship?

“Everything should be made as simple as possible, but no simpler.” – Einstein.

This is one of my favorite maxims. It is also a very difficult rule to follow, giving it a certain humor which was probably not lost on Einstein. How simple is too simple? Well, if adding just a little more detail reverses the analysis completely, it was too simple. Here’s an example from this weekend’s diversion, the NFL playoffs.

With 4:08 left in their game against the Packers, the Eagles faced 4th and goal, inches from the goal line. They trailed by 11. To win, they would either need to score a touchdown with two-point conversion and field goal (in either order), then win in overtime, or score two touchdowns. Eagles coach Andy Reid called timeout to think it over. What should he have done?

Announcer Troy Aikman argued that they should kick the field goal, saying that “you have to cut it to a one-possession game.” This is a classic example of what decision theorists call coarse decision-making. Aikman knows that it’s better to cut it to 5 or 3 than 8, but he simplifies the decision by considering 3, 5 and 8 to be similar to one another (in each case, one possession may suffice to tie or win) while they are very different from 11. Is his analysis good enough? No, it turns out he made it too simple, and in the wrong way.

Let me simplify it differently. I won’t even need the language of probability; I can put it purely in terms of verbal logic, perhaps a kind you could even explain on TV (almost). First, assume that if we score a touchdown now, the 2-point conversion will fail and the deficit will be 5 (this goes against the decision I’m advocating, so it’s an acceptable simplification.) Now, since we are going to be down at least 5, assume that we will get the ball back and score a touchdown; otherwise, our decision now is irrelevant. This makes it very easy to see which option is best right now:


If we kick a field goal, victory will depend on later converting the 2-pointer (from the 2-yard line), then winning in overtime.

If we go for it now, victory will depend only on making it now from inches away.


Would you rather try to score from 2 yards out for a tie, or try to score from inches away for a win? Looked at this way, it’s a total no-brainer. And of course, I ignored the fact that you might cut it to 3 if you score now, which gives you an even better chance to win. Andy Reid got this decision right (though one colleague, an Eagles fan, is harsh on him for needing a timeout to think about it, I find this forgivable.) The Eagles indeed scored a touchdown to cut the lead to 5, then were in position to go for the win later but were thwarted by an interception in the end zone.

What went wrong with Aikman’s simplification, or “coarsening”? One way to look at it is that he lumped the wrong scores together. His way of thinking comes very naturally, especially since one-possession vs. two-possession corresponds roughly to alive vs. dead, and this is how we tend to categorize probabilities. But in terms of win probability, an 8-point deficit is actually closer to 11 than it is to 5! If t is the probability of scoring a later touchdown, then if the deficit after this possession is

5, the probability of winning is t

8, the probability of winning is (roughly) .25t

11, the probability of winning is roughly 0.

This is based on a 50/50 chance at a two-point conversion (published figures vary) and a 50-50 chance at winning in overtime. These figures mean that it would be worthwhile to try for a touchdown even if it only worked 25% of the time (the actual figure is over 70%), and even if you never successfully cut the deficit to 3. It turns out it would be better to think of an 8-point deficit as “not quite dead” rather than “alive.”

This situation also relates to my previous entry “Risky Move.” In principle, all strategies are risky, and you should pick the one with the best chance of success. In practice, people think of the decision which resolves more of the uncertainty immediately as “risky,” and are biased against this decision. They sometimes then choose a slower, but more certain, death.

This is the most frustrating part in academic career: You come up with a cool idea, google around a bit for references, and discover that the Simpsons did it twenty years ago. It happened to Ronen and I recently when we were talking about computability of Nash equilibrium. Only thing left is to blog about it, so here we are.

A good starting point is the omitted paragraph from John Nash’ Thesis (scanned pdf), in which Nash motivates his new idea. The paragraph is not included in the published version of the thesis, it is not clear whether because of editorial intervention or Nash’ own initiative.

We proceed by investigating the question: What would be a rational prediction of the behavior to be expected of rational playing the game in question? By using the principles that a rational prediction should be unique, that the players should be able to deduce and make use of it, and that such knowledge on the part of each player of what to expect the others to do should not lead him to act out of conformity with the prediction, one is led to the concept of a solution defined before.

The `concept of a solution defined before’ is what every reader of this blog knows as Nash Equilibrium in mixed strategies. This paragraph is intriguing for several reasons, not the least of them is the fact, acknowledged by Nash, that Nash equilibrium of a game is not necessarily unique. This opens the door to the equilibrium refinements enterprise, which aims to identify the unique `rational prediction’: the equilibrium which the players jointly deduce from the description the game. The refinements literature seems to have gone out of fashion sometimes in the eighties (`embarrassed itself out’ as one prominent game theorist told me) without producing a satisfactory solution, though it is still very popular `in applications’.

Anyway, the subject matter of this post is another aspect of Nash’s argument, that the players should be able to deduce the prediction and make use of it. It is remarkable that Nash (and also von-Neumann and Morgenstern before him but I’ll leave that to another post) founded game theory not on observable behavior, as economics orthodoxy would have had it, but on unobservable reasoning process. How can we formally model reasoning process ? At the very least, the players should somehow contain the mixed strategies in their mind, which means that the strategies can be explicitly described, i.e that the real numbers that represent the probabilities of each actions are computable: Their, say, binary expansion should be the output of a Turing Machine. If this is the case then the player can also `make use’ of these mixed strategies: they have an effective way (that is, a computer program) that randomizes a strategy according to these strategies.

I hasten to say that while I refer to the agent’s mind, we must not be so narrow mindedly earth-bound as to assume our players are human beings. Our players might arrives from another planet, where evolution made a better job than what we see around us, or from another universe where the law of physics are different, or they may be the gods themselves. Species come and go, but concepts like rationality and reasoning — the subject matter of game theory — are eternal.

Well, Can the players contain the mixed strategies in their mind ? Are the predictions of game theory such that cognitive agents can reason about them and make use of them? Fortunately they are

Theorem 1 Every normal form game with computable payoffs admits a mixed Nash Equilibrium with computable mixed strategies.

My favorite way to see this is to using Tarski’s Theorem that real algebraic fields are elementary isomorphic (I also wrote about it here). Thus, Nash’s Theorem, being a first order statement, is also true in the field of computable real numbers.

The story does not ends here, though. Take another look at Nash’s omitted paragraph: Our players are not only supposed to be able to somehow hold the prediction in their minds and make use of it. They should also deduce it: Starting from the payoff matrix, one step after another, a long sequence of arguments, each following the previous one, should culminate in the `rational prediction’ of the game. You see where this leads: The prediction should be computable from the payoff matrix. Alas,

Theorem 2 There exists no computable function that get as input payoff matrix with computable payoffs and outputs a mixed Nash Equilibrium of the game.

Bottom line: Rational players can reason about and make use of Nash’s rational prediction, but they cannot deduce it. The prediction should somehow magically pop up in their minds. Here is a link to Kislaya Prasad’s paper where these theorems were already published.

A paper by Kraus et al in Psychological Science (as summarized by Pamela Paul in the Jan 2, 2011 NY Times), identifies an empathy gap between`rich’ and `poor’. In short the upper classes, are less able to read the emotions of others. Indeed, one of the authors is quoted as saying:

Upper-class people, in spite of all their advantages, suffer empathy deficits.

The explanation offered is that the lower classes, unable to simply pay people to do things, must rely on the kindness of friends and strangers to get things done.

One must be careful with newspaper summaries of the work of others. After all, journalists place a premium on writing for readers with the concentration of birds. So, it is possible many a nuance and detail were lost between the paper and the summary. Even with this in mind, the summary still peeved me.

1) The experiments involved subjects being asked to read the facial expressions of others. Why is the ability to read facial expressions necessarily a measure of empathy. Surely, words, tone, gestures matter as well. Perhaps, expressions that are easily mimicked are ignored by the upper classes given their long experience of the lower orders trying to conn  them out of their money (like one of the studies authors, I couldn’t resist grandiose speculation).

2) The term empathy deficit itself grates, suggesting that more empathy is better than less. There can be a surfeit of empathy.

3) There are some things that money can’t buy. Even the upper classes rely on the kindness of strangers  to make their way in the world. They call it networking!

I look forward to studies comparing the ability of the different classes to reduce compound lotteries, avoid the sunk cost fallacy, exhibit ambiguity aversion, hyperbolic discounting etc etc

I notice that no one has yet carried out similar studies comparing the left handed and the right handed on the same dimensions. See this 2006 column in Slate for why this might be worth pursuing.

In early December 2010 a proposition was made with the suggestion that “all public monies for the arts should cease… a better case could be made to fund professional wrestling—it’s what the working class enjoy.” It should not be difficult to google out the context in which this proposition was made, with its heavy bag of politics, religion and gender. But instead of digging out again those juicy details, it is also a good opportunity to re-think why public sponsorship of beauty is actually vital.

Public provision is typically deemed justified in cases of coordination or market failure. Vaccination is a classical example: if all kids but one are vaccinated against a particular disease, the parents of the remaining kid have little incentive to vaccinate her, since she would never catch that disease from her friends. But if all parents free-ride with the hope that others will vaccinate their children, then too few might actually do so. Hence schools mandate a certain vaccination schedule as a pre-requisite for admittance (exempting very few on religious grounds), and health services provide vaccinations for free for those who haven’t received them otherwise.

Against what disease does beauty immunize us? Thousands of years ago, our sweet tooth for hoarding fat was selected for, since fat and glucose were hard to get; likewise, our instinctive attraction to flickering movement was fit, because it meant either predator or prey. Today, however, our favorite greasy meals do not nourish our body, but rather make us obese and ill. Likewise, when we zap to the next glittering channel, website or chat-room we ride ever faster the roller-coaster of gratification; we produce more rapidly content that others consume, and the economy is growing. But all too often this content does not nourish our mind. It sums up to no more than zero-drift white noise, that makes us comfortably numb.

Beauty is the antidote to white noise. Beauty, in the sense meant here, is not in the eye of the beholder, not a matter of taste. The Taj Mahal, Bach’s ciaccona, the double helix, Godel’s incompleteness theorem don’t gratify us – almost the opposite: they arrest us. They strike us against our boundaries, against the inevitable necessity of the world, with tension, proportion, balance.

And when beauty strikes us, we wake up. We no longer just passively swallow the external sensations from the world. We begin to perceive the world actively. We willfully move not only towards the steepest gradient of pleasure, but also against our limits. This to-and-fro dance turns our sensations into sense, and some tasks emerge as meaningful challenges for us. At least for a while, we become entrepreneurs. And possibly, part of the challenge in our enterprise is not just to take advantage or to buy the time and effort of the people with whom we interact, but actually to engage with them and with their own enterprises.

Beauty cannot be provisioned in a decentralized market. Unlike with vaccinations, the problem has nothing to do with free riding. The point is that there is no way in which beauty can be marketed: there can be no promo to genuine surprise. We cannot form demand for an experience which will alter our outlook, because the new outlook makes no sense to us before we actually have it. Our only chance to have beauty is to commission it by a centralized, public initiative.

There is an additional important difference between vaccination and beauty. If a vaccination program is ever frozen but the disease bursts again, it is easy to de-frost the vaccines and start re-administering them. Beauty, in contrast, cannot be stored. Among all the books in the world that Google can scan for us there is no manual for beauty, because invigoration can be encapsulated in no formula. Beauty is always a living experience, and one can be apprenticed to beauty only by others who are already striving for it and have already been apprenticed. So if the sponsoring of beauty is ceased for a single generation, it might take many generations to restore. Unfortunately, many parts of the world have experienced such long, dull and dark periods.

It is true that funding beauty is extremely frustrating, because most of the time we get only second and third and fourth – rate imitation of beauty. The artists who wish to strike us with beauty all too often manage merely to provoke and unnerve us. In some better cases they manage only to confront us with the fractures of our era, but in a way that preempts any balancing catharsis. In worse cases we are handed pompous kitsch. And those scientists – they ask us for billions to build particle accelerators in which maybe, only maybe, they would be able to catch a glimpse of an elusive quark which would confirm the super-symmetry of the world.

But if we do not want to drown in white noise there is simply no alternative to the centralized funding of beauty. This is the only way to allow for few apprentices to eventually come up with beauty that would nourish our mind. And when this happens there is a slim chance that beauty will percolate further in society, as wide-eyed entrepreneurship is, after all, contagious.

And sometimes, just sometimes, beauty can actually pay off. Like when one college dropout Steve Jobs audited a calligraphy course, which he attested to be “beautiful, historical, artistically subtle in a way that science can’t capture”, so that ten years later he and his partners  “designed it all into the Mac.” Or when those physicists at the particle accelerator of CERN invented the internet only so as to share among themselves the huge amount of data, didn’t even think they should patent their invention, and delivered to the world more bang for the buck than could ever be imagined.

Kellogg faculty blogroll