Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor O(|bV |) agents, determining whether a par- tition of C2k+1 is individual rational is NP-Complete. Surely the problem is in NP—a certificate is a coloring of C2k−1. We can verify such a certificate (in polynomial time) by checking legality, making sure floating agents are unicol- ored while agents with edges are painted with exactly 2 col- ors, and confirm that a total of 3 colors were used. For com- pleteness, we reduce the problem 3-COL to finding such individual rational colorings.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive masses, encoded as binary rationals; here \(\mu_t=1/\tau\). Thus \(\tau\) is the support size, not the number of possible types.
Each type owns a nonempty finite simple graph \(H_t=(P_t,E_t)\). Agents are \((t,\theta)\), with \(\theta\in\mathbb T=\mathbb R/\mathbb Z\), distributed according to \(\mu_t\,d\theta\), where \(d\theta\) is normalized Lebesgue measure; agent \((t,\theta)\) owns vertices \((t,p,\theta)\) for \(p\in P_t\).
Input also includes a finite list \(R\) of undirected conflict rules \((t,p,s,r,\delta)\), where \(t\ne s\), \(p\in P_t\), \(r\in P_s\), and \(\delta\in\mathbb Q\cap[0,1)\), encoded in binary. Such a rule joins \((t,p,\theta)\) to \((s,r,\theta+\delta)\), with addition modulo \(1\). Internal edges are exactly copies of \(E_t\) at each \(\theta\).
A legal measurable \(k\)-coloring consists of Lebesgue measurable maps \(c_{t,p}:\mathbb T\to\{1,\ldots,k\}\), satisfying \(c_{t,p}(\theta)\ne c_{t,r}(\theta)\) for every internal edge and \(c_{t,p}(\theta)\ne c_{s,r}(\theta+\delta)\) for every conflict rule, almost everywhere.
Let \(\chi_{\mathrm{meas}}\) be the least positive integer \(k\) admitting a legal measurable coloring, without any individual rationality requirement. A coloring is individually rational when \(\left|\{c_{t,p}(\theta):p\in P_t\}\right|=\chi(H_t)\) for every \(t\), almost everywhere.
Given a positive binary integer \(q\), the decision problem asks whether both \(q=\chi_{\mathrm{meas}}\) and an individually rational legal measurable \(q\)-coloring exists. Set \(m=\sum_{t\in T}|P_t|\), and let \(L\) be the total input bit length; state running times in \(m,\tau,|R|,q,L\).
Is this decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For discrete societies, deciding whether a partition of an odd chordless cycle admits a globally minimum coloring using exactly each agent's induced chromatic number is \(\mathrm{NP}\)-complete when the number of agents can grow linearly with the number of vertices ([Blum–Rosenschein, 2008](https://cdn.aaai.org/AAAI/2008/AAAI08-004.pdf)).
No result settling exactly the measurable decision problem defined above was located in the literature search.
The problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. This holds even when:
Thus hardness persists when the global measurable chromatic number is known in advance. The difficulty comes entirely from individual rationality.
Suppose every conflict shift is zero. Define a finite graph \(F\) with vertex set \(\{(t,p):t\in T,\ p\in P_t\}\), containing the internal edges and the edges specified by the conflict rules.
Lemma. For every positive integer \(k\):
Proof. A finite coloring gives measurable coloring functions constant in \(\theta\), preserving both legality and the number of colors used by each type.
Conversely, take a legal measurable coloring. Each edge constraint fails only on a null set. There are finitely many constraints, so their exceptional sets have a null union. Choose \(\theta\) outside that union. Because all shifts are zero, the assignment \((t,p)\mapsto c_{t,p}(\theta)\) is a proper coloring of \(F\).
If the measurable coloring is individually rational, include the finitely many exceptional sets for individual rationality in the union before choosing \(\theta\). The resulting finite coloring uses exactly \(\chi(H_t)\) colors on each type. This proves both assertions. Consequently, \(\chi_{\mathrm{meas}}=\chi(F)\). ∎
The uniform positive masses cause no obstruction: null sets for each type are precisely Lebesgue null sets.
We reduce from graph three-colorability: given a finite simple graph \(G\), decide whether it has a proper coloring with at most three colors. This is the standard \(\mathrm{NP}\)-complete problem used as the starting problem in [Blum–Rosenschein, Theorem 7](https://cdn.aaai.org/AAAI/2008/AAAI08-004.pdf). The construction below is independent of their cycle construction.
Form \(G'\) by adjoining a disjoint triangle to \(G\), then deleting isolated vertices. These operations preserve three-colorability: isolated vertices can always be colored, and the added triangle can be colored with three colors.
Enumerate the edges of \(G'\) as \(e_i=\{u_i,v_i\}\), for \(1\leq i\leq s\). Here \(s\geq3\). Orient each edge arbitrarily to choose the notation \(u_i,v_i\).
Create distinct vertices \(a_i,b_i,z_i\) for each edge. Set \(\varepsilon=0\) when \(s\) is odd and \(\varepsilon=1\) when \(s\) is even. If \(\varepsilon=1\), create one additional vertex \(w\).
Make these vertices into a chordless cycle in the order
\(a_1,b_1,z_1,a_2,b_2,z_2,\ldots,a_s,b_s,z_s\),
inserting \(w\) between \(z_s\) and \(a_1\) when it exists. The cycle length is \(m=3s+\varepsilon\), which is odd.
Partition the cycle vertices into types as follows:
Every type is nonempty because \(G'\) has no isolated vertices.
Every cycle edge has endpoints in different types. Indeed, \(a_i\) and \(b_i\) belong to different types because \(u_i\neq v_i\); all remaining edges involve singleton separator types.
Let every \(H_t\) be the edgeless graph on its assigned vertices. Encode every cycle edge as one conflict rule with shift zero. Set every mass to \(1/\tau\), and set \(q=3\).
This is a valid instance of the stated measurable problem.
The finite graph \(F\) from the lemma is exactly the constructed odd chordless cycle.
A two-coloring of a cycle must alternate colors around the cycle, which contradicts the closing edge when its length is odd. Thus \(\chi(F)\geq3\).
For the reverse inequality, color the first \(m-1\) vertices alternately with colors \(1,2\), and color the last vertex with color \(3\). This is proper, so \(\chi(F)=3\).
By the lemma, \(\chi_{\mathrm{meas}}=3=q\), regardless of whether \(G\) is three-colorable.
Suppose \(h\) is a proper three-coloring of \(G'\). Color every vertex belonging to \(t_v\) with \(h(v)\). Each edge \(a_ib_i\) is properly colored because it represents the edge \(\{u_i,v_i\}\) of \(G'\).
For each separator \(z_i\) lying between two already colored vertices, choose a color different from those two endpoint colors. At most two colors are forbidden, so a choice exists.
If \(w\) exists, the remaining segment is \(b_s,z_s,w,a_1\). First choose the color of \(z_s\) different from that of \(b_s\). Then choose the color of \(w\) different from those of \(z_s\) and \(a_1\). Again, at most two colors are forbidden.
This gives a proper three-coloring of the cycle. Every type is monochromatic. Since each nonempty \(H_t\) is edgeless, \(\chi(H_t)=1\), so the coloring is individually rational.
Its constant measurable extension is therefore an individually rational legal measurable \(q\)-coloring.
Conversely, suppose the constructed society has an individually rational legal measurable three-coloring. By the lemma, there is a finite proper three-coloring of the cycle that uses exactly one color on each type.
Let \(h(v)\) be the common color of type \(t_v\). For every edge \(\{u_i,v_i\}\) of \(G'\), the cycle edge \(a_ib_i\) gives \(h(u_i)\neq h(v_i)\). Hence \(h\) is a proper three-coloring of \(G'\), and therefore \(G\) is three-colorable.
We have proved that \(G\) is three-colorable exactly when the constructed measurable instance is accepted. This establishes \(\mathrm{NP}\)-hardness.
Write \(n'=|V(G')|\). Since \(G'\) has no isolated vertices, \(n'\leq2s\). The output satisfies
\(m=3s+\varepsilon,\quad \tau=n'+s+\varepsilon,\quad |R|=m,\quad q=3.\)
In particular, \(\tau\leq m\) and \(\tau=\Theta(m)\). All shifts are zero, all internal edge sets are empty, and each mass \(1/\tau\) requires \(O(\log(\tau+1))\) bits.
Under ordinary explicit graph encodings, the output length is \(L=O((m+\tau+|R|)\log(m+\tau+1))\). Given an input graph with \(n\) vertices and \(e\) edges, the reduction can be implemented in \(O((n+e)\log(n+e+2))\) bit operations. Its output construction takes \(O((m+\tau+|R|)\log(m+\tau+1))\) bit operations.
Thus a polynomial-time algorithm for the stated decision problem would yield a polynomial-time algorithm for graph three-colorability. The conclusion is \(\mathrm{NP}\)-hardness; exclusion from \(\mathrm P\) is conditional on \(\mathrm P\neq\mathrm{NP}\).
For completeness, the general measurable problem also admits an explicit finite reduction, although its size can be exponential in \(L\).
Let \(D\) be the least common multiple of the reduced denominators of all shifts, with \(D=1\) if there are no rules. Write each shift as \(\delta=a_\delta/D\).
Construct a finite graph \(F_D\) on vertices \((t,p,j)\), where \(0\leq j<D\). Include:
A measurable coloring restricts to a coloring of \(F_D\) by evaluating at the finitely many points \(x+j/D\), choosing \(x\in[0,1/D)\) outside all translated exceptional null sets. Such an \(x\) exists because a finite union of null sets cannot cover that interval.
Conversely, a coloring \(g\) of \(F_D\) yields measurable functions by setting \(c_{t,p}(\theta)=g(t,p,\lfloor D\theta\rfloor)\) for the representative \(\theta\in[0,1)\). Addition of \(a_\delta/D\) changes the interval index by \(a_\delta\) modulo \(D\), so every rule is satisfied. Both directions preserve individual rationality on each set \(\{(t,p,j):p\in P_t\}\).
Therefore \(\chi_{\mathrm{meas}}=\chi(F_D)\), and individual rationality reduces to the corresponding finite constraints.
Also, \(\chi_{\mathrm{meas}}\leq m\): assign a distinct constant color to every pair \((t,p)\). Hence inputs with \(q>m\) can immediately be rejected.
For \(q\leq m\), exhaustive enumeration computes the local chromatic numbers, tests for an individually rational \(q\)-coloring of \(F_D\), and tests the absence of a proper \((q-1)\)-coloring. For \(q=1\), the last test is unnecessary.
A valid, deliberately loose bit-time bound is
\(\operatorname{poly}(L)\bigl[\tau m^{m+2}+D(m^2+|R|+\tau)q^{mD}\bigr].\)
Here \(D\leq2^L\), since the least common multiple is at most the product of the encoded denominators. This gives a finite decision procedure, without asserting a tighter complexity classification.
⟨structured verdict parsed — rendered above⟩
The output proves the requested \(\mathrm{NP}\)-hardness result. The reduction is correct, preserves both acceptance conditions, and has polynomial output size and construction time. The additional finite reduction for arbitrary rational shifts is also valid. I found no major or minor mathematical gaps requiring repair.
The output establishes hardness, rather than membership in \(\mathrm{NP}\) for the general measurable problem. It correctly makes exclusion from \(\mathrm P\) conditional on \(\mathrm P\ne\mathrm{NP}\).
Both assertions of the lemma are correct.
This argument works for every positive integer \(k\), including \(k=1\). The graphs have nonempty vertex sets, so their chromatic numbers are positive.
Consequently, the equality \(\chi_{\mathrm{meas}}=\chi(F)\) follows. Positive uniform masses preserve the distinction between null and nonnull sets, as asserted.
The starting problem is stated precisely: proper coloring of a finite simple graph with at most three colors. Its use as the source of an \(\mathrm{NP}\)-hardness reduction is valid. The cited [Blum–Rosenschein paper](https://cdn.aaai.org/AAAI/2008/AAAI08-004.pdf), in the proof of Theorem 7, does use graph three-colorability as its starting problem. The submitted construction is independent of that paper’s construction, so it requires no additional hypotheses from that theorem.
The preprocessing preserves three-colorability:
The constructed vertices are distinct. Its length \(m=3s+\varepsilon\) is odd under both parity choices: odd \(s\) gives odd \(3s\), while even \(s\) gives odd \(3s+1\). Since \(s\geq3\), there is no degenerate cycle.
The type assignment is a genuine partition. Each \(a_i\) and \(b_i\) has exactly one assigned endpoint type; each separator has its own singleton type. Removing isolated vertices ensures every endpoint type is nonempty.
Every cycle edge joins different types. The edges \(a_ib_i\) do so because the source graph is simple and therefore \(u_i\ne v_i\). Every other edge involves a singleton separator type distinct from its neighboring types.
Thus edgeless local graphs and zero-shift rules encode exactly the claimed cycle, and all instance requirements are satisfied.
The finite graph is exactly an odd chordless cycle.
The alternating-color argument correctly excludes a proper two-coloring. The supplied three-coloring is proper: the first \(m-1\) vertices alternate, and the last vertex’s third color differs from both neighbors.
Hence \(\chi(F)=3\), and the zero-shift lemma gives \(\chi_{\mathrm{meas}}=3=q\) for every output instance, including those arising from non-three-colorable source graphs. This verifies the equality condition independently of individual rationality.
Given a proper three-coloring of \(G'\), assigning its vertex color to every occurrence in the corresponding type properly colors each edge \(a_ib_i\).
The separator choices cover all remaining edges:
These choices impose no further constraints because the separators belong to singleton types.
Every endpoint type is monochromatic, as are all singleton types. Each local graph is nonempty and edgeless, so its chromatic number is exactly one. The resulting coloring therefore satisfies individual rationality, and its constant measurable extension satisfies the required measurable constraints.
The zero-shift lemma extracts a finite proper three-coloring satisfying individual rationality simultaneously for all types.
Since every local chromatic number equals one, every endpoint type has a well-defined common color. Each original edge is represented by an edge \(a_ib_i\), so these common colors properly color \(G'\).
The deletion of isolated vertices causes no problem in recovering three-colorability of \(G\): the omitted vertices can receive any available color, as already explained in the preprocessing argument.
The acceptance equivalence is therefore established in both directions.
The counts \(m=3s+\varepsilon\), \(\tau=n'+s+\varepsilon\), and \(|R|=m\) are correct.
Because \(G'\) has no isolated vertices, \(n'\leq2s\). Consequently \(\tau\leq m\). Conversely, \(\tau\geq s\) and \(m\leq3s+1\), establishing the claimed \(\tau=\Theta(m)\).
The encoding uses polynomially many vertex identifiers, type identifiers, rules, and copies of the rational mass \(1/\tau\). The stated output-length and construction-time bounds are valid under the expressly assumed ordinary explicit graph encodings. The fixed value \(q=3\) contributes only constant size.
Thus the reduction is a polynomial-time many-one reduction.
The supplementary finite reduction is valid.
Every reduced shift denominator divides \(D\), so every shift has the stated form \(a_\delta/D\). Translation by such a shift preserves the finite orbit indexed by \(j\) modulo \(D\).
For measurable-to-finite extraction, the required exceptional sets are finitely many translated null sets, including individual-rationality exceptions when applicable. Their union cannot cover the positive-length interval \([0,1/D)\). A chosen point outside that union supplies every constraint of \(F_D\) simultaneously.
For finite-to-measurable extension, the half-open interval assignment is measurable. Translation by \(a_\delta/D\) changes the interval index by \(a_\delta\) modulo \(D\), including at interval boundaries. Internal constraints and the individual-rationality constraints at each index are therefore preserved.
The conclusion \(\chi_{\mathrm{meas}}=\chi(F_D)\) follows.
Assigning distinct constant colors to the \(m\) vertex labels is legal, proving \(\chi_{\mathrm{meas}}\leq m\). Rejecting \(q>m\) is correct.
For \(q\leq m\), an individually rational proper \(q\)-coloring supplies the upper bound on the global minimum; absence of a proper \((q-1)\)-coloring supplies the matching lower bound. The \(q=1\) exception is handled correctly.
The stated exhaustive-search bound accommodates local chromatic-number computation, enumeration of finite color assignments, and checking the replicated edge and individual-rationality constraints. Binary arithmetic and color-label costs fit within the polynomial factor in \(L\).
Finally, \(D\leq2^L\) follows from bounding the least common multiple by the product of the encoded denominators. The procedure establishes decidability without claiming a polynomial-time algorithm.
None. The write-up resolves the assigned complexity question, and no additional mathematical clarification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.