d4-conf-atal-2017-0015 (d4-conf-atal-2017-0015)

Given a star \(H=(T,F)\), rational masses \(\mu_t>0\) summing to \(1\), and a succinct exact evaluator for a continuous nonnegative worth function \(V:\prod_{t\in T}[0,\mu_t]\to\mathbb{R}_{\ge 0}\) with \(V(0)=0\), decide whether there is a per-capita payoff vector \(p\in\mathbb{R}_{\ge 0}^{T}\) such that \(\sum_t\mu_t p_t=V(\mu)\) and \(\sum_t z_t p_t\ge V(z)\) for every \(z\in\prod_{t\in T}[0,\mu_t]\) whose positive-support types induce a connected subgraph of \(H\).

A society is given by its support: a list of the \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
The input includes an undirected star \(H=(T,F)\), with \(m=|F|\), and an exact evaluator represented by a rational arithmetic formula using \(+,-,\times,\min,\max\). Let \(L\) be the total input bit length. The formula defines a continuous function \(V:\prod_{t\in T}[0,\mu_t]\to\mathbb R_{\ge0}\), with \(V(0)=0\); nonnegativity and normalization are promises.
A coalition is a mass vector \(z\) in this box. It is feasible if \(z=0\) or its positive support \(\{t:z_t>0\}\) induces a connected subgraph of \(H\); singleton supports and arbitrarily small positive masses are allowed.
The continuous core consists of per-capita vectors \(p\in\mathbb R_{\ge0}^{T}\) satisfying \(\sum_{t\in T}\mu_t p_t=V(\mu)\) and \(\sum_{t\in T}z_t p_t\ge V(z)\) for every feasible \(z\). No cohesiveness, superadditivity, or supermodularity is assumed.

Is deciding whether this continuous core is nonempty solvable in time polynomial in \(m,\tau,L\), or is it NP-hard under polynomial-time Turing reductions?

For finite players, core nonemptiness with nonnegative, polynomial-time evaluable worths is coNP-complete even on stars; on trees, it is equivalent to cohesiveness, meaning that no partition into connected coalitions has total worth exceeding the grand coalition's worth ([source](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p299.pdf)). No result settling the continuous problem with the specified evaluator representation was located.

Result. Deciding continuous-core nonemptiness is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. More strongly, it is \(\mathrm{coNP}\)-hard under polynomial-time many-one reductions, even with uniform dyadic masses, a continuous piecewise-affine evaluator, and \(V(\mu)=1\).

The finite-player star result appears in [Igarashi, Theorem 5.9](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p299.pdf). The following reduction directly establishes hardness for the specified continuous formula representation.

1. A consequence of continuity.

For any connected graph \(H\), the feasible coalition vectors are dense in the entire box. Indeed, for any vector \(z\) in the box and \(0<\varepsilon<1\), define
\[ z^{(\varepsilon)}=(1-\varepsilon)z+\varepsilon\mu. \]
Every coordinate of \(z^{(\varepsilon)}\) is positive, so its support is the connected graph \(H\). Moreover, \(z^{(\varepsilon)}\) converges to \(z\).

Consequently, if \(p\) satisfies every feasible-coalition inequality, continuity gives
\[ \sum_t z_t p_t =\lim_{\varepsilon\to0}\sum_t z_t^{(\varepsilon)}p_t \ge \lim_{\varepsilon\to0}V(z^{(\varepsilon)}) =V(z). \]
Thus, in this continuous model, the inequalities for feasible coalitions imply the inequalities for the whole box. The reduction below nevertheless supplies an explicitly feasible violating coalition.

2. A continuous satisfiability detector.

Let \(\Phi\) be a \(\mathrm{3SAT}\) instance with variables \(u_1,\ldots,u_n\) and clauses \(K_1,\ldots,K_q\), where \(n,q\ge1\).

