Matchings with Group Fairness Constraints: Online and Offline Algorithms

1 Introduction

Graph matching is a fundamental problem in graph theory and theoretical computer science that has been studied extensively over the years. Computing the maximum matching in bipartite graphs, both in the online and the offline setting is an important building block in many applications in allocation problems such as ad-auctions [Mehta, 2013; Mehta et al., 2007], scheduling [McKeown et al., 1999], resource allocation [Halabian et al., 2012], school choice [Abdulkadiroglu and S¨onmez, 2003] etc. Since the notation used in these various problems differ, we use the general terms items and platforms to refer to the two parts of the bipartite graph. In practice, items may be classified based on different properties and hence may belong to certain groups or classes.

∗These three authors contributed equally.

Modeling the allocation problems as a vanilla matching problem seeks to optimize the cost of the solution alone and may inadvertently be "unfair" to some classes of items. Necessitated by the need to be fair and unbiased towards any group of items in the input, there has been a lot of recent work studying algorithms for various problems augmented with fairness constraints, such as [Celis et al., 2018; Kay et al., 2015; Costello et al., 2016; Bolukbasi et al., 2016]).

In this paper, we enforce group fairness through constraints that place an upper bound on the number of items that can be matched from a particular class to a platform. We note that group fairness constraints usually involve both upper and lower bounds. This is incompatible with the practical applications that we have in mind, namely ad-allocation and course allocation problems. For this reason, we focus only on upper bounds. We formally define the problem as follows.

ClassifiedMaximumMatching (CMM). We have a set A of items and a set P of platforms, and these sets form the two parts of a bipartite graph. The presence of an edge (a, p) indicates that item a can be matched to platform p. Let N(p) denote the neighborhood of p. Each platform p has a collection of classes Cp ⊆ 2N(p) , i.e., each item in N(p) may belong to some of the classes in Cp. Each class C ∈ Cp has an associated quota qC p denoting the maximum number of items from C that can be assigned to p. In addition, each platform p has a quota qp, which is an upper bound on the total number of items it can serve. Our goal is to compute an assignment of items to platforms so as to maximize the number of items assigned, while satisfying all the quotas.

Classes allow platforms to specify group fairness constraints - for instance the classes can be seen as properties or categories and the quotas impose the constraints that not too many items from one category are assigned to a platform. These types of fairness constraints have been studied in many practical applications. In [Abdulkadiroglu and S¨onmez, 2003], the authors address the school choice problem where fairness constraints are imposed to achieve racial, ethnic, and gender balance. In the assignment of medical residents to hospitals in Japanese Residency Matching Program (JRMP), regional quotas are introduced to ensure fairness amongst urban and rural hospitals [Kamada and Kojima, 2012; Kamada and Kojima, 2015]. Huang [Huang, 2010] motivates classifications from the perspective of enabling diversity in academic hiring. Apart frommatchings, group fairness constraints have also been studied for many other problems like the knapsack problem [Patel et al., 2021], and clustering problems [Bera et al., 2019], to name a few.

Some recent pre-prints have discussed fairness in matching problems. Soriano and Bonchi [Garc´ıa-Soriano and Bonchi, 2020] study a different notion of individual fairness that they call maxmin-fairness. Their goal is to output a solution such that the satisfaction of one agent cannot be improved without making another agent worse-off. Ma and Xu [Ma and Xu, 2020] measure fairness by the ratio of expected number of agents matched from a particular group to the expected number of agents from that group and their goal is to maximize the minimum of this ratio over all groups. Basu et al. [Basu et al., 2020] also measure fairness based on metrics involving the ratio of agents across groups and the utility they provide. While qualitatively similar, our constraints can be seen as being orthogonal to such notions of fairness.

