Games, Economics and Algorithms (Fall 2020)
Time and Location:
Monday 10:00-12:00, room 240, building 90.
Wednesday 10:00-12:00, room 5, building 34.
Instructor: Sigal Oren
Office hours: Monday 14:00-16:00
Important: Please read the Syllabus
Textbooks
The course will not follow a specific textbook. However, some of the material is covered in the following two books:
"Algorithmic Game Theory" edited by Nisan, Roughgarden, Tardos and Vazirani (AGT book)
"Networks, Crowds, and Markets" by Easley and Kleinberg
Exercises (Online submission using the CS Submission)
1) Exercise 1 due by 2/12 (20:00).
2) Exercise 2 due by 16/12 (20:00).
3) Exercise 3 due by 7/1 (20:00).
4) Exercise 4 due by 24/1 (20:00).
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) 28/10 - Introduction
2) 30/10 - Extensive Form Games.
3) 4/11 - Strategic form games, MaxMin Strategies, Nash equilibria. (videos of a game show where participants play prisoners dilemma 1 2)
4) 6/11 - zero-sum games, mixed strategies.
5) 11/11 - Non-Atomic Routing games.
13/11 - Canceled
6) 18/11 - Non-Atomic Routing games+ group work.
7) 20/11 - Congestion Games, Potential function and Price of Stability.
8) 25/11 - Congestion games, smoothness
9) 27/11 - Solution concepts: Mixed Nash equilibrium, Correlated equilibrium, Coarse correlated equilibrium.
10) 2/12 - Coarse correlated equilibrium and external regret minimization
11) 4/12 - Network cost sharing games
12) 9/12 - Selfish Load Balancing - Group work
13) 11/12 - Walrasian Equilibrium, Existence for unit demand valuations.
14) 16/12 - Walrasian Equilibrium continued + endowed equilibrium.
15) 18/12 - Facility location.
16) 23/12 - Facility location continuous + house allocation problem.
17) 25/12 - Single Parameter domain 1.
18) 30/12 - Single Parameter domain 2.
19) 1/1 - Group Work - Ad Auctions.
20) 6/1 - Multi parameter domains- VCG, Multi unit auctions.
21) 8/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.