| paper | d4-conf-ecai-2023-0039 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: Both unrestricted and globally ranked preferences give \(\mathrm{NP}\)-complete existence problems, even with uniform dyadic masses. An exact algorithm runs in \(O(\tau L^2+m^\tau\tau^3mL)\), where \(m=\tau\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite set of types \(T\), rational masses \(\mu_t\geq 0\) summing to \(1\), strict rankings \(\succ_t\) of partner types, and, in the restricted version, a global order on unordered type pairs inducing those rankings, does there exist a symmetric nonnegative matrix \(x\) with \(\sum_u x_{tu}=\mu_t\) such that for every \(x_{tu}>0\) and \(x_{sv}>0\), \(v\succ_t u\) implies \(R_s(v)\leq R_t(v)\), where \(R_t(v)=\sum_{w\succ_t v}\mu_w+\mu_v/2\)?
A continuum roommate population described by finitely many complete preference types and rational masses; the decision variable is a symmetric mass-matching matrix \(x\), and the condition compares the normalized midranks \(R_s(v)\) and \(R_t(v)\) whenever one assigned type prefers another assignment’s partner type.
Within the original model, a rank comparison can depend on which named person in a category is considered; the type-level midrank erases that identity-specific information, so the authors must accept rankings over partner categories as the relevant high-multiplicity model.
fatal: False
The mirror covers the existence questions for r-EF, wr-EF, and rBP-EF, including their stated hardness results. It leaves aside the r1-EF polynomial-time result, the wrBP-EF construction, the implication results, and the empirical study.
The strongest mirror I see is a type-level roommate market: many people are matched in pairs, and the fairness test asks whether someone has a *justified* claim to another person’s partner. Here, a type is a complete ranking of partner types. The partner types are categories, so agents of one type share the same relevant preferences.
Let the finite set of types be \(T\), with rational masses \(\mu_t\geq 0\) summing to \(1\). For a type \(t\), define its normalized rank of partner type \(v\) as
\[
R_t(v)=\sum_{w\succ_t v}\mu_w+\frac{\mu_v}{2}.
\]
This is the fraction of the population in types ranked ahead of \(v\), plus half the mass of \(v\)’s own type. It is the continuum counterpart of an agent’s rank divided by population size when people with the same type tie over members of a partner category.
A matching is a symmetric matrix \(x\geq 0\) with \(\sum_u x_{tu}=\mu_t\). Here \(x_{tu}\) is the mass of type-\(t\) agents paired with type-\(u\) agents; symmetry ensures both sides of every pairing are accounted for. A diagonal entry \(x_{tt}\) pairs mass within type \(t\). Because the population is continuous, each type’s mass can be split across partner types. A solution is such a matching whose positive type-pair assignments satisfy the chosen fairness condition. The problem is existence, with no objective, just as in the paper’s anchors.
A plausible regime is a large student-housing or seasonal-worker program where residents rank standardized partner profiles—say, schedules, languages, or household preferences. There could be hundreds of thousands of residents but only hundreds or thousands of distinct complete preference types. This is a co-modification of the paper’s model: its agents rank named individuals, while this mirror ranks partner categories. Normalized rank makes that change defensible, but it is also the main place the authors might resist the analogy.
My lead is Globally-Ranked Continuous Rank-Envy-Free Roommate Existence. An instance gives \(T\), \(\mu\), strict rankings of partner types, and, for the restricted version, a global order on unordered type pairs that induces those rankings. It asks whether a symmetric matching \(x\) exists such that, for every two positive assignments \(x_{tu}>0\) and \(x_{sv}>0\),
\[
v\succ_t u \quad\Longrightarrow\quad R_s(v)\leq R_t(v).
\]
In words, if type \(t\) prefers the partner category \(v\) assigned to type \(s\) over its own assignment \(u\), then \(s\) must not rank \(v\) worse than \(t\) does.
The anchor is Theorem 2, proved in this paper: deciding whether a roommate instance has an r-EF matching is NP-complete, even under globally-ranked preferences. This is the cleanest hardness anchor because it concerns the paper’s central, strict fairness notion and survives a strong preference restriction. I would expect the continuous question to be hard for continuum-specific reasons, though that is a conjecture, not a transfer of the theorem: a continuous matching can split mass, while the paper’s reduction reasons about individual agents. The continuous problem’s challenge is choosing a compatible support of type-pair assignments; once a support is fixed, the mass constraints are linear. It asks whether the hardness remains when the discrete pairing choices give way to divisible masses.
A second question is Globally-Ranked Continuous Weak Rank-Envy-Free Roommate Existence, using the same instance and matching. For every \(x_{tu}>0\) and \(x_{sv}>0\), it requires
\[
v\succ_t u\ \text{and}\ R_t(v)<R_s(v)
\quad\Longrightarrow\quad
R_u(t)\leq R_t(v).
\]
This mirrors the paper’s weak relaxation: an agent with a justified rank claim does not complain if their current partner ranks them at least as well as the claimant ranks the desired partner.
Its anchor is Proposition 6, proved in this paper: deciding whether a roommate instance has a wr-EF matching is NP-complete under globally-ranked preferences. The result uses the same construction as Theorem 2. I again expect continuum-specific hardness: weakening the complaint condition may create room for fractional assignments, but the support choices still interact across types. A useful next question is whether this version admits a polynomial algorithm for bounded \(\tau=|T|\), or whether hardness persists with small support.
The third question is Continuous BP Rank-Envy-Free Roommate Existence. It has the same mass-matching input, but for every two positive assignments \(x_{tu}>0\) and \(x_{sv}>0\), it requires
\[
v\succ_t u\ \text{and}\ R_t(v)<R_s(v)
\quad\Longrightarrow\quad
s\succ_v t.
\]
So when \(t\) has a justified claim to the partner type \(v\) assigned to \(s\), that type \(v\) must prefer its current partner category \(s\) over \(t\).
Its anchor is Theorem 3, proved in this paper: deciding whether a roommate instance has an rBP-EF matching is NP-complete, with no preference restriction stated. I expect this type-level problem may also be hard for continuum-specific reasons, since it combines support selection with a blocking-style condition. The paper’s theorem alone does not establish that: fractional mass could change existence. The further question is whether global ranking or other structured type preferences make this continuous version tractable.
These are existence mirrors of three computational results, not a mirror of the whole paper. In particular, they leave out the paper’s other stability and optimality results. I would not use the fact that matching is already a “continuous” allocation as support: the proposed continuation is of the population, with masses of preference types and fractional type-level assignments.
The weak point is exact fidelity to the paper’s strict preferences over named agents. In the proposed regime, people rank categories, and members of a category tie at the type level; normalized midranks represent those ties. That is a plausible high-multiplicity roommate problem, but it is not a theorem that the authors’ discrete instances reduce to it. The case survives on the narrower claim that the same rank-justified-envy question makes sense for a large population of agents with shared preferences over partner types—and that its complexity is open.
The paper does have computational anchors: Theorem 2 proves r-EF existence NP-complete even under globally ranked preferences; Proposition 6 does so for wr-EF; and Theorem 3 does so for rBP-EF. So the negative case cannot rest on a lack of results to mirror.
Its strongest objection is that all three results turn on comparisons between particular people. Rank-envy asks whether agent \(i\) ranks the *specific person* matched to \(j\) above \(j\)’s own rank of that same person. The weak variants add comparisons involving the specific people in the current pairs. A high-multiplicity model with types ranked by partner category replaces those comparisons with comparisons between category ranks.
The proposed midpoint rank \(R_t(v)\) shows where that replacement loses information. In a finite population, members of category \(v\) occupy a range of ranks. If types \(t\) and \(s\) place the categories ahead of \(v\) equally, the original comparison for a particular person \(q\in v\) can still depend on whether \(t\) or \(s\) ranks \(q\) earlier within the category. The midpoint assigns both types the same rank for \(v\), erasing that comparison. A common tie-break order or genuine indifference within categories makes the mass rank coherent, but changes the paper’s strict, person-level fairness condition. The rank comparisons are especially sensitive to this quotient: a one-place difference remains decisive in the finite model even when its normalized difference tends to zero.
That same change reaches each anchor. Theorem 2 and Proposition 6 use globally ranked preferences over named agents; a global order over type pairs is a different restriction once many people are collapsed into a category. Theorem 3’s BP condition is even more explicitly person-level. There is also a direction error in the proposed BP mirror: the paper requires the desired partner to prefer the envious agent, so the type-level condition should be \(t\succ_v s\), not \(s\succ_v t\). Correcting that fixes the formula, but not the loss of identity information.
A richer model could retain continuous traits and define ranks by the mass of people each agent prefers to a given partner. But to ask a computational complexity question, it would need a finite encoding of the trait space, preference functions, and population distribution. With finite support and category rankings, the problem is well-defined, but the fairness constraints depend on which assignment cells are positive; once that support is chosen, the remaining mass feasibility is a fractional matching problem. That makes the interesting combinatorics largely about support selection, and gives a weaker connection to the continuous-optimization machinery motivating ChoCo.
This is a case against treating the three results as faithful high-multiplicity mirrors. It is not a convincing case that no worthwhile mirror exists. A large roommate pool whose members rank standardized partner profiles is plausible, and the resulting type-level fairness question could be one the authors recognize as theirs. Under the programme’s permissive scope, the negative case is weak: the identity loss is real, but it does not rule out a valuable, explicitly type-level extension.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.