IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

We consider the problem of matchings under two-sided preferences in the presence of maximum as well as minimum quota requirements for the agents. When there are no minimum quotas, stability is the de-facto notion of optimality. In the presence of minimum quotas, ensuring stability and simultaneously satisfying lower quotas is not an attainable goal in many instances. To address this, a relaxation of stability known as envy-freeness, is proposed in literature. In our work, we thoroughly investigate envy-freeness from a computational view point. Our results show that computing envy-free matchings that match maximum number of agents is computationally hard and also hard to approximate up to a constant factor. Additionally, it is known that envy-free matchings satisfying lower-quotas may not exist. To circumvent these drawbacks, we propose a new notion called relaxed stability. We show that relaxed stable matchings are guaranteed to exist even in the presence of lower-quotas. Despite the computational intractability of finding a largest matching that is feasible and relaxed stable, we give an efficient algorithm that computes a constant factor approximation to this matching in terms of size. © 2020, Springer Nature Switzerland AG.

Department of Computer Science and Engineering

Department of Electrical Engineering

World University root node

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Envy-Freeness and Relaxed Stability: Hardness and Approximation Algorithms

In this paper, we consider the problem of computing an optimal matching in a bipartite graph $$G=(A\cup P, E)$$ where elements of A specify preferences over their neighbors in P, possibly involving ties, and each vertex can have capacities and classifications. A classification $$\mathcal {C}_u$$ for a vertex u is a collection of subsets of neighbors of u. Each subset (class) $$C\in \mathcal {C}_u$$ has an upper quota denoting the maximum number of vertices from C that can be matched to u. The goal is to find a matching that is optimal amongst all the feasible matchings, which are matchings that respect quotas of all the vertices and classes. We consider two well-studied notions of optimality namely popularity and rank-maximality. The notion of rank-maximality involves finding a matching in G with maximum number of rank-1 edges, subject to that, maximum number of rank-2 edges and so on. We present an $$O(|E|^2)$$ -time algorithm for finding a feasible rank-maximal matching, when each classification is a laminar family. We complement this with an NP-hardness result when classes are non-laminar even under strict preference lists, and even when only posts have classifications, and each applicant has a quota of one. We show an analogous dichotomy result for computing a popular matching amongst feasible matchings (if one exists) in a bipartite graph with posts having capacities and classifications and applicants having a quota of one. To solve the classified rank-maximal and popular matchings problems, we present a framework that involves computing max-flows iteratively in multiple flow networks. Besides giving polynomial-time algorithms for classified rank-maximal and popular matching problems, our framework unifies several algorithms from literature [1, 10, 12, 15]. © Springer Nature Switzerland AG 2019.

GENERAL

Classified Rank-Maximal Matchings and Popular Matchings – Algorithms and Hardness

We consider the problem of assigning applicants to posts when each applicant has a strict preference ordering over a subset of posts, and each post has all its neighbors in a single tie. That is, a post is indifferent amongst all its neighbours. Each post has a capacity denoting the maximum number of applicants that can be assigned to it. An assignment M, referred to as a matching, is said to be popular, if there is no other assignment M' such that the number of votes M' gets compared to M is more than the number of votes M gets compared to M'. Here votes are cast by applicants and posts for comparing M and M'. An applicant a votes for M over M' if a gets a more preferred partner in M than in M'. A post p votes for M over M' if p gets more applicants assigned to it in M than in M'. The number of votes a post p casts gives rise to two models. Let M(p) denote the set of applicants p gets in M. If (forumala presented)., p can cast |M(p)|-|M'(p)-many votes in favor of M, or just one vote. The two models are referred to as the multi-vote model and one-vote model in this paper. We give a polynomial-time algorithm to determine the existence of a popular matching in the multi-vote model, and to output one if it exists. We give interesting connections between the two models. In particular, we show that a matching that is popular in the one-vote model is also popular in the multi-vote model, however the converse is not true. We also give a polynomial-time algorithm to check if a given matching is popular in the one-vote model, and if not, then output a more popular matching. © Springer Nature Switzerland AG 2019.

Many-to-One Popular Matchings with Two-Sided Preferences and One-Sided Ties

