Required Text: readings will be from Approximation in Economic Design manuscript.
Lectures: Tuesday and Thursday 12:30-1:20 in Tech L170.
Instructor: Jason D. Hartline.
Office Hours: Wednesday 1:00-1:50, or by appointment; Ford 3-329.

Textbook: Approximation in Economic Design [pdf]

Announcements:

  • Final exam is due Wednesday 12/7/11 at 4pm. [final]

Homework:

  • Homework 1: exercises 2.2, 2.3, 2.5, 3.1, 3.2; due Tuesday, 10/18/11.
  • Homework 2: exercises 4.2, 4.4, 4.5, 5.1, 5.3; due Tuesday, 11/8/11.
  • Homework 3: [hw3]; due Thursday, 12/1/11.

Overview. This course combines game theory and economics with algorithms. Algorithms studies simple processes for finding optimal or near optimal solutions to complex optimization problems. The output of an algorithm is often an allocation of resources, e.g., which edges in a graph are in the shortest path or which tasks can be scheduled on a computer server. Game theory and economics study the outcome of systems of selfish agents, each optimizing their own objective. Algorithmic mechanism design combines the two fields and looks to find simple processes that result in good allocations of resources even when the input to these processes are provided by selfish agents who may try to game the system to get a more favorable outcome for themselves. These settings of selfish agents are especially relevant in computer networks such as the Internet. Unfortunately, optimal mechanisms are almost never simple enough to be implemented in practice, therefore, this course develops techniques for designing and analyzing simple mechanisms that approximate the optimal ones. From a computer science perspective, this course can be views as adding game theory to standard settings for approximation algorithms. From an economics perspective, this course can be viewed as adding approximation to standard settings in auction theory and mechanism design.

Prerequisites. Prior experience with algorithms or game theory is recommended.

Grading. 60% Problem sets, 15% Midterm, 25% Final, 3% classroom participation (bonus).

Homework Policy. Homeworks may be done in pairs. Both students must contribute to the solution of all problems. One copy of the assignment should be turned in with the names of both students on it. Both students will receive the same grade. You may consult the text book and course notes when answering homework questions; you must not consult the Internet or research papers.

Exam Policy. Exams will be take-home, open book, open notes. You may not consult other students or the Internet in the preparation of your solutions.

Schedule.

  • Week 1: Mechanism Design Overview
    • Topics: mechanism design, approximation, first-price auction, second-price auction, lottery, posted-pricings
    • Reading: Chapter 1.
  • Week 2: Equilibrium
    • Topics: Bayes-Nash equilibirum, dominant strategy equilibrium, single-dimensional agents, revenue equivalence, revelation principle, incentive compatibility.
    • Reading: Chapter 2.
  • Week 3: Optimal Mechanism Design
    • Topics: single-dimensional mechanism design, surplus-optimal mechanism (VCG), revenue-optimal mechanism (Myerson), revenue curves, virtual values, ironing.
    • Reading: Chapter 3.
  • Week 4: Bayesian Approximation
    • Topics: reserve pricing, prophet inequalities, matroids, monotone hazard rate distributions.
    • Reading: Chapter 4.
  • Week 5: Prior-independent Approximation
    • Topics: Bulow-Klemperer, single sample mechanism, digital goods.
    • Reading: Chapter 5.
  • Week 6: Prior-free Approximation
    • Topics: envy-free pricing (benchmark), random sampling auction, profit extraction, lower bounds.
    • Reading: Chapter 6.
  • Week 7: Multi-dimensional Preferences
    • Topics: unit-demand preferences, lotteries, sequential posted pricing.
    • Reading: Chapter 7.
  • Week 8: Computational Tractability
    • Topics: approximation algorithms, greedy-by-value, BIC blackbox reductions, payment computation.
    • Reading: Chapter 8.

     

[cover]

Image: Picasso's Bull, December 1945 -- January 1946.

more news