In different applications, the fairness constraints can have a different structure. In [Kamada and Kojima, 2012; Kamada and Kojima, 2015], each hospital belongs to exactly one region, hence fairness constraints partition the set of hospitals. On the other hand, in the school choice problem in [Abdulkadiroglu and S¨onmez, 2003], a student belongs to multiple constraints. The structure of the constraints crucially affects the computational complexity of finding a fair allocation. This has been illustrated in the context of bipartite matchings where one or both sides of the bipartition express preferences over the other side. Huang [Huang, 2010] and Fleiner and Kamiyama [Fleiner and Kamiyama, 2012], address the CMM problem when both sides of the bipartition have preferences over each other and the notion of optimality is stability, whereas [Nasre et al., 2019] study the CMM problem under the optimality criteria of rank-maximality and popularity. In all these cases, it has been shown that the CMM problem can be efficiently solved if the constraints have a laminar 1 structure, and is NP-hard in general [Nasre et al., 2019]. Such a restriction has been considered before in the literature, such as in the hospital-resident problem [Kamada and Kojima, 2012] or the college admissions problem [Bir´o et al., 2010; Goto et al., 2016]. However, a finer relation between the structure of the class constraints and the computational efficiency has not received much attention in literature. In this paper, we address this issue by focusing on a quantification of non-laminarity in the classes and its effect on computational efficiency. We strengthen the hardness results in [Nasre et al., 2019] and obtain new approximation algorithms for the CMM problem in the offline setting.

Next, we turn our attention to the online version of the problem. Online matching problems have numerous practical applications, such as in ad-allocations [Mehta et al., 2007], resource allocation [Devanur et al., 2011], etc. See [Mehta, 2013] for a survey on online bipartite matchings. Fairness has also been studied in online settings such as online learning [Gillen et al., 2018] or ride-hailing platforms [S¨uhr et al., 2019]. 'Fairness' in another form has been considered previously in the online literature. For example, the 'frequency caps' mentioned in [Feldman et al., 2009] places a restriction on the total number of ads that are shown to the same user, or users from a particular demographic. We study some natural online versions of the CMM problem. We first show that one of our approximation algorithms for the offline non-laminar case also works as an online algorithm, regardless of the input model. For the setting where we restrict classes to be laminar, we show that existing algorithms for online bipartite matching carry over to our setting.

1 A family C of subsets of a set S is laminar if, for every pair of sets X, Y ∈ C, either X ⊆ Y or Y ⊆ X or X ∩ Y = ∅.

1.1 Models

We study CMM problem in various settings. In practice, assigning an item a to a platform p may generate a revenue, which can be modelled as the weight of the edge (a, p). In such a case the goal of the weighted CMM problem is to compute an assignment of items to platforms so as to maximize the total weight of edges in the matching, while satisfying the quotas of all the classes. We now formally define our models.

Model 1 (Many-to-one). This is the setting described earlier. In this setting, items can match to at most one platform.

Model 2 (Many-to-many). This is a more general setting in which items may be matched to multiple platforms. In addition to the classes of platforms, each item i also has a collection of classes Ci ⊆ 2N(i) , i.e., each platform in N(i) belongs to some of the classes in Ci, and the items also have quotas for their classes. This model arises in scenarios like course allocation, where students may be allotted multiple courses subject to various restrictions. Courses may have restrictions over the number of students allotted to it from each department or from each batch.

In the setting of online matchings, the platforms are available offline and the items arrive online. When an item a ∈ A arrives online, its neighbours in P, and the classes that it participates in are revealed. It must be immediately decided if we match a to some platform and any edges matched cannot be unmatched later. In the literature, the order in which the items arrive has been studied in various models. In the adversarial model, the items can arrive in an arbitrary order. We study a natural online arrival model for the items, called the Random input model. See [Mehta, 2013] for a survey of other work on such models.

Model 3 (Random input). In this setting, there is an underlying graph G = (A∪P, E). The vertices of A arrive according to a permutation chosen uniformly at random.

1.2 Our Results

In most applications, an item typically belongs to small number of classes, hence we first study this setting. For example, [Abdulkadiroglu and S¨onmez, 2003] discusses the Boston student assignment mechanism which divides students into two categories based on whether they already have a sibling in the school and whether they are within walking distance to the school. Similarly, in a faculty hiring scenario, the number of classes (which would correspond to specializations) is independent of the number of applicants. For the scenario when there are constant number of classes we show the following result.

Theorem 1 (Informal version of Theorem 6). The CMM problem can be solved in polynomial time if there is a constant number of platforms, each with a constant number of classes. This leads to a 1 2 -approximation algorithm for an arbitrary number of platforms, each with a constant number of classes.

Now we turn to a more general setting where the number of classes is arbitrary and exploit the structural relation amongst the classes. We know from [Nasre et al., 2019] that when the classes of every platform form exactly one laminar family then the CMM problem is solvable in polynomial time. We prove the following theorem.

