Home /  Workshop /  Schedules /  Couples can be Tractable: New Algorithms and Hardness Results for the Hospitals / Residents Problem with Couples

Couples can be Tractable: New Algorithms and Hardness Results for the Hospitals / Residents Problem with Couples

Algorithms, Approximation, and Learning in Market and Mechanism Design November 06, 2023 - November 09, 2023

November 06, 2023 (11:00 AM PST - 11:45 AM PST)
Speaker(s): David Manlove (University of Glasgow)
Location: SLMath: Eisenbud Auditorium, Online/Virtual
Tags/Keywords
  • matching under preferences

  • junior doctor allocation

  • couples

  • polynomial-time algorithm

  • NP-hard

  • responsive

  • subcomplete

Primary Mathematics Subject Classification
Secondary Mathematics Subject Classification
Video

Couples can be Tractable: New Algorithms and Hardness Results for the Hospitals / Residents Problem with Couples

Abstract

We describe a novel polynomial-time algorithm for the Hospitals / Residents problem with Couples (HRC) that can find a near-feasible stable matching (adjusting the hospitals' capacities by at most 1) when couples' preferences are responsive (i.e., if one member switches to a better hospital, than the couple also improves) and subcomplete (i.e., each pair of hospitals that are individually acceptable to both members are jointly acceptable for the couple) by reducing to an instance of the Stable Fixtures problem.

We also present a new polynomial-time algorithm for HRC in a responsive, subcomplete instance that is a Dual Market, or where all couples are one of several possible types. We also describe several hardness results. We show that HRC with responsive and subcomplete couples is NP-hard, even with other strong restrictions. We also show that HRC with a Dual Market is NP-hard under several simultaneous restrictions. Finally, we show that the problem of finding a matching with the minimum number of blocking pairs in HRC is very hard to approximate, even if each couple applies to only one pair of hospitals.

Our polynomial-time solvability results greatly expand the class of known tractable instances of HRC and provide strong evidence as to why long-standing entry-level labour markets that allow couples such as the National Resident Matching Program remain successful to this day. This is joint work with Gergely Csáji, Iain McBride and James Trimble.

Supplements No Notes/Supplements Uploaded
Video/Audio Files

Couples can be Tractable: New Algorithms and Hardness Results for the Hospitals / Residents Problem with Couples

Troubles with video?

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.