The Min Max Average Cycle Weight Problem
For researchers in combinatorial optimization and fair division, this paper identifies a new problem and its complexity boundary.
The paper introduces the Min Max Average Cycle Weight problem, motivated by fair redistribution of apartments, and shows it reduces to maximum-weight matching in the clean-slate case but remains open in general.
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.