Title:Matchings under preferences with Lower Quotas
Speaker: Limaye Girija Deepak (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.