d4-conf-atal-2019-0059 (d4-conf-atal-2019-0059)

Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), finite action domains \(D_t\), nonnegative rational interaction intensities \(w_{ts}=w_{st}\), asymmetric pairwise cost tables \(f_{ts}(a,b)\), and a rational threshold \(B\), decide whether there are action shares \(\pi_{t,a}\geq 0\), with \(\sum_{a\in D_t}\pi_{t,a}=1\), such that \(J(\pi)=\sum_{t,s\in T}\mu_t\mu_s w_{ts}\sum_{a\in D_t,\,b\in D_s}\pi_{t,a}\pi_{s,b}f_{ts}(a,b)\leq B\).

A society is given by its support \(T\): the list of its \(\tau\geq 1\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has an explicitly listed nonempty finite action domain \(D_t\). Put \(m=\max_t|D_t|\), and let \(L\) be the total binary input length.
Input also comprises symmetric nonnegative rational intensities \(w_{ts}=w_{st}\), explicitly tabulated costs \(f_{ts}:D_t\times D_s\to\mathbb{Q}_{\geq 0}\), and a threshold \(B\in\mathbb{Q}\). The cost \(f_{ts}(a,b)\) is borne by the participant of type \(t\); no equality with \(f_{st}(b,a)\) is required.
A feasible allocation consists of real shares \(\pi_{t,a}\geq 0\) with \(\sum_{a\in D_t}\pi_{t,a}=1\) for every \(t\). Its cost is
\(J(\pi)=\sum_{t,s\in T}\mu_t\mu_s w_{ts}\sum_{a\in D_t,\,b\in D_s}\pi_{t,a}\pi_{s,b}f_{ts}(a,b).\)
The sum is over ordered type pairs, aggregating both participants' costs. Terms with \(t=s\) are allowed and represent interactions between independently sampled members of the same type.

Is deciding whether a feasible allocation satisfies \(J(\pi)\leq B\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finite agents with one finite-domain variable each and binary asymmetric nonnegative costs, PT-ISABB terminates and finds a globally optimal assignment; its completeness guarantee gives no polynomial running-time bound. [Source](https://www.ifaamas.org/Proceedings/aamas2019/pdfs/p1506.pdf).
No result settling this exact mass-allocation decision problem was located in the literature search.

Result

The decision problem is \(\mathsf{NP}\)-complete. Hardness holds even with a single supported type, mass \(1\), intensity \(1\), and symmetric costs in \(\{0,1\}\).

Consequently, a polynomial-time algorithm in \(m,\tau,L\) exists if and only if \(\mathsf{P}=\mathsf{NP}\).

1. A single-type reduction from CLIQUE

We use the standard \(\mathsf{NP}\)-complete problem CLIQUE: given a nonempty finite simple graph \(G=(V,E)\) and a positive integer \(k\), decide whether \(G\) contains a clique of size at least \(k\). This is among the complete problems in [Karp’s original theorem](https://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf).

Construct a society with
\[ \text{} \]
\(T=\{t\}\), \(\mu_t=1\), \(D_t=V\), and \(w_{tt}=1\).

For actions \(u,v\in V\), define \(f_{tt}(u,v)=0\) when \(\{u,v\}\in E\), and \(f_{tt}(u,v)=1\) otherwise. In particular, every diagonal cost is \(1\). Set \(B=1/k\).

All hypotheses are satisfied: the mass is positive and binary rational, the domain is nonempty, the intensity is symmetric, and all costs are nonnegative rational numbers. Writing \(x_v=\pi_{t,v}\), feasible allocations satisfy \(x_v\geq0\) and \(\sum_{v\in V}x_v=1\). Their cost is

\( \displaystyle q_G(x)=\sum_{v\in V}x_v^2+ 2\sum_{\substack{\{u,v\}\subseteq V\\u\neq v,\ \{u,v\}\notin E}}x_ux_v. \)

Each distinct unordered nonedge occurs with coefficient \(2\), because the original objective sums over ordered action pairs.

Let \(\omega(G)\) denote the maximum clique size. We will prove the exact identity

\( \displaystyle \min_{\substack{x_v\geq0\\\sum_vx_v=1}}q_G(x)=\frac{1}{\omega(G)}. \)

Eliminating nonadjacent actions from the support

Suppose \(u,v\) are distinct nonadjacent vertices with \(x_u>0\) and \(x_v>0\). Put \(r=x_u+x_v\). Keep all other coordinates fixed and replace these two coordinates by

\( \displaystyle x_u=\alpha,\qquad x_v=r-\alpha,\qquad 0\leq\alpha\leq r. \)

Because \(u,v\) are nonadjacent, their diagonal and mutual contributions together equal

\( \displaystyle \alpha^2+(r-\alpha)^2+2\alpha(r-\alpha)=r^2. \)

Define

\( \displaystyle A=\sum_{z\notin\{u,v\}}f_{tt}(u,z)x_z,\qquad C=\sum_{z\notin\{u,v\}}f_{tt}(v,z)x_z. \)

Symmetry of our cost table implies that the contributions involving exactly one of \(u,v\) equal \(2\alpha A+2(r-\alpha)C\). Thus the whole objective, as a function of \(\alpha\), is affine:

\( \displaystyle q_G(x(\alpha))=K+r^2+2\alpha A+2(r-\alpha)C, \)

where \(K\) is independent of \(\alpha\).

An affine function on \([0,r]\) attains its minimum at an endpoint. Choosing such an endpoint does not increase the cost and removes one vertex from the positive support.

Repeat this operation whenever the positive support contains a nonadjacent pair. Each operation strictly decreases its size, so the process terminates with a feasible vector \(y\) supported on a clique, and \(q_G(y)\leq q_G(x)\).

If that clique has size \(h\), then

\( \displaystyle q_G(y)=\sum_{v\in\operatorname{supp}(y)}y_v^2 \geq\frac{\bigl(\sum_{v\in\operatorname{supp}(y)}y_v\bigr)^2}{h} =\frac1h\geq\frac1{\omega(G)}. \)

The first inequality is Cauchy–Schwarz. Therefore every feasible \(x\) satisfies \(q_G(x)\geq1/\omega(G)\).

Conversely, assigning share \(1/\omega(G)\) to every vertex of a maximum clique, and zero elsewhere, gives cost \(1/\omega(G)\). This proves the identity.

Correctness and size of the reduction

It follows that

\( \displaystyle \exists\pi:\ J(\pi)\leq B \quad\Longleftrightarrow\quad \frac1{\omega(G)}\leq\frac1k \quad\Longleftrightarrow\quad \omega(G)\geq k. \)

The construction explicitly lists \(|V|^2\) binary costs; its size and construction time are polynomial in the graph input length and the encoding length of \(k\). Here \(\tau=1\) and \(m=|V|\).

This proves \(\mathsf{NP}\)-hardness while fully accounting for arbitrary real shares.

2. Polynomial-size rational certificates

We now prove membership in \(\mathsf{NP}\), including instances with asymmetric costs and same-type interactions.

Index all type-action pairs by a coordinate set \(I\), and put \(N=|I|=\sum_t|D_t|\). Define the rational matrix

\( \displaystyle H_{(t,a),(s,b)}=\mu_t\mu_s w_{ts}f_{ts}(a,b), \qquad Q=\frac{H+H^{\mathsf T}}2. \)

Then \(Q\) is symmetric, its encoding length is polynomial in \(L\), and the objective is exactly \(J(x)=x^{\mathsf T}Qx\).

The feasible set is a nonempty compact product of simplices. Hence the continuous objective attains a global minimum at some \(x^*\).

Let \(S=\{i:x_i^*>0\}\), let \(z=x_S^*\), and let \(R=Q_{S,S}\). Every type has at least one coordinate in \(S\). For each type \(t\), choose one such coordinate \(i_t\).

For any \(i\in S\) belonging to type \(t\), sufficiently small perturbations in both directions along \(e_i-e_{i_t}\) remain feasible. Differentiating at the minimum therefore gives

\( \displaystyle (Rz)_i=(Rz)_{i_t}. \)

Consider the rational polytope

\( \displaystyle P_S=\left\{y\in\mathbb R^S: y\geq0,\quad \sum_{i\in S:\,\operatorname{type}(i)=t}y_i=1\ \text{for every }t,\quad (Ry)_i=(Ry)_{i_t}\ \text{for every }i\in S \right\}. \)

It contains \(z\) and is bounded.

For any \(y\in P_S\), put \(d=y-z\). The coordinates of \(d\) sum to zero within each type. Both \(Rz\) and \(Ry\) are constant within each type, so

\( \displaystyle d^{\mathsf T}Rz=d^{\mathsf T}Ry=0. \)

Using symmetry of \(R\), we obtain

\( \displaystyle y^{\mathsf T}Ry-z^{\mathsf T}Rz =(y-z)^{\mathsf T}R(y+z)=0. \)

Thus every point of \(P_S\), extended by zeros outside \(S\), achieves the global minimum.

A nonempty bounded polytope has a vertex. Moreover, every vertex of \(P_S\) has polynomial-size rational coordinates. Here is the encoding argument. Write \(d_S=|S|\), and let \(h\) bound the numerator and denominator bit lengths of its constraint coefficients. At a vertex, \(d_S\) linearly independent active constraints determine the coordinates. Clearing denominators separately in each row produces integer coefficients with bit length \(O(d_Sh)\). Cramer’s rule expresses each coordinate as a ratio of determinants. The determinant expansion bounds their bit lengths by \(O(d_S^2h+d_S\log d_S)\), which is polynomial in \(L\).

Consequently, every yes-instance has a feasible rational allocation of polynomial encoding length attaining the minimum, and hence satisfying \(J\leq B\). A verifier checks nonnegativity, each type’s normalization, and the objective inequality using exact rational arithmetic in polynomial time. The decision problem belongs to \(\mathsf{NP}\).

3. Conclusion and relation to PT-ISABB

The reduction and certificate argument together establish \(\mathsf{NP}\)-completeness. The hardness already arises from independently sampled members of one type: the quadratic terms encode maximum clique size.

The cited finite-agent completeness guarantee is compatible with this conclusion. [PT-ISABB’s Theorem 4.4](https://www.ifaamas.org/Proceedings/aamas2019/pdfs/p1506.pdf) establishes completeness, while Section 4.3 describes exponential growth of search-phase messages with the agent count.

⟨structured verdict parsed — rendered above⟩

The output resolves the exact mass-allocation decision problem. The reduction proves \(\mathsf{NP}\)-hardness for the stated single-type restriction, and the rational-certificate argument establishes membership in \(\mathsf{NP}\). I found no mathematical gaps requiring repair.

• Reduction inputs and admissibility. The construction satisfies all input restrictions: one supported type, positive mass \(1\), nonempty domain \(V\), intensity \(1\), and nonnegative symmetric rational costs. Same-type interactions are expressly permitted by USER_TASK, so the quadratic objective is legitimate. The source problem CLIQUE is stated with the necessary graph and threshold conventions.

• Objective expansion. The expression for \(q_G\) is correct. Each diagonal contributes \(x_v^2\); each distinct unordered nonedge contributes \(2x_ux_v\); edges contribute zero. This correctly accounts for the ordered action-pair sum without introducing an additional factor.

• Support elimination. For a positive nonadjacent pair, preserving \(r=x_u+x_v\) preserves feasibility. The diagonal and mutual terms sum to \(r^2\), and symmetry gives the stated remaining contribution \(2\alpha A+2(r-\alpha)C\). Thus the objective is affine in \(\alpha\). An endpoint minimizes it and removes exactly one positive coordinate. Repetition terminates because support size strictly decreases, and its terminal support is a nonempty clique.

• Minimum-cost identity. On a clique support of size \(h\), only diagonal terms remain. Cauchy–Schwarz applies to the \(h\) positive shares whose sum is \(1\), giving \(q_G(y)\geq 1/h\geq 1/\omega(G)\). Combined with \(q_G(y)\leq q_G(x)\), this establishes the lower bound for every feasible real allocation. Uniform shares on a maximum clique attain the bound. Both directions of the identity are proved.

• Reduction correctness, size, and edge cases. Since \(k\) and \(\omega(G)\) are positive, the reciprocal comparison has the stated direction. The threshold \(1/k\) has encoding length polynomial in the encoding length of \(k\), and the explicitly listed cost table has polynomial size. The argument also covers \(k=1\), \(k>|V|\), singleton graphs, and edgeless graphs. It does not assume integral or rational shares in proving hardness.

• General quadratic representation. The definitions of \(H\) and \(Q\) preserve the original objective, including asymmetric costs and same-type terms. Symmetrization is valid because \(x^{\mathsf T}Hx=x^{\mathsf T}H^{\mathsf T}x\). Products and sums of the input rationals have polynomial encoding length. Explicit domain listings ensure that \(N=\sum_t|D_t|\) is polynomially bounded in \(L\).

• Existence and stationarity of a minimizer. The feasible product of simplices is nonempty and compact, so the continuous objective attains its minimum. Every type has a positive coordinate at a feasible minimizer. Within its positive support, sufficiently small perturbations in both directions along the stated same-type directions are feasible. Differentiation therefore establishes the equalities defining \(P_S\). Singleton type supports cause no problem: their corresponding equality is tautological.

• Constancy of the objective on \(P_S\). The polytope contains \(z\), has rational linear constraints, and is bounded by nonnegativity and type normalization. For any \(y\in P_S\), the vector \(d=y-z\) has zero sum within every type. Both \(Rz\) and \(Ry\) are constant within each type, so both displayed inner products vanish. Symmetry of \(R\) validates the quadratic-difference identity. Consequently, every point of \(P_S\), extended by zeros, has the same globally minimal cost. This step does not require convexity of the quadratic objective.

• Polynomial-size certificates. The polytope vertex facts are applicable even if \(P_S\) has lower dimension. At a vertex, a full-rank selection of active constraints determines the coordinates. Row-wise denominator clearing and the stated determinant bounds give polynomial coordinate bit lengths; the right-hand sides are only \(0\) or \(1\). Thus the certificate bound is uniform in the input length. Neither finding \(S\) nor computing the minimizer is required for certificate existence. Exact rational verification of feasibility and the threshold inequality takes polynomial time.

• Conclusion and cited context. The established hardness and membership imply \(\mathsf{NP}\)-completeness and the claimed equivalence with \(\mathsf{P}=\mathsf{NP}\). The ancillary PT-ISABB statement matches Theorem 4.4 and Section 4.3 of the [cited paper](https://www.ifaamas.org/Proceedings/aamas2019/pdfs/p1506.pdf). That finite-agent result is not used as a theorem about continuous allocations.

No additional mathematical clarification is necessary. The empty display near the construction is merely a removable formatting artifact.

⟨structured verdict parsed — rendered above⟩