d4-conf-atal-2014-0420 (d4-conf-atal-2014-0420)

Given a finite supported type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), per-unit vote weights \(a_t>0\), a quota \(Q\), a compatibility graph \(H\) on \(T\), and a target type \(t^\star\), decide whether there are masses \(x_t\in[0,\mu_t]\) for \(t\ne t^\star\) and \(\delta\in(0,\mu_{t^\star}]\) such that the types with \(x_t>0\) form a clique in \(H\), each is compatible with \(t^\star\), and \(\sum_{t\ne t^\star}a_tx_t<Q\le\sum_{t\ne t^\star}a_tx_t+a_{t^\star}\delta\).

A society is given by its support: a nonempty list \(T\) of \(\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 remaining input consists of positive binary rational per-unit vote weights \(a_t\), a binary rational quota \(0<Q\le\sum_{t\in T}a_t\mu_t\), a simple undirected compatibility graph \(H\) on \(T\), and a target \(t^\star\in T\). Mass within each type is mutually compatible; compatibility between distinct types is given by edges of \(H\).
Decide whether real masses \(x_t\in[0,\mu_t]\) for \(t\ne t^\star\) and \(\delta\in(0,\mu_{t^\star}]\) exist such that \(C=\{t\ne t^\star:x_t>0\}\) is a clique, every member of \(C\) is adjacent to \(t^\star\), and \(\sum_{t\ne t^\star}a_tx_t<Q\le\sum_{t\ne t^\star}a_tx_t+a_{t^\star}\delta\). The empty clique is allowed.
Let \(L\) be the total binary input length. State running times in \(\tau\) and \(L\); this graph-based problem has no separate dimension or candidate parameter \(m\).

Is this continuous decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For finite indivisible agents, deciding whether a designated agent is critical in some feasible winning coalition is \(\mathrm{NP}\)-complete, even when every vote weight equals \(1\). [Discrete hardness result](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p37.pdf)
No result settling this exact continuous decision problem was located in the literature search.

Result

The continuous decision problem is \(\mathrm{NP}\)-complete, even when all per-unit vote weights equal \(1\) and all type masses are equal. Consequently, it is \(\mathrm{NP}\)-hard and is not in \(\mathrm{P}\) unless \(\mathrm{P}=\mathrm{NP}\).

1. Exact characterization of continuous feasibility

Define the full vote capacity of type \(t\) by \(w_t=a_t\mu_t\), and let \(N=N_H(t^\star)\) be the target’s neighborhood. For a subset \(S\subseteq N\), write \(W(S)=\sum_{t\in S}w_t\).

Lemma. The instance is feasible if and only if there is a clique \(S\subseteq N\), possibly empty, satisfying
\[ W(S)+w_{t^\star}\ge Q. \]

Proof. Suppose feasible masses exist, and let \(C\) be their positive support outside the target. By hypothesis, \(C\subseteq N\) is a clique. Since \(x_t\le\mu_t\) and \(\delta\le\mu_{t^\star}\),
\[ Q\le\sum_{t\in C}a_tx_t+a_{t^\star}\delta \le W(C)+w_{t^\star}. \]
Thus \(C\) satisfies the claimed capacity condition.

Conversely, suppose a clique \(S\subseteq N\) satisfies that condition.

If \(Q\le w_{t^\star}\), choose all \(x_t=0\) and \(\delta=Q/a_{t^\star}\). Positivity of \(Q\) and \(a_{t^\star}\) gives \(0<\delta\le\mu_{t^\star}\), and the required inequalities become \(0<Q= a_{t^\star}\delta\).

If \(Q>w_{t^\star}\), put \(b=Q-w_{t^\star}>0\). Then \(W(S)\ge b\), so \(\alpha=b/W(S)\) satisfies \(0<\alpha\le1\). Choose \(x_t=\alpha\mu_t\) for \(t\in S\), choose \(x_t=0\) otherwise, and choose \(\delta=\mu_{t^\star}\). The positive support is exactly \(S\), and
\[ \sum_{t\ne t^\star}a_tx_t=b<Q, \qquad \sum_{t\ne t^\star}a_tx_t+a_{t^\star}\delta=b+w_{t^\star}=Q. \]
Here strictness follows from \(w_{t^\star}>0\). Every constraint is therefore satisfied. \(\square\)

Thus the continuous freedom removes the need to match a particular vote total: the remaining task is to find a clique with sufficient full capacity.

2. Membership in \(\mathrm{NP}\)

A certificate is simply a subset \(S\subseteq T\setminus\{t^\star\}\), encoded by an incidence vector of length \(\tau\). The verifier checks:

• Every vertex of \(S\) is adjacent to \(t^\star\).
• Every pair of distinct vertices of \(S\) is adjacent.
• \(W(S)+w_{t^\star}\ge Q\).

The lemma proves that these checks are both necessary and sufficient; real numbers need not appear in the certificate.

For completeness, the numerical check takes polynomial bit time. Write the input rationals as \(a_t=p_t/q_t\), \(\mu_t=u_t/v_t\), and \(Q=p_Q/q_Q\), with positive integer denominators. The integer
\[ D=q_Q\prod_{t\in T}q_tv_t \]
is a common denominator for \(Q\) and every \(w_t\). Its bit length is \(O(L)\), because the total bit length of its factors is at most \(L\). The scaled integers \(DQ\) and \(Dw_t\), and their sums, also have \(O(L)\) bits.

Using schoolbook integer arithmetic, computing these scaled values takes \(O(\tau L^2)\) bit operations. The graph checks take \(O(\tau^2)\) time after constructing an adjacency matrix. Hence certificate verification takes \(O(\tau L^2+\tau^2)\) time, proving membership in \(\mathrm{NP}\).

3. Hardness with equal masses and unit per-unit weights

Reduce from the standard \(\mathrm{NP}\)-complete problem CLIQUE: given a simple graph \(G=(V,E)\) with \(n\ge1\) vertices and an integer \(1\le k\le n\), decide whether \(G\) contains a clique of size at least \(k\).

Choose \(\tau\) to be the smallest power of two satisfying \(\tau\ge n+1\). Create one type for each vertex of \(G\), the target type \(t^\star\), and \(\tau-n-1\) additional types. Set
\[ \mu_t=\frac1\tau,\qquad a_t=1\quad\text{for every }t\in T, \qquad Q=\frac{k+1}{\tau}. \]

The compatibility graph preserves \(G\) on the original vertex types, joins \(t^\star\) to every original vertex, and leaves every additional type isolated.

All input requirements hold: masses are positive and sum to \(1\), weights are positive, and \(0<Q\le1=\sum_ta_t\mu_t\). Moreover, all masses and the quota are dyadic rationals, so the construction works even under that narrower interpretation of “binary rational.”

Forward direction. If \(G\) contains a clique with at least \(k\) vertices, select exactly \(k\) of them. Give each selected type its full mass \(1/\tau\), give every other non-target type mass zero, and take \(\delta=1/\tau\). Then
\[ \sum_{t\ne t^\star}a_tx_t=\frac{k}{\tau} <\frac{k+1}{\tau}=Q =\sum_{t\ne t^\star}a_tx_t+a_{t^\star}\delta. \]
Compatibility holds by construction.

Reverse direction. Suppose the continuous instance is feasible. Its positive non-target support \(C\) contains only original vertex types, because the additional types are not adjacent to \(t^\star\). It is therefore a clique in \(G\). The mass bounds imply
\[ \frac{k+1}{\tau}=Q \le\sum_{t\in C}x_t+\delta \le\frac{|C|+1}{\tau}, \]
and hence \(|C|\ge k\). Thus \(G\) contains the required clique.

Since \(\tau<2(n+1)\), the output has length \(O(n^2+n\log n)\) using an adjacency-matrix encoding, and the construction takes polynomial time. This proves \(\mathrm{NP}\)-hardness.

The universal-target graph construction also appears in Theorem 2 of the supplied [discrete hardness paper](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p37.pdf). The argument above separately verifies normalization and both directions for continuous masses.

4. Running time in \(\tau\) and \(L\)

A direct exact algorithm enumerates every subset of \(N_H(t^\star)\), checks whether it is a clique, and tests the lemma’s capacity condition. There are at most \(2^{\tau-1}\) subsets.

After the integer preprocessing described above, each subset requires \(O(\tau^2+\tau L)\) bit operations: pairwise compatibility checks and addition of at most \(\tau\) integers of \(O(L)\) bits. The resulting running time is
\[ O\!\left(\tau L^2+2^{\tau-1}(\tau^2+\tau L)\right). \]

In particular, the problem is polynomial-time solvable for every fixed support size \(\tau\). No separate dimension or candidate parameter is used.

⟨structured verdict parsed — rendered above⟩

The prover’s output correctly resolves the task: the continuous decision problem is NP-complete, including the restriction to equal type masses and per-unit vote weights \(1\). No major or minor mathematical issues were found.

1. Exact feasibility characterization

The definitions \(w_t=a_t\mu_t\), \(N=N_H(t^\star)\), and \(W(S)=\sum_{t\in S}w_t\) are consistent with the input. Every \(w_t\) is strictly positive.

Necessity. For feasible masses, the positive non-target support \(C\) is a clique contained in \(N\). The inequalities
\[ Q\le\sum_{t\in C}a_tx_t+a_{t^\star}\delta \le W(C)+w_{t^\star} \]
follow directly from the individual mass bounds and positive vote weights. Thus the capacity condition is necessary.

Sufficiency when \(Q\le w_{t^\star}\). The proposed empty support is permitted. The choice \(\delta=Q/a_{t^\star}\) is strictly positive and at most \(\mu_{t^\star}\). It satisfies both the strict losing inequality and the winning inequality. Equality \(Q=w_{t^\star}\) is covered.

Sufficiency when \(Q>w_{t^\star}\). Here \(b=Q-w_{t^\star}>0\), and the capacity hypothesis gives \(W(S)\ge b>0\). Consequently, division by \(W(S)\) is valid and \(0<\alpha=b/W(S)\le1\). Since all masses are positive, the constructed positive support is exactly \(S\). The non-target vote total is \(b\), which is strictly below \(Q\) because \(w_{t^\star}>0\). Adding the target’s full capacity gives exactly \(Q\).

The lemma is therefore proved in both directions. It also covers empty cliques and instances with only the target type.

2. Membership in NP

The incidence-vector certificate has length \(\tau\). The adjacency checks establish precisely that the selected subset is a clique in the target’s neighborhood. The numerical check establishes the lemma’s capacity condition. Thus the certificate is necessary and sufficient; no certificate involving real numbers is required.

The bit-complexity argument is valid:

• \(D=q_Q\prod_{t\in T}q_tv_t\) is divisible by the denominator of every capacity and by the quota’s denominator.
• Its bit length is \(O(L)\).
• The scaled capacities, scaled quota, and sums have \(O(L)\) bits: numerator lengths and the additional bits from summation remain bounded by \(O(L)\).
• Schoolbook multiplication and exact division support the claimed preprocessing bound \(O(\tau L^2)\).
• Constructing and checking an adjacency matrix fits within \(O(\tau L^2+\tau^2)\), including reading the input.

The claimed polynomial certificate-verification bound is justified.

3. NP-hardness reduction

The stated source problem is the standard NP-complete CLIQUE decision problem restricted to \(n\ge1\) and \(1\le k\le n\). These restrictions exclude only trivial cases and do not undermine its use as a hardness source.

Validity of the constructed instance. The construction creates exactly \(\tau\) types. Their equal positive masses sum to \(1\), and all per-unit weights equal \(1\). Since \(k+1\le n+1\le\tau\), the quota satisfies
\[ 0<Q=\frac{k+1}{\tau}\le1=\sum_{t\in T}a_t\mu_t. \]
Choosing \(\tau\) as a power of two ensures that every constructed rational is dyadic. The compatibility graph is simple and undirected.

Forward implication. Any clique of size at least \(k\) contains a clique of size exactly \(k\). Assigning full mass to those types gives non-target votes \(k/\tau\); adding the target’s full mass gives exactly the quota. The required strict inequality and every compatibility condition hold.

Reverse implication. Isolated additional types cannot belong to the positive support because they are not adjacent to the target. Therefore the positive support \(C\) is a clique in the original graph. The displayed capacity bound
\[ \frac{k+1}{\tau}\le\sum_{t\in C}x_t+\delta \le\frac{|C|+1}{\tau} \]
correctly implies \(|C|\ge k\). Fractional participation cannot invalidate this implication.

Size and runtime. The bound \(\tau<2(n+1)\) is correct, including when \(n+1\) is already a power of two. An adjacency matrix uses \(O(n^2)\) bits, and the numerical data use \(O(n\log n)\) bits. The construction is polynomial in the source input length.

The reduction establishes NP-hardness under both claimed restrictions.

4. Literature attribution

The attribution is accurate: Theorem 2 of the linked paper uses original graph vertices together with an additional universally compatible agent, unit weights, and quota \(k+1\). [The cited paper](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p37.pdf) supports this statement.

The continuous reduction is independently verified in the prover’s output; the paper is not being used to substitute for its correctness proof.

5. Exact algorithm and final classification

There are at most \(2^{\tau-1}\) subsets of the target’s neighborhood. After preprocessing, the claimed per-subset cost \(O(\tau^2+\tau L)\) covers clique checks and addition and comparison of scaled capacities. Hence
\[ O\!\left(\tau L^2+2^{\tau-1}(\tau^2+\tau L)\right) \]
is a valid upper bound.

For fixed \(\tau\), this bound is polynomial in \(L\). That statement is consistent with NP-completeness when \(\tau\) varies with the input. The conditional conclusion concerning membership in P is also correct.

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