May 10, 2010
Why Nash Might Not Be So Bad

Can you name a constructive use of the Nash equilibria concept? I’m not talking about things that are covered under the von Neumann minimax result, which has had an obvious impact on multiple, disparate things (LP Duality and Yao’s Theorem, to name a couple). I’m talking about a real 3+ player game outside of the laboratory where someone is playing a Nash equilibrium strategy and doing well with it.

Give up? The only research in this line I’ve seen is my good buddy Sam’s work on poker. Many poker bots use equilibrium (or nearly equilibrium) strategies for their heads-up (two player) play (you can find out more about poker bots at Alberta’s poker bot research site). However, Sam also is interested in three-player research, which ventures beyond the minimax result into dark waters. Here’s some of his work on equilibrium play in three-person tournaments. But more significantly, in his online play (and he’s one of the best single-table tournament players in the world), Sam incorporates these Nash equilibrium calculations into how he plays his endgames.

What about poker makes it amenable to the Nash concept? Here’s a hypothesis: In complex, real-world games where collusion is not allowed, Nash equilibria coincide with “good strategies”.

Now, there’s no justification for such a result at all — it’s not like the Nash equilibria have any peculiar special power. I think that it’s a combination of three things:

  • That playing Nash means you won’t be directly and straightforwardly exploited.

  • That collusion is forbidden, meaning teams of opponents will not exploit you.

  • Poker is so difficult and challenging that pretty much any strategy in which you’re not being directly exploited is a reasonable one — though given the enormous state space of the problem, finding something not directly exploitable is harder than it sounds.

A concept proves its mettle by its constructive use in the real world, and in this respect I think that poker research, particularly if it’s a poker bot playing Nash that ends up being able to win no-limit multi-player tournaments, represent the best hope for the Nash concept. Do you know of any other constructive uses of Nash equilibria?

1:51pm  |   URL: http://tmblr.co/ZtlAMyZ0KoT
(View comments) 
Filed under: AI economics 
April 20, 2010
Prospect Theory and the Weather

Prospect theory is a descriptive utility concept. Though the wikipedia page makes it seem complex, the idea is essentially that people treat gains and losses differently, reacting more sensitively to losses than to gains. Okay, sure, that seems pretty straightforward. But what makes the idea subtle is that it induces a path dependence that runs counter to traditional notions of utility: two people in the same state can have wildly different utilities just based on the path they took to get there.

What’s interesting is the way that opinions about weather seem to validate this kind of path dependence. Unlike utility, which is essentially a fictional conceit, weather is externally verifiable and (to a large extent totally) objective.

The best illustration of prospect theory in weather is June Gloom, a phenomenon which describes increased early summer cloudiness in (southern) California. June Gloom is real: looking at San Diego’s weather, you can see the dip where the city is about 10% cloudier in May and June. But not only is Pittsburgh cloudier than San Diego in June (58% to 55%), Pittsburgh’s sunniest month is cloudier than every single month in San Diego. But of course there’s no wikipedia page for “Perpetual Pittsburgh Gloom”.

Prospect theory implies a heightened sensitivity to the downside; put another way, the best way to make a bad outcome seem better is to compare it to something even worse. Check out this wonderful line from Buffalo’s wikipedia page:

Buffalo has a reputation for snowy winters, but it is rarely the snowiest city in New York State.

See? It’s not that bad.

6:02am  |   URL: http://tmblr.co/ZtlAMyVwfo4
(View comments) 
Filed under: economics 
April 13, 2010
The Problem with 2-D Thinking

When I took undergraduate macro, I was deluged with graphs, lines, and intersections. Problems would be introduced, lines drawn (almost always from SW to NE and from NW to SE, with the occasional vertical or horizontal line thrown in there for good measure), the lines shifted, and those problems “solved”. At first, I fought hard to figure out what was going on from first principles and then trying to translate that back to the graphs — difficult because economists insist on swapping the axes of all their plots. Eventually though, I was worn down enough that I just stopped seeing the axes. By the final I was blindly moving curves “to the left” or “up” without any regard to the significance of what I was doing.

The problem with this isn’t what you’d expect. It’s not the fact that I did a terrible job of learning some simple models. And it’s not the simplicity of those models themselves — there’s an awful lot you can represent well in two dimensions. The problem is the intrinsic structure of two dimensions — of only having one variable to adjust — encourages thinking that moving to an equilibrium is somehow profoundly easy.

After all, in two dimensions, the notion of an equilibrium from intersecting lines is straightforward. Just follow the gradient, duh. But once you start expanding the number of variables, and those variables start interacting in funny ways, this idea falls apart. Surprisingly, maybe even shockingly, adjusting the prices of over-demanded things up and the prices of under-demanded things down does not lead to equilibrium generally, even “in the long term” and even for reasonably well-behaved and well-defined preferences.

While the idea of instantaneous equilibrium — that at every single instant of time everything is in General Equilibrium — has fallen out of favor, the notion that the economy is “equilibrium seeking” in a way that moves things “close to an equilibrium” in the “long term” is pervasive. Paul Krugman, in his gushing New Yorker profile says this:

