Rakesh Vohra: Rounding in Matching Problems from Economics

Matching problems in Economics, frequently differ from traditional matching problems in that the matching with desired properties one seeks is not the solution to linear optimization problem defined over the set of feasible matchings. The difference arises from the role of preferences. Nevertheless, one can still use familiar LP rounding techniques to obtain matchings that come `close' to the desired matchings.

1-sided matching problem, because only one side has preferences, easily fit into the traditional optimization framework, and so one can employ LP rounding techniques in these applications. 2-sided matching problems (both sides have preferences) present a challenge, because the matchings of interest may not exist. I'll describe how Scarf's lemma combined with well known rounding arguments can be used to `solve' such 2-sided matching problems.

I'll assume a knowledge of linear programming but no prior knowledge about economic aspects of matching.