Thursday, September 26, 2013
Jason Hartline writes:
Please share the following announcement:
*** Online Self-study on Mechanism Design and Approximation ***
To enroll: go to course page on Piazza and enroll as a student.
Synopsis. This course is a self-study course based on the manuscript "Mechanism Design and Approximation" which is based on a graduate course that has been developed at Northwestern over the past five years. Over the fall quarter we will work through roughly one chapter per week. The week will start with students reading and discussing the material of the chapter and it will conclude with students working together to solve and write up solutions to the chapter exercises. The textbook is in final draft and your comments and suggestions will help improve the book for future students.
Excerpt from Chapter 1: Our world is an interconnected collection of economic and computational systems. Within such a system, individuals optimize their actions to achieve their own, perhaps selfish, goals; and the system combines these actions with its basic laws to produce an outcome. Some of these systems perform well, e.g., the national residency matching program which assigns medical students to residency programs in hospitals, e.g., auctions for online advertising on Internet search engines; and some of these systems perform poorly, e.g., financial markets during the 2008 meltdown, e.g., gridlocked transportation networks. The success and failure of these systems depends on the basic laws governing the system. Financial regulation can prevent disastrous market meltdowns, congestion protocols can prevent gridlock in transportation networks, and market and auction design can lead to mechanisms for allocating and exchanging goods or services that yield higher profits or increased value to society.
This text focuses on a combined computational and economic theory for the study and design of mechanisms. A central theme will be the tradeoff between optimality and other desirable properties such as simplicity, robustness, computational tractability, and practicality. This tradeoff will be quantified by a theory of approximation which measures the loss of performance of a simple, robust, and practical approximation mechanism in comparison to the complicated and delicate optimal mechanism. The theory provided does not necessarily suggest mechanisms that should be deployed in practice, instead, it pinpoints salient features of good mechanisms that should be a starting point for the practitioner.