Popular Maximum-Utility Matchings with Matroid Constraints

• 成果类型: Article; Early Access
• 署名作者: Csaji, Gergely; Kiratly, Tamas; Takazawa, Kenjiro; Yokoi, Yu
• 署名单位: Eotvos Lorand University; HUN-REN; HUN-REN Centre for Economic & Regional Studies; Eotvos Lorand University; Hosei University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0633
• 发表日期: 2025
• 关键词: House allocation; intersection; complexity; marriage

摘要

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 oneand 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 onesided 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.