2021FA_COMP_SCI_496-0_SEC4 Special Topics in Computer Science: Mechanism Design

Mechanism Design
Fall 2021, Northwestern U.

Required Textbook: Hartline, Mechanism Design and Approximation, manuscript, 2014-2021.
Lectures: TuTr 9:30-10:50am, Ford ITW.
Instructor: Jason D. Hartline
Office Hours: Seeley Mudd 3015, TBA.
Announcements and Discussion: Campuswire
Collaborative Reading: Perusall
Peer Review: PeerPal

Synopsis: This course studies the design of mechanisms to mediate the interaction of strategic individuals so that desirable outcomes are attained. A central theme will be the tradeoff between optimality of an objective such as revenue or welfare 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 class focuses on techniques for performing this analysis, economic conclusions, and consequences for practice. The class will follow the textbook manuscript at: http://jasonhartline.com/MDnA/. 

The class discussion and exercises will focus on theoretical analyses with the aim of preparing students for research in mechanism design.

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

Grading: 40% problem sets, 30% peer review, 30% exams, 5% classroom participation (bonus).

Homework Policy: Homeworks are to be done in pairs. Both students must contribute to the solution of all problems. Only one copy of the assignment should be turned in. 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.  It is recommended to type up solutions in LaTeX (e.g. overleaf.com) or Markdown (e.g. hackmd.io), see Latex Hints.

Peer Grading: Students will be participating in a peer grading mechanism.  In part, this is to get some experience with a designed mechanism.  Peer reviews should be done according to the published Peer Reviewing Guide (with Grading Rubric).

Academic Integrity: Students in this course are required to comply with the policies found in the booklet, "Academic Integrity at Northwestern University: A Basic Guide". All papers submitted for credit in this course must be submitted electronically unless otherwise instructed by the professor. Your written work may be tested for plagiarized content. For details regarding academic integrity at Northwestern or to download the guide, visit: https://www.northwestern.edu/provost/policies/academic-integrity/index.html

COVID-19 Policies: Students, faculty, and staff must comply with University expectations regarding appropriate classroom behavior, including those outlined below and in the COVID-19 Code of Conduct.  If a student fails to comply with the COVID-19 Code of Conduct or other University expectations related to COVID-19, the instructor may ask the student to leave the class. The instructor is asked to report the incident to the Office of Community Standards for additional follow-up.  Faculty staff, and students are required to wear masks and to quarantine on positive COVID-19 testing.

Class Recordings: This class or portions of this class will be recorded by the instructor for educational purposes. Your instructor will communicate how members of the class can access the recordings. Portions of the course that contain images, questions or commentary/discussion by students will be edited out of any recordings that are saved beyond the current term.

Tentative Schedule:

• Week 1: Mechanism Design and Approximation Overview
  • Topics: mechanism design, approximation, philosophy thereof, 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, BNE characterization, revenue equivalence, uniqueness, 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), amortized analysis, virtual values, ironing, revenue curves, revenue linearity.
  • Reading: Chapter 3.
• Week 4: Bayesian Approximation
  • Topics: reserve pricing, posted pricing, prophet inequalities, correlation gap, 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: Bayes-Nash Approximation
  • Topics: first-price auction (asymmetric distributions), simultanious composiotion, "price of anarchy", "smoothness" paradigms.
  • Reading: Chapter 6.
• Week 7: Multi-dimensional and Non-linear Preferences (part 1)
  • Topics: single-agent pricing, revenue linearity, marginal revenue mechanism, interim feasibility, convex optimization.
  • Reading: TBA.
• Week 8: Multi-dimensional and Non-linear Preferences (part 2)
  • Topics: single-agent pricing, revenue linearity, marginal revenue mechanism, interim feasibility, convex optimization.
  • Reading: TBA.
• Week 9: Multi-dimensional Preferences (Approximation)
  • Topics: unit-demand preferences, marginal revenue mechanism, correlation gap, approximate revenue linearity, single-dimensional representative environments, reduction to single-dimensional pricing.
  • Reading: Chapter 7.
• Week 10: Computational Tractability
  • Topics: approximation algorithms, greedy-by-value, BIC blackbox reductions, payment computation.
  • Reading: Chapter 8.