Real-world matching scenarios, like the matching of students to courses in a university setting, involve complex downward-feasible constraints like credit limits, time-slot constraints for courses, basket constraints (say, at most one humanities elective for a student), in addition to the preferences of students over courses and vice versa, and class capacities. We model this problem as a many-to-many bipartite matching problem where both students and courses specify preferences over each other and students have a set of downward-feasible constraints. We propose an Iterative Algorithm Framework that uses a many-to-one matching algorithm and outputs a many-to-many matching that satisfies all the constraints. We prove that the output of such an algorithm is Pareto-optimal from the student-side if the many-to-one algorithm used is Pareto-optimal from the student side. For a given matching, we propose a new metric called the Mean Effective Average Rank (MEAR), which quantifies the goodness of allotment from the side of the students or the courses. We empirically evaluate two many-to-one matching algorithms with synthetic data modeled on real-world instances and present the evaluation of these two algorithms on different metrics including MEAR scores, matching size and number of unstable pairs. © 2019, Springer Nature Switzerland AG.

Student Course Allocation with Constraints

In this paper, we consider the Hospital Residents problem (HR) and the Hospital Residents problem with Lower Quotas (HRLQ). In this model with two sided preferences, stability is a well accepted notion of optimality. However, in the presence of lower quotas, a stable and feasible matching need not exist. For the HRLQ problem, our goal therefore is to output a good feasible matching assuming that a feasible matching exists. Computing matchings with minimum number of blocking pairs (Min-BP) and minimum number of blocking residents (Min-BR) are known to be NP-Complete. The only approximation algorithms for these problems work under severe restrictions on the preference lists. We present an algorithm which circumvents this restriction and computes a popular matching in the HRLQ instance. We show that on data-sets generated using various generators, our algorithm performs very well in terms of blocking pairs and blocking residents. Yokoi [20] recently studied envy-free matchings for the HRLQ problem. We propose a simple modification to Yokoi’s algorithm to output a maximal envy-free matching. We observe that popular matchings outperform envy-free matchings on several parameters of practical importance, like size, number of blocking pairs, number of blocking residents. In the absence of lower quotas, that is, in the Hospital Residents (HR) problem, stable matchings are guaranteed to exist. Even in this case, we show that popularity is a practical alternative to stability. For instance, on synthetic data-sets generated using a particular model, as well as on real world data-sets, a popular matching is on an average 8-10% larger in size, matches more number of residents to their top-choice, and more residents prefer the popular matching as compared to a stable matching. Our comprehensive study reveals the practical appeal of popular matchings for the HR and HRLQ problems. To the best of our knowledge, this is the first study on the empirical evaluation of popular matchings in this setting. © Krishnapriya A M, Meghana Nasre, Prajakta Nimbhorkar, and Amit Rawat; licensed under Creative Commons License CC-BY

Leibniz International Proceedings in Informatics, LIPIcs

How good are popular matchings?

Exhaustive identification of all possible alternate pathways that exist in metabolic networks can provide valuable insights into cellular metabolism. With the growing number of metabolic reconstructions, there is a need for an efficient method to enumerate pathways, which can also scale well to large metabolic networks, such as those corresponding to microbial communities. We developed MetQuest, an efficient graph-theoretic algorithm to enumerate all possible pathways of a particular size between a given set of source and target molecules. Our algorithm employs a guided breadth-first search to identify all feasible reactions based on the availability of the precursor molecules, followed by a novel dynamic-programming based enumeration, which assembles these reactions into pathways of a specified size producing the target from the source. We demonstrate several interesting applications of our algorithm, ranging from identifying amino acid biosynthesis pathways to identifying the most diverse pathways involved in degradation of complex molecules. We also illustrate the scalability of our algorithm, by studying large graphs such as those corresponding to microbial communities, and identify several metabolic interactions happening therein. MetQuest is available as a Python package, and the source codes can be found at https://github.com/RamanLab/metquest. © 2018 The Author(s).

Department Of Biotechnology

Fulltext

Scientific Reports

Enumerating all possible biosynthetic pathways in metabolic networks

Hassin et al. [9] consider the Max-Exp-Cover-R problem to study the facility location problem on a graph in the presence of unreliable links when the link failure is according to the Linear Reliability Order (LRO) model. They showed that for unbounded R the problem is polynomial time solvable and for R = 1 and planar graphs the problem is NP-Complete. In this paper, we study the Max-Exp-Cover-1 problem under the LRO edge failure model. We obtain a fixed parameter tractable algorithm for Max-Exp-Cover-1 problem for bounded treewidth graphs, parameterized by the treewidth. We extend the Baker’s technique (Baker, J. ACM 1994) to obtain PTAS for Max-Exp-Cover-1 problem under the LRO model on planar graphs. We observe that the coverage function of the Max-Exp-Cover-R problem is submodular and the problem admits a (1 - 1/e)-approximation for any failure model in which the expected coverage of a set by another set can be computed in polynomial time. © 2018, Springer International Publishing AG, part of Springer Nature.

