Perfect Matchings and Popularity in the Many-to-Many Setting
Telikepalli Kavitha, Kazuhisa Makino · 2024
Read Perfect Matchings and Popularity in the Many-to-Many Setting by Telikepalli Kavitha, Kazuhisa Makino (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00384.txt.
Description
Abstract We consider a matching problem in a bipartite graph G G where every vertex has a capacity and a strict preference order on its neighbors. Furthermore, there is a cost function on the edge set. We assume G G admits a perfect matching, i.e., one that fully matches all vertices.
Catalog record
| CREATOR | Telikepalli Kavitha, Kazuhisa Makino |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-00384
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Perfect Matchings and Popularity in the Many-to-Many Setting Thanks: This result appeared in FSTTCS 2023 [ 29 ] . This version gives a simple proof that corrects a technical gap in the proof for the many-to-many setting in the conference version. Telikepalli Kavitha, Kazuhisa Makino Abstract We consider a matching problem in a bipartite graph G G where every vertex has a capacity and a strict preference order on its neighbors. Furthermore, there is a cost function on the edge set. We assume G G admits a perfect matching, i.e., one that fully matches all vertices. It is only perfect matchings that are feasible for us and we are interested in those perfect matchings that are popular within the set of perfect matchings. It is known that such matchings (called popular perfect matchings) always exist and can be efficiently computed. What we seek here is not any popular perfect matching, but a min-cost one. We show a polynomial-time algorithm for finding such a matching; this is via a characterization of popular perfect matchings in G G in terms of stable matchings in a colorful auxiliary instance. This is a generalization of such a characterization that was known in the one-to-one setting. 1 Introduction Consider a matching problem in a bipartite graph G=(A\cup B,E) where every vertex v\in A\cup B has a strict ranking of its neighbors. For convenience, vertices in A will be called agents and those in B will be called jobs . Every agent/job v has an integral capacity \mathsf{cap}(v)\geq 1 and seeks to be matched to \mathsf{cap}(v) many neighbors. This is the bipartite b -matching framework. This model is also called the many-to-many setting in matchings under preferences. This is a well-studied model that is a natural generalization of several real-world settings such as matching students to schools and colleges [ 1 , 3 ] and residents to hospitals [ 8 , 35 ] . Note that agents (i.e., students/residents) in these applications have capacity 1 while in the many-to-many setting, agents are allowed to have capacity more than 1. For example, when A is a set of students and B is a set of projects, the many-to-many setting allows for the flexibility that not only can several students work on one project, but a student can be part of several projects. One such application is a management system for a conference where program committee members have preferences over submissions and each submission has a ranking of PC members as per their suitability -- in terms of their areas of expertise -- to review this paper. 1 1 1 PC members typically have rankings with ties over papers; we can instead assume a project evaluation committee where each member has a strict ranking of the project proposals that he/she would like to evaluate and each proposal needs a certain number of independent evaluations. Every PC member (also, assume every paper) has a capacity. Definition 1 A matching M in a many-to-many instance G=(A\cup B,E) is a subset of the edge set E such that |M(v)|\leq\mathsf{cap}(v) for each vertex v , where M(v)=\{u:(u,v)\in M\} . Though vertices in both the sets A and B have capacities, note that M can contain at most one copy of any edge since M is a set (and not a multiset). Let us assume that the input instance admits a perfect matching, i.e., one that matches each vertex in A\cup B fully up to its capacity. Such a model occurs in the conference management system application mentioned above where PC members have to place bids and then they are explicitly asked to bid again for submissions that have received too few bids. Thus it will be ensured that the input instance admits a matching where each PC member a gets assigned to \mathsf{cap}(a) many papers and each paper b is assigned to \mathsf{cap}(b) many PC members. So we assume our input instance admits a perfect matching and we seek a best perfect matching as per vertex preferences. In the domain of matchings under preferences, stable matchings are usually regarded as the best matchings. Stable matchings. A matching M is stable if there is no edge that blocks M , where an edge (a,b)\notin M blocks M if (i) either a has less than \mathsf{cap}(a) partners in M or a prefers b to its worst partner in M and (ii) either b has less than \mathsf{cap}(b) partners in M or b prefers a to its worst partner in M . Stable matchings always exist in G and a natural modification of the Gale-Shapley algorithm [ 17 ] finds one. However stability is a strong and rather restrictive notion, e.g., stable matchings need not have maximum cardinality. Consider the following instance where A=\{a,a^{\prime}\},B=\{b,b^{\prime}\} , and all vertex capacities are 1. The preferences of agents are as follows: a:b\succ b^{\prime} and a^{\prime}:b . That is, the top choice of a is b and its second choice is b^{\prime} while a^{\prime} has only one neighbor b . Similarly, the preferences of jobs are as follows: b:a\succ a^{\prime} and b^{\prime}:a . This instance has only one stable matching S=\{(a,b)\} that leaves a^{\prime} and b^{\prime} unmatched. Observe that this instance has a perfect matching M=\{(a,b^{\prime}),(a^{\prime},b)\} that matches all agents and jobs. However M is not stable as the edge (a,b) blocks M . For the problem of selecting a best perfect matching, one with the least number of blocking edges would be a natural relaxation of stability. But finding such a matching is NP-hard [ 5 ] even in the one-to-one setting. A well-studied relaxation of stability that offers a meaningful and tractable solution to the problem of finding a “best perfect matching” is the notion of popularity . Popularity. Popularity is based on voting by vertices on matchings. In the one-to-one setting, the preferences of a vertex over its neighbors extend naturally to preferences over matchings—so every vertex orders matchings in the order of its partners in these matchings. Popular matchings are weak Condorcet winners [ 13 , 32 ] in this voting instance where vertices are voters and matchings are candidates. In other words, a popular matching M does not lose a head-to-head election against any matching N where each vertex v either casts a vote for the matching in \{M,N\} that it prefers or v abstains from voting if its assignment is the same in M and N . For any vertex v and its neighbors u and u^{\prime} , let \mathsf{vote}_{v}(u,u^{\prime}) be v ’s vote for u versus u^{\prime} . More precisely, \mathsf{vote}_{v}(u,u^{\prime})=1 if v prefers u to u^{\prime} , it is -1 if v prefers u^{\prime} to u , and it is 0 otherwise (so u=u^{\prime} ). Thus in the one-to-one setting, every vertex v casts its vote which is \mathsf{vote}_{v}(u,u^{\prime})\in\{0,\pm 1\} , where M(v)=\{u\} and N(v)=\{u^{\prime}\} , for M versus N in their head-to-head election. Recall that we are in the many-to-many setting, i.e., vertices have capacities. So we need to specify how a vertex votes over different subsets of its neighbors. Thus we need to compare two subsets M(v) and N(v) of \mathsf{Nbr}(v) for any vertex v , where \mathsf{Nbr}(v) is the set of neighbors of v . We will follow