Imagine devising a set of rules for a game such that the dominant strategy of every player is to truthfully reveal their valuations and/or strategies: this is just one of the ambitious goals of mechanism design, the science of rule-making and the most useful branch of game theory. Fifteen years ago, a pioneering paper of Nisam and Ronen (Algorithmic Mechanism Design) merged it with computer science by including the requisite that computations should also be reasonably tractable for every involved player: this created a fruitful field of research that contributed every tool of algorithmics and computational complexity, from combinatorial optimization and linear programming to approximation algorithms and complexity classes.
In practice, Algorithmic Mechanism Design is also behind the successes of the modern Internet economy: every ad-auctions uses it results, like Google’s DoubleClick auctions or Yahoo’s Auctions, and peer-to-peer networks and network protocols are being designed under its guiding principles. It has also contributed to spectrum auctions and matching markets (kidneys, school choice systems and medical positions) and it has also generated interesting models, like the first one that justifies the optimality of the fee-setting structure of real estate agents, stock brokers and auction houses (see Fee Setting Intermediaries).
Up until a decade ago, the only way to learn this fascinating field of research was by venturing to read papers dispersed between the areas of economics, game theory and computer science, but this changed in 2008 with the publication of the basic textbook of the field, [amazon_link id=“0521872820” target=“_blank” ]Algorithmic Game Theory[/amazon_link], also available online:
Now a bit dated, it has recently been complemented with some great resources:
- [amazon_link id=“0199570515” target=“_blank” ]The Handbook of Market Design[/amazon_link], of which the part I have liked the most is the one on experiments.
- The online courses of Tim Roughgarden, a real master on choosing and presenting the best proofs of this field: Algorithmic Game Theory and Frontiers in Mechanism Design.
- The on-going writing of a more specific book, Mechanism Design and Approximation
And that’s enough to begin with: hundred of hours of learning insightful research with fantastic applications!