Facility location on planar graphs with unreliable links

We consider the well-studied Hospital Residents (HR) problem in the presence of lower quotas (LQ). The input instance consists of a bipartite graph G = (R ? H, E) where R and H denote sets of residents and hospitals, respectively. Every vertex has a preference list that imposes a strict ordering on its neighbors. In addition, each hospital h has an associated upper-quota q+(h) and a lower-quota q-(h). A matching M in G is an assignment of residents to hospitals, and M is said to be feasible if every resident is assigned to at most one hospital and a hospital h is assigned at least q-(h) and at most q+(h) residents. Stability is a de-facto notion of optimality in a model where both sets of vertices have preferences. A matching is stable if no unassigned pair has an incentive to deviate from it. It is well-known that an instance of the HRLQ problem need not admit a feasible stable matching. In this paper, we consider the notion of popularity for the HRLQ problem. A matching M is popular if no other matching M gets more votes than M when vertices vote between M and M. When there are no lower quotas, there always exists a stable matching and it is known that every stable matching is popular. We show that in an HRLQ instance, although a feasible stable matching need not exist, there is always a matching that is popular in the set of feasible matchings. We give an efficient algorithm to compute a maximum cardinality matching that is popular amongst all the feasible matchings in an HRLQ instance. © Meghana Nasre and Prajakta Nimbhorkar.

Popular matchings with lower quotas

We consider the problem of computing popular matchings in a bipartite graph G = (R ∪ H, E) where R and H denote a set of res-idents and a set of hospitals respectively. Each hospital h has a positive capacity denoting the number of residents that can be matched to h. The residents and the hospitals specify strict preferences over each other. This is the well-studied Hospital Residents (HR) problem which is a generaliza-tion of the Stable Marriage (SM) problem. The goal is to assign residents to hospitals optimally while respecting the capacities of the hospitals. Sta-bility is a well-accepted notion of optimality in such problems. However, motivated by the need for larger cardinality matchings, alternative notions of optimality like popularity have been investigated in the SM setting. In this paper, we consider a generalized HR setting – namely the Laminar Classified Stable Matchings (LCSM+) problem. Here, additionally, hospi-tals can specify classifications over residents in their preference lists and classes have upper quotas. We show the following new results: We define a notion of popularity and give a structural characterization of popular matchings for the LCSM+ problem. Assume n = |R| + |H| and m = |E|. We give an O(mn) time algorithm for computing a maximum cardinality popular matching in an LCSM+ instance. We give an O(mn2) time algo-rithm for computing a matching that is popular amongst the maximum cardinality matchings in an LCSM+ instance. © Springer International Publishing AG 2017.

Popularity in the generalized hospital residents setting

We consider list coloring of planar graphs without cycles of length in {4, …, 8}. List coloring is a generalization of the classical vertex coloring problem where each vertex has a list of colors associated with it. The goal is to proper vertex color the graph, such that each vertex gets a color available in its list. In this note, we prove that it is possible to 3-list color planar graphs without cycles of length in {4, …, 8} and with restrictions on 9-cycles. © 2016

Electronic Notes in Discrete Mathematics

List Coloring of Planar Graphs with Forbidden Cycles

We consider the strategic issues of the popular matchings problem. Let G = (A ∪ P, E) be a bipartite graph, where A denotes a set of agents, P denotes a set of posts, and the edges in E are ranked. Each agent ranks a subset of posts in an order of preference, possibly involving ties. A matching M is popular if there exists no matching M′ such that the number of agents that prefer M′ to M exceeds the number of agents that prefer M to M′. Consider a centralized market where agents submit their preferences and a central authority matches agents to posts according to the notion of popularity. Since a popular matching need not be unique, we assume that the central authority chooses an arbitrary popular matching. Let a1 be the sole manipulative agent who is aware of the true preference lists of all other agents. The goal of a1 is to falsify her preference list to get better always, that is, in the falsified instance (i) every popular matching matches a1 to a post that is at least as good as the most preferred post that she gets when she was truthful, and (ii) some popular matching matches a1 to a post better than the most preferred post p that she gets when she was truthful, assuming that p is not one of a1's (true) most preferred posts. We show that the optimal cheating strategy for a manipulative agent to get better always can be computed in O(m + n) time when preference lists are all strict and in O(√nm) time when preference lists are allowed to contain ties. Here n = |A| + |P| and m = |E|. To compute the cheating strategies, we develop a switching graph characterization of the popular matchings problem involving ties. The switching graph characterization was studied for the case of strict lists by McDermid and Irving [J. Comb. Optim., 22 (2011), pp. 339-358] and was open for the case of ties. We show an O(√nm) time algorithm to compute the set of popular pairs using the switching graph. These results are of independent interest and answer a part of the open questions posed by McDermid and Irving. © 2014 Society for Industrial and Applied Mathematics.

