Algorithmic Game Theory: The Next Decade

[RG # 123] Algorithmic Game Theory: The Next Decade

March 1 - August 31, 2011


Michal Feldman (Tel Aviv University)
Noam Nisan (The Hebrew University)

The last decade has seen the emergence and growth of a new interdisciplinary field of research often termed "Algorithmic Game Theory". This field lies at the crossroads of computer science, game theory, and economics; a combination which is necessary for addressing many of the challenges posed by the Internet. Not only is this field full of intellectual excitement internally, and not only has it already begun to intellectually influence the three parent disciplines, but it also has significant implications for the Internet, as evidenced by the large number of researchers in the field hired by Google, Yahoo, and Microsoft.

At the approximate age of ten years, it seems that the field of Algorithmic Game Theory is maturing. The goal of this group is to elucidate the main challenges of the field and attempt to chart the future course of the field for the next decade.

Some research topics that will be explored:

- Networks with contagious risk, the different aspects of how the evaluation of the Generalized Second Price mechanisms are used for selling ads on the Internet, and the understanding of the performance of simple auctions and modeling auctions used in practice (Eva Tardos)

- Interviewing in stable matching problems and cost-sharing mechanisms (Nicole Immorlica)

- Sketching valuation functions, the equilibria of simple market mechanisms, and optimal multi-item auctions (Noam Nisan)

- Auction design for agents with uncertain, private values (Anna Karlin)

- A general framework for computing optimal correlated equilibria in compact games, computing Nash equilibria of action-graph games via support enumeration, mechanical design and auctions, and computational equilibrium analysis of voting games (Kevin Leyton-Brown)

- Envy-free mechanisms for multiunit auctions with budgets, cost sharing games with capacitated network links, and game theoretic perspectives of the facility location problem (Michal Feldman)

- Bargaining in networks (Amos Fiat)




Michal Feldman

The Hebrew University of Jerusalem
Michal is a professor in the School of Business Administration and the Center for the Study of Rationality at The Hebrew University of Jerusalem.

Amos Fiat

Tel Aviv University
Amos is a professor in the School of Computer Science and the School of Mathematical Sciences at Tel Aviv University.

Noam Nisan

The Hebrew University of Jerusalem
Noam is a professor in the School of Computer Science and Engineering at The Hebrew University of Jerusalem.