Topics in Algorithmic Game Theory
Credit Points: 3.0
Hours: 3 lecture
Instructor: Ahuva Mu’alem (ד”ר אהובה מועלם)
Prerequisites: Data Structures and Introduction to Algorithms (61145 and 61213, or equivalent).
Following the development of the Internet computer scientists have begun to take an interest in economics and game theory. Game theory deals with the analysis of strategic situations which involve players with conflicting interests and attempts to answer questions such as what the best strategy is for each participant and how to predict the outcome of a given game.
The purpose of the course is to review a variety of topics related to the interplay amongst three areas: economics, game theory and computer science. For example, in 2006, more than 95% of Google’s profits come from selling keywords in search engine advertising platforms. Additionally, eBay is a leading consumer-to-consumer platform developed by a programmer. Bitcoin is a new emerging electronic currency. All these computerized platforms can be seen as auctions or economic mechanisms.
The course will include lectures enlarging on the relevant theory and discussing related practical applications.The course begins with a short introduction to game theory. We will then review a variety of classic topics and contemporary issues. The final part of the course will be devoted to presentations by students.
1. Introduction to Game Theory
2. Price of Anarchy and Braess’s paradox
3. Social Choice and Arrow’s Impossibility result
4. Auction Theory and Mechanism Design
5. Internet search engine advertising
7. Computation of Nash Equilibria and Sperner’s Lemma
9. Fair allocations of network bandwidth, cake cuttings and rental Harmony
- David Easley and Jon Kleinberg., Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press, 2010. (Free version here)
- Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani., Algorithmic Game Theory, Cambridge University Press, 2007.(Free version here)