Matchings under Preferences

Matchings under preferences involves finding a matching in a graph that has a set of vertices and edges, and each vertex has a preference ordering on its neighbors. The matching needs to respect the preferences of the vertices, and hence different optimality criteria can be considered to choose a "good" matching.

The course will start with the stable matchings problem. The problem has several interesting variants, and the set of stable matchings has a rich and interesting structure. The goal of the course is to introduce this area and illustrate the algorithms developed. Several of these algorithms are currently being used in practice. Thus the results have a practical appeal, and there are also some connections with game theory.

Gale and Roth have done seminal work in this area, which was rewarded with Nobel prize in Economics in 2012.

  • References
    • Book: The stable marriage problem: Structure and Algorithms by Gusfield and Irving
    I will post references whenever material outside this book is covered.
  • Evaluation
    • There will be a quiz and an endsem. There will be presentations if and only if the audience size is at most 5.
  • Assignments and exam papers
    • Assignment
  • Lectures
    1. March 4th: Introduction to matchings under preferences, variations like stable marriage, stable roommates, hospital/residents problems, Gale-Shapley algorithm for strict and complete preference lists and when both the bipartitions have the same size
    2. March 7th: Correctness of the GS algorithm, man-optimal and women-optimal stable matchings, sets of unequal sizes
    3. March 11th: Stable marriage with incomplete lists, stable matchings with indifference: super-stable, strongly stable, and weakly stable matchings, existence
    4. March 14th: Algorithms for super-stable and strongly stable matchings in case of ties and complete preference lists (Details of strongly stable matching algorithm left as exercise) (Reference)
    5. March 18th: Example showing that there may not be a man-optimal or woman-optimal weakly stable matching, 3/2-approximation for maximum cardinality weakly stable matchings with one-sided ties (Reference, and this for the example)
      Recently, a (1+1/e)-approximation algorithm has been given in this paper
    6. March 21st: Lattice structure of stable matchings (Section 1.3 from [GI])
    7. March 25th: Stable roommates problem: polynomial-time algorithm (Section 4.2 of [GI] or the original paper)
    8. March 28th: Stable roommates problem continued
    9. April 1st: Hospital/Residents problem: stable matchings, rural hospitals theorem, hospital optimality and pessimality [GI]
    10. April 4th: Popular matchings in the stable marriage problem (Ref)