Notes to Self: Algorithmic Game Theory

Algorithmic Game Theory is the name given to a subfield where computer science and game theory overlap. The idea is to use the tools of algorithm design and analysis to try and understand economic problems, chiefly as they appear on the internet. The field is about ten years' old, and there is already a codification of the first big results in these two books:

"Algorithmic Game Theory" (Cambridge University Press)

"Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations" (Yoav Shoham, Kevin Leyton-Brown)

There are ample web resources on the topic as well. These computer scientists love the bloggery.

Here are a few courses on the subject:

Tim Roughgarden's Algorithmic Game Theory course at Stanford.

Another course at Stanford, this time on adwords and search.

Éva Tardos's course from Cornell

Kousha Etessami's course from Edinburgh, much more elementary than the first two.

I'll add more as I find them.

One question is how the tools and concepts of Algorithmic Game Theory overlap with Velupillai's Algorithmic Economics, which I'm working on at the moment, and with the Algorithmic Information Theory results of people like Gregory Chaitin, and the Probability and Finance work of Shafer and Vvok. Very cool, new, and fertile crossover point from computer science to game theory to economics, all in an algorithmic (and in that sense, computable) fashion.

Key Papers (I'll add to this list as I read more)

Nissan, Algorithms for Selfish Agents

Koutsoupias and Papadimitriou Worst-case Equilibria

Akcoglu, Aspnes, et al, Graph-theoretic auctions

Papadimitriou and Yannakakis, Bounded Rationality and Computational Complexity

Singh Kearns and Mansour Nash Convergence of Gradient Dynamics in General-Sum Games


My slice of pizza has a lot of links and comments on the personalities behind many of the AGT advances.

2 Replies to “Notes to Self: Algorithmic Game Theory”

Comments are closed.