d4-conf-sagt-2024-0018

The strongest mirror I see is egalitarian optimization over stable half-partitions of a typed population. It keeps the paper’s central object—stability of predecessor and successor partnerships—and its profile-cost objective, while making the population itself continuous.

Consider a non-atomic society with \(\tau\) types, rational masses \(\mu_i\) summing to \(1\), and a strict ranking \(r_i\) over partner types for each type \(i\). A type is a cohort whose members share the same preferences over cohorts; they are indifferent among people within a cohort. This is plausible, for example, in a large university or co-living programme assigning thousands of residents to partnerships for alternating periods, where people rank lifestyle or schedule cohorts rather than named individuals. One could have tens of thousands of residents and a few dozen types.

Let \(q_{i,j,k}\) be the mass of type-\(i\) people whose successor is type \(j\) and predecessor is type \(k\). Each person still has definite predecessor and successor partnerships; \(q\) records how much mass receives each configuration. For a continuous stable half-partition, require that each type’s mass appears once in each role: \(\sum_{j,k}q_{i,j,k}=\mu_i\), \(\sum_{a,k}q_{a,i,k}=\mu_i\), and \(\sum_{a,j}q_{a,j,i}=\mu_i\). Also require \(q_{i,j,k}=0\) whenever \(r_i(j)>r_i(k)\), so the successor is at least as preferred as the predecessor.

To express the paper’s no-blocking condition, let \(b_{i,h}(q)\) be the mass of type-\(i\) people whose predecessor ranks below type \(h\): \(b_{i,h}(q)=\sum_{j,k:\,r_i(h)<r_i(k)}q_{i,j,k}\). For distinct types \(i,h\), stability requires \(b_{i,h}(q)=0\) or \(b_{h,i}(q)=0\); for \(i=h\), require \(b_{i,i}(q)=0\). Otherwise positive masses on both sides could form a blocking pair. This is a continuous version of the paper’s predecessor-based stability test.

My lead is Continuous Egalitarian Stable Half-Partition: given the typed society and a rational budget \(K\), decide whether it has a stable \(q\) with cost at most \(K\), where
\[ \mathrm{cost}(q)=\frac12\sum_{i,j,k}q_{i,j,k}\bigl(r_i(j)+r_i(k)\bigr). \]
Return such a \(q\) if one exists. As the paper’s stable-partition theorem guarantees existence in its finite model, the cleanest analogue is to consider typed societies admitting at least one stable \(q\), or to include a feasible \(q\) as a certificate that the budget constraint is the question at issue.

The anchor is Theorem 4.16, proved in this paper: deciding, given an SR instance and integer \(k\), whether it has a stable partition of egalitarian cost at most \(k\) is NP-complete, whether or not the instance is promised solvable. The paper reduces from the stable-matching hardness of Feder [19] for the solvable case, then extends the result to unsolvable instances. The proposed continuous problem mirrors the same stable-partition objective; it asks whether hardness survives when masses can split among type-level partnership configurations.

A second anchor is Theorem 4.17, also proved here: unless \(P=NP\), no polynomial-time algorithm approximates the maximum-first-choice stable-partition problem within any constant factor, for either solvable or unsolvable instances. The paper builds on Simola and Manlove [57] for the stable-matching result and extends it to partitions. Its typed-population counterpart uses the same stable \(q\) and maximizes
\[ \mathrm{FC}(q)=\sum_{i,j,k}q_{i,j,k} \bigl(\mathbf 1[r_i(j)=1]+\mathbf 1[r_i(k)=1]\bigr). \]
Given a rational target \(B\), the associated decision problem asks whether some stable \(q\) has \(\mathrm{FC}(q)\ge B\); the optimization problem returns a maximizing \(q\). This is a distinct objective on the same feasible set, and the paper’s inapproximability result makes it a useful second anchor.

I expect both typed problems to be continuum-specifically hard, provisionally. The original theorems do not establish that: their reductions use named agents and discrete preference lists, whereas this mirror groups people by cohort preference and permits type mass to split. But the typed stability conditions still contain a choice for each pair of types about which side must have zero blocking mass. Fixing those choices yields linear constraints, so a direct baseline is to enumerate the \(2^{\binom{\tau}{2}}\) choices and solve an LP for each. That gives an \(2^{\binom{\tau}{2}}\operatorname{poly}(\tau,L)\) algorithm and makes fixed-\(\tau\) instances tractable. The open question is whether the choice structure can be handled in polynomial time in \(\tau\), or whether it makes the variable-\(\tau\) problem hard.

The mirror is plausible because its society is the distribution \(\mu\), its decision is a stable half-assignment of that mass, and its objectives are exactly the paper’s profile cost and first-choice count at type level. Fractional values arise from the mass of people in each configuration, not from giving an individual a fractional predecessor or successor.

The weakest point is the change from strict rankings of named agents to rankings of types, with indifference among members of a type. That changes blocking opportunities and rank costs, so the paper’s theorems cannot simply be carried over. It is also a real extension: the paper notes ties as future work. Still, cohort preferences are a coherent high-multiplicity regime, and the proposed problems preserve the stable-partition question rather than replacing it with an outcome-space or axiomatic continuity question. The first bridge to establish would be a dictionary between discrete instances with homogeneous cohorts and the continuous \(q\)-model: a discrete stable partition induces type-level masses, while the reverse direction needs a realization or rounding result.