i

IEORE 8100: Matching markets and algorithms

Instructor. Yuri Faenza, IEOR Department, Columbia University. Contact.

Important: if you are NOT a Ph.D. student and would like to take the class for credit, write to the instructor.

Schedule. (still tentative): Tue-Thu, 2:40pm-3:55pm, 480 Computer Science Building.

Content. In matching markets, we have a set of agents that want to sell/buy/exchange goods. Each agent has a preference pattern describing how much she likes other agents or good, and the goal is to find an assigments of goods to agents as to maximize a certain objective function, or as to satisfy certain constraints. Matching marktes arise, for instance, in school allocation, job placement, and refugee resettlement problems.
Matching markets go beyond classical matching problems, where typically a feasible solution is easy to find. Hence, classical algorithmic techniques need to be integrated with new ideas. In this class, we will study algorithms for many matching markets, starting from the classical concept of stable matchings, and then exploring more modern and sophisticated solution concepts. Our point of view will mainly be that of an optimizer, i.e., we will look to find provably good solutions in a provably short amount of time.

See here for a tentative detailed schedule.

Grading. The final grade will be based on: homeworks, scribing, and a final project that will be either working on a research question, or reading and summarizing in class a research paper.