Theorem 2. There is a polynomial-time algorithm achieving an approximation ratio of 1 ∆+1 for the many-to-one setting (Model 1) where each item belongs to at most ∆ laminar families of classes per platform. This generalizes to the weighted many-to-many setting (Model 2) where for each edge (a, p), the classes of a and p that contain (a, p) can be partitioned into ∆ + 1 laminar families.

The above result is applicable in scenarios like adallocation where the number of classes can be arbitrary, but any ad belongs to a few of them. Complementing this, we also obtain hardness results for computing the optimal CMM.

Proposition 1. (i) CMMcannot be approximated to a factor of nϵ-1 for any ϵ > 0 unless P = NP, where n = |A|, even when there is a single platform and all edge weights are one.

• (ii) When there is a single platform, and additionally, each item appears in at most ∆ classes, the problem is NPhard to approximate within a factor O ( log2 ∆ ∆ ).

The proof of Proposition 1 follows from a reduction from the MAXIMUM INDEPENDENT SET problem.

In the online setting, we first remark that our algorithm from Theorem 2 works as an online algorithm in the unweighted case, even when the input is adversarially chosen.

Theorem 3. There is a polynomial-time online algorithm achieving, in any input model, a competitive ratio of 1 ∆+1 for the many-to-one setting (Model 1) where each item belongs to at most ∆ laminar families of classes per platform. The algorithm extends to the many-to-many setting (Model 2) where the classes of a and p containing each edge (a, p) can be partitioned into ∆+ 1 laminar families.

Having achieved a competitive ratio that is close to the lower bound (from Proposition 1 (ii)), we consider the case where classes are restricted to be laminar. We consider the random order input model (Model 3) and show that a simple greedy algorithm from the literature also works for CMM and that it achieves the same competitive ratio. We use the technique of randomized dual fitting which has been used to analyse competitive ratios in works such as [Devanur et al., 2013; Huang et al., 2018].

Theorem 4. There is a polynomial-time algorithm achieving a competitive ratio of 1 - 1e for CMM with laminar classes in the random input model.

1.3 Implications for Other Problems

Although the CMM problem is modelled as a matching of items to platforms, we show that the classes capture problems which are well studied and are of independent interest.

Maximum Independent Set on Hypergraphs. Given a hypergraph H = (V,E), and a function f : E → Z+, compute the largest set of vertices S such that for every e ∈ E, |S ∩ e| ≤ f(e). We note that when f(e) = 1 for each edge e, this is the problem of computing the strong maximum independent set and when f(e) = |e| - 1, this is the weak maximum independent set problem. These problems are well-studied for bounded-degree hypergraphs; [Halld´orsson and Losievskaja, 2009] describe algorithms achieving factors of 1∆ and 5 ∆+3 for the strong and weak cases respectively, where ∆ denotes the maximum degree of a vertex in H. For the weak independent set, this was further improved to O ( log∆ ∆ log log ∆ ) in [Agnarsson et al., 2013]. However, to the best of our knowledge, there is no known approximation algorithm for the case when f(e) is an arbitrary value - we call this the GENERALIZED MAXIMUM INDEPENDENT SET on hypergraphs. We state our approximation result for independent sets on hypergraphs below, which is a consequence of Theorem 2.

Proposition 2. There is a polynomial time 1∆ approximation algorithm for the problem of computing a GENERALIZED MAXIMUM INDEPENDENT SET on hypergraphs with maximum degree ∆.

For the case when average degree of the vertices is ∆, we get the following:

Theorem 5. There is a r 4∆ approximation algorithm for the generalized independent set where r = OPT n and ∆ denotes the average degree of a vertex.

For the CMM problem, this implies an OPT 4∆n approximation algorithm when we only have an upper bound on the average number of laminar families of classes an item belongs to, and there is only one platform.

Ranking and Group Fairness. In an apparently different model, Celis et al. [Celis et al., 2018] consider ranking n items from a universe of m items, where n ≪ m. Items are assigned properties, and upper quotas for the number of items from any property in the top k ranks. When items have at most ∆ properties each, they give a 1 ∆+2 approximation while allowing constraints to be violated by a factor of 2. This problem can be reduced to the CMM problem and our algorithm from Theorem 2 achieves the same approximation factor without violating any class constraints. We leave the reduction to the full version of this paper [Sankar et al., 2021].