SIAM Journal on Discrete Mathematics

Popular matchings: Structure and strategic issues

Let (Formula presented.) be a bipartite graph where A denotes a set of agents, P denotes a set of posts and ranks on the edges denote preferences of the agents over posts. A matching M in G is rank-maximal if it matches the maximum number of applicants to their top-rank post, subject to this, the maximum number of applicants to their second rank post and so on. In this paper, we develop a switching graph characterization of rank-maximal matchings, which is a useful tool that encodes all rank-maximal matchings in an instance. The characterization leads to simple and efficient algorithms for several interesting problems. In particular, we give an efficient algorithm to compute the set of rank-maximal pairs in an instance. We show that the problem of counting the number of rank-maximal matchings is #P-Complete and also give an FPRAS for the problem. Finally, we consider the problem of deciding whether a rank-maximal matching is popular among all the rank-maximal matchings in a given instance, and give an efficient algorithm for the problem. © Springer International Publishing Switzerland 2014.

Rank-maximal matchings – structure and algorithms

We consider the all pairs all shortest paths (APASP) problem, which maintains the shortest path dag rooted at every vertex in a directed graph G = (V,E) with positive edge weights. For this problem we present a decremental algorithm (that supports the deletion of a vertex, or weight increases on edges incident to a vertex). Our algorithm runs in amortized O(ν∗2 ・ log n) time per update, where n = |V |, and ν∗ bounds the number of edges that lie on shortest paths through any given vertex. Our APASP algorithm can be used for the decremental computation of betweenness centrality (BC), which is widely used in the analysis of large complex networks. No nontrivial decremental algorithm for either problem was known prior to our work. Our method is a generalization of the decremental algorithm of Demetrescu and Italiano [3] for unique shortest paths, and for graphs with ν∗ = O(n), we match the bound in [3]. Thus for graphs with a constant number of shortest paths between any pair of vertices, our algorithm maintains APASP and BC scores in amortized time O(n2 ・ log n) under decremental updates, regardless of the number of edges in the graph. © Springer International Publishing Switzerland 2014.

Decremental all-pairs ALL shortest paths and betweenness centrality

We present an incremental algorithm that updates the betweenness centrality (BC) score of all vertices in a graph G when a new edge is added to G, or the weight of an existing edge is reduced. Our incremental algorithm runs in O(v * · n) time, where v * is bounded by m *, the number of edges that lie on a shortest path in G. We achieve the same bound for the more general incremental vertex update problem. Even for a single edge update, our incremental algorithm is the first algorithm that is provably faster on sparse graphs than recomputing with the well-known static Brandes algorithm. It is also likely to be much faster than Brandes on dense graphs since m * is often close to linear in n. Our incremental algorithm is very simple, and we give an efficient cache-oblivious implementation that incurs O(n · sort(v *)) cache misses, where sort is a well-known measure for caching efficiency. © 2014 Springer-Verlag Berlin Heidelberg.

Betweenness centrality - Incremental and faster

