d4-conf-aaai-2021-0901 (d4-conf-aaai-2021-0901)

Given advertisers \(K\), types \(T\) with rational masses \(\mu_t>0\) summing to \(1\), pre-spend beliefs \(s_t\in\Delta_K\), per-capita budgets \(\beta_k\), nonnegative saliences \(a_u\) with \(\sum_u\mu_u a_u=1\), and a rational exact finite Friedkin–Johnsen quotient \(H\ge0\) with \(\sum_t H_{t,u}=1\), compute a pure Nash equilibrium in per-type spends \(b_{t,k}\ge0\) satisfying \(\sum_t\mu_t b_{t,k}\le\beta_k\). Define \(r_{t,k}(b)=(s_{t,k}+b_{t,k})/(1+\sum_{\ell\in K}b_{t,\ell})\), \(z_{u,k}(b)=\sum_t H_{t,u}r_{t,k}(b)\), and \(U_k(b)=\sum_u\mu_u a_u z_{u,k}(b)\); the output must satisfy \(U_k(b)\ge U_k(b'_{\cdot,k},b_{-k})\) for every advertiser \(k\) and every feasible unilateral deviation \(b'_{\cdot,k}\). Seek running time polynomial in \(K\), \(\tau=|T|\), and rational input bit length \(L\).

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Let \(K\) be a nonempty advertiser set and \(m=|K|\).
The remaining inputs are binary rational pre-spend beliefs \(s_t\in\Delta_K\), budgets \(\beta_k>0\), and saliences \(a_u\ge0\) satisfying \(\sum_u\mu_u a_u=1\). Let \(L\) be the total input bit length.
The supplied rational influence matrix \(H\ge0\) satisfies \(\sum_t H_{t,u}=1\) and is promised to be an exact finite Friedkin–Johnsen quotient, meaning \(H=(I+Q)^{-\mathsf T}\) for a rational matrix \(Q\) with zero row sums and nonpositive off-diagonal entries.
Advertiser \(k\) chooses real per-capita spends \(b_{t,k}\ge0\) with \(\sum_t\mu_t b_{t,k}\le\beta_k\); its entire spend vector may change in a unilateral deviation.
Define \(r_{t,k}(b)=(s_{t,k}+b_{t,k})/(1+\sum_{\ell\in K}b_{t,\ell})\), \(z_{u,k}(b)=\sum_t H_{t,u}r_{t,k}(b)\), and \(U_k(b)=\sum_u\mu_u a_u z_{u,k}(b)\).
An exact pure Nash equilibrium is a feasible profile satisfying \(U_k(b)\ge U_k(b'_{\cdot,k},b_{-k})\) for every \(k\) and every feasible real unilateral deviation. Exact coordinates use real algebraic encoding by integer polynomials and rational isolating intervals.

Is computing an exact pure Nash equilibrium polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?

For finite-node societies, pure equilibria exist for nondecreasing convex constant-sum payoffs, and polynomial-time computation is claimed for linear payoffs. [Source](https://jpdickerson.com/pubs/christia21scalable.pdf)
That result does not specify an exact algebraic output encoding or establish its bit complexity; no verified source located settles the exact support-mass problem stated here.

Status and encoding convention

Polynomial-time exact computation is impossible under explicit coefficient-list encoding, because the required output can have superpolynomial length. I do not establish $\mathrm{NP}$-hardness.

Here an integer polynomial is represented by an explicit dense or sparse list of its coefficients and exponents, together with a rational isolating interval. The output-length argument does not apply to arithmetic-circuit representations of polynomials or representations by systems of equations.

In addition to reproving the output-length obstruction from the notes, I establish two further results:

• Every instance with $m\geq 2$ has a unique pure Nash equilibrium, including instances with zero beliefs or zero effective payoff weights.
• Deciding whether an equilibrium coordinate exceeds a supplied rational threshold admits a polynomial-time many-one reduction from square-root-sum comparison.

These results do not settle the remaining $\mathrm{NP}$-hardness question.

1. Payoff reduction and equilibrium certificates

Define the effective weights
$$ w_t=\sum_u\mu_u a_u H_{t,u}. $$
They satisfy $w_t\geq 0$ and
$$ \sum_t w_t =\sum_u\mu_u a_u\sum_tH_{t,u} =1. $$
Interchanging finite sums gives
$$ U_k(b)=\sum_t w_t\frac{s_{t,k}+b_{t,k}}{D_t(b)}, \qquad D_t(b)=1+\sum_\ell b_{t,\ell}. $$
Because $\sum_k s_{t,k}=1$,
$$ \sum_k U_k(b)=1. $$

Let
$$ X_k=\left\{v\in\mathbb R^\tau: v_t\geq 0,\ \sum_t\mu_t v_t\leq\beta_k\right\}, \qquad X=\prod_kX_k. $$
Every $X_k$ is nonempty, compact, and convex: in particular, $v_t\leq\beta_k/\mu_t$.

Write
$$ g_{t,k}(b)=\frac{\partial U_k}{\partial b_{t,k}}(b) =\frac{w_t(D_t-s_{t,k}-b_{t,k})}{D_t^2}. $$
For fixed opposing spends, put $c_{t,k}=1+\sum_{\ell\neq k}b_{t,\ell}$. The derivatives of the type contribution with respect to the advertiser’s own spend $x$ are
$$ \frac{w_t(c_{t,k}-s_{t,k})}{(c_{t,k}+x)^2}, \qquad -\frac{2w_t(c_{t,k}-s_{t,k})}{(c_{t,k}+x)^3}. $$
Since $c_{t,k}\geq 1\geq s_{t,k}$, the payoff is differentiable and concave in the advertiser’s entire spend vector.

Consequently, a feasible profile $b$ is an equilibrium exactly when, for every advertiser $k$,
$$ \sum_t g_{t,k}(b)(v_t-b_{t,k})\leq 0 \qquad\text{for every }v\in X_k. $$
Necessity follows by differentiating the payoff along each feasible segment from $b_{\cdot,k}$ to $v$. Sufficiency follows from the concave-function inequality
$$ U_k(v,b_{-k})-U_k(b) \leq \sum_tg_{t,k}(b)(v_t-b_{t,k}). $$
Thus these conditions address arbitrary feasible vector deviations.

A useful sufficient certificate is budget exhaustion together with multipliers $\lambda_k\geq 0$ satisfying
$$ g_{t,k}(b)=\mu_t\lambda_k \quad\text{if }b_{t,k}>0, \qquad g_{t,k}(b)\leq\mu_t\lambda_k \quad\text{if }b_{t,k}=0. $$
Indeed, for every feasible $v$,
$$ \begin{aligned} U_k(v,b_{-k})-U_k(b) &\leq\sum_tg_{t,k}(b)(v_t-b_{t,k})\\ &\leq\lambda_k\sum_t\mu_t(v_t-b_{t,k})\\ &\leq 0. \end{aligned} $$
The second inequality uses $v_t\geq 0$ at coordinates where $b_{t,k}=0$.

2. Existence and uniqueness for all nontrivial instances

For $m=1$, the payoff is identically $1$, so the zero profile is a rational equilibrium. Henceforth assume $m\geq 2$.

2.1. Existence

Let $g(b)$ denote the vector of all the partial derivatives above. Consider
$$ \Phi(b)=P_X(b+g(b)), $$
where $P_X$ is Euclidean projection onto $X$.

Projection exists and is unique because $X$ is compact and convex and squared Euclidean distance is strictly convex. Its characterization is
$$ p=P_X(u) \quad\Longleftrightarrow\quad (u-p)\cdot(y-p)\leq 0 \quad\text{for every }y\in X. $$
This follows by differentiating squared distance along segments in $X$; the converse follows by expanding $\|u-y\|^2$.

Applying this characterization to $p=P_X(u)$ and $q=P_X(v)$ gives
$$ \|p-q\|^2\leq(p-q)\cdot(u-v)\leq\|p-q\|\|u-v\|. $$
Thus projection is continuous. The vector $g$ is continuous because all denominators satisfy $D_t\geq 1$. Therefore $\Phi$ is a continuous self-map of the nonempty compact convex set $X$.

Brouwer’s fixed-point theorem gives $b=\Phi(b)$. The projection characterization then yields
$$ g(b)\cdot(y-b)\leq 0 \qquad\text{for every }y\in X. $$
Taking $y$ to differ from $b$ in only one advertiser’s vector and applying Section 1 proves that $b$ is an equilibrium.

2.2. Budgets and positive multipliers

Let
$$ T_+=\{t:w_t>0\}. $$
This set is nonempty.

At an equilibrium, each advertiser $k$ has a strictly positive marginal at some type in $T_+$. Suppose instead that all those marginals were zero. Their nonnegative numerators would imply
$$ s_{t,k}=1, \qquad b_{t,j}=0\quad\text{for every }j\neq k, \qquad t\in T_+. $$
For any other advertiser $j$, the simplex condition would give $s_{t,j}=0$ on $T_+$, and hence $U_j(b)=0$. Advertiser $j$ could obtain positive payoff by spending its positive budget on any one type in $T_+$. This contradicts equilibrium.

The existence of a positive marginal has two consequences.

First, every advertiser exhausts its budget: otherwise it could increase spend slightly at a type with positive marginal.

Second, no advertiser spends at a coordinate with zero marginal. If it did, transferring a sufficiently small positive expenditure from that coordinate to one with positive marginal would have positive directional derivative and would improve its payoff. In particular,
$$ b_{t,k}=0\qquad\text{when }w_t=0. $$

Since $\beta_k>0$ and the budget is exhausted, advertiser $k$ has an active coordinate. At any two active coordinates, feasible transfers in both directions show that their normalized marginals $g_{t,k}/\mu_t$ are equal. Transfers from an active coordinate to an inactive coordinate show that the inactive normalized marginal is no larger.

Thus every equilibrium satisfies the certificate in Section 1 with
$$ \lambda_k>0. $$

2.3. A monotonicity identity

Fix a type $t$, suppress its index, and write
$$ x_k=s_{t,k}+b_{t,k}, \qquad D=\sum_kx_k, \qquad p_k=\frac{x_k}{D}. $$
Then $p_k\geq 0$ and $\sum_kp_k=1$.

Let $J$ be the Jacobian, with respect to the spends at this type, of the vector whose entries are $g_k=w(D-x_k)/D^2$. Direct differentiation gives
$$ J_{kk}=-\frac{2w(D-x_k)}{D^3}, \qquad J_{kj}=\frac{w(2x_k-D)}{D^3} \quad(j\neq k). $$

For any $d\in\mathbb R^m$, put $S=\sum_kd_k$. Then
$$ \begin{aligned} d^{\mathsf T}Jd &=\frac{w}{D^3} \left(2(x\cdot d)S-DS^2-D\sum_kd_k^2\right)\\ &=-\frac{w}{D^2} \sum_i p_i \left( \sum_{j\neq i}d_j^2+ \left(\sum_{j\neq i}d_j\right)^2 \right) \leq 0. \end{aligned} $$
The second equality uses
$$ \sum_{j\neq i}d_j^2+ \left(\sum_{j\neq i}d_j\right)^2 =\sum_jd_j^2+S^2-2Sd_i. $$

For $w>0$, equality holds precisely when, for every $i$ with $p_i>0$, all coordinates $d_j$ with $j\neq i$ vanish.

Since each type’s marginals depend only on that type’s spends, integrating this identity along a segment gives
$$ (g(b)-g(c))\cdot(b-c)\leq 0 \qquad\text{for all }b,c\in X. $$

2.4. Uniqueness

Suppose $b$ and $c$ are equilibria, and put $d=b-c$. Their first-order conditions imply
$$ g(b)\cdot d\geq 0, \qquad g(c)\cdot d\leq 0. $$
Together with monotonicity, this gives
$$ (g(b)-g(c))\cdot d=0. $$

Along the segment $c+\theta d$, the expression in Section 2.3 is a sum of continuous nonpositive terms, one for each type. Its integral is zero. Therefore each term is zero at every point of the segment.

Fix $t\in T_+$ and examine the midpoint. If its vector $p$ has at least two positive coordinates, the equality characterization forces $d_{t,\cdot}=0$.

Otherwise $p_i=1$ for some $i$. Nonnegativity of beliefs and spends then implies
$$ s_{t,i}=1, \qquad s_{t,j}=b_{t,j}=c_{t,j}=0 \quad(j\neq i). $$
Advertiser $i$ has zero marginal at this type at both endpoints. Section 2.2 therefore gives
$$ b_{t,i}=c_{t,i}=0. $$
Again $d_{t,\cdot}=0$.

For $t\notin T_+$, both equilibria spend zero by Section 2.2. Hence $b=c$.

Every instance with $m\geq 2$ has exactly one pure Nash equilibrium.

3. A reusable family with an explicit equilibrium

Choose positive rational numbers $q_1,\ldots,q_n$ and positive rational weights $\rho_1,\ldots,\rho_n$ satisfying
$$ \sum_i\rho_i=1, \qquad 1\leq r_i:=\sqrt{q_i}<\frac{17}{16}. $$
Define
$$ A=\sum_i\rho_iq_i, \qquad \bar r=\sum_i\rho_i r_i, \qquad C=\frac54. $$

There are two advertisers and two types $(i,+),(i,-)$ for each index. Set
$$ \mu_{i,+}=\mu_{i,-}=\frac{\rho_i}{2}, \qquad a_{i,+}=a_{i,-}=\frac{q_i}{A}, \qquad \beta_1=\beta_2=\frac18, $$
and
$$ (s_{i,+,1},s_{i,+,2})=\left(\frac14,\frac34\right), \qquad (s_{i,-,1},s_{i,-,2})=\left(\frac34,\frac14\right). $$
Take $H=I$. The Friedkin–Johnsen promise holds with $Q=0$, and salience normalization holds because
$$ \sum_t\mu_ta_t=\sum_i\rho_i\frac{q_i}{A}=1. $$

Define
$$ x_i=C\frac{r_i}{\bar r}-1 $$
and the profile
$$ b_{i,+,1}=x_i,\quad b_{i,+,2}=0, \qquad b_{i,-,1}=0,\quad b_{i,-,2}=x_i. $$
Since $1\leq r_i,\bar r<17/16$,
$$ \frac3{17}<x_i<\frac{21}{64}<\frac12. $$
Each advertiser’s expenditure is
$$ \frac12\sum_i\rho_i x_i =\frac12(C-1) =\frac18. $$

Here $w_t=\mu_ta_t$. Put
$$ \lambda=\frac{3\bar r^2}{4AC^2}>0. $$
At an active coordinate, the advertiser’s initial belief is $1/4$ and the opposing spend is zero, so
$$ \frac{g_{t,k}}{\mu_t} =\frac{q_i}{A}\frac{3/4}{(1+x_i)^2} =\lambda. $$
At an inactive coordinate, its initial belief is $3/4$ and its opponent spends $x_i$, so
$$ \frac{g_{t,k}}{\mu_t} =\frac{q_i}{A}\frac{1/4+x_i}{(1+x_i)^2} =\lambda\frac{1/4+x_i}{3/4} <\lambda. $$
The certificate in Section 1 applies. Section 2 proves uniqueness.

Thus the displayed profile is the unique equilibrium of this rational family.

4. Superpolynomial output length

4.1. Rational instances of polynomial input length

For each $n\geq 2$, choose distinct primes
$$ 2^{i+8}<p_i<2^{i+9}, \qquad 1\leq i\leq n. $$
Bertrand’s postulate guarantees these choices: for every integer $N\geq 2$, there is a prime strictly between $N$ and $2N$. Apply it with $N=2^{i+8}$; the intervals are disjoint. [Soundararajan, *Bertrand’s Postulate and the Existence of Finite Fields*](https://arxiv.org/pdf/2007.01389)

Put
$$ d_i=\lfloor\sqrt{p_i}\rfloor, \qquad q_i=\frac{p_i}{d_i^2}, \qquad r_i=\frac{\sqrt{p_i}}{d_i}, \qquad \rho_i=\frac1n. $$
Since the primes are nonsquares and $d_i\geq 16$,
$$ 1<r_i<1+\frac1{d_i}\leq\frac{17}{16}. $$
Section 3 therefore applies.

Each $p_i,d_i,q_i$ has $O(i)$ bits. The rational number
$$ A=\frac1n\sum_iq_i $$
can be written with numerator and denominator of $O(n^2)$ bits by using the product of the denominators as a common denominator. Each salience $q_i/A$ consequently has $O(n^2)$ bits.

Including the explicit identity matrix,
$$ m=2,\qquad \tau=2n,\qquad L=O(n^3). $$
This is an existence argument for a worst-case family; efficient selection of these primes is not needed.

4.2. Independent square-root sign changes

For completeness, define
$$ F_j=\mathbb Q(\sqrt{p_1},\ldots,\sqrt{p_j}). $$
I prove inductively that $F_j$ has basis
$$ e_S=\prod_{i\in S}\sqrt{p_i}, \qquad S\subseteq\{1,\ldots,j\}, $$
and admits all independent sign changes of the displayed square roots as automorphisms.

For $j=0$, the field is $\mathbb Q$, its basis is $\{1\}$, and its sole sign-change automorphism is the identity.

Assume the assertion for $j$. If some $z\in F_j$ satisfied $z^2=p_{j+1}$, every sign-change automorphism $\sigma$ would satisfy $\sigma(z)=z$ or $\sigma(z)=-z$.

Expand $z$ in the asserted basis. Distinct basis elements have distinct sign characters: changing the sign at an index in the symmetric difference of two subsets distinguishes them. Therefore two different basis elements cannot both have nonzero coefficients in an element sent to either itself or its negative by every sign change. Hence
$$ z=ce_S \qquad\text{for some }c\in\mathbb Q. $$
But then
$$ p_{j+1}=c^2\prod_{i\in S}p_i, $$
which contradicts prime-exponent parity: the exponent of the new prime on the left is odd and its exponent on the right is even.

Thus adjoining $\sqrt{p_{j+1}}$ doubles the degree and produces the claimed enlarged basis. Each existing automorphism extends in both ways, by sending
$$ a+b\sqrt{p_{j+1}} \quad\text{to}\quad \sigma(a)\pm\sigma(b)\sqrt{p_{j+1}}. $$
These maps preserve multiplication because $\sigma$ fixes $p_{j+1}$. This completes the induction.

In particular, the $r_i$ are linearly independent over $\mathbb Q$, and all independent sign changes of them are automorphisms of $F_n$.

4.3. Exponentially many real conjugates

The equilibrium coordinate
$$ x_1=\frac{Cn r_1}{\sum_i r_i}-1 $$
has, under a sign vector $\varepsilon\in\{-1,1\}^n$, the image
$$ x_1^{(\varepsilon)} =\frac{Cn\varepsilon_1r_1}{\sum_i\varepsilon_i r_i}-1. $$
Every denominator is nonzero by linear independence.

Two images are equal exactly when
$$ \varepsilon_1\sum_i\delta_i r_i =\delta_1\sum_i\varepsilon_i r_i. $$
Linear independence makes this equivalent to
$$ \varepsilon_1\delta_i=\delta_1\varepsilon_i \qquad\text{for every }i. $$
Thus equality occurs exactly when $\delta=\varepsilon$ or $\delta=-\varepsilon$. There are $2^{n-1}$ distinct images.

All are real, and none is zero. Indeed, a zero image would imply
$$ Cn\varepsilon_1r_1=\sum_i\varepsilon_i r_i, $$
contradicting linear independence because $n\geq 2$.

If a nonzero integer polynomial $P$ satisfies $P(x_1)=0$, applying every sign-change automorphism shows that all these images are roots of $P$. Therefore every defining integer polynomial has at least $2^{n-1}$ distinct nonzero real roots.

4.4. Sparse encoding does not avoid the obstruction

A nonzero real polynomial with $h$ nonzero monomials has at most $h-1$ distinct positive roots and at most $h-1$ distinct negative roots.

For positive roots, prove this by induction on $h$. A monomial has none. Otherwise factor out the smallest power of the variable; this preserves positive roots and leaves a polynomial with a nonzero constant term. Its derivative has exactly $h-1$ nonzero monomials, so by induction it has at most $h-2$ distinct positive roots. Rolle’s theorem bounds the original polynomial’s distinct positive roots by $h-1$. Apply the same argument to $P(-X)$ for negative roots.

Consequently, any defining polynomial for $x_1$ has
$$ 2^{n-1}\leq 2(h-1), \qquad h\geq 2^{n-2}+1. $$
An explicit sparse list therefore requires exponentially many entries. A dense list is no shorter. An isolating interval does not remove the need to supply the polynomial.

Since the equilibrium is unique, an algorithm cannot choose a different equilibrium with shorter coordinates. The required output length is $\Omega(2^n)$ while $L=O(n^3)$.

Under explicit dense or sparse coefficient-list encoding, no algorithm can compute an exact equilibrium in time polynomial in $m,\tau,L$.

5. Square-root-sum reduction for equilibrium-coordinate comparison

This section concerns a decision problem, so its output has constant length.

Define equilibrium-coordinate comparison as follows: given a valid instance with $m\geq 2$, a coordinate $(t,k)$, and a rational threshold $h$, decide whether its unique equilibrium satisfies
$$ b^*_{t,k}\geq h. $$

The standard integer-threshold square-root-sum problem asks, for positive binary integers $N_1,\ldots,N_n,B$, whether
$$ S:=\sum_{i=1}^n\sqrt{N_i}\leq B. $$
This formulation appears in [Etessami and Yannakakis, *On the Complexity of Nash Equilibria and Other Fixed Points*](https://homepages.inf.ed.ac.uk/kousha/nash_focs07_full_j_spec_issue_sub.pdf).

5.1. Polynomial-time construction

For $1\leq i\leq n$, set
$$ M_i=256N_i, \qquad d_i=\lfloor\sqrt{M_i}\rfloor, \qquad q_i=\frac{M_i}{d_i^2}. $$
Add a reference index $0$ with
$$ M_0=256,\qquad d_0=16,\qquad q_0=1. $$
Define
$$ E=\sum_{i=0}^n d_i, \qquad \rho_i=\frac{d_i}{E}. $$

Every $d_i\geq 16$, and
$$ 1\leq r_i:=\sqrt{q_i}<1+\frac1{d_i}\leq\frac{17}{16}. $$
Thus these quantities define an instance of Section 3 with $2(n+1)$ types.

All supplied quantities are rational. Integer square roots can be computed by binary search in polynomial time. The integers $d_i$ have bit lengths bounded by the source input length. A common denominator formed from the product of the $d_i^2$ also has polynomial bit length. Hence the normalized saliences, masses, identity matrix, and the entire instance can be constructed in polynomial time and have polynomial total bit length.

5.2. The designated coordinate answers the source instance

The weighted mean of the square roots is
$$ \bar r =\sum_{i=0}^n\frac{d_i}{E}\frac{\sqrt{M_i}}{d_i} =\frac{16(1+S)}{E}. $$
Since $r_0=1$, the unique equilibrium has reference coordinate
$$ b^*_{0,+,1} =C\frac{r_0}{\bar r}-1 =\frac{CE}{16(1+S)}-1. $$
Supply the rational threshold
$$ h=\frac{CE}{16(1+B)}-1. $$
Its bit length is polynomial in the source input length.

Because both denominators are positive and reciprocal is strictly decreasing,
$$ b^*_{0,+,1}\geq h \quad\Longleftrightarrow\quad S\leq B. $$
Equality is preserved.

This is a polynomial-time many-one reduction from square-root-sum comparison to equilibrium-coordinate comparison. It already holds with two advertisers, identity influence, positive saliences, and strictly positive beliefs.

This reduction does not prove $\mathrm{NP}$-hardness. In particular, it does not supply an $\mathrm{NP}$-hard source problem or a polynomial-time recovery procedure for such a source problem from an equilibrium output.

6. A polynomial-size exact equilibrium description

The preceding comparison problem also has a direct formulation in the existential theory of the reals.

Introduce real variables $b_{t,k}$ and $\lambda_k$, and abbreviate
$$ D_t=1+\sum_jb_{t,j}, \qquad R_{t,k} =\mu_t\lambda_kD_t^2-w_t(D_t-s_{t,k}-b_{t,k}). $$
Consider the constraints
$$ \begin{gathered} b_{t,k}\geq 0,\qquad \lambda_k\geq 0,\\ \sum_t\mu_t b_{t,k}=\beta_k,\\ R_{t,k}\geq 0,\qquad b_{t,k}R_{t,k}=0. \end{gathered} $$

Every equilibrium satisfies them by Section 2.2. Conversely, dividing by $D_t^2>0$ gives exactly the certificate of Section 1, so every solution is an equilibrium.

The polynomials have degree at most $4$. Their coefficients are rational and have polynomial bit length; computing the $w_t$ and clearing denominators preserves polynomial description length. Expanding each $D_t^2$ also produces only polynomially many monomials.

Adding the inequality $b_{t,k}\geq h$ therefore gives a polynomial-size existential real formula equivalent to equilibrium-coordinate comparison.

This description is compact even when an individual coordinate’s explicit univariate defining polynomial is exponentially long. It does not provide a polynomial-time algorithm for the requested output encoding.

7. What remains open

The output-length result completely rules out polynomial-time production of the stipulated explicit coefficient-list output. The convex-programming argument in the supplied paper does not establish that stronger output guarantee. [Christia et al., Section 3](https://jpdickerson.com/pubs/christia21scalable.pdf)

The new uniqueness theorem and square-root-sum reduction give structural and decision-complexity information beyond that obstruction. However, neither proves $\mathrm{NP}$-hardness of the exact equilibrium search task.

The unresolved part is a hardness classification under an explicitly specified polynomial-time reduction notion for the requested search output. Output length alone does not establish such hardness, and the square-root-sum reduction concerns a coordinate-comparison decision problem.

⟨structured verdict parsed — rendered above⟩

Verification report

Result: partial. The substantive mathematics is correct under the prover’s explicit coefficient-list encoding convention. It establishes an output-length obstruction, existence and uniqueness for $m\geq 2$, and a square-root-sum reduction to equilibrium-coordinate comparison. It does not establish $\mathrm{NP}$-hardness of the requested equilibrium search problem.

No central mathematical step is refuted. The main outstanding issue is completion of the requested complexity classification.

1. Payoff reduction and equilibrium certificates

Verified.

The effective weights satisfy $w_t\geq 0$ and $\sum_t w_t=1$ by the stated column normalization of $H$ and salience normalization. Interchanging the finite sums correctly gives the reduced payoff. The constant-sum identity follows from
$$ \sum_k(s_{t,k}+b_{t,k})=D_t. $$

Each feasible set is nonempty, convex, closed, and bounded because $\mu_t>0$ and
$$ 0\leq v_t\leq \frac{\beta_k}{\mu_t}. $$

Both displayed own-spend derivatives are correct. The inequality $c_{t,k}\geq s_{t,k}$ verifies concavity, including the cases of zero weights and zero marginal contributions.

The first-order characterization is necessary and sufficient for every feasible vector deviation. Necessity uses feasible segments; sufficiency uses differentiable concavity on the advertiser’s entire feasible set.

The multiplier certificate is correctly presented as sufficient. Its inequality at inactive coordinates has the correct direction because the deviating spend there is nonnegative. Budget exhaustion and $\lambda_k\geq 0$ justify the final inequality.

2. Existence, positive multipliers, and uniqueness

2.1. Existence

Verified.

The projection characterization and nonexpansiveness inequality are correct. Consequently, $\Phi$ is continuous and maps the nonempty compact convex set $X$ into itself.

The finite-dimensional form of Brouwer’s theorem applies: a continuous self-map of a nonempty compact convex subset of Euclidean space has a fixed point. The projection condition at that fixed point gives the product-space variational inequality, and restricting it to one advertiser gives the equilibrium conditions from Section 1.

The separate treatment of $m=1$ is correct: its payoff is identically $1$, and the zero profile is feasible.

2.2. Budget exhaustion and positive multipliers

Verified.

If an advertiser has zero marginal at every positively weighted type, the nonnegative terms in each marginal numerator must vanish. This gives the stated beliefs and opposing spends. Another advertiser then has zero payoff and a feasible positive-payoff deviation, using its strictly positive budget and a type in the nonempty set $T_+$.

Thus every advertiser has a positive marginal somewhere. A slack budget permits an improving increase there.

The transfer argument also works with unequal support masses: the transferred quantity is expenditure, so the associated coordinate changes are scaled by their positive masses. Transferring expenditure from a zero-marginal coordinate to a positive-marginal coordinate has positive directional derivative. Hence zero-marginal coordinates receive no equilibrium spending.

Transfers between active coordinates establish equality of normalized marginals; transfers to inactive coordinates establish the required inequality. Budget exhaustion, positive budgets, and the absence of spending at zero-marginal coordinates justify $\lambda_k>0$.

2.3. Monotonicity identity

Verified.

Both Jacobian entries are correct. The quadratic-form identity and its expansion into nonpositive terms agree algebraically.

For $w>0$, the equality characterization is exact: every summand with $p_i>0$ must vanish, which requires every $d_j$ with $j\neq i$ to vanish.

The denominators stay positive throughout every feasible segment. Integrating the Jacobian quadratic form therefore gives the claimed monotonicity inequality.

2.4. Uniqueness

Verified.

The equilibrium inequalities imply
$$ g(b)\cdot(b-c)\geq 0, \qquad g(c)\cdot(b-c)\leq 0. $$
Together with monotonicity, these force equality.

The segment integrand consists of finitely many continuous nonpositive terms. A zero integral forces each term to vanish throughout the segment.

At a positively weighted type, two positive midpoint coordinates force the entire difference vector to vanish. If only one midpoint coordinate is positive, nonnegativity forces every other belief and endpoint spend there to be zero. The remaining advertiser has zero marginal at that type, so Section 2.2 forces its endpoint spends to vanish as well.

Zero-weight types already have zero equilibrium spending. Thus the uniqueness conclusion follows, including the advertised degenerate beliefs and weights.

3. Explicit equilibrium family

Verified.

All masses are positive and sum to $1$. The saliences are positive rational numbers with the required normalization. The identity influence matrix satisfies the quotient promise with $Q=0$.

The bounds are correct:
$$ \frac{3}{17}<x_i<\frac{21}{64}<\frac12. $$
They ensure nonnegative spending and the strict inactive-coordinate marginal inequality.

Each advertiser’s expenditure is exactly $1/8$. The active normalized marginal equals the displayed $\lambda$, and the inactive normalized marginal is strictly smaller. The certificate proves equilibrium, and Section 2 proves uniqueness.

4. Output-length obstruction

4.1. Input length and prime selection

Verified.

Bertrand’s postulate supplies a prime in each stated interval, whose disjointness ensures distinctness. The cited source states the required prime-existence theorem. [Soundararajan](https://arxiv.org/pdf/2007.01389)

The floor-square-root construction gives the required range for $r_i$. The claimed bit bounds for $A$, the saliences, and the full input are valid. In particular,
$$ L=O(n^3),\qquad m=2,\qquad \tau=2n. $$

Efficient prime selection is unnecessary for this worst-case output-length argument.

4.2. Independent sign changes

Verified.

The induction correctly excludes a square root of the new prime from the previously constructed field. The sign-character argument forces the hypothetical square root to be a rational multiple of one basis element; prime-exponent parity then gives a contradiction.

The resulting degree doubling, basis extension, and automorphism extensions are valid. Linear independence of the $r_i$ follows from the asserted basis.

4.3. Distinct real conjugates

Verified.

Every signed denominator is nonzero by linear independence. Equality between two images is correctly reduced to equality of their sign vectors up to simultaneous reversal. Therefore there are exactly $2^{n-1}$ distinct images.

All are real and nonzero. Applying the field automorphisms to any nonzero integer polynomial vanishing at $x_1$ correctly shows that every image is also a root. The argument applies to every defining polynomial, not just the minimal polynomial.

4.4. Sparse and dense representations

Verified.

The induction using differentiation and Rolle’s theorem correctly bounds the number of distinct positive roots of an $h$-term polynomial by $h-1$. Applying it to $P(-X)$ gives the corresponding negative-root bound.

Consequently,
$$ h\geq 2^{n-2}+1. $$
Both explicit sparse and dense coefficient lists therefore require exponentially many entries. An isolating interval cannot eliminate that polynomial requirement.

Uniqueness prevents selecting another equilibrium with shorter coordinates. The lower bound $\Omega(2^n)$ against $L=O(n^3)$ rules out polynomial-time production in the stated output representation.

Minor encoding clarification. USER_TASK names integer polynomials and isolating intervals without expressly specifying their serialization. The prover explicitly adopts the conventional coefficient-list representation, so its conclusion is valid under that convention. The report should retain this qualification rather than describe coefficient lists as expressly stipulated by the task.

5. Square-root-sum reduction

Verified for the formally defined non-strict comparison problem.

The cited source uses the stated integer-threshold square-root-sum formulation. [Etessami and Yannakakis](https://homepages.inf.ed.ac.uk/kousha/nash_focs07_full_j_spec_issue_sub.pdf)

The scaling, integer square roots, reference index, and positive rational weights satisfy Section 3’s hypotheses, including when some source integers are perfect squares. Their construction and bit lengths are polynomial.

The weighted mean and designated coordinate are correctly computed. Positivity of the denominators gives
$$ b^*_{0,+,1}\geq h \quad\Longleftrightarrow\quad S\leq B, $$
including equality.

Minor wording issue. The introduction says “exceeds,” whereas the defined and proved comparison uses $\geq$. Replace the introductory wording with “is at least.” Equality cases prevent treating the two predicates as interchangeable.

The prover correctly limits the consequence: this decision reduction does not establish $\mathrm{NP}$-hardness of exact equilibrium search.

6. Polynomial-size existential description

Verified in the stated comparison setting $m\geq 2$.

Section 2 supplies budget exhaustion and the multiplier conditions for every equilibrium. Conversely, positivity of $D_t^2$ permits division and recovers the sufficient certificate.

The maximum degree is correctly bounded by $4$, including complementarity. Computing the effective weights, clearing rational denominators, and expanding the squared sums preserve polynomial description length.

Adding the threshold inequality gives the asserted existential real formula. This compact system does not supply the requested explicit univariate coordinate output.

7. Scope and actionable feedback

The discussion of the supplied paper is consistent with its convex-programming argument: that argument does not provide the explicit algebraic-coordinate output guarantee audited here. [Christia et al., Section 3](https://jpdickerson.com/pubs/christia21scalable.pdf)

Major incompleteness relative to USER_TASK. The output rules out polynomial-time explicit output, but supplies no $\mathrm{NP}$-hardness proof for the search task. This is an acknowledged limitation, not a false inference. Output length alone does not complete the requested classification.

The minimum remaining requirements are:

• State the coefficient-list interpretation consistently as an encoding convention.
• Align the introductory comparison wording with $\geq$.
• To complete the original assignment, specify a search-reduction notion and establish the claimed hardness under it. The current coordinate-comparison reduction does not meet that requirement.

The existing results constitute substantial verified progress and are worth retaining.

⟨structured verdict parsed — rendered above⟩