IEOR 8100 Topics in OR: Economics and Computation (Fall 2014)

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 Readings (Tentative; a bit too ambitious):

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.

·         Irving, Stable Marriage and Indifference, Discrete Applied Mathematics, 1994.

·         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

Lectures (will update as we go along):

PART I: STABLE MATCHINGS AND APPLICATIONS

  • Lecture 2 (Thu 4/9): Stable Matchings: basic properties of the deferred-acceptance algorithm.