Simultaneous Matchings. Kutz et al. [Kutz et al., 2008] study the problem called simultaneous matchings which is defined as follows: given a bipartite graph G = (X ∪ D, E) and a collection F ⊆ 2X , find the largest solution M ⊆ E such that ∀ C ∈ F, M∩(C×D) is a matching. This problem can be reduced to the CMM problem where every vertex d in D has constraints F (excluding vertices to which d has no edge), and each class has quota 1. The approximation factor in [Kutz et al., 2008] is better but the constraints are significantly more restricted than ours.

2 Offline Approximation Algorithms

In light of the strong inapproximability result for the general CMM problem (Proposition 1), we describe approximation algorithms for some special cases.

2.1 Proof of Theorem 2

In this section, we consider the case when, for each platform p and item a, the classes containing a can be partitioned into at most ∆ laminar families. We first present a 1∆ -approximation algorithm for the case when there is only one platform. This algorithm also generalizes the maximum independent set in hypergraphs (Proposition 2). We extend this algorithm to a 1 ∆+1 -approximation algorithm for the case with multiple platforms and even to the many-to-many setting.

Let G = (A∪{p}, E) be an instance of the CMM problem with a single platform p and a family of classes C with the above restriction.

Reduction to the GENERALIZED MAXIMUM INDEPENDENT SET problem: We construct an instance H = (V, EH) by setting V = {vi | ai ∈ A} and EH = {eC | C ∈ C}, and f(eC) = q(C). We call a set S ⊆ V feasible if for every e ∈ E , |S ∩ e| ≤ f(e). We call a set S ⊆ V maximal if S is feasible and S ∪ {v} is not feasible for every v ∈ V \ S. Our algorithm is a simple greedy algorithm: output a maximal set of vertices. To prove the approximation, we use the following lemma. See the full version of this paper for the proof.

Lemma 1. Consider a set S ⊆ V and a set B ⊆ V \ S such that S ∪B is a maximal set of vertices. Then for every feasible set C such that S ⊆ C and C ∩ B = ∅, we have |C| ≤ |S| + ∆|B|.

Let ALG denote any maximal independent set of H and OPT be the optimal independent set. In the above lemma, set S = ALG ∩ OPT, B = ALG \ OPT, C = OPT . The lemma implies |OPT| ≤ ∆|ALG|. This proves Proposition 2. We note that this also gives us a 1∆ -approximation for the CMM problem in the single platform case when every item belongs to at most ∆ laminar families of the platform. It is also easy to see that this algorithm runs in time O(|V ||EH|). For every vertex, we add it if it does not exceed the quota of any edge it belongs to.

Multiple Platforms. We can use the previous result to obtain a 1 ∆+1 approximation for the multiple platforms case via a simple O(|E|)-time reduction to the single platform case: For every edge (a, p), make a new item ea,p. Replace all the platforms by a single dummy platform. Since classes are subsets of the neighbourhood sets of items or platforms, they can also be seen as subsets of edges of the graph. These naturally form classes over the items ea,p. This combined with the result for the single platform case gives an O(|E| · |C|) algorithm for the multiple platform case where |C| is the total number of classes, establishing Theorem 2.

Remark 1 (Weights on items). We remark that the same analysis goes through even if items have weights and the goal is to compute a maximum weight matching. The algorithm simply keeps matching the highest weight item that can feasibly match to the platform.

2.2 Constant Number of Classes

We can also prove Theorem 2 via the following general statement combined with Proposition 2. We leave the proof to the full version of this paper [Sankar et al., 2021]. We will also need this to prove Theorem 1.

Lemma 2. Given a polynomial-time α-approximation algorithm for the many-to-one matching problem with a single platform, we can obtain a polynomial-time α 1+α - approximation for the matching problem with multiple platforms.

Theorem 6 (Formal version of Theorem 1). The CMM problem can be represented as an IP with 2∆ variables if there is only one platform with ∆ classes. This can be solved in time O(22∆ poly(n)), and also gives rise to a 12 -approximation in time O(22∆ poly(n)) for multiple platforms, each with ∆ classes of items.

Sketch. For an instance with ∆ classes, every item can be represented by a ∆-bit incidence vector of the classes it belongs to. This partitions the items into 2∆ types. Our ILP has one variable for each type. The runtime is obtained via [Lenstra, 1983]. Theorem 1 follows by setting ∆ = O(1). In practice, there exist integer program heuristics that are faster (for example, see [Fischetti et al., 2005]). For arbitrarily large number of platforms, each with a constant number of classes, we can use this with Lemma 2 to get a 12 -approximation.

