Thursday, November 11, 2021

20 Years of Algorithmic Game Theory

Twenty years ago DIMACS hosted a Workshop on Computational Issues in Game Theory and Mechanism Design. This wasn't the very beginning of algorithmic game theory, but it was quite the coming out party. From the announcement

The research agenda of computer science is undergoing significant changes due to the influence of the Internet. Together with the emergence of a host of new computational issues in mathematical economics, as well as electronic commerce, a new research agenda appears to be emerging. This area of research is collectively labeled under various titles, such as "Foundations of Electronic Commerce", Computational Economics", or "Economic Mechanisms in Computation" and deals with various issues involving the interplay between computation, game-theory and economics.

This workshop is intended to not only summarize progress in this area and attempt to define future directions for it, but also to help the interested but uninitiated, of which there seem many, understand the language, the basis principles and the major issues.

Working at the nearby NEC Research Institute at the time I attended as one of those "interested but unititated."

The workshop had talks from the current and rising stars in the field in both the theoretical computer science, AI and economics communities. The presentations included some classic early results including Competitive Analysis of Incentive Compatible Online Auctions, How Bad is Selfish Routing? and the seminal work on Competitive Auctions

Beyond the talks, just having the powerhouse of people at the meeting, established players, like Noam Nisan, Vijay Vazirani, Eva Tardos and Christos Papadimitriou, with several newcomers who are now the established players including Tim Roughgarden and Jason Hartline just to mention a few from theoretical computer science. 

The highlight was a panel discussion on how to overcome the methodological differences between computer scientists and economic game theorists. The panelists were an all-star collection of  John Nash, Andrew Odlyzko, Christos Papadimitriou, Mark Satterthwaite, Scott Shenker and Michael Wellman. The discussion focused on things like competitive analysis though to me, in hindsight, the real difference is between the focus on models (game theory) vs theorems (CS). 

Interest in these connections exploded after the workshop and a new field blossomed.

4 comments:

  1. The workshop that attracted me into Algorithmic Game Theory took place about a year later, in Cambridge, UK
    Topics in computer communication and networks
    I think that's when AGT came to Europe. Some of the well-known people in the area attended it.

    ReplyDelete
  2. Do CS people and Economists work TOGETHER on this?
    Did they overcome the methological differences?
    Have useful things come out of the study?
    I ask non-rhetorically as always

    ReplyDelete
  3. Hi Bill,

    This Simons program, in Fall 2019, will probably answer your question:
    https://simons.berkeley.edu/programs/market2019

    A book on the same topic, co-edited with Federico Echenique and Nicole Immorlica, and including over 50 authors, coming from both disciplines, will be published by CUP early next year.

    ReplyDelete
  4. @gasarch - yes, it wasn't too hard once I figured out that "exogenous" means "forming part of the input data" :-)

    ReplyDelete