Introduction to Algorithmic Game Theory (Spring 2015)

When: Sundays, 12:15-14:00.

Where: Ziskind 1.

Instructor: Shahar Dobzinski (dobzin@gmail.com)

TA: Keren Cohavi (keren.cohavi@weizmann.ac.il)

Please register to the Google group of the course.

Textbook

The course will not follow a specific textbook but "Algorithmic Game Theory" might serve as a useful reference sometimes.

Exercises

• 1. Exercise 1. Due 12/4.

  2. Exercise 2. Due 26/4. Updated 20/4 (typo in 2c).

  3. Exercise 3. Due 19/5.

  4. Exercise 4. Due 7/6. Bonus question 2(e) is cancelled.

  5. Exercise 5. Due 28/6.

  6. Exam. Due 19/7.

Lectures

1. Game theory and computer science, introduction to game theory.

2. Congestion games, price of anarchy and price of stability.

3. Smoothness, price of anarchy bounds for congestion games via smoothness, selfish load balancing.

4. Selfish load balancing (cont.).

5. Network formation games.

6. Single item auctions, VCG.

7. Combinatorial auctions and single minded bidders.

8. Multi-unit auctions: incentives and computation.

9. Finish multi-unit auctions, small world.

10. Small world.

11. Technology diffusion.

12. Friendship paradox and balance theory.

Tentative Topics

1. Basics of game theory.

2. Congestion games.

3. The price of anarchy and the price of stability.

4. Single item auctions.

5. Combinatorial auctions.

6. The VCG mechanism.

7. Incentives and computational considerations.

8. Social networks.