{"ID":2889926,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.20253","arxiv_id":"2507.20253","title":"The Min Max Average Cycle Weight Problem","abstract":"When an old apartment building is demolished and rebuilt, how can we fairly redistribute the new apartments to minimize envy among residents? We reduce this question to a combinatorial optimization problem called the *Min Max Average Cycle Weight* problem. In that problem we seek to assign objects to agents in a way that minimizes the maximum average weight of directed cycles in an associated envy graph. While this problem reduces to maximum-weight matching when starting from a clean slate (achieving polynomial-time solvability), we show that this is not the case when we account for preexisting conditions, such as residents' satisfaction with their original apartments. Whether the problem is polynomial-time solvable in the general case remains an intriguing open problem.","short_abstract":"When an old apartment building is demolished and rebuilt, how can we fairly redistribute the new apartments to minimize envy among residents? We reduce this question to a combinatorial optimization problem called the *Min Max Average Cycle Weight* problem. In that problem we seek to assign objects to agents in a way th...","url_abs":"https://arxiv.org/abs/2507.20253","url_pdf":"https://arxiv.org/pdf/2507.20253v1","authors":"[\"Noga Klein Elmalem\",\"Rica Gonen\",\"Erel Segal-Halevi\"]","published":"2025-07-27T12:49:37Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.GT\"]","methods":"[]","has_code":false}