Kira Goldner
About
Research
Teaching
Service
Resources
Blog


DS 574: Algorithmic Mechanism Design
Fall 2023
Boston University

Course Details

Instructor: Professor Kira Goldner (goldner@).
Office Hours: Tuesday 3:30–4:30pm and by appointment.
Office Location: CCDS 1339 (665 Comm Ave).

Teaching Fellow: Peiran Xiao (pxiao@).
Office Hours: TBD
OH Location: TBD.

Lectures:
Tuesday/Thursday 1:30—3:15pm, KCB 107.

Important Links:

Course Description: This course is an introduction to the interdisciplinary area of Algorithmic Mechanism Design: where computational perspectives are applied to economic problems, and economic techniques are brought to problems from computer science. We will explore a broad range of topics at the frontier of new research, starting with some of the fundamentals, such as welfare-maximizing auctions and types of Nash Equilibria. Throughout the semester, the class will also learn about prevalent topics such as (1) Data Science & Incentives, (2) Mechanism Design for Social Good, and (3) optimization and robustness in mechanism design.

The course is aimed at graduate students but will be accessible to motivated advanced undergraduate or masters students with some background in proofs (DS 122), algorithms (DS 320), and probability (MA 581).

Homework: Biweekly homeworks will be posted on Piazza when they become available. Homework must be typed up using LaTeX; here is a quick resource on LaTeX and here is a LaTeX template you may use for the homework. Here is another short guide to LaTeX. You may find it easier to use Overleaf.

Lecture Schedule

Below is a table with that will reflect what we cover in each lecture and will point to corresponding reading material. Lectures listed more than one date in advance are tentative topics. There is no required textbook for this course, as all materials are available online for free and we will switch between materials. Some shorthand for the reading material:

  • R1.x = Tim Roughgarden's AGT lecture notes, lecture x. (Alternatively available in book form here.)
  • R2.x = Tim Roughgarden's AMD lecture notes, lecture x.
  • Hx = Jason Hartline's textbook "Mechanism Design and Approximation," chapter x.
  • Kx = Anna Karlin's textbook "Game Theory, Alive," chapter x. (Also in book form.)
Resources listed are optional, and often multiple versions of the same material are listed so that you can find what is best suited to you.

Date Topic Resources
Sep 5 Overview and Policies, Intro to AGT Slides, Worksheet, R1.1-2
Sep 7 Incentive Compatibility R1.3
Sep 12 The Revelation Principle R1.4, H2
Sep 14 Myersonian Virtual Welfare R1.5, H3.3
Sep 19 Ironing Virtual Values and Quantile Space H3.3.3-4
Sep 21 Ironing Intuition, Multidimensional Settings and VCG R1.7
Sep 26 Ascending Auctions I R2.1-2
Sep 28 Ascending Auctions II & Walrasian Equilibria R2.2-3,5
Oct 3 Recap and Big Picture
Oct 5 LP Duality I: Primals, Duals, Weak Duality
Oct 10 NO CLASS (Monday schedule)
Oct 12 LP Duality II: Strong Duality, Complementary Slackness, Welfare
Oct 17 LP Duality III: Lagrangian Duality CDW STOC '16
Oct 19 LP Duality IV: Algorithmic Rev Max
Oct 24 LP Duality V: Approximate Revenue Maximization CDW STOC '16
Oct 26 Projects & Prophet Inequalities Projects, R1.6
Oct 31 Prior Independence: Bulow-Klemperer & Single Sample R1.6, H5.2-3
Nov 2 Gains from Trade in Two-Sided Markets BGG '20
Nov 7 Mechanism Design for Social Good: Health Insurance Markets EGW '20
Nov 9 Mechanism Design for Social Good: Kidney Exchange
Nov 14 Mechanism Design for Social Good: COVID Testing and the Research-to-Practice Pipeline (Francisco J. Marmolejo Cossío) LMCJRGGBVTAL '21, LMCMP '22
Nov 16 Interdependent Values I
Nov 21 Interdependent Values II
Nov 23 NO CLASS (Thanksgiving)
Nov 28 Selling Separately or Bundling R2.18, BILW '14, CDW '16
Nov 30 Carbon Auctions
Dec 5 Project Presentations
Dec 7 Project Presentations



Huge gratitude to Jason Hartline and Tim Roughgarden for their publicly available materials which have made the development of this course possible.