Mechanism Design Reading Group

Logistics

Time: Thursdays 10am - noon.

Location: We meet in Gates 498, except for:

10/18 : Gates 459
11/1 : Gates 453a

Food: You are responsible for bringing food to the meeting the week before your talk. Take the receipt to Wendy (across from Tim's office) for reimbursement.

Instructions

Please read the papers before each meeting as this will make for a more interesting discussion. If you are presenting, make sure to meet with Tim early in the week to go over details of your talk and what points you want to emphasize. Also, each speaker is encouraged to propose a relevant research problem, and we will schedule an ad-hoc time on friday to meet and explore it in more depth.

Relevant General References:

Algorithmic Game Theory(username=agt1user, password=camb2agt) Chapters 9, 11, 12

Schedule

Week 1 [Oct 4] (Tim)
- Overview of reading group themes.
- Review of the VCG mechanism and various issues with it (complexity, communication, revenue, etc.).
- Introduction to various characterization questions.
- Main reference: Noam's intro AGT chapter.
Week 2 [Oct 11]: Single-parameter problems (Shaddin/Peerapong).
- Part I: Archer-Tardos characterization.
- Part II: Applications: upper and lower bounds for scheduling problems (AT01), sponsored search with non-separable CTRs (Aggarwal et al EC 06), maybe more.
- Review chapters 9.3, 9.5, and 12.2 in AGT.
- Additional reference: Chapter 12 in Algorithmic Game Theory
Week 3 [Oct 18]: Revenue-maximization in single-parameter problems (Bayesian). (Ian/Nathan)
- Part I: Myerson's characterization of Bayesian incentive-compatible single-item auctions. Comparison to Archer-Tardos characterization. (Reference: Hartline/Karlin AGT chapter.) If time: brief discussion of Ledyard's EC 07 paper.
- Part II: Algorithmic pricing (Chawla/Hartline/Kleinberg, EC 07).
No meeting on Oct 25.
Week 4 [Nov 1]: Combinatorial auctions: Positive Results. (Nikola/Qiqi)
- Part I: Lavi/Swamy FOCS '05.
- Part II: Dobzinski et al STOC 06 paper.
Week 5 [Nov 8]: Combinatorial auctions: negative results. (Arik/Aneesh)
- Part I: Nisan's ICALP 02 paper.
- Part II: Dobzinski/Nisan STOC '07 paper.
Week 6: [Nov 15]: Multi-parameter machine scheduling. (Alex/Arash)
- Part I: Nisan/Ronen STOC '99, Christodoulou et al SODA '07.
- Part II: Lavi/Swamy, EC '07.
No meeting Nov 22.
Week 7 [Nov 29]: Characterizations: Roberts' Theorem. (Shahar/ Mukund)
- References: Roberts' original paper, two simplified proofs of Roberts' theorem, Lavi/Mu'alem/Nisan, Vohra 2007 working paper.
Week 8: [Dec 6] (Tim) More on characterizations (e.g. Saks/Yu EC 05) and wrap-up/conclusions.