2.3 Bounded Average Degree

We extend the result from the previous section for a single platform to the case when the average number of laminar families of classes an item belongs to is bounded by ∆. We state it in terms of GENERALIZED MAXIMUM INDEPENDENT SEThere. Now consider the case where the hypergraph H constructed above has only bounded average degree of ∆.

Proof of Theorem 5. Since the average degree is ∆, for any f, there cannot be more than nf vertices of degree more than f∆. Suppose we estimate r and set f = 2r . We call a vertex low degree if its degree is at most f∆, otherwise the vertex is high degree. Then the number of low degree vertices is ≥ n (1 - r2 ). In the graph induced by the low degree vertices, the size of the optimal independent set is at least OPT 2 , since at most OPT 2 vertices of high degree. We use our 1∆ approximation algorithm on the graph induced by the low degree vertices. Since this graph has maximum degree ≤ 2∆ r , the size of the independent set has size ≥ r·OPT 4∆ .

Thus, our approximation ratio is at least r 4∆ . We finally need to estimate r. We guess a value of OPT from 1 to n and run the above procedure for each of the guesses. Amongst all the solutions that we obtain, we pick the one with the highest cardinality. This is guaranteed to do at least as well as the case when we picked the correct value of OPT .

3 Online Algorithms

The online algorithm for Theorem 3 is essentially the same as the one in Proposition 2 and works even for an arbitrary input model. Whenever an item arrives online, we match it to a platform such that the matching remains feasible. If there is no such platform, we leave it unmatched. The output is a maximal set, which by Proposition 2, gives us the required competitive ratio. However, we point out that this only works for the unweighted version.

We now look at an 'easier' version of CMM where the classes form a laminar family. This version is known to have an efficient offline algorithm, via the construction of a simple flow network. A similar construction is used to compute the rank-maximal matching in [Nasre et al., 2019]. In this setting, we look at the many-to-many CMM model (Model 2) and assume an input model where the item set arrives in a uniformly random permutation (Model 3). For the sake of the analysis, we assume that a random variable yi picked uniformly at random from [0, 1] for every item ai, and the items arrive in the increasing order of yi. Therefore the random vector ⃗y := (y1, y2, . . . , yn) fully describes the order of arrival of the items. We use ⃗y-i to represent the vector after removing yi from ⃗y. We use the following greedy algorithm, and analyze its competitive ratio (in expectation): Keep an arbitrary, fixed ranking of all the platforms in P . When an item arrives online, match it to as many platforms as possible, picking the highest ranked ones.

Sketch of Theorem 4. We use a linear programming relaxation of our problem to analyze our algorithm. We set the primal values according to the output of our algorithm, thereby ensuring the feasibility of the primal solution. Now we need to construct an appropriate dual solution. We use the following folklore fact about the well-known method of dual fitting in designing algorithms. This technique is used in [Devanur et al., 2013; Huang et al., 2018] among others.

In the primal LP, we have a variable xij = 1 ⇐⇒ item ai is matched to platform pj. We also have constraints for both the item and platform classes. In the dual LP, we have variables corresponding to constraints in the primal LP. We describe the LP formally in the full version of this paper.

Fact 1 (Folklore). Suppose we can set the dual variables such that the primal objective is equal to the dual objective, and the dual constraints of the form α ≥ 1 instead satisfy E[α] ≥ F . Then, our algorithm has a competitive ratio F in expectation.

Now, we set the dual variables so that the dual constraints have a lower bound of F. The following is the key lemma in analyzing how the algorithm behaves depending on ⃗y. Although it is inspired by [Devanur et al., 2013; Huang et al., 2018; Goel and Mehta, 2008], our many-tomany model (Model 2) is more complicated in that moving one vertex up the ranking can cause more changes to the matching because an item can match to multiple platforms. Even apart from the platform classes, we must take care of item classes as well. To that end, we use the following lemma.

Lemma 3. For any i, j such that j ̸= i, if an item aj is matched to some platforms at yi = 1, then it cannot be unmatched from any platform at yi = θ ∈ [0, 1] due to an item class.

