EECS 510 - Algorithmic Mechanism Design
Recommended Text: Nisan, Roughgarden, Tardos, and Vazirani, Algorithmic Game Theory, Cambridge, 2007. [order from amazon.com][download pdf]
Lectures: Tuesday and Thursday 11:00-12:20, Tech MG28.
Instructor: Jason D. Hartline.
Announcement and Discussion Board: amd-08 [at] googlegroups.com
Overview. As the Internet has developed to become the single most important arena for resource sharing among parties with diverse and selfish interests, traditional algorithmic and distributed systems approaches are insufficient. To prevent undesirable Internet phenomena such as spam in email systems, bid-sniping in eBay's auction marketplace, free-loading in file-sharing networks, and click-fraud in Internet advertising; game-theoretic and economic considerations from auction theory must be applied. Algorithmic Mechanism Design merges the computational considerations of algorithm and system design with the considerations of the Economics subfield of Mechanism Design. The2007 Nobel Prize in Economics was awarded to Hurwicz, Maskin, and Myerson, for their foundational work in Mechanism Design recognizing it as fundamental to the field of Economics. Likewise, algorithmic mechanism design is fundamental to the study of computer systems and networks.
This course provides an in-depth study of topics in the interface of theoretical computer science and the economics subfield of mechanism design. This course will survey foundational mechanism design theory (including the Nobel prize winning work), it will study computational issues in economic settings, and will discuss the role of algorithmic techniques in economic design and analysis. Motivating applications will be taken from the design of Internet services such as auctions, advertising, and reputation systems.
Prerequisites. Discrete math, probability, or statistics, e.g., EECS 310 (Mathematical Foundations of Computer Science). Algorithms, e.g.,EECS 336 (Introduction to Algorithms), is recommended but not necessary.
Grading. 10% classroom participation and 90% homework and projects.
- Week 1: Mechanism Design Overview
- Topics: Vickrey auction, Vickrey with reserve, path auctions, single-minded combinatorial auctions, computation in MD, approximation in MD, surplus, profit.
- Reading: , [2: Section 1], and [3: Section 1].
- Week 2: Single-Parameter Mechanism Design, VCG, and Computation.
- Topics: single-parameter agents, surplus maximization, Vickrey-Clarke-Groves (VCG) mechanism, Lehmann-O'Callaghan-Shoham (LOS) mechanism, approximation mechanisms.
- Reading: [2: Sections 2 and 3], , and .
- Homework: give a constant approximation mechanism for Knapsack Auctions.
- Week 3: Bayesian Mechanism Design
- Topics: Bayes-Nash quilibrium, Bayesian incentive compatibity, revelation principle, expected profit maximization.
- Reading: [3: Section 2] and .
- Homework: choose a project topic, discuss with instructor.
- Week 4: Bayesian Mechanism Design (cont)
- Topics: expected profit maximization, revenue equivalence, all-pay auctions.
- Reading: , , and  (optional: ).
- Homework: read papers for project; comment on .
- Week 5: Prior-Free Mechanism Design
- Topics: prior-free optimal mechanism design, digital goods auctions, profit benchmarks, deterministic lower bounds.
- Reading: [3: Section 3], [AGT: Chapter 13, Sections 1-4], , and .
- Homework: read papers for project; comment on  and .
- Week 6: Prior-Free Mechanism Design (cont.)
- Topics: profit extraction, random sampling auctions, lower bounds, mechanism design decision problems.
- Reading: [3: Section 3], [AGT: Chapter 13, Sections 1-4],  and .
- Homework: start project research; comment on  and .
- Week 7: Online Mechanism Design
- Topics: online auctions, expert learning, multi-armed bandit learning.
- Reading: [3: Section 4], [AGT: Chapter 16, Chapter 4],  and .
- Homework: continue project research; comment on  and .
- Week 8: Guest Lecture and Online Pricing (cont.)
- Guest Lecture (Tuesday, May 20th): Rakesh Vohra on Matching Markets.
- Topics (Thursday, May 22nd): multi-armed bandit learning, online pricing.
- Reading: [AGT: Chapter 16],  and .
- Homework: continue project research; comment on .
- Week 9: Structured Procurement
- Topics: path auctions, spanning tree auctions, matroids, frugality.
- Reading: [AGT: Chapter 13, Section 5], , , and .
- Homework: continue project research; comment on .
- Week 10: Multi-Parameter Mechanism Design
- Topics: VCG, combinatorial auctions, query models, weak monotonicity, random sampling auctions, algorithmic pricing.
- Reading: [AGT: Chapter 9, Sections 3-5; Chapter 11, Sections 4-6; Chapter 13, Section 3.3], , , , and .
- Homework: finish project research; comment on .
- 2007 Nobel Prize in Economics [overview.pdf] [details.pdf]
- Roughgarden, "Lecture Notes on Combinatorial Auctions" [ps]
- Hartline, "Lecture Notes on Optimal Mechanism Design" [pdf]
- Nisan, Ronen, "Algorithmic Mechanism Design", 2001. [pdf]
- Lehmann, O'Callaghan, and Shoham, "Truth Revelation in Approximately Efficient Combinatorial Auctions", 2002. [link]
- Myerson, "Optimal Auction Design", 1981. [link]
- Bulow and Klemperer, "Auctions Versus Negotiations", 1981. [link]
- Elkind, "Designing And Learning Optimal Finite Support Auctions", 2007. [pdf]
- Vickrey, "Counterspeculation, Auctions, and Competitive Sealed Tenders", 1961. [link]
- Goldberg, Hartline, Karlin, Saks, and Wright, "Competitive Auctions", 2006. [pdf]
- Hartline and McGrew, "From Optimal Limited to Unlimited Supply Auctions", 2005. [pdf]
- Baliga and Vohra, "Market Research and Market Design", 2003. [link]
- Feige, Flaxman, Hartline, and Kleinberg, "On the Competitive Ratio of the Random Sampling Auction", 2005. [pdf]
- Abrams, "Revenue Maximization when Bidders Have Budgets", 2006. [pdf]
- Blum and Hartline, "Near-Optimal Online Auctions", 2005. [pdf]
- Hajiaghayi, Kleinberg, and Parks, "Adaptive Limited Supply Online Auctions", 2004. [pdf]
- Babaioff, Immorlica, Kleinberg, "Matroids, Secretary Problems, and Online Mechanisms", 2007. [pdf]
- Karlin, Kempe, Tamir, "Beyond VCG: Frugality of Truthful Mechanisms", 2005. [pdf]
- Cary, Flaxman, Hartline, Karlin, "Auctions for Structured Procurement", 2008. [pdf]
- Balcan, Blum, Hartline, Mansour, "Mechanism Design via Machine Learning", 2005, [pdf]
- Dobinski, Nisan, Shapira, "Truthful Randomized Mechanisms for Combinatorial Auctions", 2006. [link]
- Gurusuami, Hartline, Karlin, Kempe, Kenyon, McSherry, "On Profit-Maximizing Envy-Free Pricing", 2005, [pdf]
- Balcan, Blum, "Approximation Algorithms and Online Mechanisms for Item Pricing", 2007, [pdf]
- Hartline, "Lecture Notes on Frugality" [pdf]
- Week 3 (April 17th): projects chosen.
- Week 5 (May 1): project survey paper due (suggested: 5-10 pages).
- Week 8 (May 22): project draft due (suggested: 8-15 pages).
- Week 11 (June 13): final paper due (suggested: 8-15 pages).