Govind S. Sankar

JAAMAS Journal 2025 Journal Article

Optimal matchings with one-sided preferences: fixed and cost-based quotas

• K. A. Santhini
• Govind S. Sankar
• Meghana Nasre

Abstract We consider the well-studied many-to-one bipartite matching problem of assigning applicants \({\varvec{\mathcal {A}}}\) to posts \({\varvec{\mathcal {P}}}\) where applicants rank posts in the order of preference. This setting models many important real-world allocation problems like assigning students to courses, applicants to jobs, amongst many others. In such scenarios, it is natural to ask for an allocation that satisfies guarantees of the form “match at least 80% of applicants to one of their top three choices” or “it is unacceptable to leave more than 10% of applicants unassigned”. The well-studied notions of rank-maximality and fairness fail to capture such requirements due to their property of optimizing extreme ends of the signature of a matching. We, therefore, propose a novel optimality criterion, which we call the “weak dominance ” of ranks. We investigate the computational complexity of the new notion of optimality in the setting where posts have associated fixed quotas. We prove that under the fixed quota setting, the problem turns out to be NP-hard under natural restrictions. We provide randomized algorithms in the fixed quota setting when the number of ranks is constant. We also study the problem under a cost-based quota setting and show that a matching that weakly dominates the input signature and has minimum total cost can be computed efficiently. Apart from circumventing the hardness, the cost-based quota setting is motivated by real-world applications like course allocation or school choice where the capacities or quotas need not be rigid. We also show that when the objective is to minimize the maximum cost, the problem under the cost-based quota setting turns out to be NP-hard. To complement the hardness, we provide a randomized algorithm when the number of ranks is constant. We also provide an approximation algorithm which is an asymptotic faster alternative to the randomized algorithm.

ICML Conference 2024 Conference Paper

Individual Fairness in Graph Decomposition

• Kamesh Munagala
• Govind S. Sankar

In this paper, we consider classic randomized low diameter decomposition procedures for planar graphs that obtain connected clusters that are cohesive in that close by pairs of nodes are assigned to the same cluster with high probability. We consider the additional aspect of individual fairness – pairs of nodes at comparable distances should be separated with comparable probability. We show that classic decomposition procedures do not satisfy this property. We present novel algorithms that achieve various trade-offs between this property and additional desiderata of connectivity of the clusters and optimality in number of clusters. We show that our individual fairness bounds may be difficult to improve by tying the improvement to resolving a major open question in metric embeddings. We finally show the efficacy of our algorithms on real planar networks modeling Congressional redistricting.

ECAI Conference 2023 Conference Paper

Online Algorithms for Matchings with Proportional Fairness Constraints and Diversity Constraints

• Anand Louis
• Meghana Nasre
• Prajakta Nimbhorkar
• Govind S. Sankar

Matching problems with group-fairness constraints and diversity constraints have numerous applications such as in allocation problems, committee selection, school choice, etc. Moreover, online matching problems have lots of applications in ad allocations and other e-commerce problems like product recommendation in digital marketing. We study two problems involving assigning items to platforms, where items belong to various groups depending on their attributes; the set of items are available offline and the platforms arrive online. In the first problem, we study online matchings with proportional fairness constraints. Here, each platform on arrival should either be assigned a set of items in which the fraction of items from each group is within specified bounds or be assigned no items; the goal is to assign items to platforms in order to maximize the number of items assigned to platforms. In the second problem, we study online matchings with diversity constraints, i. e. for each platform, absolute lower bounds are specified for each group. Each platform on arrival should either be assigned a set of items that satisfy these bounds or be assigned no items; the goal is to maximize the set of platforms that get matched. We study approximation algorithms and hardness results for these problems. The technical core of our proofs is a new connection between these problems and the problem of matchings in hypergraphs. Our experimental evaluation shows the performance of our algorithms on real-world and synthetic datasets exceeds our theoretical guarantees.

SODA Conference 2023 Conference Paper

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs

• Jacob Focke
• Dániel Marx
• Fionn Mc Inerney
• Daniel Neuen
• Govind S. Sankar
• Philipp Schepper
• Philip Wellnitz

AAMAS Conference 2022 Conference Paper

Optimal Matchings with One-Sided Preferences: Fixed and Cost-Based Quotas

• Santhini K. A.
• Govind S. Sankar
• Meghana Nasre

We consider the well-studied many-to-one bipartite matching problem of assigning applicants A to posts P where applicants rank posts in the order of preference. This setting models many important real-world allocation problems like assigning students to courses, applicants to jobs, amongst many others. In such scenarios, it is natural to ask for an allocation that satisfies guarantees of the form “match at least 80% of applicants to one of their top three choices” or “it is unacceptable to leave more than 10% of applicants unassigned”. The well-studied notions of rank-maximality and fairness fail to capture such requirements due to their property of optimizing extreme ends of the signature of a matching. We, therefore, propose a novel optimality criterion, which we call as the “cumulative better signature”. We investigate the computational complexity of the new notion of optimality in the setting where posts have associated fixed quotas. We prove that under the fixed quota setting, the problem turns out to be NP-hard under natural restrictions. We provide randomized algorithms in the fixed quota setting when the number of ranks is constant. We also study the problem under a cost-based quota setting and show that min-cost cumulative better matching can be computed efficiently. Apart from circumventing the hardness, the cost-based quota setting is motivated by real-world applications like course allocation or school choice where the capacities or quotas need not be rigid.

IJCAI Conference 2021 Conference Paper

Matchings with Group Fairness Constraints: Online and Offline Algorithms

• Govind S. Sankar
• Anand Louis
• Meghana Nasre
• Prajakta Nimbhorkar

We consider the problem of assigning items to platforms in the presence of group fairness constraints. In the input, each item belongs to certain categories, called classes in this paper. Each platform specifies the group fairness constraints through an upper bound on the number of items it can serve from each class. Additionally, each platform also has an upper bound on the total number of items it can serve. The goal is to assign items to platforms so as to maximize the number of items assigned while satisfying the upper bounds of each class. This problem models several important real-world problems like ad-auctions, scheduling, resource allocations, school choice etc. We show that if the classes are arbitrary, then the problem is NP-hard and has a strong inapproximability. We consider the problem in both online and offline settings under natural restrictions on the classes. Under these restrictions, the problem continues to remain NP-hard but admits approximation algorithms with small approximation factors. We also implement some of the algorithms. Our experiments show that the algorithms work well in practice both in terms of efficiency and the number of items that get assigned to some platform.