| paper | d4-conf-atal-2021-0160 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: the feasibility problem belongs to \(\mathrm P\), with running time polynomial in \(\tau\) and \(L\) for fixed \(m=3\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.2
statement extracted from the paper’s text layer
Given a finite set \(R\) of positive integer reward types, a rational distribution \(\mu\) over \(R\), and a target \(\kappa\), consider candidate mass \(1\) and a job pool of mass \(3\), with reward-\(a\) jobs of mass \(3\mu_a\). For each multiset \(Q\) of three rewards from \(R\) summing to \(\kappa\), let \(\lambda_Q\ge 0\) be the mass of candidates assigned that triple. Does there exist \(\lambda\) such that \(\sum_Q\lambda_Q=1\) and, for every \(a\in R\), \(\sum_Q m_a(Q)\lambda_Q=3\mu_a\), where \(m_a(Q)\) counts occurrences of \(a\) in \(Q\)?
A continuum of interchangeable candidate mass receives integral triples of jobs; job types are rewards in \(R\), and the inventory of each reward scales with candidate mass. The variables \(\lambda_Q\) specify the mass assigned to each triple, and feasibility enforces both the per-candidate reward target \(\kappa\) and the job-type supply constraints.
Covers the \(mK_{1,3}\) star-forest instances used in Theorem 3.2’s 3-Partition reduction; it leaves the other hardness results, the FPT results, and Fair-NET on general infrastructure graphs alone.
The strongest positive case is the star-forest hardness result, because the paper’s own job-assignment example gives it a natural high-multiplicity interpretation.
Theorem 3.2—proved in this paper by reduction from 3-Partition—says that Fair-NET is NP-hard even when the infrastructure is a forest of maximum degree \(3\). Since such forests have feedback vertex set number \(0\), it also says Fair-NET is para-NP-hard parameterized by \(\mathrm{fvs}+\Delta\). The reduction uses \(m\) copies of \(K_{1,3}\): the leaves carry the \(3m\) job rewards in \(W\), and the \(m\) centers carry the target label \(\kappa=\sum W/m\). A fair labeling exists exactly when the jobs can be split among the \(m\) centers in triples summing to \(\kappa\).
My lead mirror is Continuous Three-Job Fair Assignment. An instance has a finite set \(R\) of positive integer reward types, a rational distribution \(\mu\) over \(R\), and a target \(\kappa\). Imagine candidate mass \(1\), each unit representing a candidate who must receive exactly three jobs; the shared job pool has mass \(3\), with fraction \(\mu_a\) of its jobs of reward type \(a\). The question is whether the jobs can be assigned so every candidate’s three rewards sum to \(\kappa\).
Precisely, let \(Q\) range over multisets of three elements of \(R\) whose rewards sum to \(\kappa\). A solution is a set of nonnegative masses \(\lambda_Q\) such that \(\sum_Q\lambda_Q=1\) and, for every \(a\in R\), \(\sum_Q m_a(Q)\lambda_Q=3\mu_a\), where \(m_a(Q)\) counts how often reward \(a\) occurs in \(Q\). Each unit of candidate mass therefore receives an *integral triple* of job types; only the mass of candidates assigned to each triple can be fractional. This is the continuous \(K_{1,3}\) infrastructure: every leaf sees its center’s label \(\kappa\), and every center sees three rewards totaling \(\kappa\), so all neighborhood sums agree.
This seems like a question the authors would recognize. The paper itself describes assigning jobs to candidates with equal total reward, and its hardness reduction is exactly the three-jobs-per-candidate star case. A plausible regime is a very large program with many interchangeable teams, each assigned three tasks, where rewards come from a small standardized catalog: \(N\) teams, \(3N\) jobs, and \(\tau=|R|\) reward types with \(\tau\ll N\). Type must include every relevant job feature, such as eligibility; if those features are highly individualized, the support grows and the high-multiplicity interpretation weakens.
I expect this mirror to be Class A. There are at most \(\binom{\tau+2}{3}\) triple variables, and the conditions above form a rational linear-program feasibility problem. Its size is polynomial in \(\tau\) and the input bit length \(L\). The finite problem requires whole jobs to be partitioned among the actual candidates; the continuous problem allows different fractions of the candidate population to receive different integral triples. That makes the hardness reduction’s partitioning combinatorics a plausible source of hardness that can dissolve with population continuization.
There is also a clean bridge to the discrete problem. Any fair assignment to \(m\) candidates gives a feasible \(\lambda\) with masses in multiples of \(1/m\). Conversely, a rational feasible \(\lambda\) can be scaled to give a fair assignment in some replicated finite instance. It need not give a fair assignment at the original finite population size. That leaves useful follow-up questions about the required replication factor and finite-size rounding.
The soft spot is scope: this mirror fixes the infrastructure to repeated three-job stars, the job-assignment regime the paper explicitly introduces. It does not continuize arbitrary input graphs or the other hardness results. Also, the 3-Partition reduction can use many distinct rewards, so it does not itself establish hardness in the small-\(\tau\) regime that best motivates the continuum. Those limits matter, but they do not make this a made-up analogue: it is a precise continuous version of a job-allocation problem in the paper, and it covers a named hardness anchor on its own terms.
Theorem 3.2 is the hardest anchor to defeat, and I do not think it falls. The paper itself gives the job-assignment interpretation, and its star-forest reduction is exactly that case: each candidate receives three jobs, and each candidate’s reward sum must equal \(\kappa\). If candidates are interchangeable and jobs are grouped by all relevant features, the continuous model preserves the per-candidate constraint by assigning each unit of candidate mass an integral triple. Only the mass assigned to each triple is fractional. That is a credible high-multiplicity regime, with no apparent loss of identity information the question needs.
The proposed feasibility system is a faithful continuous version: it asks whether the job-type distribution can be expressed as a mixture of reward triples summing to \(\kappa\). It is an LP with \(O(\tau^3)\) triple variables. So the continuum does not collapse the question; some job distributions admit such a mixture and others do not. The fact that a rational solution may require a replicated finite instance, rather than the original population size, is a meaningful part of the high-multiplicity bridge.
The strongest objection I can make is about the result’s reach and novelty. This mirror isolates the paper’s simplest application, and its algorithm follows directly from a configuration LP. It does not address Fair-NET on general infrastructure graphs. Also, when the reward support is fixed, the corresponding discrete star problem can be expressed with integer counts of the finitely many valid triples, so the paper’s NP-hardness does not establish hardness in that regime. These points make the mirror narrower than the paper’s overall study, but they do not defeat it: the continuous question still has a plausible large-population setting, and distinguishing its fractional feasibility from discrete partitioning is precisely the kind of result the programme seeks.
So the negative case is weak here. I would not argue that this mirror is unworthy of the programme’s time; Theorem 3.2 survives the strongest version of the proposed mirror.
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.