Algorithmic Mechanism Design (Fall 2013)

When: Thursdays, 14:00-15:45.

Where: Ziskind 1.

Instructor: Shahar Dobzinski (dobzin@gmail.com)

Please register to the Google group of the course.

Textbook

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

Exercises

• 1. Exercise 1. Due 21/11. (slightly updated 1/11)

  2. Exercise 2. Due 5/12.

  3. Exercise 3. Due 26/12. New deadline: 28/12. See the google group for a discussion of q3.

  4. Exercise 4. Due: 16/1. Corrected Q1 (8/1) and clarified Q2 (14/1).

  5. Exam. Due: 2/3. Please check the google group frequently. Updated Q1, Q2 (22/2).

Lectures

1. Games theory and computer science, introduction to game theory, basics of auction design.

2. Basics of auction design, a comparison of second and first price auctions.

3. The revelation principle, basic properties of truthful mechanisms, revenue equivalence.

4. Virtual valuations, Myerson theorem, some alternatives to Myerson.

5. Correlated distributions and the lookahead auction.

6. VCG.

7. Combinatorial auctions with single minded bidders.

8. Multi-unit auctions.

9. Multi-unit auctions, characterizations and computational efficiency, Roberts theorem.

10. Weak monotonicity, proof of Roberts theorem.

11. Unrelated machine scheduling.

Tentative Topics

1. Basics of game theory and auction design.

2. Single item auctions.

3. Revenue maximization in single item auctions.

4. Combinatorial auctions.

5. The VCG mechanism.

6. Incentives and computational considerations.

7. Characterizations of truthful mechanisms.

8. Generalized second price auctions.