Answer: Polynomial-time solvable; an exact equilibrium always exists.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateWith general utilities and the LIKE mechanism, problem PURE NASH EQUILIBRIUM is P.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of types \(T\), blocs \(G\), and item categories \(J\), let each type \(t\) belong to a bloc \(g(t)\), have rational mass \(\mu_t\), and have utility \(u_{tj}\) for category \(j\), with \(\sum_t\mu_t=1\). Category \(j\) has rational per-branch supply \(q_j\), represented by \(Nq_j\) indivisible copies for a population of \(N\) branches. Choose positive-bid masses \(x_{tj}\in[0,\mu_t]\), setting \(x_{tj}=0\) when \(u_{tj}=0\). With \(P_j=\sum_t x_{tj}\), bloc \(g\)’s normalized expected utility is \(U_g(x)=\sum_{j:P_j>0}q_j\frac{\sum_{t:g(t)=g}u_{tj}x_{tj}}{P_j}\), with a zero term when \(P_j=0\). Find a feasible profile \(x\) such that \(U_g(x)\ge U_g(x'_g,x_{-g})\) for every bloc \(g\) and every feasible unilateral change \(x'_g\) to its bid masses.
A society is given by its support: a 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. A surjection \(g:T\to G\) partitions types into nonempty blocs. There are \(m=|J|\ge1\) item categories, with positive rational supplies \(q_j\) per unit population and nonnegative rational utilities \(u_{tj}\). Let \(L\) be the total input bit length.
Each bloc simultaneously chooses real positive-bid masses \(x_{tj}\in[0,\mu_t]\) for its types, with \(x_{tj}=0\) whenever \(u_{tj}=0\). These choices are independent across categories; there are no bidding costs or budgets. Fractional masses describe deterministic participation by portions of a type, not randomized bloc strategies.
LIKE allocates each category proportionally to positive-bid mass. Write \(P_j=\sum_t x_{tj}\). Bloc \(g\) maximizes its aggregate normalized expected utility \(U_g(x)=\sum_{j:P_j>0}q_j\frac{\sum_{t:g(t)=g}u_{tj}x_{tj}}{P_j}\); an unbid category contributes zero and remains unallocated.
An equilibrium is a feasible profile satisfying \(U_g(x)\ge U_g(x'_g,x_{-g})\) for every bloc \(g\) and every feasible joint change \(x'_g\) of all its types across all categories. Indifference is allowed.
Is computing an exact equilibrium, or determining that none exists, polynomial-time solvable in \(m,\tau,|G|,L\), or is it NP-hard?
For finite agents with general utilities, computing a group pure Nash equilibrium under LIKE is polynomial-time solvable; a bound of \(O(n^3m)\) is reported ([Aleksandrov–Walsh](https://www.ijcai.org/proceedings/2017/0007.pdf)). No result settling this exact continuous bloc model was located.
Every instance satisfying the stated assumptions admits an exact equilibrium. Moreover, an equilibrium can be computed in polynomial time in the binary input size, and every coordinate of the computed equilibrium satisfies \(x_{tj}\in\{0,\mu_t\}\).
Thus fractional participation is allowed but is not needed for existence or efficient computation.
For each category \(j\), define its contribution to bloc \(g\)’s payoff by
\(U_{gj}(x_{\cdot j})=q_j\frac{\sum_{t:g(t)=g}u_{tj}x_{tj}}{\sum_t x_{tj}}\)
when its denominator is positive, and by zero otherwise.
The feasible strategy set is a Cartesian product across categories, and \(U_g=\sum_j U_{gj}\). Consequently, if a profile admits no profitable unilateral deviation in any individual category, then it admits no profitable joint deviation: each summand under a joint deviation is at most its original value.
It therefore suffices to construct an equilibrium for one category. Fix that category and suppress its index. Since \(q>0\), maximizing its payoff is equivalent to maximizing the ratio without the factor \(q\).
Write
\(B_g=\sum_{t:g(t)=g}x_t,\qquad N_g=\sum_{t:g(t)=g}u_tx_t,\qquad P=\sum_t x_t.\)
When \(P>0\), define the threshold \(\theta_g=N_g/P\). The bloc’s category payoff is \(q\theta_g\).
Lemma. Suppose \(P>0\), every coordinate satisfies \(x_t\in\{0,\mu_t\}\), and, for every type with \(u_t>0\),
Then the profile is an equilibrium for this category, including against arbitrary feasible real-valued joint changes within a bloc.
Proof. Fix a bloc \(g\), and let \(y_t\in[0,\mu_t]\) be any feasible replacement for its coordinates. Let \(R=P-B_g\) be the unchanged bid mass outside the bloc. Set
\(N_g(y)=\sum_{t:g(t)=g}u_ty_t,\qquad B_g(y)=\sum_{t:g(t)=g}y_t.\)
Because \(N_g=\theta_gP\), we have the identity
\(N_g(y)-\theta_g\bigl(R+B_g(y)\bigr)=\sum_{t:g(t)=g}(u_t-\theta_g)(y_t-x_t).\)
Every summand on the right is nonpositive:
If \(R+B_g(y)>0\), division by this positive denominator gives
\(\frac{N_g(y)}{R+B_g(y)}\le\theta_g.\)
If \(R+B_g(y)=0\), the deviating payoff is zero by definition, whereas the current payoff \(q\theta_g\) is nonnegative. Thus no feasible deviation improves the bloc’s payoff. This holds for every bloc. \(\square\)
If every utility in the category is zero, feasibility forces every bid mass to be zero, and this profile is an equilibrium.
Otherwise, use the following algorithm.
Any violating type may be selected at each iteration. Each type is removed at most once, so there are at most \(\tau\) deletions.
The remaining points are to show that the denominator stays positive and that previously removed types satisfy the lemma’s inequality at termination.
Call a bloc interested if it contains a type with positive utility. For an interested bloc \(g\), let
\(M_g=\max_{t:g(t)=g}u_t>0.\)
At every feasible profile with \(P>0\),
\(N_g\le M_gB_g\le M_gP,\)
so \(\theta_g\le M_g\). Hence a participating type with utility \(M_g\) never satisfies the deletion condition \(u_t<\theta_g\).
All such types participate initially and remain throughout the algorithm. Therefore every interested bloc retains positive bid mass, and \(P\) remains positive after every deletion.
Suppose type \(t\) is removed from bloc \(h\). Write \(a=\mu_t\) and \(u=u_t\). The deletion condition is \(u<\theta_h\). Before deletion, let the total mass be \(P\); afterward it is \(P'=P-a>0\).
For the deleting bloc,
\(\theta'_h-\theta_h=\frac{N_h-ua}{P-a}-\frac{N_h}{P}=\frac{a(\theta_h-u)}{P-a}>0.\)
For any other bloc \(g\), its numerator is unchanged, so
\(\theta'_g-\theta_g=\frac{N_g}{P-a}-\frac{N_g}{P}=\frac{aN_g}{P(P-a)}\ge0.\)
Thus every bloc’s threshold is nondecreasing throughout the algorithm.
At termination, every participating type satisfies \(u_tP\ge N_{g(t)}\), equivalently \(u_t\ge\theta_{g(t)}\).
Now consider a positive-utility type \(t\) that was removed. At its deletion, it satisfied
\(u_t<\theta_{g(t)}.\)
Its bloc’s threshold can only increase afterward. Therefore, at termination, it still satisfies \(u_t<\theta_{g(t)}\).
All coordinates remain either zero or their full input mass, and the final denominator is positive. The sufficient-condition lemma therefore applies and proves that the returned profile is a category equilibrium against every feasible real-valued deviation.
Applying this algorithm independently to each category and using Section 1 gives an equilibrium of the full game. This proves existence for every valid input, including categories with no interested bloc and categories with exactly one interested bloc.
A direct implementation scans at most \(\tau\) types to find a deletion, performs at most \(\tau\) deletions per category, and maintains the numerators and total mass. This requires \(O(m\tau^2)\) arithmetic operations. The comparisons and updates can be implemented using integers of polynomial bit length, as follows.
Write the input masses as \(\mu_t=a_t/b_t\), and take
\(D=\prod_t b_t,\qquad M_t=D\mu_t.\)
Then every \(M_t\) is an integer and \(\sum_tM_t=D\).
For a fixed category, write its utilities as \(u_t=c_t/d_t\), and take
\(E=\prod_t d_t,\qquad V_t=Eu_t.\)
Every \(V_t\) is a nonnegative integer. If \(A\) denotes the currently participating types, maintain
\(S=\sum_{t\in A}M_t,\qquad W_g=\sum_{\substack{t\in A\\g(t)=g}}M_tV_t.\)
These represent the original quantities exactly:
\(P=S/D,\qquad N_g=W_g/(DE).\)
The deletion test is precisely the integer comparison
\(V_tS<W_{g(t)}.\)
Deleting type \(t\) updates
\(S\leftarrow S-M_t,\qquad W_{g(t)}\leftarrow W_{g(t)}-M_tV_t.\)
The products defining \(D\) and \(E\) have \(O(L)\) bits because the input denominators have total bit length at most \(L\). Also \(S\le D\), and
\(W_g\le D\max_tV_t.\)
The input numerators and the integers \(V_t\) have \(O(L)\) bits, so all maintained integers and comparison products have \(O(L)\) bits. Using schoolbook integer multiplication and division gives, for example, a coarse bound of \(O(m\tau^2L^2)\) bit operations, including preprocessing.
Finally, each output coordinate is either zero or its original rational mass. Thus the output itself has polynomial length and requires no algebraic-number representation.
The cited finite-agent tractability statement appears in [Aleksandrov–Walsh, Theorem 3](https://www.ijcai.org/proceedings/2017/0007.pdf). The proof above establishes existence and polynomial bit complexity directly for the specified continuous support model.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the stated continuous model. Every valid instance admits an exact equilibrium, and the proposed algorithm computes one in polynomial bit complexity. No major or minor issues were found.
The feasible strategy set is a Cartesian product across categories, and each category’s payoff depends only on participation in that category. Thus, for any joint unilateral deviation by a bloc, each category contribution is bounded above by its original contribution whenever the original profile is an equilibrium in every category. Summing these inequalities establishes the full equilibrium condition.
Removing the factor \(q_j\) during each category’s optimization is valid because the task assumes \(q_j>0\).
Fixing a bloc leaves the outside mass \(R=P-B_g\) unchanged. The displayed identity
\[
N_g(y)-\theta_g(R+B_g(y))
=\sum_{t:g(t)=g}(u_t-\theta_g)(y_t-x_t)
\]
is correct: the corresponding expression at the current profile is \(N_g-\theta_gP=0\).
Every summand has the asserted sign. At a fully participating coordinate, the threshold condition and upper bound on participation give a nonpositive product. At an excluded positive-utility coordinate, the threshold condition and nonnegativity of participation also give a nonpositive product. Zero-utility coordinates cannot change under the task’s feasibility rule.
Consequently, the argument bounds the payoff under every feasible real-valued replacement of all coordinates in the bloc, rather than merely individual-coordinate deviations.
Both denominator cases are handled correctly. For a positive deviating denominator, division preserves the inequality. For a zero deviating denominator, the payoff is zero by the task’s definition and cannot exceed the current nonnegative payoff. The lemma therefore also covers deviations withdrawing all participation when there is no outside bidder.
If every utility in a category is zero, feasibility forces the zero profile, so there are no alternative feasible strategies in that category.
Otherwise, initialization is feasible and has positive total participation because positive-utility types have strictly positive masses. Each deletion removes a currently participating type permanently. There are at most \(\tau\) deletions, irrespective of the order in which violations are selected.
For an interested bloc, nonnegative utilities and participation imply
\[
N_g\le M_gB_g\le M_gP.
\]
Hence its threshold never exceeds its maximum utility whenever \(P>0\). A maximum-utility type therefore cannot satisfy the strict deletion condition.
Such types participate initially and have positive masses. Their retention guarantees that the denominator remains positive after every deletion. This justifies all divisions used later in the proof.
A deleted type is fully participating, so the removed mass is exactly \(a=\mu_t>0\), and its numerator contribution is exactly \(ua\).
For its own bloc, the stated difference
\[
\theta'_h-\theta_h=\frac{a(\theta_h-u)}{P-a}>0
\]
follows correctly from the strict deletion condition and positivity of the remaining denominator.
For every other bloc, the numerator is unchanged and nonnegative, giving
\[
\theta'_g-\theta_g=\frac{aN_g}{P(P-a)}\ge0.
\]
This includes uninterested blocs, whose thresholds remain zero. Thus every threshold is nondecreasing.
Termination gives the required weak threshold inequality for every participating type. Each excluded positive-utility type was removed under a strict threshold violation; threshold monotonicity preserves that violation through termination.
Every coordinate remains either zero or its full mass, and the denominator remains positive. The lemma therefore applies directly. Equality cases cause no difficulty because indifference is permitted and deletion uses a strict inequality.
The proof also covers categories with exactly one interested bloc: denominator positivity does not depend on having a competing interested bloc, and the lemma explicitly handles withdrawal to a zero denominator.
The common-denominator construction gives integers \(M_t\) and \(V_t\), and normalization of the masses gives \(\sum_tM_t=D\). The representations
\[
P=S/D,\qquad N_g=W_g/(DE)
\]
are correct. Clearing positive denominators transforms the deletion condition exactly into \(V_tS<W_{g(t)}\). Both integer updates are also correct.
The bit lengths of \(D\) and each category’s \(E\) are bounded by the total input denominator length. The scaled utilities have \(O(L)\) bits. Moreover, \(S\le D\) and \(W_g\le D\max_tV_t\), so the maintained integers and comparison products have \(O(L)\) bits.
At most \(\tau+1\) scans of at most \(\tau\) types per category yield \(O(m\tau^2)\) arithmetic operations. Schoolbook arithmetic supports the stated coarse \(O(m\tau^2L^2)\) bit bound, including preprocessing. The output uses original rational masses or zero and therefore has polynomial length.
This computation uses the listed support directly; it does not expand masses into a finite population.
[Aleksandrov–Walsh, Theorem 3](https://www.ijcai.org/proceedings/2017/0007.pdf) states polynomial tractability for LIKE with general utilities, and its proof reports the cited finite-agent bound. The continuous-model argument is established independently here, so no transfer of that theorem’s hypotheses is needed.
No additional clarification, missing lemma, or repair is required. The existence proof also settles the nonexistence alternative: no valid input under the stated assumptions lacks an equilibrium.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.