Algorithmic Game Theory (Spring 2017)

Time and Location:

Thursday 12:00-14:00, room 104 (building 28)

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 book:

Exercises

1. Exercise 1 - due 23/4

2. Exercise 2 - due 14/5

3. Exercise 3 - due 5/6

4. Exercise 4 - due 25/6

Lectures

1. 16/3 - Introduction + basic game theory (Slides).

2. 23/3 - Atomic Routing Games, Potential Games.

3. 30/3 - Atomic Routing Games, Price of Stability and Price of Anarchy for linear cost functions.

4. 20/4 - Smooth Games + Selfish Load Balancing.

5. 27/4 - Network Cost Sharing.

6. 4/5 - Mechanism Design without money - facility location + top trading cycle

7. 11/5 - Auctions and single parameter domain.

8. 18/5 - Single parameter domain 2 - public project, single minded bidders.

9. 25/5 - VCG, Multi-unit Auctions.

10. 1/6 - Maximal in Range Mechanisms, Multi-unit Auctions.

11. 8/6 - Time Inconsistent Planning 1 - naive agents

12. 15/6 - Time Inconsistent Planning 2

13. 22/6 - Time Inconsistent Planning - sophisticated agents.

Tentative topics:

1. Price of anarchy : The ways strategic behavior of agents can deteriorate the performance of systems and how we can (sometimes) mitigate this.

2. Mechanism design and algorithmic mechanism design: Designing auctions which are efficient both from an economic perspective and from a computational perspective.

3. Incentives in Computer Science: We will briefly discuss some of the following topics: behavioral economics and computer science, incentives in: Bitcoin, Peer-to-Peer networks and BGP and kidney exchange.