| Title | : | Envy-free matchings and relaxed stable matchings under two-sided preferences |
| Speaker | : | Limaye Girija Deepak (IITM) |
| Details | : | Thu, 22 Jun, 2023 11:30 AM @ SSB 233 First Floor, |
| Abstract: | : | This work investigates problems related to computing matchings under two-sided preferences. In this setting, we are given two sets of entities A and B, each entity in both sets has preferences over the other set, and the entities in B have capacities to fill in. We aim to assign every entity in A to at most one entity in B such that the capacities of entities in B are respected, and the assignment is optimal with respect to preferences. This setting models several applications, for instance, school admission, appointing doctors in hospitals, and candidate recruitment in jobs, to name a few. Stability is a well-accepted notion of optimality in this setting, that implies the absence of a blocking pair, that is, a pair of entities unassigned to each other but would like to deviate from their current assignment(s) and get matched with each other. In this work, we consider two practical scenarios wherein the above-described setting fails to provide a satisfactory solution. In the first scenario, in addition to the capacities, entities in the set B have demands to fulfil. Stable matchings that fulfil demands are not guaranteed to exist. We investigate an alternate optimality notion proposed in the literature in the presence of demands and propose a new notion that is guaranteed to exist in the presence of demands. We propose the problem of computing a largest matching that is optimal with respect to preferences as well as fulfils demands. We thoroughly investigate the computational complexity of this problem. Our results include NP-hardness, inapproximability, approximation algorithms and a polynomial time algorithm for a tractable case. Given the hardness, we also investigate its parameterized complexity and present kernelization and FPT results. The second scenario is motivated by applications that mandate assigning every entity in the set A. In the setting described earlier, the capacities of entities in B cannot be violated, which forbids matching every agent in A. We propose a new model to accommodate this requirement using cost-based allocation. Our goal is to compute an assignment that is optimal with respect to preferences as well as costs. We consider two natural objectives on costs (local and global) and a suitable notion of optimality (envy-freeness) in our model. We investigate the computational complexity of computing an optimal matching that matches every entity in the set A. We show that optimizing the local objective is efficiently solvable; however, optimizing the global objective is computationally hard. For the latter case, we presentapproximation algorithms that are simple and practically appealing and an improved approximation algorithm using Linear Programming for a particular hard case. We complement our theoretical results with an empirical evaluation with the following goals: assess the performance of our approximation algorithms in practice, assess the quality of the computed matchings and compare the cost-based model with the standard setting. We illustrate via our evaluation that the proposed cost-based model turns out to be a promising alternative to the standard setting. Web Conference Link : https://meet.google.com/bgx-hnaw-nzw |
