Popular Maximum-Utility Matchings with Matroid Constraints

We investigate weighted settings of popular matching problems with matroid constraints. The concept of popularity was originally defined for matchings in bipartite graphs, where vertices have preferences over the incident edges. There are two standard models, depending on whether vertices on one or both sides have preferences. A matching M is popular if it does not lose a head-to-head election against any other matching. In our generalized models, one or both sides have matroid constraints, and a weight function is defined on the ground set. Our objective is to find a popular optimal matching, that is, a maximum-weight matching that is popular among all maximum-weight matchings satisfying the matroid constraints. For both one- and two-sided preferences models, we provide efficient algorithms to find such solutions, combining algorithms for unweighted models with fundamental techniques from combinatorial optimization. The algorithm for the one-sided preferences model is further extended to a model where the weight function is generalized to an M${}^{♮}$-concave utility function. Finally, we complement these tractability results by providing hardness results for the problems of finding a popular near-optimal matching. These hardness results hold even without matroid constraints and with very restricted weight functions.

History: This paper has been accepted for the Special Issue on Mathematics of Market Design.

Funding: This work was supported by the Japan Science and Technology Corporation [JST CRONOS Japan Grant JPMJCS24K2, JST ERATO Grant JPMJER2301, and JST PRESTO Grant JPMJPR212B]; the Japan Society for the Promotion of Science [JSPS KAKENHI Grants JP20K11699, JP24K02901, and JP24K14828]; Nemzeti Kutatási, Fejlesztési és Innovációs Hivatal (Hungarian National Research, Development and Innovation Office (NKFIH)) [Grants K143858 and TKP2021-NKTA-62]; and Magyar Tudományos Akadémia (Lendület Programme of the Hungarian Academy of Sciences) [Grant LP2021-1/2021]. C. Csáji was supported by Nemzeti Kutatási, Fejlesztési és Innovaciós Alap (the Ministry of Culture and Innovation of Hungary from the National Research, Development and Innovation Fund), financed under the KDP-2023 funding scheme [Grant C2258525].