d4-conf-atal-2014-0290 (d4-conf-atal-2014-0290)

Given a graph \(H=(T,F)\), positive rational masses \(\mu_t\) with \(\sum_{t\in T}\mu_t=1\), and affinities \(w_{ts}=-1\) for \(\{t,s\}\in F\) and \(0\) otherwise, does there exist a stable allocation among exactly three nonempty coalitions? An allocation is \(x_{ti}\geq 0\), with \(\sum_{i=1}^{3}x_{ti}=\mu_t\) and positive total mass in each coalition; type-\(t\) utility in coalition \(i\) is \(u_t(i)=\sum_{s\in T}w_{ts}x_{si}\). Require individual rationality \(u_t(i)\geq 0\) for each occupied type-coalition pair, and no blocking deviation of the paper's exact-\(k\) form interpreted over mass, in which every participating mass strictly benefits while exactly three coalitions remain.

The input is a finite simple undirected graph \(H=(T,F)\) and a society given by its support: the list of \(\tau=|T|\geq1\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; set \(m=|T|=\tau\), and let \(L\) be the total input bit length.
Affinities are fixed: \(w_{ts}=-1\) when \(\{t,s\}\in F\), and \(w_{ts}=0\) otherwise, including \(w_{tt}=0\). Coalitions need not be connected.
An allocation consists of real masses \(x_{ti}\geq0\), for \(i\in\{1,2,3\}\), satisfying \(\sum_i x_{ti}=\mu_t\) and \(\sum_t x_{ti}>0\) for each \(i\). Types may split across coalitions. Define \(u_t(i)=\sum_s w_{ts}x_{si}\).
A blocking deviation selects real participating masses \(0\leq y_{ti}\leq x_{ti}\) and a destination \(r\in\{1,2,3\}\), with \(y_{tr}=x_{tr}\) for all \(t\), \(\sum_{t,i\ne r}y_{ti}>0\), and \(\sum_t(x_{ti}-y_{ti})>0\) for every \(i\ne r\).
These masses form one coalition with type masses \(b_t=\sum_i y_{ti}\); all nonparticipants remain in their original coalitions. The deviation blocks precisely when \(\sum_s w_{ts}b_s>u_t(i)\) for every pair \((t,i)\) with \(y_{ti}>0\), including participants from the destination coalition.
An allocation is stable if it admits no blocking deviation and is individually rational: \(u_t(i)\geq0\) whenever \(x_{ti}>0\).

Is deciding whether a stable allocation among exactly three nonempty coalitions exists in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For finite indivisible agents, existence in the corresponding exact-\(k\) core is \(\mathrm{NP}\)-hard for every fixed \(k>2\); the three-coalition reduction uses only affinities \(-1\) and \(0\). The [journal extension](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aij2018a.pdf) retains this result and requires deviations to absorb one whole coalition while leaving every other coalition nonempty.
No result settling the continuous problem defined above was identified in the literature search.

Result

The decision problem is \(\mathrm{NP}\)-complete. More precisely, for every permitted positive mass vector, a stable allocation among exactly three nonempty coalitions exists if and only if \(\ H\ \) is three-colorable. Thus splitting types does not remove the computational obstruction.

Here, “three-colorable” means that there exists a map \(\ c:T\to\{1,2,3\}\ \) assigning different colors to adjacent vertices; the map need not use all three colors.

1. No allowed deviation can block

Fix any feasible allocation \(\ x\ \), without assuming individual rationality. Consider a deviation satisfying the stated participation constraints, with destination \(\ r\ \) and resulting masses \(\ b_t=\sum_i y_{ti}\ \).

Because the deviation absorbs the entire destination coalition, for every \(\ s\in T\ \),
\[ b_s=x_{sr}+\sum_{i\ne r}y_{si}\geq x_{sr}. \]
All affinities are nonpositive. Consequently, for every \(\ t\in T\ \),
\[ \sum_s w_{ts}b_s\leq \sum_s w_{ts}x_{sr}=u_t(r). \]

The destination is nonempty, so some \(\ t\ \) satisfies \(\ x_{tr}>0\ \). For this type, \(\ y_{tr}=x_{tr}>0\ \), and blocking requires the strict inequality \(\ \sum_s w_{ts}b_s>u_t(r)\ \). This contradicts the preceding inequality.

Therefore every feasible allocation admits no blocking deviation. Under the definition in the question, stability is equivalent to individual rationality.

2. Individual rationality is equivalent to independent coalition supports

Define the support of coalition \(\ i\ \) by \(\ S_i=\{t\in T:x_{ti}>0\}\ \), and define the neighborhood of \(\ t\ \) by \(\ N_H(t)=\{s\in T:\{t,s\}\in F\}\ \). The prescribed affinities give
\[ u_t(i)=-\sum_{s\in N_H(t)}x_{si}\leq0. \]

Suppose the allocation is individually rational. Whenever \(\ x_{ti}>0\ \), individual rationality requires \(\ u_t(i)\geq0\ \), hence
\[ \sum_{s\in N_H(t)}x_{si}=0. \]
Every summand is nonnegative, so \(\ x_{si}=0\ \) for every neighbor \(\ s\ \) of \(\ t\ \). Thus no edge has both endpoints in \(\ S_i\ \): each coalition support is an independent set.

Conversely, suppose every \(\ S_i\ \) is independent. If \(\ x_{ti}>0\ \), no neighbor of \(\ t\ \) has positive mass in coalition \(\ i\ \). The displayed utility formula then yields \(\ u_t(i)=0\ \). This proves individual rationality.

Therefore an allocation is stable exactly when all three coalition supports are independent.

3. Equivalence with three-colorability

A stable allocation yields a proper coloring. Since \(\ \sum_i x_{ti}=\mu_t>0\ \), each type occupies at least one coalition. Choose any such coalition and set \(\ c(t)=i\ \).

If an edge \(\ \{t,s\}\in F\ \) had \(\ c(t)=c(s)=i\ \), both endpoints would belong to the independent set \(\ S_i\ \), a contradiction. Hence \(\ c\ \) is a proper three-coloring. This argument applies even when types split across several coalitions.

A proper coloring yields a stable allocation with exactly three nonempty coalitions. Initially allocate every type entirely to its color:
\[ x_{t,c(t)}=\mu_t,\qquad x_{ti}=0\quad\text{for }i\ne c(t). \]
All coalition supports are independent.

If a coalition label \(\ j\ \) is empty, choose any positive entry \(\ x_{ti}=a>0\ \) in an occupied coalition. Replace \(\ x_{ti}\ \) by \(\ a/2\ \) and set \(\ x_{tj}=a/2\ \). This preserves every type’s total mass. Coalition \(\ i\ \) remains nonempty, its support remains independent, and the newly occupied coalition has singleton support \(\ \{t\}\ \), which is independent because the graph is simple.

Repeat for any remaining empty label. There are at most two repetitions. The resulting allocation has exactly three nonempty coalitions and independent supports, so Sections 1–2 prove that it is stable.

This also handles support sizes \(\ \tau=1\ \) and \(\ \tau=2\ \).

4. Complexity and binary mass encoding

We use the standard theorem that deciding three-colorability of finite simple undirected graphs is \(\mathrm{NP}\)-complete; see [Garey, Johnson, and Stockmeyer, *Some simplified NP-complete graph problems*](https://doi.org/10.1016/0304-3975%2876%2990059-1).

For a polynomial reduction, let \(\ G\ \) be a nonempty input graph with \(\ n\ \) vertices. Set
\[ q=\lceil\log_2 n\rceil,\qquad N=2^q. \]
Construct \(\ H\ \) by adding \(\ N-n\ \) isolated vertices to \(\ G\ \), and assign every vertex the mass \(\ \mu_t=2^{-q}\ \).

These masses are positive dyadic rationals and sum to one. Moreover, \(\ N\leq2n\ \), and each mass has encoding length \(\ O(1+\log n)\ \), so the construction has polynomial total bit length. Adding isolated vertices preserves three-colorability. By Section 3,
\[ G\text{ is three-colorable} \quad\Longleftrightarrow\quad (H,\mu)\text{ admits a stable allocation}. \]
This proves \(\mathrm{NP}\)-hardness even for uniform dyadic masses.

For membership in \(\mathrm{NP}\), a certificate is simply a proper three-coloring of \(\ H\ \). It has length \(\ O(m)\ \), and checking every edge takes polynomial time. Section 3 proves that this certificate characterizes stable-allocation existence; no certificate involving arbitrary real masses is needed.

Therefore the problem is \(\mathrm{NP}\)-complete, and a running time polynomial in \(\ m,\tau,L\ \) would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves the continuous problem as stated. Stable-allocation existence is equivalent to three-colorability for every permitted positive mass vector. The claimed \(\mathrm{NP}\)-completeness follows. No major or minor mathematical issues were found.

• The deviation argument is valid for every feasible allocation.

The participation constraint \(y_{sr}=x_{sr}\), together with nonnegativity of all other participating masses, gives
\[ b_s=x_{sr}+\sum_{i\ne r}y_{si}\geq x_{sr}. \]
Since every \(w_{ts}\leq0\), multiplication reverses the corresponding inequality, and finite summation gives
\[ \sum_s w_{ts}b_s\leq\sum_s w_{ts}x_{sr}=u_t(r). \]

Feasibility requires the destination coalition to be nonempty. Hence some \(t\) has \(x_{tr}>0\), and the absorption requirement makes \(y_{tr}>0\). The blocking definition explicitly requires strict improvement for this destination participant. The displayed inequality rules that out.

This proves the asserted absence of blocking deviations without assuming individual rationality. The additional requirements concerning incoming participants and nonempty residual coalitions do not undermine the argument: every allowed deviation already satisfies the constraints used in the contradiction. Consequently, stability is equivalent to individual rationality.

• The characterization by independent supports is exact.

The prescribed affinities give
\[ u_t(i)=-\sum_{s\in N_H(t)}x_{si}\leq0. \]
For \(x_{ti}>0\), individual rationality therefore forces this finite sum of nonnegative masses to vanish. Each neighboring mass \(x_{si}\) must be zero. Thus no coalition support contains both endpoints of an edge.

Conversely, independence of a coalition support ensures that every occupied type has zero neighboring mass there, so its utility equals zero. The argument checks precisely the occupied pairs required by individual rationality; no condition on unoccupied pairs is needed.

• Extracting a coloring remains valid when types split.

Positivity of \(\mu_t\) and the mass-conservation constraint ensure that each type occupies at least one coalition. Choosing one occupied label for each type defines a map into \(\{1,2,3\}\).

If adjacent types received the same label, both would lie in that coalition’s independent support. This is impossible. The choices may be arbitrary: independence establishes correctness for every such selection.

• The converse construction satisfies exact nonemptiness.

Allocating each type wholly to its color preserves its prescribed mass and produces independent supports. This initial array may have empty labels, but the subsequent construction resolves them before asserting feasibility.

At each filling step, a positive entry exists because the total allocated mass is one. Replacing a positive mass \(a\) by two masses \(a/2\) preserves nonnegativity and the type’s total mass. The donor coalition remains nonempty. Its support remains independent, and the previously empty coalition acquires singleton support. Simplicity of the graph ensures that this singleton is independent.

Each step decreases the number of empty labels by one without creating another empty label. At most two steps suffice. This reasoning also covers \(\tau=1\) and \(\tau=2\), since the same type may be split repeatedly. The final allocation meets all feasibility and stability requirements.

• The hardness reduction respects the mass encoding.

For \(n\geq1\), the definitions \(q=\lceil\log_2 n\rceil\) and \(N=2^q\) give
\[ n\leq N\leq2n. \]
Thus the number of added isolated vertices is nonnegative and polynomially bounded. The \(N\) masses \(2^{-q}\) are positive dyadic rationals and sum exactly to one. Their stated encoding bound is valid, including \(n=1\), where \(q=0\).

Adding isolated vertices preserves three-colorability in both directions. The equivalence already established therefore supplies the required reduction. Restricting the source to nonempty graphs introduces no substantive issue: excluding the single empty graph does not affect hardness.

The cited theorem is stated with the relevant graph domain and decision property. The cited [Garey–Johnson–Stockmeyer paper](https://www.sciencedirect.com/science/article/pii/0304397576900591) supports the three-colorability complexity result. The reduction meets its finite simple undirected graph hypotheses.

• Membership in \(\mathrm{NP}\) is justified despite real allocation variables.

A coloring uses constant-size labels for each of the \(m\) vertices, giving certificate length \(O(m)\). Checking the labels and all edge inequalities takes polynomial time.

The proved equivalence supplies both completeness and soundness of this certificate. In particular, a valid coloring certifies existence of an allocation with exactly three nonempty coalitions through the written construction. No assumption that arbitrary feasible real allocations have short encodings is used.

Together, hardness and membership establish \(\mathrm{NP}\)-completeness. Since \(m=\tau\) and both are bounded by the explicit input length, the final implication concerning a running time polynomial in \(m,\tau,L\) is also valid.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