We consider an extension of the popular matching problem in this paper. The input to the popular matching problem is a bipartite graph G=(A∪B,E)<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>G</mi><mo>=</mo><mo stretchy="false">(</mo><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">A</mi></mrow><mo>∪</mo><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">B</mi></mrow><mo>,</mo><mi>E</mi><mo stretchy="false">)</mo></math>, where A<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">A</mi></mrow></math>&nbsp;is a set of people, B<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">B</mi></mrow></math>&nbsp;is a set of items, and each person a∈A<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mo>∈</mo><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">A</mi></mrow></math>&nbsp;ranks a subset of items in order of preference, with ties allowed. The popular matching problem seeks to compute a matching M ∗ between people and items such that there is no matching M where more people are happier with M than with M ∗. Such a matching M ∗ is called a popular matching. However, there are simple instances where no popular matching exists.Here we consider the following natural extension to the above problem: associated with each item b∈B<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi><mo>∈</mo><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">B</mi></mrow></math>&nbsp;is a non-negative price cost(b), that is, for any item b, new copies of b can be added to the input graph by paying an amount of cost(b) per copy. When G does not admit a popular matching, the problem is to “augment” G at minimum cost such that the new graph admits a popular matching. We show that this problem is NP-hard; in fact, it is NP-hard to approximate it within a factor of n1−−√/2<math xmlns="http://www.w3.org/1998/Math/MathML"><msqrt><msub><mi>n</mi><mrow class="MJX-TeXAtom-ORD"><mn>1</mn></mrow></msub></msqrt><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mn>2</mn></math>, where n 1 is the number of people. This problem has a simple polynomial time algorithm when each person has a preference list of length at most 2. However, if we consider the problem of constructing a graph at minimum cost that admits a popular matching that matches all people, then even with preference lists of length&nbsp;2, the problem becomes NP-hard. On the other hand, when the number of copies of each item is fixed, we show that the problem of computing a minimum cost popular matching or deciding that no popular matching exists can be solved in O(mn 1) time, where m is the number of edges.

Journal of Combinatorial Optimization

Popularity at minimum cost

