Wednesday, October 31, 2007

New Book : Algorithmic Game Theory

I recently received my "desk copy" of the new book Algorithmic Game Theory, edited by Nisan, Roughgarden, Tardos, and Vazirani.

While I haven't read it cover-to-cover yet, I'm very impressed by the book. It's taken a large area with a fairly short history, and broken it up into reasonable-sized chunks each written by an expert, with most chunks covering a new and active research area. For example, Michael Kearns writes about Graphical Games, Christos Papadimitriou explains the complexity of finding Nash equilibria, Jon Kleinberg discusses cascading behavior in networks and the corresponding economic issues, Ramesh Johari and David Parkes and Joan Feigenbaum and so many others have chapters on their specialties, and so on. Overall I count 45 contributors! The result is a solid tome that really combines breadth and depth to create a resource that I assume works well for people working in the area and is certainly useful for an outsider trying to look in and see what's going on. There are also exercises in some chapters; it could certainly be used as a textbook.

I'd like to see other books of this form, built up by a coalition of experts to cover emerging areas. You do lose something with this approach -- for example, many concepts are defined multiple times in various chapters, and while the authors have made an effort pointing out relations among chapters, you don't really have the sense of coherence you get from most textbooks or books about research written by a single author. On the other hand, you do get a much broader coverage of topics than you'd probably see from a single-author textbook, and I assume that it was easier to spread the workload among authors. It's not clear to me any single author (or group of 3-4) could have put something like this together in any reasonable amount of time. Kudos to the editors (and authors).

What other topics could benefit from a treatment like this?


Anonymous said...

(i) Coding theory and applications in CS.

(ii) Data streams.


Anonymous said...

Excellent. Now, how do I get *my* desk copy of Algorithmic Game Theory?