Once we have the lemma, we show Theorem 4 the following way. Let α ≥ 1 be such a dual constraint. We want to show that E [α] ≥ F or equivalently, Ey-i [Eyi [α]] ≥ F . We look at the inner expectation. We fix y-i and vary yi from 0 to 1, and show using dual-fitting arguments and Lemma 3 that E [α] ≥ (1 - 1e ). From Fact 1, this proves Theorem 4.

4 Experiments

In this section, we present the experimental evaluation of our offline algorithms from Theorem 1 and Theorem 2. We use a total of seven datasets which we categorize as real-world and synthetic datasets. The three real-world datasets are sourced from an elective allocation process at an educational institution. The four synthetic datasets are generated as described below. All experiments were run on a laptop running on a 64-bit Windows 10 Home edition, and equipped with an Intel Core i7-7500U CPU @2.7GHz and 12GB of RAM. For solving integer programs, we used IBM ILOG CPLEX Optimization Studio 20.1 through its Python API. All code was written to run on Python 3.8.

Real-World Datasets. We use data from three courseregistration periods at an educational institution. Each dataset has around 100 courses and 2000 students. The students and the courses correspond to items and platforms respectively in our model. The edges represent the courses that a student is interested in. The students are partitioned into 13 departments (majors) as well as 5 batches (1st year-5th year). Each course has an overall quota denoting the maximum number of students that can be allotted to it. For each course, we introduce a quota for each department and a quota for each batch. Each course belongs to one of two categories, and each student can be matched to at most one course of each category. The goal is to maximize the number of edges selected subject to these constraints. This can be immediately viewed as an instance of CMM.

Synthetic Datasets. Modelled on the real-world datasets, we synthetically generate large instances and compare the performance of our algorithms to the optimal algorithm implemented using a matching Integer Linear Program. The synthetic datasets are generated as follows. Datasets labelled 'large' have 500 courses, and 20 departments with 10,000 students in each department. The datasets labelled 'small' have 300 courses, and 20 departments with 2,000 students in each department. The students have a degree that is chosen uniformly at random between 3 and 10 in the 'dense' datasets and between 3 and 5 in the 'sparse' datasets. Students choose their courses randomly based on a non-uniform probability distribution. This distribution is defined by assigning a random 'popularity' value to each course. We observe this feature in the real-world dataset, where all courses are not equally popular. We also experiment without this feature, and obtain similar results.

We compare our performance and running-time with the optimal solution obtained by solving the standard Matching ILP augmented with the constraints for each class. All running-times include the time taken for file I/O. The solution values and running-times were averaged over 10 runs. Though our algorithms are deterministic, these implementations utilize some randomness because of the use of hashtables. Observe that since we have two laminar families of classes, Theorem 1 and Theorem 2 provide theoretical guarantees of only 1 2 and 13 respectively. However, the performance of the algorithms on both real-world and random data are close to optimal. All our tables provide absolute values of the solution value and running-time of the algorithm from Theorem 1 (column 1 2 -approx) and algorithm from Theorem 2 (column ∆-approx), as well as the relative value or relative speedup in comparison to that of the Matching ILP (column OPT).

4.1 Observations

Tables 1, 2 provide the solution values and running times for real-world instances and Tables 3, 4 provide the same for the synthetic datasets. In both these datasets, both of our algorithms output solutions with value at least 90% of the optimum value. This seems to suggest that both real-world or random settings are 'easier' than the worst-case instances for our algorithms. Furthermore, we believe that the significantly improved running-time more than makes up for loss of 10% in the output value. The biggest speedups are observed in the 'large' datasets, where our algorithms achieve speedups of 15× and 30× respectively. This is expected because the ILP takes time exponential in the size of the graph.

5 Conclusion

In this paper we gave approximation algorithms for the CMM problem in various offline and online settings. Improving these approximation factors or showing matching lower bounds are natural open questions. There are existing algorithms that break the 1 - 1/e barrier for online bipartite matching without group fairness constraints such as [Feldman et al., 2009]; obtaining similar bounds for online CMM

is also an interesting open problem.

Acknowledgements

We acknowledge some initial discussions with Ajay Saju Jacob. We are grateful to the anonymous reviewers for their comments. AL was supported in part by SERB Award ECR/2017/003296 and a Pratiksha Trust Young Investigator Award. MN and PN are supported in part by SERB Award CRG/2019/004757.