Games, Networks and Algorithms (Fall 2016)
Time and Location:
Tuesday 14:00-16:00, room 238 (building 90)
Thursday 12:00-14:00, room 239 (building 90)
Instructor: Sigal Oren
Office hours: Tuesday 10:00-12:00, room 220 (building 37)
Textbooks
The course will not follow a specific textbook. But, some of the material is covered in the following two books:
"Algorithmic Game Theory" (AGT book)
Exercises
1. Exercise 1 - Due 26/11 (submission on CS online system)
2. Exercise 2 - Due 22/12 (submission on CS online system)
3. Exercise 3 - Due 5/1 (submission on CS online system)
4. Exercise 4 - Due 21/1 (submission on CS online system)
Lectures
(When applicable, I'll add references that discuss similar material. These references will not include all the material that was taught in class and may cover other material or use different notations, proof techniques, etc. )
1. 26/10 - Introduction + basic game theory (related article to the friendship paradox)
2. 28/10 - Non-Atomic Routing Game - definition, price of anarchy and over provisioning.
3. 4/11 - Atomic Routing Game - equilibrium existence, potential games, price of stability.
4. 6/11 - Atomic Routing Game - price of stability (continuation), price of anarchy + smooth games.
Some of the material in lectures 2,3,4 is covered in Chapter 18 of the AGT book. Also, lecture notes 11,12,13 from Tim Rougharden's class cover similar topics.
5. 10/11 - Facility Location Game - definition + Potential function.
6. 12/11 - Facility Location Game - price of anarchy + solution concepts.
The Facility location game is also covered in Chapter 19.4 of the AGT book and lecture note 14 from Tim Rougharden's class
7. 17/11 - solution concepts, robust price of anarchy for smooth games, selfish load balancing
8. 19/11 - Selfish load balancing - price of anarchy for pure and mixed equilibria, Network cost sharing.
9. 24/11 - Introduction to mechanism design - single item auctions, truthfulness and monotonicity in single-parameter domains.
10. 26/11 - Single-minded bidders - approximations and truthfulness.
11. 1/12 - Ad Auctions
12. 3/12 - Multi-parameter settings - weak-monotonicity and VCG.
13. 8/12 - Taxation Principle, Walrasian equilibrium and combinatorial auctions with unit demand bidders.
14. 10/12 - Ascending auction for unit demand bidders, auction ends with minimal Walrasian equilibrium prices.
15. 15/12 - Unit demand bidders - Minimal Walrasian prices equal VCG prices.
16. 17/12 - Multi-Unit auctions.
17. 22/12 - Unrelated machine scheduling
18. 24/12 - Mechanism design without money
19. 29/12 - Canceled
20. 31/12 - Mechanism design without money.
21. 5/1 - Small World (1)
22. 7/1 - Small World (2)
23. 12/1 - Random Graphs models and Preferential Attachment.
24. 14/1 - Web Search - HITS and PageRank.
25. 19/1 - Epidemics - branching process and influence maximization.
26. 21/1 - Influence maximization.
Tentative topics:
1. Basic game theory: Solution concepts for modeling the interaction between strategic players (for example, Nash equilibrium).
2. Price of anarchy: The ways strategic behavior of agents can deteriorate the performance of systems and how we can (sometimes) mitigate this.
3. Mechanism design and algorithmic mechanism design: Designing auctions that are efficient both from an economic perspective and from a computational perspective.
4. Social Networks: Game theoretic models of behavior in networks, Properties of social networks and the principles driving them, Cascading behavior in networks