Instructor: Jay Sethuraman (Office hours: Fridays 10-12, and by appointment.)
Time/location: TR 11:40-12:55 PM in Mudd 317.
Course description: Advanced topics at the intersection of economics and computation (broadly interpreted). Topics include an extensive treatment of stable matchings and applications; house allocation problems and extensions; computational aspects of social choice; black-box reductions in algorithmic mechanism design; revenue maximization in single and multi-parameter settings (tentative).
Prerequisites: Some exposure to optimization, algorithms, and probabilistic reasoning.
Course requirements: Problem sets (probably 3 or 4) should be completed by all students. In addition, I may ask students to lead the discussion of the research papers and to make a presentation during the second half of the course. Students taking the course for credit are also required to complete a course project: this could be a survey of recent research in an area or an attempt at formulating new research questions or working on open research problems (details TBA).
Topics and
PART I: STABLE MATCHINGS: THEORY AND
APPLICATIONS
·
Gusfield/Irving, The Stable Marriage Problem: Structure and Algorithms, 1989.
·
Roth/Sotomayor, Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis,
1992.
·
Knuth, Stable
Marriage and its Relation to Other Combinatorial Problems, 1976.
·
Gale/Shapley, College Admissions and
the Stability of Marriage, Amer.
Math. Monthly, 1962.
·
Roth/Rothblum/VandeVate, Stable
Matchings, Optimal Assignments, and Linear Programming, Math. Oper. Res,
1993.
·
Teo/Sethuraman, The
Geometry of Fractional Stable Matchings and its Applications, Math. Oper. Res.,
1998.
·
Roth/Vande Vate, Random
Paths to Stability in Two Sided Matching, Econometrica, 1990.
·
Balinski/Baiou, The Stable Allocation (Or Ordinal Transportation) Problem,
Math. Oper. Res., 2002.
·
Hatfield/Milgrom, Matching
with Contracts, American Economic
Review, 2005.
·
Kojima/Manea, Axioms for Deferred Acceptance,
Econometrica, 2010.
·
Erdil/Ergin, What’s
the matter with tie-breaking, American
Economic Review, 2008.
·
Tan, A
necessary and sufficient condition for the existence of a complete stable matching,
Journal of Algorithms, 1991.
·
·
Fleiner, A
Fixed-Point Approach to Stable Matchings and Some Applications, Math. Oper. Res., 2003.
·
Adachi, On
a characterization of stable matchings, Economics
Letters, 2000.
·
Subramanian, A new approach
to stable matching problems, SICOMP,
1994.
·
Feder, A new
fixed point approach for stable networks and stable marriages, JCSS, 1992.
·
Fleiner/Kamiyama, A matroid
approach to stable matchings with lower quotas, SODA 2012.
·
Echenique, Contracts versus
Salaries in Matching, American Economic Review, 2013.
·
Kominers,
·
Sonmez (extensions)
·
Parag (Survey)
·
Sonmez and Abdulkadiroglu (survey)
·
Featherstone
·
Azevedo/Leshno
·
Abdulkadiroglu, Che, Yasuda?
·
Kelso and Crawford,
·
Crawford and Knoer, Job Matching with
Heterogenous Firms and Workers, Econometrica, 1981.
·
Demange, Gale, and Sotomayor, Multi-Item
Auctions, Journal of Politcal Economy, 1986.
·
Kelso and Crawford, Job
Matching, Coalition Formation, and Gross Substitutes, Econometrica, 1982.
·
Gul and Stacchetti, Walrasian Equilibrium with
Gross Substitutes, Journal of Economic Theory, 1999.
PART II: HOUSE ALLOCATION
·
Leonard
·
Hylland and Zeckhauser
·
Zhou
·
Sonmez and Abdulkadiroglu
·
Bogomolnaia and Moulin (2 papers)
·
Recent papers: BM, Rastegari
·
Shapley Scarf
·
Sonmez survey
PART III: COMPUTATIONAL ASPECTS OF
SOCIAL CHOICE
·
Arrow’s theorem and Gibbard-Satterthwaite’s
theorem
·
Domain restrictions: single-peakedness, etc.
·
Kalai-Muller, Kalai-Muller-Satterthwaite
·
Conitzer and others
PART IV: ALGORITHMIC MECHANISM
DESIGN: BLACK-BOX REDUCTIONS
PART V: REVENUE-MAXIMIZATION IN
SINGLE AND MULTI-PARAMETER SETTINGS
· Myerson (optimal auctions)
· Border,
· Che, Kim, and Mirrendorf, Border’s theorem and generalizations
· Hart and Nisan, Approximate Revenue Maximization with Multiple Items, EC 2012.
· Manelli and Vincent, Bundling As An Optimal Selling Mechanism For A Multiple-Good Monopolist, JET 2006
· Cai, Daskalakis, and Weinberg, Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization, FOCS 2012
· Alaei, Fu, Haghpanah, Hartline, Malekian, Bayesian Optimal Auctions via Multi- to Single-agent Reduction, EC 2012