We consider the cheating strategies for the popular matchings problem. Let G = (A[P,E) be a bipartite graph where A denotes a set of agents, P denotes a set of posts and the edges in E are ranked. Each agent ranks a subset of posts in an order of preference, possibly involving ties. A matching M is popular if there exists no matching M0 such that the number of agents that prefer M0 to M exceeds the number of agents that prefer M to M0. Consider a centralized market where agents submit their preferences and a central authority matches agents to posts according to the notion of popularity. Since a popular matching need not be unique, we assume that the central authority chooses an arbitrary popular matching. Let a1 be the sole manipulative agent who is aware of the true preference lists of all other agents. The goal of a1 is to falsify her preference list to get better always, that is, to improve the set of posts she gets matched to in the falsified instance. We show that the optimal cheating strategy for a single agent to get better always can be computed in O(m + n) time when preference lists are all strict and in O(p nm) time when preference lists are allowed to contain ties. Here n = |A| + |P| and m = |E|. To compute the cheating strategies, we develop a switching graph characterization of the popular matchings problem involving ties. The switching graph characterization was studied for the case of strict lists by McDermid and Irving (J. Comb. Optim. 2011) and was open for the case of ties. We show an O(p nm) time algorithm to compute the set of popular pairs using the switching graph. These results are of independent interest and answer a part of the open questions posed by McDermid and Irving.

Popular matchings: Structure and cheating strategies

We consider the problem of matching people to items, where each person ranks a subset of items in an order of preference, possibly involving ties. There are several notions of optimality about how to best match a person to an item; in particular, popularity is a natural and appealing notion of optimality. A matching M* is popular if there is no matching M such that the number of people who prefer M to M* exceeds the number who prefer M* to M. However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not admit popular matchings. This motivates the following extension of the popular matchings problem: Given a graph G=(A∪B,E) where A is the set of people and B is the set of items, and a list 〈c1,...,c|B|〉 denoting upper bounds on the number of copies of each item, does there exist 〈x1,...,x|B|〉 such that for each i, having xi copies of the i-th item, where 1≤xi≤ci, enables the resulting graph to admit a popular matching? In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each ci is 1 or 2. We show a polynomial time algorithm for a variant of the above problem where the total increase in copies is bounded by an integer k. © 2010 Elsevier B.V. All rights reserved.

Theoretical Computer Science

Popular matchings with variable item copies

A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph is (strongly) rainbow connected if there exists a (geodesic) rainbow path between every pair of vertices. The (strong) rainbow connectivity of a graph G, denoted by (src(G), respectively) rc(G) is the smallest number of colors required to edge color the graph such that G is (strongly) rainbow connected. In this paper we study the rainbow connectivity problem and the strong rainbow connectivity problem from a computational point of view. Our main results can be summarised as below: For every fixed k ≥ 3, it is NP-Complete to decide whether src(G) ≤ k even when the graph G is bipartite. For every fixed odd k ≥ 3, it is NP-Complete to decide whether rc(G) ≤ k. This resolves one of the open problems posed by Chakraborty et al. [4] hardness for the even case. The following problem is fixed parameter tractable: Given a graph G, determine the maximum number of pairs of vertices that can be rainbow connected using two colors. For a directed graph G, it is NP-Complete to decide whether rc(G) ≤ 2. © P. Ananth, M. Nasre, and K.K. Sarpatwar.

Department of Ocean Engineering

Rainbow connectivity: Hardness and tractability

We investigate the following problem: given a set of jobs and a set of people with preferences over the jobs, what is the optimal way of matching people to jobs? Here we consider the notion of popularity. A matching M is popular if there is no matching M such that more people prefer M to M than the other way around. Determining whether a given instance admits a popular matching and, if so, finding one, was studied by Abraham et al. (SIAM J. Comput. 37(4):1030-1045, 2007). If there is no popular matching, a reasonable substitute is a matching whose unpopularity is bounded. We consider two measures of unpopularity-unpopularity factor denoted by u(M) and unpopularity margin denoted by g(M). McCutchen recently showed that computing a matching M with the minimum value of u(M) or g(M) is NP-hard, and that if G does not admit a popular matching, then we have u(M)≥2 for all matchings M in G. Here we show that a matching M that achieves u(M)=2 can be computed in O(m\sqrt n) time (where m is the number of edges in G and n is the number of nodes) provided a certain graph H admits a matching that matches all people. We also describe a sequence of graphs: H=H 2,H 3,⋯,H k such that if H k admits a matching that matches all people, then we can compute in O(km\sqrt n) time a matching M such that u(M)≤k-1 and g(M)\le n(1-\frac2 k). Simulation results suggest that our algorithm finds a matching with low unpopularity in random instances. © 2010 Springer Science+Business Media, LLC.

Algorithmica (New York)

Bounded unpopularity matchings

We study the problem of matching applicants to jobs under one-sided preferences; that is, each applicant ranks a non-empty subset of jobs under an order of preference, possibly involving ties. A matching&nbsp;<math><mi is="true">M</mi></math>&nbsp;is said to be more popular than&nbsp;<math><mi is="true">T</mi></math>&nbsp;if the applicants that prefer&nbsp;<math><mi is="true">M</mi></math>&nbsp;to&nbsp;<math><mi is="true">T</mi></math>&nbsp;outnumber those that prefer&nbsp;<math><mi is="true">T</mi></math>&nbsp;to&nbsp;<math><mi is="true">M</mi></math>. A matching is said to be popular if there is no matching more popular than it. Equivalently, a matching&nbsp;<math><mi is="true">M</mi></math>&nbsp;is popular if&nbsp;<math><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">M</mi><mo is="true">,</mo><mi is="true">T</mi><mo is="true">)</mo></mrow><mo is="true">≥</mo><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">T</mi><mo is="true">,</mo><mi is="true">M</mi><mo is="true">)</mo></mrow></math>&nbsp;for all matchings&nbsp;<math><mi is="true">T</mi></math>, where&nbsp;<math><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">X</mi><mo is="true">,</mo><mi is="true">Y</mi><mo is="true">)</mo></mrow></math>&nbsp;is the number of applicants that prefer&nbsp;<math><mi is="true">X</mi></math>&nbsp;to&nbsp;<math><mi is="true">Y</mi></math>.Previously studied solution concepts based on the popularity criterion are either not guaranteed to exist for every instance (e.g., popular matchings) or are NP-hard to compute (e.g., least unpopular matchings). This paper addresses this issue by considering mixed matchings. A mixed matching is simply a probability distribution over matchings in the input graph. The function&nbsp;<math><mi is="true">ϕ</mi></math>&nbsp;that compares two matchings generalizes in a natural manner to mixed matchings by taking expectation. A mixed matching&nbsp;<math><mi is="true">P</mi></math>&nbsp;is popular if&nbsp;<math><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">P</mi><mo is="true">,</mo><mi is="true">Q</mi><mo is="true">)</mo></mrow><mo is="true">≥</mo><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">Q</mi><mo is="true">,</mo><mi is="true">P</mi><mo is="true">)</mo></mrow></math>&nbsp;for all mixed matchings&nbsp;<math><mi is="true">Q</mi></math>.We show that popular mixed matchings always exist and we design polynomial time algorithms for finding them. Then we study their efficiency and give tight bounds on the price of anarchy and price of stability of the popular matching problem.