Answer: —
Theorem 6.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a polynomial time algorithm that, given a median opinion game G = (𝐺, 𝒔, 𝜶, 𝜷,𝜸) and an initial profile 𝒛, finds the minimal integer value 𝛿∈Z≥0 such that the global median of 𝒛 is stabilized when all the median weights 𝛾𝑖 are increased by 𝛿.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(\tau\) types with rational masses \(\mu_a\ge0\), \(\sum_a\mu_a=1\), intrinsic opinions \(s_a\), initial public opinions \(z_a^0\), rational weights, and block influences \(K_{ab}\), define \(M_\mu(z)=\min\{x:\sum_{a:z_a\le x}\mu_a\ge\tfrac12\}\). Each positive-mass type \(a\) asynchronously replaces its common public opinion by a best response minimizing \(\alpha_a|s_a-y|+\sum_bK_{ab}|z_b-y|+\gamma_a|M_\mu(y,z_{-a})-y|\). Find the minimum integer \(\delta^\star\ge0\) such that, after replacing every \(\gamma_a\) by \(\gamma_a+\delta^\star\), all equilibria reachable from \(z^0\) have the same global median \(M_\mu\).
A society is given by its support: \(\tau\ge1\) types with positive binary-rational masses \(\mu_a\), where \(\sum_a\mu_a=1\); \(\tau\) is the support size, not the number of possible types.
Input also includes \(s_a,z_a^0\in\mathbb Q\) and nonnegative binary-rational coefficients \(\alpha_a,\gamma_a,K_{ab}\), with \(K_{aa}=0\). Influences may be directed; \(K_{ab}\) is the total coefficient of type \(b\)'s opinion, with no additional mass factor.
Each type has one common public opinion \(z_a\in\mathbb R\). Define the lower mass median by \(M_\mu(z)=\min\{x\in\mathbb R:\sum_{a:z_a\le x}\mu_a\ge\tfrac12\}\).
For \(\delta\in\mathbb Z_{\ge0}\), let \(C_a^\delta(y;z_{-a})=\alpha_a|s_a-y|+\sum_{b\ne a}K_{ab}|z_b-y|+(\gamma_a+\delta)|M_\mu(y,z_{-a})-y|\), where \((y,z_{-a})\) replaces the entire mass of type \(a\)'s opinion by \(y\).
A legal asynchronous move selects one type and any \(y\in\arg\min_{u\in\mathbb R}C_a^\delta(u;z_{-a})\), provided \(C_a^\delta(y;z_{-a})<C_a^\delta(z_a;z_{-a})\); indifferent moves are excluded, and no further tie-breaking is imposed.
An equilibrium has \(z_a\in\arg\min_{y\in\mathbb R}C_a^\delta(y;z_{-a})\) for every type. It is reachable if obtained from \(z^0\) by finitely many legal moves, including zero moves.
Let \(\delta^\star\) be the least nonnegative integer for which the reachable equilibria are nonempty and all have the same \(M_\mu\); output \(\infty\) if no such integer exists. Let \(m=|\{s_a,z_a^0:a\in[\tau]\}|\), and let \(L\) be the total binary input length.
Can \(\delta^\star\) be computed in time polynomial in \(m,\tau,L\), or is computing it NP-hard?
For finite individual-agent societies with nonnegative integer coefficients, the minimum uniform integer increase is computable in polynomial time ([discrete algorithm](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p271.pdf)).
Extremal equilibria reachable by improvement dynamics are also computable in polynomial time ([extended results](https://research.chalmers.se/publication/551682/file/551682_Fulltext.pdf)); no result settling the specified mass-based problem was located.
The general polynomial-time versus NP-hardness question remains unresolved. I establish three additional results for the exact move rules in the question:
The third result shows why the second does not, by itself, justify binary search for $\delta^\star$.
Fix a type $a$, its opponents’ opinions, and write $w=\mu_a$. Define
$$
R_a(x)=\sum_{\substack{b\ne a\\z_b\le x}}\mu_b.
$$
Set
$$
\ell_a=
\begin{cases}
\min\{z_b:b\ne a,\ R_a(z_b)\ge\tfrac12-w\},&w<\tfrac12,\\
-\infty,&w\ge\tfrac12,
\end{cases}
$$
and
$$
u_a=
\begin{cases}
\min\{z_b:b\ne a,\ R_a(z_b)\ge\tfrac12\},&w\le\tfrac12,\\
+\infty,&w>\tfrac12.
\end{cases}
$$
Whenever an endpoint is required to be finite, it exists because the residual total mass is $1-w$. The thresholds also give $\ell_a\le u_a$. Write $J_a=[\ell_a,u_a]$, allowing infinite endpoints.
Lemma 1. For every $y\in\mathbb R$,
$$
M_\mu(y,z_{-a})=\operatorname{proj}_{J_a}(y),
$$
and therefore
$$
|M_\mu(y,z_{-a})-y|=\operatorname{dist}(y,J_a).
$$
Proof. If $y<\ell_a$, the endpoint $\ell_a$ is finite. Below $\ell_a$, residual cumulative mass is less than $\tfrac12-w$, so even after adding type $a$ the cumulative mass is less than $\tfrac12$. At $\ell_a$, adding $w$ reaches the threshold. Thus the median is $\ell_a$.
If $\ell_a\le y\le u_a$, residual mass strictly below $y$ is less than $\tfrac12$. This follows from the definition of $u_a$ when it is finite; otherwise the entire residual mass is less than $\tfrac12$. Residual mass at or below $y$, together with $w$, reaches $\tfrac12$, by the definition of $\ell_a$ or by $w\ge\tfrac12$. Hence the lower median is $y$.
Finally, if $y>u_a$, the endpoint $u_a$ is finite. Residual mass first reaches $\tfrac12$ at $u_a$, before encountering type $a$. The median is therefore $u_a$. $\square$
Consequently,
$$
C_a^\delta(y;z_{-a})
=
\alpha_a|s_a-y|
+\sum_{b\ne a}K_{ab}|z_b-y|
+(\gamma_a+\delta)\operatorname{dist}(y,J_a).
$$
This is a continuous convex piecewise linear function. Its finite breakpoints are intrinsic or opponent opinions. Sorting these points and scanning the exact rational slopes computes its minimizer interval in polynomial time.
We will also use the consequence
$$
M_\mu(z)\in J_a(z_{-a})
$$
for every type $a$: the projection formula identifies the current median as a point of that interval.
Assume throughout this section that
$$
\alpha_a=0,\qquad K_{ab}=0
$$
for every $a,b$. Intrinsic opinions then have no effect.
For a fixed $\delta$, call a type active if $\gamma_a+\delta>0$, and let
$$
S_\delta=\{a:\gamma_a+\delta>0\}.
$$
An inactive type has identically zero cost and cannot make a legal move. An active type has best-response set $J_a$. Its current opinion is a best response precisely when it equals the current median.
Let
$$
q=M_\mu(z^0),\qquad
B=\sum_{a:z_a^0<q}\mu_a,\qquad
H=\sum_{a:z_a^0>q}\mu_a.
$$
Theorem 2. In the pure median case, all reachable equilibria at a fixed $\delta$ have the same median if and only if both of the following conditions hold:
$$ \mu_a+H\le\tfrac12. $$
$$ \mu_a+B<\tfrac12. $$
When these conditions hold, the unique reachable equilibrium median is $q$.
First consider any profile $z$ with median $r$. If an active type has $z_a\ne r$, it can legally move to $r$.
Indeed, $r\in J_a(z_{-a})$, so the new opinion has zero cost. The old cost is
$$
(\gamma_a+\delta)|r-z_a|>0.
$$
By Lemma 1, replacing this opinion by $r$ preserves the median $r$.
Repeat for every active type not already at $r$. After at most $\tau$ moves, all active types have opinion $r$, while inactive types retain their opinions. The resulting profile is an equilibrium with median $r$.
Thus every median occurring at a reachable profile also occurs at a reachable equilibrium. In particular, an equilibrium with median $q$ is always reachable from $z^0$.
At any profile with median $q$, write $B_z$ and $H_z$ for the masses strictly below and strictly above $q$.
Suppose $z_a<q$. Lemma 1 gives $\ell_a=q$. Also $\mu_a<\tfrac12$, since otherwise the median could not lie strictly above $z_a$. Residual mass strictly below $q$ is less than $\tfrac12$, while residual mass at or below $q$ is
$$
1-H_z-\mu_a.
$$
Hence $u_a=q$ precisely when this last quantity is at least $\tfrac12$. Therefore
$$
z_a<q
\quad\Longrightarrow\quad
J_a=\{q\}
\ \Longleftrightarrow\
H_z+\mu_a\le\tfrac12.
$$
Now suppose $z_a>q$. Lemma 1 gives $u_a=q$. If $\mu_a\ge\tfrac12$, then $\ell_a=-\infty$, so the interval is not a singleton, and $B_z+\mu_a<\tfrac12$ is impossible.
If $\mu_a<\tfrac12$, residual mass strictly below $q$ is $B_z$. Residual mass at or below $q$ is at least $\tfrac12$. Thus the residual quantile at threshold $\tfrac12-\mu_a$ is exactly $q$ precisely when
$$
B_z<\tfrac12-\mu_a.
$$
Consequently,
$$
z_a>q
\quad\Longrightarrow\quad
J_a=\{q\}
\ \Longleftrightarrow\
B_z+\mu_a<\tfrac12.
$$
The different strictness of the two inequalities comes from the lower median convention.
Suppose a stated condition fails for an active type initially away from $q$. The preceding characterization gives
$$
J_a(z_{-a}^0)\ne\{q\}.
$$
Since this interval contains $q$, choose $y\in J_a$ with $y\ne q$. Moving type $a$ to $y$ is strictly improving: its old cost is positive and its new cost is zero. Lemma 1 says the new median is $y$.
The completion argument produces a reachable equilibrium with median $y$. It also produces one with median $q$. Thus uniqueness fails.
Suppose both conditions hold. We prove inductively that every legal move replaces an opinion by $q$ and preserves the median.
Initially, every active type away from $q$ has best-response set $\{q\}$. Active types already at $q$ have zero cost and cannot move; inactive types cannot move either.
After moves to $q$, the masses strictly below and above $q$ can only decrease. Every type still away from $q$ retains its initial opinion and side of $q$. Therefore the inequalities ensuring that its best-response set is $\{q\}$ remain valid:
$$
H_z+\mu_a\le H+\mu_a\le\tfrac12
$$
for a type below $q$, and
$$
B_z+\mu_a\le B+\mu_a<\tfrac12
$$
for a type above $q$.
The next legal move must therefore also be to $q$, preserving the median. Every reachable profile, and hence every reachable equilibrium, has median $q$. $\square$
At $\delta=0$, the active types are those with $\gamma_a>0$. For every integer $\delta\ge1$, all types are active.
If the criterion holds at $\delta=0$, then $\delta^\star=0$. If it fails there, an initially active type witnesses its failure. That same type remains active for every larger $\delta$, so uniqueness fails forever. Thus
$$
\boxed{
\delta^\star=
\begin{cases}
0,&\text{if the criterion of Theorem 2 holds for }S_0,\\
\infty,&\text{otherwise}.
\end{cases}}
$$
Computing the weighted median, $B,H$, and the inequalities takes polynomial time in $\tau,L$.
Take four types with
$$
\mu_a=\tfrac14,\qquad
\alpha_a=0,\qquad
K_{ab}=0,\qquad
\gamma_a=1,
$$
and initial opinions
$$
z^0=(0,1,2,3).
$$
For every $\delta\ge0$ and every $r\in(1,2)$, the following sequence is legal:
| Moving type | Move | Best-response interval before the move |
|---|---|---|
| $1$ | $0\longrightarrow r$ | $[1,2]$ |
| $4$ | $3\longrightarrow r$ | $[1,r]$ |
| $3$ | $2\longrightarrow r$ | $[1,r]$ |
| $2$ | $1\longrightarrow r$ | $\{r\}$ |
These intervals follow directly from the residual thresholds $\tfrac14$ and $\tfrac12$. In each row, the old opinion lies outside the interval and the new opinion belongs to it.
The terminal profile is $(r,r,r,r)$, an equilibrium with median $r$. Thus every $\delta$ admits uncountably many reachable equilibrium medians, and
$$
\delta^\star=\infty.
$$
This phenomenon requires neither a type of mass at least $\tfrac12$ nor zero median coefficients.
Fix $\delta$, and define
$$
I=\{s_a,z_a^0:a\in[\tau]\},\qquad
A=\min I,\qquad B=\max I.
$$
The hypothesis in this section is:
For every type $a$ and every opponents’ profile in $[A,B]^{\tau-1}$, the global best-response set consists of exactly one point.
Write that point as $f_a(z)$.
Theorem 3. Under this hypothesis, the componentwise largest and smallest reachable equilibria can be computed in time polynomial in $m,\tau,L$ and the binary length of $\delta$. Comparing their medians decides whether the reachable equilibrium median is unique.
Increasing opponents’ opinions coordinatewise weakly increases both residual quantiles $\ell_a,u_a$.
For a fixed argument $t$, the right derivative of an influence term is
$$
D^+\bigl(K_{ab}|z_b-t|\bigr)
=
K_{ab}\bigl(2\mathbf 1_{\{z_b\le t\}}-1\bigr).
$$
Increasing $z_b$ weakly decreases this derivative. The right derivative of the distance term is
$$
D^+\operatorname{dist}(t,[\ell_a,u_a])
=
-\mathbf 1_{\{t<\ell_a\}}
+\mathbf 1_{\{t\ge u_a\}},
$$
with the natural interpretation for infinite endpoints. Increasing either endpoint weakly decreases this derivative as well.
Therefore, increasing opponents’ opinions weakly decreases the entire right derivative at every $t$.
A convex piecewise linear function with a unique minimizer has negative right derivative strictly below that minimizer and positive right derivative strictly above it. Otherwise convexity would give a nontrivial interval of minimizers. The derivative comparison consequently implies
$$
z\le z'
\quad\Longrightarrow\quad
f_a(z)\le f_a(z').
$$
Thus $f$ is coordinatewise monotone.
At a profile whose opinions belong to $I$, every finite cost breakpoint belongs to $I$. A unique minimizer must be a finite breakpoint: a minimizer strictly inside an interval of linearity would force the slope there to be zero, giving multiple minimizers.
It follows inductively that every legal path from $z^0$ stays in $I^\tau$. In particular, the uniqueness hypothesis applies throughout every such path.
Starting from $z^0$, repeatedly select any type satisfying
$$
z_a<f_a(z)
$$
and replace its opinion by $f_a(z)$. Every move is legal and strictly increases one coordinate. Since coordinates stay in $I$, this phase uses at most $\tau(m-1)$ moves.
Let $u$ be its terminal profile. Then
$$
f(u)\le u.
$$
Moreover, $u$ bounds every profile reachable from $z^0$.
To prove this, initially $z^0\le u$. If a reachable profile $v$ satisfies $v\le u$, its next legal move replaces one coordinate by
$$
f_a(v)\le f_a(u)\le u_a.
$$
All other coordinates remain bounded by $u$. Induction proves the assertion.
Now, starting from $u$, repeatedly select a type satisfying
$$
z_a>f_a(z)
$$
and replace its opinion by $f_a(z)$.
The invariant $f(z)\le z$ is preserved. For the moving type, opponents are unchanged, so its new coordinate equals its response. For every other type, monotonicity weakly decreases its response while its coordinate remains unchanged.
This phase strictly decreases coordinates and also uses at most $\tau(m-1)$ moves. At termination, $z=f(z)$, so the resulting profile $E^+$ is a reachable equilibrium.
Let $e$ be any reachable equilibrium. We have $e\le u$. During the second phase, if $e\le z$, then the new coordinate satisfies
$$
f_a(z)\ge f_a(e)=e_a.
$$
Thus $e\le z$ remains invariant, and
$$
e\le E^+.
$$
Hence $E^+$ is the componentwise largest reachable equilibrium.
Reverse the two directions: first perform all available downward moves to $f_a(z)$, then all available upward moves.
At the end of the first phase, its profile $\ell$ satisfies $f(\ell)\ge\ell$ and bounds every reachable profile from below. During the second phase, $f(z)\ge z$ remains invariant. The same finite-chain argument gives a reachable equilibrium $E^-$, and comparison with any reachable equilibrium shows
$$
E^-\le e.
$$
Both constructions use polynomially many best-response calculations.
Finally, the mass median is coordinatewise monotone. Indeed, $x\le y$ implies
$$
\{a:y_a\le t\}\subseteq\{a:x_a\le t\}
$$
for every $t$, so $M_\mu(x)\le M_\mu(y)$. Therefore every reachable equilibrium $e$ satisfies
$$
M_\mu(E^-)\le M_\mu(e)\le M_\mu(E^+).
$$
Since both endpoint equilibria are reachable, uniqueness holds exactly when
$$
M_\mu(E^-)=M_\mu(E^+).
$$
This proves Theorem 3.
The uniqueness hypothesis holds for every nonnegative integer $\delta$ if
$$
\alpha_a\in\mathbb Z_{\ge0}+\tfrac12,
\qquad
\gamma_a,K_{ab}\in\mathbb Z_{\ge0}.
$$
Between consecutive breakpoints, a cost slope has the form
$$
\varepsilon_0\alpha_a
+\sum_{b\ne a}\varepsilon_bK_{ab}
+(\gamma_a+\delta)h,
$$
where $\varepsilon_0,\varepsilon_b\in\{-1,1\}$ and $h\in\{-1,0,1\}$. This slope is a half-integer and hence cannot vanish.
Also $\alpha_a>0$, so the cost tends to infinity as $|y|$ tends to infinity and attains its minimum. Multiple minimizers would, by convexity, give a nontrivial interval on which the function is constant, contradicting the absence of zero slopes. Thus every unilateral minimizer is unique, for every real opponents’ profile.
The following example satisfies the sufficient condition just proved.
Take three types with
$$
(\mu_1,\mu_2,\mu_3)
=
\left(\tfrac38,\tfrac38,\tfrac14\right),
$$
$$
(s_1,s_2,s_3)=(0,0,1),\qquad
z^0=(1,1,0),
$$
and
$$
\alpha_1=\alpha_2=\alpha_3=\tfrac12,\qquad
\gamma_1=\gamma_2=\gamma_3=0.
$$
The only nonzero influences are
$$
K_{13}=K_{23}=1.
$$
Every mass is strictly below $\tfrac12$, and every best response is unique for every integer $\delta\ge0$.
For $a=1,2$, the unilateral cost is
$$
\tfrac12|y|+|z_3-y|.
$$
Its unique minimizer is $z_3$. Indeed,
$$
\tfrac12|y|+|z_3-y|
\ge
\tfrac12|z_3|+\tfrac12|y-z_3|,
$$
with strict inequality over the minimum whenever $y\ne z_3$.
Type $3$ has cost $\tfrac12|1-y|$, whose unique minimizer is $1$. Thus the only equilibrium is
$$
(1,1,1).
$$
It is reachable by moving type $3$ first. Hence the reachable equilibrium median is unique at $\delta=0$.
First, $(1,1,1)$ remains reachable. Initially, type $3$ has $J_3=\{1\}$, so its cost is
$$
\left(\delta+\tfrac12\right)|1-y|.
$$
Its move from $0$ to $1$ is strictly improving and produces the equilibrium $(1,1,1)$.
There is also a legal path to $(0,0,0)$:
$$
\tfrac32|y|+\delta\operatorname{dist}(y,[0,1]),
$$
uniquely minimized at $0$. It legally moves from $1$ to $0$.
$$
\left(\tfrac32+\delta\right)|y|,
$$
so it legally moves from $1$ to $0$.
At $(0,0,0)$, types $1,2$ have unique best response $0$. Type $3$ has cost
$$
\tfrac12|1-y|+\delta|y|.
$$
For $\delta\ge1$, its unique minimizer is $0$, because
$$
\tfrac12|1-y|+\delta|y|
\ge
\tfrac12+\left(\delta-\tfrac12\right)|y|.
$$
Thus $(0,0,0)$ is an equilibrium.
The two reachable equilibrium medians are $0$ and $1$. Therefore, for this instance,
$$
\{\delta\in\mathbb Z_{\ge0}:
\text{the reachable equilibrium median is unique}\}
=
\{0\}.
$$
In particular, uniqueness is not an upward-closed property of $\delta$, even under globally unique best responses and with all masses below $\tfrac12$.
Theorem 2 completely solves a nontrivial subclass of the stated problem. Theorem 3 supplies a polynomial fixed-parameter-value test under unique responses. The example in Section 4 establishes that even this hypothesis does not make binary search on $\delta$ valid.
These results do not settle the unrestricted complexity classification. A complete resolution still requires either a polynomial algorithm covering tied responses and the integer parameter search, or a hardness reduction for the exact strict-improvement reachability rules.
⟨structured verdict parsed — rendered above⟩
The output establishes correct partial results but does not resolve the assigned complexity question. I found no false mathematical statement or substantive internal gap in the three claimed results. The outstanding major issue is scope: neither a polynomial-time algorithm for unrestricted $\delta^\star$ nor a hardness reduction is provided.
The prover explicitly acknowledges this limitation, so the output does not falsely claim a complete solution.
Lemma 1 is correct, including the boundary cases.
The finite endpoints exist as claimed:
The inequality $\ell_a\le u_a$ follows from the ordering of the residual thresholds whenever both endpoints are finite.
The three cases in the projection proof are valid:
Thus
$$
M_\mu(y,z_{-a})=\operatorname{proj}_{J_a}(y)
$$
holds under the specified lower-median convention.
The resulting cost expression is continuous, convex, and piecewise linear. Its finite breakpoints are among intrinsic and opponent opinions. The stated slope-scanning computation is valid, with unbounded minimizer intervals represented by infinite endpoints.
No issue found.
For an active type, the cost is a positive multiple of $\operatorname{dist}(y,J_a)$, so its best-response set is exactly $J_a$. By Lemma 1, its current opinion lies in this interval exactly when it equals the current median.
For an inactive type, the cost is identically zero, so strict improvement is impossible.
The completion argument is valid. Moving an active type from an opinion different from the current median $r$ to $r$:
After at most $\tau$ such moves, every active type is at $r$, and every inactive type remains a best responder. Hence an equilibrium with that median is reached.
This establishes the required nonemptiness of reachable equilibria throughout this subclass.
The asymmetric inequalities are correct and essential.
For a type below $q$, its mass must satisfy $\mu_a<\tfrac12$. Removing its mass makes the lower residual threshold first occur at $q$, so $\ell_a=q$. The upper endpoint equals $q$ precisely when
$$
1-H_z-\mu_a\ge\tfrac12,
$$
equivalently,
$$
H_z+\mu_a\le\tfrac12.
$$
For a type above $q$, the upper endpoint is $q$. When $\mu_a<\tfrac12$, the lower residual threshold first occurs at $q$ precisely when
$$
B_z<\tfrac12-\mu_a.
$$
Equality would place that threshold strictly below $q$, explaining the strict inequality.
When $\mu_a\ge\tfrac12$, the lower endpoint is $-\infty$, so the interval cannot be a singleton; the proposed strict inequality is also impossible.
If a condition fails, the relevant active type initially differs from $q$ and has a nonsingleton best-response interval containing $q$. Choosing another point $y$ in that interval is a legal strict improvement, and Lemma 1 makes the new median exactly $y$.
The completion argument then gives reachable equilibria with medians $y$ and $q$. This correctly disproves uniqueness.
The induction is valid. Under the stated conditions, every initially movable type has the singleton best-response set $\{q\}$. Moving such types to $q$ only decreases the masses strictly below and above $q$, so the relevant inequalities remain true for every type still away from $q$.
Types already at $q$ and inactive types cannot move. Therefore all reachable profiles retain median $q$, and reachable equilibria exist by completion.
The conclusion
$$
\delta^\star\in\{0,\infty\}
$$
is correct in this subclass.
If the criterion holds at $\delta=0$, the least successful integer is already zero. If it fails, an initially active type witnesses failure and remains active for every larger integer, so the same initial-profile obstruction persists.
Computing the weighted median, the two side masses, and the inequalities requires polynomially many exact rational operations with polynomial bit complexity.
The argument also covers $\tau=1$ and the case where all types are initially inactive.
No issue found.
All four listed best-response intervals are correct.
For equal masses $\tfrac14$, the residual thresholds are $\tfrac14$ and $\tfrac12$. Along the displayed path, these give, successively,
$$
[1,2],\qquad [1,r],\qquad [1,r],\qquad \{r\}.
$$
For $r\in(1,2)$, every old opinion lies outside its interval, and every selected new opinion belongs to it. Since $\gamma_a+\delta=1+\delta>0$, every move strictly improves cost.
The consensus profile is an equilibrium. Distinct choices of $r$ produce distinct reachable equilibrium medians for every nonnegative integer $\delta$.
The claimed uncountable family and $\delta^\star=\infty$ are established.
The right-derivative formulas are correct, including at breakpoints.
Increasing an opponent’s opinion decreases or preserves the right derivative of its influence term. Increasing either residual quantile likewise decreases or preserves the right derivative of the distance term. The intrinsic term is unchanged.
For a convex piecewise linear function with a unique minimizer, the right derivative is strictly negative below that minimizer and strictly positive above it. Otherwise a zero-slope interval would contradict uniqueness.
Consequently, the derivative comparison yields the stated monotonicity of $f_a$.
A unique minimizer must occur at a finite breakpoint: any minimizer within an interval of linearity would produce multiple minimizers.
All finite breakpoints belong to $I$ whenever opponents’ opinions belong to $I$. Thus every legal path remains in $I^\tau$, and the hypothesis on opponents’ profiles in $[A,B]^{\tau-1}$ applies throughout.
This argument correctly addresses unrestricted real-valued move choices: under the uniqueness hypothesis, those choices cannot introduce new opinions.
The first phase consists entirely of legal strict improvements, since a coordinate different from its unique best response has strictly greater cost.
Each coordinate strictly increases through a set of $m$ values, giving at most $\tau(m-1)$ moves. At termination,
$$
f(u)\le u.
$$
The induction bounding every reachable profile by $u$ is valid: monotonicity and $f(u)\le u$ ensure that every subsequent response remains below the corresponding coordinate of $u$.
In the downward phase, the invariant $f(z)\le z$ is preserved. The moving type’s response does not depend on its own coordinate, and every other response weakly decreases. Termination therefore gives a reachable fixed point.
The comparison with an arbitrary reachable equilibrium correctly proves that this fixed point is the componentwise largest reachable equilibrium.
The reversed construction uses the same argument with all order inequalities reversed. This symmetry is sufficient here; no additional mathematical hypothesis is needed.
Each construction uses at most $2\tau(m-1)$ moves. Finding an eligible type and evaluating responses takes polynomial time. Opinions remain among input values, and the rational slope calculations have polynomial bit complexity in the input length and the binary length of $\delta$.
Coordinatewise monotonicity of the weighted median is correctly proved by the cumulative-mass inclusion. Since both extremal equilibria are reachable, their medians agree exactly when every reachable equilibrium has that median.
Theorem 3 is established as a conditional fixed-$\delta$ result. It does not establish this algorithm for general instances with tied best responses.
The half-integer argument is correct.
With
$$
\alpha_a\in\mathbb Z_{\ge0}+\tfrac12,
\qquad
\gamma_a,K_{ab}\in\mathbb Z_{\ge0},
$$
and integer $\delta$, every slope between breakpoints is a nonzero half-integer.
The positive intrinsic coefficient makes the cost coercive, so a minimizer exists. Convexity would turn multiple minimizers into a constant interval, contradicting the absence of zero slopes.
The condition therefore guarantees a unique global best response for every real opponents’ profile and every permitted $\delta$.
No issue found.
The three-type example meets all input restrictions, and the sufficient uniqueness condition applies.
At $\delta=0$, the triangle-inequality bound correctly establishes that types $1$ and $2$ uniquely respond to $z_3$, while type $3$ uniquely responds with $1$. Hence the unique equilibrium is $(1,1,1)$, reached by moving type $3$ first.
For every integer $\delta\ge1$:
$$
\tfrac12|1-y|+\delta|y|
\ge
\tfrac12+\left(\delta-\tfrac12\right)|y|
$$
makes zero the unique best response of type $3$.
Thus both medians zero and one are reachable for every positive integer $\delta$. The successful parameter set is exactly $\{0\}$.
The example correctly refutes upward closure of median uniqueness. It invalidates a binary-search justification based on that property, but does not rule out other polynomial parameter-search methods.
Major issue: the unrestricted assignment remains unresolved.
The pure-median criterion solves a subclass. The extremal algorithm requires unique responses and treats a supplied parameter value. The counterexample identifies an obstruction to one proposed search principle. None determines the complexity of computing unrestricted $\delta^\star$.
No expositional clarification can close this gap. To complete the assignment, the prover must supply either:
These are missing substantive results, rather than repairs to the proofs already presented.
⟨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.