Reference Text: Approximation in Economic Design manuscript.
Seminar meetings: Tuesday 3:00-5:50 in Tech M177.
Instructor: Jason D. Hartline.
Office Hours: by appointment; Ford 3-329.
Discussion: nu-amd-2012 [at] googlegroups.com
Overview. This course topic is in the intersection of 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. Course readings will be taken from the economics literature on mechanism design and the computer science literature on algorithmic mechanism design.
Prerequisites. Prior experience with algorithms, game theory, and economics is recommended (E.g., from EECS 395/495 Algorithmic Mechanism Design)
Grading. 30% survey paper, 30% research paper, 20% class presentation, 10% class participation. 10% paper summaries
Course work. All prepared course work shall be turned in by email to the course instructor by midnight unless otherwise specified.
- Paper summaries: either (a) a one paragraph summary of the paper including the abstract model considered and main result(s) or (b) description of a main result and a "followup" research question not answered in the paper. Paper summaries are due by the start of class.
- Participation: ask and answer questions during class, contribute to discussion of papers.
- Presentation: prepare a presentation on an assigned paper and lead discussion. presentations should be 20-30 minutes (not including discussion). Presentations should clearly state the model, the results, the significance, and intuition for the results (perhaps by proof sketch). Papers will be presented in pairs and the students presenting paired papers should work together to ensure that their presentations are consistent.
- Survey Paper: students should prepare a survey paper (at least 10 pages) summarizing an area related to the course readings. Surveys should cover at least 5 papers at least 3 of which were not assigned in the course readings. Surveys should present a cohesive, integrated summary of the topic area. Proposals due January 22 (Sunday); papers due Feb 12.
- Research Paper: students should prepare an original research paper preferably on a topic related to their survey paper. Final papers should be written using the ACM format. Proposals due February 19; first-drafts due March 4; final-drafts due March 11.
Collaboration Policy. Papers and other course work may be done in pairs. Only one copy of work done in pairs should be turned with the names of both students on it.
- Week 1: Approximation via Independence
- Qiqi Yan "Mechanism Deign via Correlation Gap" 2011. [arxiv]
- Saeed Alaei "Bayesian Combinatorial Auctions: Expanding Single-buyer Mechanisms to Many Buyers" 2011. [arxiv]
- Week 2: Independence in the Limit
- Jackson, M. O. and H. F. Sonnenschein "Overcoming incentive constraints by linking decisions" 2007. [JSTOR]
- Armstrong. "Price discrimination by a many‐product firm" 1999. [JSTOR]
- Week 3: Unit-demand Pricing
- Chawla, Malec, and Sivan, "The power of randomness in Bayesian optimal mechanism design" 2011. [arxiv]
- Cai and Daskilakis, "Extreme-Value Theorems for Optimal Multidimensional Pricing" 2011. [arxiv]
- Week 4: Computation
- Dughmi and Roughgarden, "Black-box Randomized Reductions in Algorithmic Mechanism Design" 2010. [pdf]
- Lavi and Swamy, "Truthful and Near-optimal Mechanism Design via Linear Programming" 2005. [pdf]
- Week 5: Correlation
- Cremer and Mclean. "Full Extraction of the Surplus in Bayesian and Dominant Strategy Auctions" 1988. [JSTOR]
- Dobzinski, Fu, and Kleinberg "Optimal Auctions with Correlated Bidders are Easy" 2011. [arxiv]
- Week 6: Implementation
- Jackson "A crash course in implementation theory" 2001. [springer]
- Bergemann and Morris "Robust Mechanism Design" 2005. [JSTOR]
- Week 7: Cross-reporting
- Azar, Chen, and Micali, "Crowdsourced Bayesian Auctions" [pdf]
- Caillaud and Robert "Implementation of the revenue-maximizing auction by an ignorant seller" 2005. [springer]
- Week 8: Exchanges
- Myerson and Satterthwaite "Efficient Mechanisms for Bilateral Trading" 1983. [sciencedirect]
- Loertscher and Niedermayer, "Fee Setting Intermediaries: On Real Estate Agents, Stock Brokers, and Auction Houses" 2008. [pdf]
- Weak 9: Budget Feasibility / Frugality
- Bei, Chen, Gravin, and Lu, "Budget-feasible mechanisms via Random Sampling" 2011.[arxiv]
- Kempe, Salek, Moore, "Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts" 2010. [arxiv]
Image: Picasso's Bull, December 1945 -- January 1946.