{"ID":6138156,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T08:45:50.451512195Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07160","arxiv_id":"2607.07160","title":"Stable Matchings with Minimum Utility Gap","abstract":"We introduce the Stable Matching Problem with Minimum Utility Gap, which seeks a stable matching in which the utilities received by individual agents are as balanced as possible. Our framework can handle many-to-many matchings and general utility functions on partner sets that are consistent with the agents' preferences. We consider two measures for comparing agents' utilities: the difference between the maximum and minimum utilities, and their ratio. We provide a polynomial-time algorithm for both versions. The algorithm exploits the rotation-poset representation of the set of stable matchings and, in particular, the fact that the rotations affecting each agent form a chain in this poset. To position our result, we also clarify its relation to existing frameworks: we show that our objectives are not captured by the recent minimum-cut representability framework, while identifying a special case that admits a submodular function minimization interpretation.","short_abstract":"We introduce the Stable Matching Problem with Minimum Utility Gap, which seeks a stable matching in which the utilities received by individual agents are as balanced as possible. Our framework can handle many-to-many matchings and general utility functions on partner sets that are consistent with the agents' preference...","url_abs":"https://arxiv.org/abs/2607.07160","url_pdf":"https://arxiv.org/pdf/2607.07160v1","authors":"[\"Yao Sheng\",\"Yu Yokoi\"]","published":"2026-07-08T08:52:28Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}