The maximum cardinality stable matching problem is central for 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 for the maximum cardinality stable matching problem with a constant factor smaller than 4/3. 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. For the general case, i.e., for the case of ties of size at most L, we develop a new algorithm with approximation factor (3L-2)/(2L -1). Interestingly, our approximation factor matches the integrality gap for the case of ties of size at most L.

Joint work with Robert Chiang, Jochen Koenemann, Natig Tofigzade.