Fair Matchings and Related Problems

Let $$G = (A \cup B, E)$$G=(A?B,E) be a bipartite graph, where every vertex ranks its neighbors in an order of preference (with ties allowed) and let $$r$$r be the worst rank used. A matching $$M$$M is fair in $$G$$G if it has maximum cardinality, subject to this, $$M$$M matches the minimum number of vertices to rank $$r$$r neighbors, subject to that, $$M$$M matches the minimum number of vertices to rank $$(r-1)$$(r-1) neighbors, and so on. We show an efficient combinatorial algorithm based on LP duality to compute a fair matching in $$G$$G. We also show a scaling based algorithm for the fair b-matching problem. Our two algorithms can be extended to solve other profile-based matching problems. In designing our combinatorial algorithm, we show how to solve a generalized version of the minimum weighted vertex cover problem in bipartite graphs, using a single-source shortest paths computation--this can be of independent interest.