À¶Ý®ÊÓƵ

Abstract:

The maximum cardinality stable matching problem is central in game theory. When participants are allowed to have ties in their preferences, the problem of finding a stable matching of maximum cardinality is NP-hard, 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. 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. Also in case when L equals 2, our result matches the known UGC-hardness result.   We will also discuss the potential for improving the best known UGC-hardness result for the maximum cardinality stable matching problem.