For \(x\in[0,1]^n\), define each literal’s value by
\[ \lambda_{u_i}(x)=x_i,\qquad \lambda_{\neg u_i}(x)=1-x_i. \]
Define
\[ C_\Phi(x)=\min_{1\le j\le q}\ \max_{\ell\in K_j}\lambda_\ell(x), \qquad D(x)=\sum_{i=1}^n\min(x_i,1-x_i), \]
and
\[ A_\Phi(x)=\max\bigl(0,C_\Phi(x)-D(x)\bigr). \]

Lemma. If \(\Phi\) is unsatisfiable, then \(A_\Phi(x)=0\) throughout \([0,1]^n\). If \(\Phi\) is satisfiable, some \(a\in\{0,1\}^n\) satisfies \(A_\Phi(a)=1\).

Proof. Given any \(x\), round its coordinates to the Boolean assignment
\[ a_i= \begin{cases} 0,&x_i<1/2,\\ 1,&x_i\ge1/2. \end{cases} \]
Write \(d_i=\min(x_i,1-x_i)\). Every literal that is false under \(a\) has continuous value exactly \(d_i\): a false positive literal has \(a_i=0\) and value \(x_i=d_i\); a false negative literal has \(a_i=1\) and value \(1-x_i=d_i\).

If \(\Phi\) is unsatisfiable, some clause \(K_j\) is false under \(a\). All its literals therefore have values bounded by \(D(x)\), giving
\[ C_\Phi(x) \le \max_{\ell\in K_j}\lambda_\ell(x) \le D(x). \]
Hence \(A_\Phi(x)=0\).

Conversely, at a satisfying Boolean assignment \(a\), every clause has maximum literal value \(1\), while \(D(a)=0\). Therefore \(A_\Phi(a)=1\). This proves the lemma.

3. Constructing the society and evaluator.

Let
\[ N=2^{\lceil\log_2(n+1)\rceil}. \]
Construct a star with \(N\) types: a center \(c\), variable leaves \(t_1,\ldots,t_n\), and \(N-n-1\) additional leaves. Give every type mass
\[ \mu_t=\frac1N. \]
These masses are positive dyadic rationals and sum to \(1\).

For any coalition \(z\), put
\[ x_i=Nz_{t_i},\qquad y=Nz_c. \]
All these normalized coordinates lie in \([0,1]\). Define
\[ B_\Phi(z)=\min\bigl(y,1-y,A_\Phi(x)\bigr), \qquad V_\Phi(z)=\sum_{t\in T}z_t+B_\Phi(z). \]

This evaluator meets every promise:

• It is a rational arithmetic formula using only the permitted operations. Multiplication occurs only by the integer constant \(N\).
• It is continuous and piecewise affine.
• Since \(y\), \(1-y\), and \(A_\Phi(x)\) are nonnegative throughout the box, \(B_\Phi(z)\ge0\), so \(V_\Phi(z)\ge0\).
• At \(z=0\), the gate coordinate is \(y=0\), giving \(B_\Phi(0)=0\) and \(V_\Phi(0)=0\).
• At the grand coalition, \(y=1\), so \(B_\Phi(\mu)=0\) and

\[ V_\Phi(\mu)=\sum_t\mu_t=1. \]

4. The singleton constraints force a unique candidate payoff.

Let \(e_t\) denote the coordinate unit vector for type \(t\). The full-mass singleton coalition \(\mu_t e_t\) is feasible.

If \(t=c\), its gate coordinate is \(y=1\); otherwise it is \(y=0\). In either case the bonus vanishes, and
\[ V_\Phi(\mu_t e_t)=\mu_t. \]
Every core vector must therefore satisfy
\[ \mu_t p_t\ge\mu_t, \]
hence \(p_t\ge1\) for every type.

Efficiency requires
\[ \sum_t\mu_t p_t=V_\Phi(\mu)=1=\sum_t\mu_t. \]
Because every \(\mu_t\) is positive and every \(p_t-1\) is nonnegative, this equality forces \(p_t=1\) for every type. Thus the only possible core vector is \(\mathbf1\).

5. Correctness of the reduction.

