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).
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.
· Sonmez (extensions)
· Parag (Survey)
· Sonmez and Abdulkadiroglu (survey)
· 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
· Hylland and Zeckhauser
· 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)
· 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
Lectures (will update as we go along):
PART I: STABLE MATCHINGS AND APPLICATIONS