“Economics is really about two stories. One is the story of the old economist and younger economist walking down the street, and the younger economist says, ‘Look, there’s a hundred-dollar bill,’ and the older one says, ‘Nonsense, if it was there somebody would have picked it up already.’ So sometimes you do find hundred-dollar bills lying on the street, but not often—generally people respond to opportunities. The other is the Yogi Berra line ‘Nobody goes to Coney Island anymore; it’s too crowded.’ That’s the idea that things tend to settle into some kind of equilibrium where what people expect is in line with what they actually encounter.”

The notion of settling into an equilibrium is simple, straightforward, and natural: reinforced with every graph you draw on a white board. And it’s only when you start trying to compute an equilibrium using gradients that you find out it doesn’t actually work. Strangely enough, they don’t teach that in undergraduate macro.

12:05pm  |   URL: http://tmblr.co/ZtlAMyUw2L2
(View comments) 
Filed under: economics 
April 5, 2010
Why Solution Concepts Don’t Work

On the face of it, solution concepts seem like a useful tool. You’re making some assumptions when you talking about behavior, and solution concepts let you lock in those assumptions and then treat them formally.

The issue, of course, is that you take this enormous space of what could happen in an interaction, and choose to focus only on what your model says will happen. And most perversely, we seem to actively encourage models which are as specific as possible; the best models are those which promise unique solutions. This dimensionality reduction is a brittle process that leads to ridiculous, counter-intuitive, and empirically false results (like the Revenue Equivalence Theorem).

Essentially, current approaches are maximally specific, but one thing we know from AI is that you can produce much more accurate predictive models by being maximally general. Say you have some history about the way people are behaving. The least specific model that is consistent with this history, the one with maximum entropy, will almost certainly be the best predictor of actual behavior. My favorite demonstration of maximum entropy is Brian Ziebart’s video from his research on predicting the destination of drivers. As an analogy, consider that current solution concepts would just say “He’s going to the airport” and leave it at that.

We should strive for robust models, and you can’t get robustness without embracing uncertainty.

12:37am  |   URL: http://tmblr.co/ZtlAMyTfC_1
(View comments) 
Filed under: economics AI 
April 1, 2010
What is Constructive Economics?

Constructive Economics is the design, construction, implementation, and analysis of new economic structures. It’s about building things, making them real, and treating them as solid objects worthy of respect, admiration, study, and further improvement. Above all else: make it real.

Less Talk, More Rock

So what does making it real look like?

Most profoundly, it involves the rejection of most equilibrium analysis and game theory. Game theory is only relevant inasmuch as it gives prescriptions for the strategy that you should be playing — like the minimax result for two-player zero-sum games and dominant strategies generally. To presume precisely how other people will behave is arrogant.

A canonical work in Constructive Economics would include the design, implementation, and analysis of a novel structure. Of course, such projects take a lot of time (and often, money) to implement, so making them real may not be directly feasible. But we should also embrace descriptions of practical systems that could be implemented, where here practical means a workable solution to an issue people are actually encountering. Research that might apply to auctions, doesn’t. At the same time, just because a market already exists shouldn’t exempt it from study. Markets should be regarded as natural phenomena, and their outputs should be subject to the Scientific Method. Just how do markets work, anyway?

Now let’s talk about what isn’t constructive:

  • Making real stuff is not the same as discarding un-real stuff. Work that describes what’s not possible should be treated warily. Oftentimes, such impossibilities are driven by modeling assumptions that don’t hold in practice. It’s much better to observe something actually happening in the real world and work back from that (e.g., The Rural Hospital Theorem)

  • Constructive Economics rejects the developing movement which argues that people are best modeled as perfectly rational agents that can’t solve NP hard problems. This is grafting two unrealistic paradigms on top of one another, producing a Frankenstein of shitty modeling.

Where Do We Go From Here?

Constructive Economics means embracing new fields. We need to pay more attention to details that are usually ignored, like interaction interfaces, which can have huge impacts on results. Furthermore, some of the most innovative economic structures of the last decade have emerged from outside the academic community, on Wall Street. Nobody in Computer Science writes papers on new kinds of mortgage bonds or interest rate swaps — but why not? Can’t we make a better VADM?

It also means abandoning some of the things we’ve traditionally regarded as sacrosanct. Rationality flies right into the garbage the moment you start seriously looking at the behavior of real people. Common knowledge of joint probability distributions? Half the people using your market don’t even know what a probability distribution is. Independent private valuations? Hell, even I’ve bid twice in an eBay auction. Worst-case bounds and hardness results? You might be surprised to find out how powerful CPLEX is.

There’s lots of overlap with these ideas and other parts of Econ/CS: Behavioral game theory and average-case analysis, to name a couple. What makes Constructive Economics different? Back to the first dictum: make it real. When I think about traditional, non-constructive, economic thinking, the image I find most appropriate is that of “lecturing birds on flying”. Birds already fly pretty well. Let’s start building airplanes.

6:05pm  |   URL: http://tmblr.co/ZtlAMyTCYj8
(View comments) 
Filed under: economics