Suppose first that \(\Phi\) is unsatisfiable. By the lemma, \(A_\Phi(x)=0\) everywhere. Consequently,
\[ B_\Phi(z)=0,\qquad V_\Phi(z)=\sum_t z_t \]
throughout the box. The vector \(p=\mathbf1\) satisfies efficiency and every coalitional inequality with equality. The core is therefore nonempty.

Now suppose that \(\Phi\) has a satisfying assignment \(a\in\{0,1\}^n\). Choose the coalition
\[ z_c=\frac1{2N},\qquad z_{t_i}=\frac{a_i}{N}, \]
and give every additional leaf mass zero. Its support contains the center and some subset of its leaves, so it induces a connected subgraph, including when that subset is empty.

Here \(y=1/2\), \(x=a\), and \(A_\Phi(a)=1\). Hence
\[ B_\Phi(z)=\frac12,\qquad V_\Phi(z)=\sum_t z_t+\frac12. \]
The unique candidate payoff \(p=\mathbf1\) violates this feasible coalition’s inequality:
\[ \sum_t z_t p_t=\sum_t z_t<V_\Phi(z). \]
Thus the core is empty.

We have proved the exact equivalence
\[ \Phi\text{ is unsatisfiable} \quad\Longleftrightarrow\quad \operatorname{Core}(V_\Phi,H,\mu)\ne\varnothing. \]

6. Encoding size and complexity conclusion.

Since \(N<2(n+1)\), the construction has
\[ \tau=N,\qquad m=N-1, \]
both polynomial in the source input size. Every mass and scaling constant has \(O(\log(n+2))\) bits.

After expanding the definitions, the evaluator is an arithmetic formula, without any need for shared subexpressions. The baseline sum uses \(O(N)\) operations, the clause detector uses \(O(q)\), and the rounding penalty uses \(O(n)\). Nested binary minima and maxima implement all displayed multiargument operations. Thus the total output bit length \(L\) is polynomial in the \(\mathrm{3SAT}\) input length.

The equivalence above gives a polynomial-time many-one reduction from \(\mathrm{3UNSAT}\) to core nonemptiness. Therefore core nonemptiness is \(\mathrm{coNP}\)-hard. A polynomial-time algorithm with a core-nonemptiness oracle decides \(\mathrm{3SAT}\) using one query and reversing its answer, establishing the requested \(\mathrm{NP}\)-hardness under polynomial-time Turing reductions.

In particular, an algorithm polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verdict

The proof is correct and resolves the assigned question. It establishes that continuous-core nonemptiness is \(\mathrm{coNP}\)-hard under polynomial-time many-one reductions and therefore \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. No major or minor mathematical issues were found.

Step-by-step verification

1. Density of feasible coalitions

The density argument is valid. Every mass \(\mu_t\) is strictly positive, so for \(0<\varepsilon<1\), every coordinate of
\[ z^{(\varepsilon)}=(1-\varepsilon)z+\varepsilon\mu \]
is positive. The vector remains in the box because it is a convex combination of two box elements. Its support is the whole connected graph, making it feasible.

For a fixed payoff vector \(p\), both the linear payment function and \(V\) are continuous. Passing to the limit therefore preserves the coalitional inequality. The conclusion applies to every box vector, including vectors with disconnected support and the zero vector.

This observation is correct but is not needed for the reduction: the later violating coalition is explicitly feasible.

2. Satisfiability detector

The lemma is correct in both directions.

For the stated rounding rule, every literal false under the rounded assignment has value \(d_i=\min(x_i,1-x_i)\). The tie case \(x_i=1/2\) is covered: the rounded variable is true, and its false negative literal has value \(1/2=d_i\).

If the formula is unsatisfiable, the rounded assignment falsifies at least one clause. Every literal in that clause has value at most \(D(x)\), since each \(d_i\) is a nonnegative summand of \(D(x)\). Thus \(C_\Phi(x)\le D(x)\), and the outer maximum gives \(A_\Phi(x)=0\).

At a satisfying Boolean assignment, every clause has maximum literal value \(1\), while every summand of \(D\) is zero. Hence \(A_\Phi(a)=1\).

