Google's auction for TV ads (and some thoughts on Practice and Theory)

Noam Nisan at Algorithmic Game Theory posts a preliminary version of his paper Google's auction for TV ads.

It is part of a post titled AGT and practice, which is worth reading along with the paper. In the paper, Nisan and his coauthors first describe the Google system and some of its requirements, then outline a (too) simple model (an ascending auction of the Demange, Gale, Sotomayor line), and then discuss ways in which the model is too simple.

All of this made me think of writing a post sometime called "Practice and Theory." I don't know that I have enough to say on that right now, but the main idea would be to reflect on some of the ways that market design, and the theoretical work that supports it, differ from traditional (theoretical) game theory.

In a traditional theory paper, a problem is presented, along with a model of that problem, and an exact solution. Producing such a paper is a bit like finding a fixed point: in the course of proving the theorem, it may be necessary to adjust the model, and the statement of the theorem, and perhaps the definition of the problem, in order that the parts all fit together properly.

In a market design paper, in contrast, the problem and to a large extent the model may be fixed in advance, and so what has to be adjusted is the solution. Sometimes an exact solution can't be found (perhaps an impossibility theorem shows that there is no exact solution), and instead some sort of approximate solution is found. Traditional theorists sometimes look at the results and say that they don't look like a good theory paper, which should find an exact solution. Part of our job as market designers, and theorists who do market design, is to help explain this difference.