Games, Economics and Algorithms (Fall 2018)
Time and Location:
Tuesday 14:00-16:00, room 233, building 90.
Thursday 12:00-14:00, room 134, building 90.
Instructor: Sigal Oren
Office hours: Thursday 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)
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. 24/10 - Opening lecture
2. 26/10 - Extensive form games, Chomp, Strategic form games. (videos of a game show where participants play prisoners dilemma 1 2)
3. 31/10 - MaxMin Strategies, Nash equilibria.
4. 2/11 - Mixed Strategies.
5. 7/11 - Non-Atomic Routing Games - Bounding the Price of Anarchy - reference
6. 9/11 - Non-Atomic Routing - Group work - network over provision
7. 14/11 - Congestion games - Potential functions and Price of Stability.
8. 16/11 - Congestion games - Price of Stability and Price of Anarchy.
9. 21/11 - Facility location games - definition and existence of pure Nash eq. via potential function/
10. 23/11 - Facility location games - Price of Anarchy.
11. 28/11 - Solution Concepts - Mixed Nash equilibrium, correlated equilibrium, coarse correlated equilibrium.
12. 30/11 - Robust price of anarchy, learning coarse correlated equilibrium.
13. 5/12 - Learning - Multiplicative weights.
14. 7/12 - Selfish Load Balancing - Group work + convergence of max weight best response to a Nash equilibrium.
15. 12/12 - Network Cost Sharing
16. 14/12 - Mechanism Design with no money - Facility Allocation.
17. 19/12 - Mechanism Design with no money - The House Allocation problem.
18. 21/12 - 2nd price auction and single parameter domains.
19. 26/12 - Single parameter domains - single minded bidders
20. 28/12 - Comments about Exercise 2, Group work: Ad auctions.
21. 2/1 - VCG + Walrasian Equilibrium
22. 4/1- Multi-Unit Auctions
23. 9/1 - Multi-Unit Auctions + Unrelated Machine Scheduling
24. 11/1 - Group work Scheduling + Comments about ex 3 q2.
25. 16/1 - Present bias 1
26. 18/1 - Present bias 2
Tentative Topics
1) Basic game theory: we will discuss some solution concepts for modeling the interaction between strategic players (for example, Nash equilibrium).
2) Price of anarchy: we will discuss 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: we will learn to design auctions which are efficient both from an economic perspective and from a computational perspective.
4) Advanced topics: time permitting, we will discuss some topics in the interface of behavioral economics and computer science. We will also see some examples of incentives in computer science including Bitcoin and Peer to Peer networks.