Repeated literals cause no difficulty, and a tautological clause cannot be the falsified clause used in the unsatisfiable direction. The assumptions \(n,q\ge1\) ensure all displayed operations are defined and are compatible with the standard restricted \(\mathrm{3SAT}\) source problem.

3. Society and evaluator promises

The construction satisfies the task’s input requirements.

• \(N\) is a power of two with \(n+1\le N<2(n+1)\), so the specified number of additional leaves is nonnegative.
• The star has exactly \(N\) supported types. All masses are positive dyadic rationals and sum to \(1\).
• The normalized coordinates \(x_i\) and \(y\) belong to \([0,1]\) throughout the coalition box.
• The evaluator uses only permitted operations and rational constants. Products involve only constant scaling.
• Finite sums, minima, and maxima of affine functions give a continuous piecewise-affine function.
• Every argument of \(B_\Phi\) is nonnegative on the box, so both \(B_\Phi\) and \(V_\Phi\) are nonnegative.
• The gate gives \(B_\Phi(0)=0\) and \(B_\Phi(\mu)=0\), establishing \(V_\Phi(0)=0\) and \(V_\Phi(\mu)=1\).

The task imposes no upper bound on intermediate coalition values, so the positive bonus violates no promise.

4. Unique candidate payoff

Every full-mass singleton is feasible. For the center singleton, \(y=1\); for every leaf singleton, \(y=0\). In both cases the bonus vanishes, so the singleton inequality forces \(p_t\ge1\).

Efficiency then gives
\[ \sum_t\mu_t(p_t-1)=0. \]
All summands are nonnegative and all masses are strictly positive. Consequently every \(p_t-1\) must be zero. The unique possible core vector is therefore \(\mathbf1\), which also satisfies the required nonnegativity condition.

5. Reduction correctness

For an unsatisfiable formula, the detector vanishes throughout the box. The resulting evaluator equals the baseline payment under \(\mathbf1\), so this vector satisfies efficiency and every feasible-coalition inequality.

For a satisfiable formula, the proposed coalition lies in the box. Its center mass is strictly positive, and its other positive coordinates are leaves adjacent to the center. Its support is therefore connected. If all assignment coordinates are zero, the support is the center singleton, which is expressly allowed.

The calculations are exact: \(y=1/2\), \(x=a\), and \(A_\Phi(a)=1\), giving \(B_\Phi(z)=1/2\). Thus the coalition strictly violates the inequality for the unique candidate payoff.

Both directions of the claimed equivalence are established.

6. Formula size and complexity conclusion

The encoding argument correctly addresses a formula, rather than assuming shared subexpressions.

After expansion, each clause has at most three literal occurrences, so the clause detector uses \(O(q)\) operations. The penalty uses \(O(n)\), and the baseline uses \(O(N)\). Repeated variable references and scaling constants contribute only polynomially many bits. Binary nesting implements the displayed multiargument minima and maxima without exponential duplication.

The graph and mass list likewise have polynomial encoding length. Thus the construction is a polynomial-time many-one reduction from \(\mathrm{3UNSAT}\) to the promised continuous-core problem.

The reduction’s orientation is correct: unsatisfiable instances correspond to nonempty cores. Reversing the answer to one core-nonemptiness oracle query decides \(\mathrm{3SAT}\), yielding the requested Turing hardness. A polynomial-time algorithm in \(m,\tau,L\) would therefore imply \(\mathrm P=\mathrm{NP}\). The proof appropriately makes no claim of membership in \(\mathrm{coNP}\) for the general continuous problem.

The background attribution also checks out: [Igarashi’s Theorem 5.9](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p299.pdf) states finite-player core-nonemptiness hardness on stars with nonnegative worths. The continuous reduction does not depend on transferring that theorem.

Repair feedback

No mathematical repair or additional clarification is needed. The proof establishes the claimed hardness within the specified evaluator representation and all input promises.

⟨structured verdict parsed — rendered above⟩