Algorithmic Game Theory
Objectives:
Over the last few years there has been explosive growth in the research done at the interface of computer science, game theory and economic theory, largely motivated by the emergence of internet. This course treats algorithms for equilibria in games and markets, computational auctions and mechanism design, the “price of anarchy”, as well as applications in networks, peer-to-peer systems, security, information markets and more.
Skills:
With the successful attention of the class, the student is expected to be able to:
- recognize algorithmic problems of game theory,
- model them, and
employ suitable algorithms to solve them
Prerequisites:
It is good for the undergraduate student to have attended the undergraduate course on Game Theory. The basic notion of Nash equilibrium, in its various forms (concurrent actions, extended games, repeated games, probabilistic games) will be presented also through this course.
Content:
• Basic solution concepts and computational issues
o Complexity of finding Nash equilibriums in two player games, in strategic and extended forms. Combinatorial algorithms.
• Algorithmic mechanism design
o Mechanism design without money. Combinatorial auctions. Profit maximization. Distributed algorithms. Cost sharing. Online mechanisms
• Quantifying the inefficiency of equilibria
o Routing games. Selfish load balancing. The price of anarchy.
• Applications
o Communication networks. Peer-to-peer systems. Cascading behavior in networks. Information security. Prediction markets. Manipulation-resistant reputation systems. Sponsored search auctions.
Textbooks:
1. N. Nisan, N. Roughgarden, E. Tardos and V.V.Vazirani, Algorithmic Game Theory. Cambridge University Press2007.
2. David Easley and Jon Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press, 2010.
Assessment:
• 50% written exams
• 50% projects (3 distinct projects)
