Required Text: readings will be from Approximation in Economic Design manuscript.
Textbook: Approximation in Economic Design [pdf]
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.
Image: Picasso's Bull, December 1945 -- January 1946.