| Title | : | Matchings under preferences with Lower Quotas |
| Speaker | : | Girija Limaye (IIT Madras) |
| Details | : | Tue, Feb 25, 2020 3:00 PM, @ Turing Hall |
| Abstract | : | We consider a setting involving residents and hospitals, where both residents and hospitals have a preference order over a subset of the other side and each hospital specifies an upper-quota and a lower-quota. We consider the problem of matching residents to hospitals such that a resident is matched to at most one hospital and a hospital is matched to at most upper-quota-many residents. A matching is feasible if every hospital fulfills its lower-quota.
Among all such feasible matchings, our goal is to compute one that is optimal according to the preferences. This problem models important applications like course-allocation, assigning teaching assistants in academic institution. When lower quotas are not present, stability is a well-studied notion of optimality. However in presence of lower quotas, there exist instances
that admit no stable, feasible matching. For such instances, different relaxations like almost-stability, popularity and envy-freeness are studied.
In this talk, we will first focus on envy-freeness. We will present combinatorial problems specific to envy-free matchings when the preference lists are strict or when they contain ties. We will present NP-hardness results and approximation algorithm when the preferences are strict. However, there exist lower-quota instances which do not admit a feasible, envy-free matching. We will present a new notion of optimality called relaxed stability such that any instance with lower quotas is guaranteed to admit a feasible, relaxed stable matching. Popular matchings in above setting is also a well-studied problem. We will explore popular matchings in presence of lower quotas where only one side has a preference ordering. |