On the Approximability of the Stable Matching Problem with Ties of Size Two
- PDF / 2,793,959 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 26 Downloads / 204 Views
On the Approximability of the Stable Matching Problem with Ties of Size Two Robert Chiang1 · Kanstantsin Pashkovich2 Received: 23 July 2019 / Accepted: 17 March 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The stable matching problem is one of the central problems of algorithmic game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum cardinality is an NP -hard problem, even when the ties are of size two. Moreover, in this setting it is UGC-hard to provide an approximation with a constant factor smaller than 4/3. In this paper, we give a tight analysis of an approximation algorithm given by Huang and Kavitha for the maximum cardinality stable matching problem with ties of size two, demonstrating an improved 4/3-approximation factor. Keywords Stable matchings · Ties · Maximum cardinality · Approximation algorithm
1 Introduction The stable matching problem is of crucial importance in game theory. In an instance of a maximum cardinality stable matching problem we are given a bipartite graph G = (A ∪ B, E) with bipartition A and B. Following the standard terminology, we refer to A as men and B as women. For a ∈ A , we define N(a) to be the subset of nodes in B adjacent to a in G; analogously we define N(b) for b ∈ B. Each person c ∈ A ∪ B has strict preferences over N(c). A matching M is called a stable matching if there are no a ∈ A and b ∈ B such that a is either unmatched or prefers b to the woman he is matched to by M and b is either unmatched or prefers a to the man she is matched to by M. Clearly, if a matching M is not stable, then it * Kanstantsin Pashkovich [email protected] Robert Chiang [email protected] 1
Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo N2L 3G1, ON, Canada
2
School of Computer Science and Electrical Engineering, University of Ottawa, 800 King Edward Avenue, Ottawa K1N 6N5, ON, Canada
13
Vol.:(0123456789)
Algorithmica
contains a pair (a, b), a ∈ A , b ∈ B satisfying the above conditions; such a pair (a, b) is called a blocking pair for M. In their seminal work, Gale and Shapley developed a polynomial running time algorithm to find a stable matching [2]. Moreover, since all stable matchings have the same cardinality [3], the algorithm of Gale and Shapley finds a maximum cardinality stable matching in polynomial running time. The situation changes when the people are allowed to have ties. In the case of ties, stable matchings for the same instance of a problem can have different cardinalities. Moreover, it is NP -hard to find a maximum cardinality stable matching even when there are ties of size two only [12]. In this case, it is NP -hard to approximate the maximum cardinality of a stable matching with a constant factor smaller than 21/19 and UGC (Unique Game Conjecture)-hard to approximate with a constant factor smaller than 4/3 [15]. We would like to note that the maximum cardinality stable matching problem with ties appears
Data Loading...
