d4-conf-ecai-2023-0405

The strongest mirror is the paper’s minimum-switch implementation problem. Consider a large co-living development or university housing system: \(N\) residents share a finite set of resident types, where a type records the resident’s valuation of every room and their budget. Standardized rooms and recurring resident profiles make \(N\) much larger than the number \(\tau\) of types plausible. Let the society be a distribution \(\mu\) over those types, and let the rooms remain distinct. Their capacities scale with the population: with total resident mass normalized to \(1\), each of \(N\) rooms has capacity \(1/N\).

Call the continuous problem Mass-Switch Implementation. Its input includes type masses \(\mu_t\), room capacities \(\rho_r\), values \(v_{tr}\), budgets \(b_t\), a rent per resident \(\ell\), and a proposed type-symmetric fractional rent solution \((x,p)\). Here \(x_{tr}\) is the fraction of the lease that each resident of type \(t\) spends in room \(r\), and \(p_t\) is that type’s payment. Require \(\sum_r x_{tr}=1\), \(\sum_t\mu_t x_{tr}=\rho_r\), \(\sum_t\mu_t=1\), \(\sum_r\rho_r=1\), and \(\sum_t\mu_t p_t=\ell\). Also require \(p_t\le b_t\), individual rationality \(\sum_r x_{tr}v_{tr}-p_t\ge0\), and envy-freeness: for every pair \(t,t'\),
\[ \sum_r x_{tr}v_{tr}-p_t \ge \sum_r x_{t'r}v_{tr}-p_{t'}. \]
The room-capacity constraint is the co-modification needed to preserve one room per resident as the population becomes continuous.

A schedule has finitely many phases of rational durations \(\lambda_1,\ldots,\lambda_K>0\), summing to \(1\), and for each type \(t\), a rational distribution \(z_t\) over room sequences \((r_1,\ldots,r_K)\). Every sequence used by type \(t\) must satisfy \(\sum_s\lambda_s\mathbf 1[r_s=r]=x_{tr}\) for every room \(r\). At each phase \(s\), each room must be full:
\[ \sum_t\mu_t\sum_{\mathbf r:r_s=r} z_t(\mathbf r)=\rho_r. \]
The decision problem, Mass-Switch Implementation with threshold \(B\), asks whether such a schedule exists with total switching mass at most
\[ \sum_t\mu_t\sum_{\mathbf r}z_t(\mathbf r) \sum_{s=1}^{K-1}\mathbf 1[r_s\ne r_{s+1}] \le B. \]
Its optimization version minimizes this quantity. The distribution over paths lets a type’s nonatomic cohort divide across different schedules, while each resident’s own time shares still implement the specified fractional allocation.

My anchor is Theorem 3, which the paper proves: MINSUM-SWITCH-IMPLEMENTATION is NP-complete. Its input is a fractional solution \(X\) and an integer threshold \(k\); it asks whether \(X\) has an implementation— a Birkhoff–von Neumann decomposition together with an ordering of its allocations—whose sum of agent switch prices is at most \(k\). The paper proves hardness by reduction from PARTITION. Mass-Switch Implementation mirrors that implementation question, restricted to symmetric rent solutions over a continuous population. Unfolding each type into repeated residents recovers the paper’s matrix view; the difference is that the input is organized by type mass, with \(N\) potentially much larger than \(\tau\).

I would initially bet on tractability for small \(\tau\): mass can be divided among path profiles, which may erase the all-or-nothing choices behind the discrete PARTITION reduction. The concrete questions for a prover are whether the pricing or path-coupling problem admits an algorithm polynomial in the room count \(m\), \(\tau\), and input bit length \(L\), and whether it is at least fixed-parameter tractable in \(\tau\). The difficulty is real: each path must realize exact time shares, and room capacities must balance in every phase. Those constraints may retain hard combinatorics even when many residents share each type.

This case covers only the implementation stage in Sections 5.2–5.3, not the existence or computation of fair fractional rent solutions, the B-EF results, or the whole paper. Its weakest point is that Theorem 3’s hardness is for unrestricted matrices; it does not establish hardness for type-symmetric instances with \(\tau\ll N\). And the paper already fractionalizes allocations. The proposed mirror is not that outcome-space continuity: it makes the resident population a distribution over types, with room supply scaling alongside it. The authors should recognize it as their implementation question in that high-multiplicity regime, while the hardness boundary remains open.