| paper | d4-conf-ijcai-2021-0372 |
| 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: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite project set \(P\) partitioned into groups \(P_1,\ldots,P_q\), integer quotas \((\ell_j,u_j)\), a scale \(N\), and a listed support \(T\) of strict rankings with rational masses \(\mu_t>0\) summing to \(1\), does there exist a selection \(y\in\{0,1\}^{P}\) and assignment masses \(x_{tr}\geq 0\) such that \(\sum_{r\in P}x_{tr}=\mu_t\), \(\sum_{t\in T}x_{tr}=y_r/N\), \(\sum_{r\in P}y_r=N\), and \(\ell_j\leq\sum_{r\in P_j}y_r\leq u_j\) for every \(j\), with \(x_{tr}>0\) implying \(r\succ_t p\) for every unselected project \(p\) (that is, every \(p\) with \(y_p=0\))?
Mass-FF-CSA: each type \(t\) is a complete ranking over distinct projects; the population has rational mass \(\mu_t\); binary variables \(y_p\) select \(N\) projects, each receiving mass \(1/N\); assignment masses \(x_{tp}\) fill those selected projects and all type supplies; group quotas constrain selection, and every type assigned to a project must rank it above every unselected project.
The mirror covers Theorem 2’s frustration-free allocation existence problem under project quotas, including either of its stated restrictions. It leaves the popularity results, other characterizations, empirical comparisons, and dynamics aside.
The strongest mirror I believe is a high-multiplicity version of the paper’s frustration-free allocation problem with project quotas. Picture a large conference with many speakers and more available presentation slots than speakers. Slots are grouped by day or track, with lower and upper quotas on how many slots are used. Speakers share a small number \(\tau\) of complete rankings over the slots: for example, \(N\) speakers may fall into a handful of common day-and-time preference profiles. The slots remain distinct projects; the population is what becomes continuous.
Let \(\mu_t\) be the fraction of speakers with ranking \(t\), with rational masses summing to \(1\). Let \(N\) be the population scale, so each selected slot has capacity \(1/N\) in normalized mass. This keeps the number of selected slots equal to \(N\), while allowing a cohort of one ranking type to be divided across slots. The mass assigned to any particular slot is still an integral bundle—one slot per unit of population mass. Group quotas continue to count selected slots.
The paper’s anchor is Theorem 2, proved there: deciding whether a constrained selection-allocation instance has an FF allocation is NP-complete, even under group-oriented preferences or, separately, when there is no trivial group upper quota. The paper’s reduction establishes those restrictions separately, not simultaneously.
I would hand a prover this mirror, Mass-FF-CSA. Its input is a finite set of projects \(P\), partitioned into groups \(P_1,\ldots,P_q\); integer quotas \((\ell_j,u_j)\); a population scale \(N\); and a listed support \(T\) of strict rankings, each with rational mass \(\mu_t>0\). The question is whether there are binary selection variables \(y_p\) and nonnegative assignment masses \(x_{tp}\) such that
\[
\sum_{p\in P}x_{tp}=\mu_t,\qquad
\sum_{t\in T}x_{tp}=y_p/N,\qquad
\sum_{p\in P}y_p=N,
\]
and
\[
\ell_j\leq \sum_{p\in P_j}y_p\leq u_j
\quad\text{for every }j.
\]
The frustration-free condition is that whenever \(x_{tq}>0\), every unselected project \(p\) is ranked below \(q\) by type \(t\): \(q\succ_t p\). A solution is such a pair \((x,y)\).
I expect this problem to be continuum-specifically hard when the project set and quota structure grow. The mass flow removes the need to decide which named individual gets each slot, but the choice of selected projects remains binary and subject to group quotas. That leaves substantial selection combinatorics. Theorem 2 motivates the question but does not prove its hardness: fractional mass assignments might make some instances feasible that have no discrete FF allocation. A new reduction—or a tractability result—would be needed, particularly for the regime \(N\gg\tau\).
This is a close match to the authors’ question: the allocation remains one project per person, selection remains part of the decision, quotas are still on project groups, and FF still asks whether anyone prefers an unselected project to their assignment. It covers Theorem 2’s constrained FF-existence result, not the paper’s popularity variants, empirical comparisons, or dynamics. Useful follow-up questions are whether the continuous problem is tractable for fixed \(\tau\), whether the paper’s group-oriented and no-trivial-upper-quota condition yields a polynomial continuous algorithm, and how its complexity depends on \(m,\tau,L\), and \(q\).
The weak link is the slot-capacity scaling. In the discrete paper, each project is assigned to exactly one named agent. In the mirror, each slot carries mass \(1/N\), and a preference cohort can split across slots. That is a natural high-multiplicity flow model for a large scheduling population, but authors who see named project ownership as essential to their question could reject it as too much of a change.
Theorem 2 is the strongest anchor to attack: it is a named computational result, and agents with identical complete rankings are interchangeable for the problem. So “agents have identities” does not defeat the mirror.
The best objection is that the proposed large-population story must scale the project set along with the population. With one agent per project, \(n\leq m\); holding the projects fixed puts a hard ceiling on the number of agents. To take \(N\) large, the number of distinct slots, the selection variables, and the quota bounds must grow too. The model then scales the population and its resource universe together, with agents ranking an expanding set of named projects. The conference example works only if the supply of distinct slots grows roughly with the number of speakers. Keeping the slots fixed would require multiple agents per project, a capacitated extension that changes the paper’s matching constraint.
There is also little automatic smoothing in the proposed mass assignment. For a fixed selected set and type masses with \(N\mu_t\) integral, the assignment constraints are a bipartite matching flow with integer capacities. The flow polytope is integral, so fractional assignment introduces no new flexibility on that aligned subfamily. The remaining selection decisions \(y_p\) are binary and carry the project and quota combinatorics. That makes this a plausible high-multiplicity formulation, but the proposed mirror does not by itself reveal a continuous-optimization structure that helps with Theorem 2.
This case against is weak as a universal verdict. The authors could reasonably recognize a capacitated version as their problem—their conclusion calls extensions to multiple agents per project natural—and large cohorts choosing among many distinct projects are conceivable. Theorem 2 still motivates a meaningful question about what happens when preference types repeat, and the supplied prior-art distinctions give no basis to call that question already solved. I can make the mirror look less like a fixed-environment population limit, but I cannot honestly defeat it across all plausible scenarios.
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.