Games, Economics and Algorithms (Fall 2019)
Time and Location:
Tuesday 14:00-16:00, room 136, building 90.
Wednesday 14:00-16:00, room 125, building 90.
Instructor: Sigal Oren
Office hours: Tuesday 10:00-12:00, room 220 (building 37)
Syllabus (Notice the changes from previous years)
Textbooks
The course will not follow a specific textbook. However, some of the material is covered in the following two books:
"Algorithmic Game Theory" (AGT book)
Exercises
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) 16/10 - Openning lecture
2) 17/10 - Extensive form games
3) 23/10 - Strategic form games, MaxMin Strategies, Nash equilibria. (videos of a game show where participants play prisoners dilemma 1 2),
4) 24/10 - Zero-sum games.
5) 31/10 - Mixed Nash Equilibria, Non-Atomic routing games.
6) 6/11 - Non-Atomic routing games bounds on the price of anarchy.
7) 7/11 - Non-Atomic Routing - Group work - network over provision
8) 14/11 - Congestion games: potential function.
9) 20/11 - Congestion games: price of stability.
10) 21/11 - Congestion games: price of anarchy, smoothness.
11) 27/11 - Network cost sharing: price of stability, strong equilibrium, strong price of anarchy.
12) 28/11 - Group work - Selfish Load Balancing.
13) 4/12 - Selfish load balancing - equilibrium existence. Walrasian equilibrium - definition.
14) 5/12 - Walrasian equilibrium - first welfare theorem, existence in unit demand auctions.
15) 11/12 - Mechanism design without money 1 - faculty location.
16) 12/12 - Mechanism design without money 2, group work on facility location.
17) 18/12 - Guest lecture by Oren Roth - Top Trading Cycle
18) 19/12 - Mechanism Design single parameters domain - 2nd price auction, public project.
19) 25/12 - Single Parameter Domain 1.
20) 26/12 - Single Parameter Domain 2 + Group work on ad auctions.
21) 1/1 - Multi parameter domains- VCG, Multi unit auctions.
22) 2/1 - Multi unit auctions, Maximal in Range.
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.