| paper | d4-conf-aaai-2008-0140 |
| 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}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given finitely many role types \(T\), masses \(\mu_t=1/|T|\), finite owned graphs \(H_t\), rational-shift cross-role conflict rules on \(\mathbb{T}=\mathbb{R}/\mathbb{Z}\), and a palette bound \(q\), decide whether \(q\) is the minimum number of colors in a legal measurable coloring and whether such a \(q\)-coloring exists with \(\left|\{c_{t,p}(\theta):p\in P_t\}\right|=\chi(H_t)\) for every role \(t\) and almost every \(\theta\).
A continuum of recurring scheduling cells, each containing one agent of each role type \(t\in T\), with mass \(\mu_t=1/|T|\). Each type has an owned conflict graph \(H_t=(P_t,E_t)\), and rational-shift rules specify cross-role conflicts. Assign ordinary discrete colors measurably as \(c_{t,p}(\theta)\); minimize the global palette size subject to legality almost everywhere and each agent using exactly \(\chi(H_t)\) colors almost everywhere.
A distribution over roles does not by itself specify the conflict graphing, so this mirror depends on an additional relational input whose high-multiplicity encoding the paper does not study.
fatal: False
Covers Theorem 7’s NP-complete decision problem for individual-rational partitions of odd cycles; leaves the Pareto-efficiency and fairness results, the cycle characterizations, and Theorem 9 on split graphs untouched.
The strongest positive case is Theorem 7, proved in this paper. It states that, even when the global graph is an odd cycle and the number of agents is \(O(|V|)\), deciding whether the agent partition is individual rational is NP-complete. Here “individual rational” means that the cycle has a legal globally optimal coloring and every agent’s subgraph uses exactly \(\chi(G_i)\) colors. Since an odd cycle has chromatic number \(3\), this asks whether it has a legal \(3\)-coloring that lets every agent use as few colors as its own subgraph requires. The paper reduces \(3\)-COL to this question by constructing an odd cycle and partition from the input graph.
A continuous version I find credible is Continuum Individual-Rational Coloring. Think of a large federation of recurring scheduling cells. Each cell has one agent of each role \(t\in T\), and the cells are indexed by \(\theta\in\mathbb T=\mathbb R/\mathbb Z\). The population type \(t\) has mass \(\mu_t=1/|T|\). A type specifies the agent’s finite owned conflict graph \(H_t=(P_t,E_t)\), its meeting positions, and its role in the shared conflict pattern. Across roles, a finite list of rules \((t,p,u,q,\delta)\), with rational \(\delta\in\mathbb Q/\mathbb Z\), says that meeting \(p\) of role \(t\) in cell \(\theta\) conflicts with meeting \(q\) of role \(u\) in cell \(\theta+\delta\). The rules are uniform across the population, so agents of a role share the same structure up to rotation of the cells.
A coloring is a measurable assignment \(c_{t,p}(\theta)\) of ordinary, discrete color labels to meetings. It is legal when conflicting meetings receive different colors almost everywhere. Let \(q^\star\) be the least number of colors permitting a legal measurable coloring. The decision problem is: given this finite graphing description and a palette size \(q\), is \(q=q^\star\), and is there a legal coloring with \(q\) colors for which, for every role \(t\) and almost every \(\theta\),
\[
\left|\{c_{t,p}(\theta):p\in P_t\}\right|=\chi(H_t)?
\]
A yes solution is that measurable coloring together with the fact that \(q\) is globally minimal. Individual rationality remains a per-agent condition; “almost every” accounts for the atomless population.
The connection to Theorem 7 is exact in the zero-shift subfamily. Make each agent of the odd-cycle instance a role, let \(H_t\) be its part of the cycle, and put \(\delta=0\) on each cross-role cycle edge. At every \(\theta\), the agents form a copy of the same partitioned odd cycle, so \(q^\star=3\). An individual-rational measurable coloring exists exactly when the original cycle partition is individual rational: any such coloring restricts to a valid individual-rational coloring for almost every \(\theta\), and any discrete solution can be repeated across all cells. The construction has finite rational encoding and preserves the reduction’s polynomial size. Thus this mirror is NP-hard by hardness transfer, a Class B case; I make no claim that it is in NP.
The scenario fits the paper’s stated scheduling application: many recurring scheduling cells, with the same office roles and shared conflict rules. The type count \(\tau=|T|\) is finite for each instance while each role has a continuum of agents. In the hard instances, however, \(\tau\) grows with the source graph. This mirrors the paper’s actual theorem, which uses \(O(|V|)\) agents; it does not claim that hardness survives with a fixed number of types. The continuous object is the agent population, while meetings still receive integral color labels.
This case covers Theorem 7’s individual-rationality decision problem. It does not extend the paper’s Pareto-efficiency or fairness results. Further questions include whether the problem becomes tractable for bounded \(\tau\), whether nonzero shifts introduce continuum-specific hardness or tractability, and whether Theorem 9’s split-graph characterization extends to these population graphings.
My weakest point is that the clean hardness reduction repeats the finite instance across cells: the population becomes continuous, but the hard combinatorics remain in the finite role template. A referee could regard that as a conservative high-multiplicity lift with little computational benefit. I still think it is a defensible mirror of the authors’ problem: it preserves their central question—whether global optimality can coexist with each agent’s local color requirement—and broader shifted interaction patterns give the model room to ask genuinely continuous questions.
Theorem 7 is a real computational anchor: deciding whether a partition of an odd cycle is individual rational is NP-complete. The strongest objection is about what that problem takes as input. Its essential data are a particular graph and a partition of its vertices among agents. An agent’s role is defined by which vertices it owns and how those vertices connect to everyone else. A distribution over agent types alone cannot preserve that incidence pattern; the proposed mirror has to add a graphing that says which agents interact.
For the proposed graphing, that extra structure makes the continuum largely a set of repeated finite instances. If all shifts \(\delta\) are rational, they generate a finite subgroup of the circle. With \(D\) the least common multiple of their denominators, the graphing breaks into finite orbits of at most \(D\) cells. Measurable feasibility then reduces to feasibility on a finite orbit, repeated across the circle. In the zero-shift reduction, it is exactly the same partitioned odd cycle at every \(\theta\). The masses \(\mu_t\) do not determine the interaction pattern or enter the individual-rationality condition; the finite template does.
Repeating scheduling cells can be a sensible high-multiplicity setting, so that point alone does not rule out the mirror. But the paper’s question is whether a *single* coordinated graph admits a globally optimal coloring that is individually rational for each owner. Repeating the entire graph across a continuum gives many copies of that question, not a population-level coloring question whose inputs are type masses. Asking what fraction of cells admit such a coloring could use mass, but it would be a different objective from Theorem 7’s decision problem.
A stronger version would couple cells through irrational shifts, producing infinite orbits and potentially nontrivial measurable-coloring questions. That is mathematically plausible, but it adds a dynamical network to the paper’s finite graph-partition model. Its complexity could be worth studying; the difficulty is establishing that it is a continuous mirror of the authors’ problem rather than a new problem about measurable graph colorings.
So the negative case is weak at its hardest point: the recurring-cell scenario is plausible, and a reader could reasonably count its repeated roles as a high-multiplicity population. I would argue against this anchor on the grounds that the proposed continuum adds little population-level structure, but I cannot honestly conclude that no worthwhile mirror exists in any scenario.
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.