Answer: Polynomial-time solvable ($\mathrm P$) for fixed $m=2$, with arbitrary explicitly listed support size $\tau$.
Proposition 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMarkets consisting of a single trade con- verge to equilibrium after O(V ) BRs. Two-agent FSMs with two trades converge to equilibrium after O(V 2) BRs. We prove the single-trade case by contradiction: suppose that the dynamic does not terminate. Then we observe that one agent always accepts her counterpart’s offer for the trade ω, while the other always rejects.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite-support rational mass distribution \(\mu\) over complete two-agent, two-trade FSM lane types, each with integer valuation tables, tie-breaking, and initial offers, let \(H_\theta\) be the random number of Algorithm 1 best-response updates until equilibrium for type \(\theta\). Given rational \(B\), decide whether \(\bar H=\sum_{\theta}\mu_\theta\mathbb{E}[H_\theta]\le B\).
A society is given by its support: a list of \(\tau\geq1\) types with positive binary-rational masses \(\mu_\theta\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; types describe independent market lanes, with no interaction between lanes.
Each type specifies two agents and exactly \(m=2\) distinct bilateral trades, each with a designated buyer and the other agent as seller; opposite trade directions are allowed. It includes each agent's complete finite integer valuation table \(v_i:2^\Omega\to\mathbb Z\), with \(v_i(\varnothing)=0\), a fixed strict priority order on bundles for breaking utility ties, and arbitrary integer initial offers \(\sigma^i_\omega\). Values and offers may be negative.
Write \(\Omega_{i,b}\) and \(\Omega_{i,s}\) for agent \(i\)'s buying and selling trades, and \(\chi^i_\omega=1\) for buying and \(\chi^i_\omega=-1\) for selling. At integer prices \(p\), let \(D_i(p)\) be the priority-selected maximizer of \(v_i(S)-\sum_{\omega\in S}\chi^i_\omega p_\omega\).
Promise that these selected demands are fully substitutable: for all \(p,p'\in\mathbb Z^\Omega\), writing \(D=D_i(p)\), \(D'=D_i(p')\), if selling prices are unchanged and buying prices weakly decrease, then \(D\cap\Omega_{i,s}\subseteq D'\cap\Omega_{i,s}\) and \(\{\omega\in D'\cap\Omega_{i,b}:p_\omega=p'_\omega\}\subseteq D\); if buying prices are unchanged and selling prices weakly increase, then \(D\cap\Omega_{i,b}\subseteq D'\cap\Omega_{i,b}\) and \(\{\omega\in D'\cap\Omega_{i,s}:p_\omega=p'_\omega\}\subseteq D\).
In each lane initialize the unsatisfied set to \(U=\{1,2\}\). While \(U\neq\varnothing\), choose \(i\) uniformly from \(U\), set \(p_\omega=\sigma^{-i}_\omega\), and simultaneously replace each own offer by \(p_\omega\) if \(\omega\in D_i(p)\), and by \(p_\omega-\chi^i_\omega\) otherwise. Remove \(i\) from \(U\), and add the other agent if any offer changed.
Equilibrium means termination at \(U=\varnothing\). Let \(H_\theta\) count every update, including updates that change no offer, from initialization through termination; its expectation is over the random agent selections. The input also contains \(B\in\mathbb Q\); let \(L\) be the total binary input length and \(V\geq1\) the maximum absolute valuation or initial offer.
Is deciding whether \(\sum_\theta\mu_\theta\mathbb E[H_\theta]\leq B\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard, with running times measured in \(m=2\), \(\tau\), and \(L\)?
For discrete markets, convergence takes \(O(V)\) updates with one trade and \(O(V^2)\) updates for two-agent fully substitutable markets with two trades. [Verified convergence result](https://arxiv.org/html/2412.13972v2)
These bounds depend on numerical magnitudes and do not settle the binary-input mass-average decision problem.
For fixed $m=2$, both conditional stopping counts of every lane can be computed exactly in polynomial time in the binary input length. Consequently, so can the mass-weighted expectation and its comparison with $B$.
The essential point is that long trajectories can be counted in blocks. Full substitutability makes the response maps preserve coordinatewise order, and the four-bundle utility tables give only constantly many boundaries where a response can change.
Fix a lane, and identify its two trades with coordinates $1,2$. For agent $i$, define the response map
$$
R_i(p)_\omega
=
p_\omega-\chi^i_\omega
\left(1-\mathbf 1_{\{\omega\in D_i(p)\}}\right).
$$
All orders between vectors below are coordinatewise.
The first selected agent is uniformly distributed over the two agents. After its update, the unsatisfied set contains exactly the other agent: that agent was already unsatisfied, irrespective of whether any offer changed. Subsequently, every changing update forces selection of the other agent, and every unchanged update terminates the process.
Thus, conditional on the first selected agent, the trajectory is deterministic. Write its stopping count as $H^{(i)}$. Then
$$
\mathbb E[H]=\frac{H^{(1)}+H^{(2)}}2.
$$
The two conditional counts need not be distinct.
Fix the first agent $i$, and let $j$ denote the other agent. Put
$$
y^0=\sigma^j,\qquad x^0=R_i(y^0),\qquad T=R_i\circ R_j.
$$
We will count iterations of $T$ starting from $x^0$. One iteration represents an update by $j$ followed by an update by $i$.
Before such a pair, let $x$ be agent $i$’s offers and $y_{\mathrm{old}}$ agent $j$’s offers. The invariant
$$
x=R_i(y_{\mathrm{old}})
$$
holds initially and after every completed pair. Agent $j$ next produces
$$
y=R_j(x).
$$
If $y=y_{\mathrm{old}}$, the process terminates at this update, and necessarily
$$
T(x)=R_i(y)=x.
$$
If $y\neq y_{\mathrm{old}}$, agent $i$ updates next and terminates precisely when $T(x)=x$.
Consequently, every iteration with $T(x)\neq x$ corresponds to two changing updates. Let
$$
x^k=T^k(x^0),
$$
and let $k$ be the first index for which $T(x^k)=x^k$. Then
$$
H^{(i)}
=
\begin{cases}
2k+2,&R_j(x^k)=y_{\mathrm{old}},\\
2k+3,&R_j(x^k)\neq y_{\mathrm{old}},
\end{cases}
$$
where
$$
y_{\mathrm{old}}
=
\begin{cases}
y^0,&k=0,\\
R_j(x^{k-1}),&k>0.
\end{cases}
$$
It therefore suffices to compute the first fixed-point index $k$, the fixed point, and its immediate predecessor when $k>0$.
We use the convergence theorem supplied in the question: two-agent fully substitutable markets with two trades terminate under this unit-step dynamic. Its hypotheses apply here: valuations and offers are integers, the initial offers are arbitrary, the fixed priorities give consistent unique demands, and the selected demands satisfy exactly the stated full-substitutability conditions. Both trade-direction patterns are permitted. Hence both conditional trajectories terminate. [Proposition 5 and Appendix A.1](https://arxiv.org/html/2412.13972v2)
For every agent $i$,
$$
p\leq p'\quad\Longrightarrow\quad R_i(p)\leq R_i(p').
$$
Proof. It suffices to increase one price coordinate by one and check every output coordinate.
For the output coordinate whose price increases, the claim follows directly from the unit response rule. If it is a buying coordinate, its possible responses at price $p_\omega$ lie in
$$
\{p_\omega-1,p_\omega\},
$$
whereas at price $p_\omega+1$ they lie in
$$
\{p_\omega,p_\omega+1\}.
$$
For a selling coordinate the corresponding sets are
$$
\{p_\omega,p_\omega+1\},
\qquad
\{p_\omega+1,p_\omega+2\}.
$$
Thus this output cannot decrease.
Consider the other coordinate, whose own price remains unchanged.
For a buying coordinate,
$$
R_i(p)_\omega
=
p_\omega-1+\mathbf 1_{\{\omega\in D_i(p)\}},
$$
so expanding demand weakly increases the response. For a selling coordinate,
$$
R_i(p)_\omega
=
p_\omega+1-\mathbf 1_{\{\omega\in D_i(p)\}},
$$
so contracting demand weakly increases the response.
Every output coordinate therefore weakly increases. Repeating unit increases proves the claim. $\square$
In particular, $T$ preserves coordinatewise order.
For every $x\in\mathbb Z^2$,
$$
T(x)-x\in\{-1,0,1\}^2.
$$
Proof. Write
$$
r_i(p)_\omega=1-\mathbf 1_{\{\omega\in D_i(p)\}}.
$$
Because $\chi^j_\omega=-\chi^i_\omega$,
$$
R_j(x)_\omega=x_\omega+\chi^i_\omega r_j(x)_\omega.
$$
Thus
$$
T(x)_\omega-x_\omega
=
\chi^i_\omega
\left(
r_j(x)_\omega-r_i(R_j(x))_\omega
\right),
$$
which belongs to $\{-1,0,1\}$. $\square$
Before reaching its first fixed point, the orbit of $T$ consists of:
Proof. If $x^r\leq x^{r+1}$, order preservation implies
$$
x^{r+1}=T(x^r)\leq T(x^{r+1})=x^{r+2}.
$$
Hence a nonnegative displacement forces all later displacements to be nonnegative. The analogous statement holds for nonpositive displacements.
By Lemma 2, the only displacements incomparable with zero are $(1,-1)$ and $(-1,1)$. If two successive displacements were these two opposite vectors, then
$$
x^{r+2}=x^r,
$$
giving a nontrivial two-cycle of $T$. Section 1 shows that such a cycle would prevent the original process from terminating, contrary to convergence.
Therefore, until a comparable displacement occurs, every displacement is the same mixed vector. Thereafter the orbit is monotone. $\square$
Set
$$
M=2V+1.
$$
Every actual offer remains in $[-M,M]$.
Indeed, the valuation difference between bundles differing by one trade has absolute value at most $2V$. Consequently, a buyer strictly demands a trade priced below $-2V$, and a seller strictly demands a trade priced above $2V$, regardless of the other trade.
Initially all offers lie in $[-V,V]$. A buyer’s response could leave $[-M,M]$ only by rejecting at price $-M$ and subtracting one, which the preceding strict-demand observation excludes. A seller could leave it only by rejecting at price $M$ and adding one, also excluded. Induction proves the bound.
This also bounds the number of nonfixed $T$ iterations. The initial mixed segment has at most $2M$ steps, because either coordinate moves by one at every step. The subsequent monotone segment has at most $4M$ nonfixed steps, because each step changes at least one coordinate and the total coordinate variation is at most $4M$. Hence
$$
k\leq 6M.
$$
In particular, all stopping counts have $O(\log V)$ bits. Computing them in polynomial time still requires the acceleration argument below.
Introduce four linear forms:
$$
\ell_1(x)=x_1,\qquad
\ell_2(x)=x_2,\qquad
\ell_+(x)=x_1+x_2,\qquad
\ell_-(x)=x_1-x_2.
$$
For two distinct bundles $S,Q$, an agent’s utility difference is
$$
u_i(S,p)-u_i(Q,p)
=
v_i(S)-v_i(Q)
-
\sum_{\omega=1}^2
\chi^i_\omega
\left(
\mathbf 1_{\{\omega\in S\}}
-
\mathbf 1_{\{\omega\in Q\}}
\right)p_\omega.
$$
Its coefficient vector is a nonzero vector in $\{-1,0,1\}^2$. After possibly changing its sign, its equality boundary therefore has the form
$$
\ell(x)=c,
\qquad
\ell\in\{\ell_1,\ell_2,\ell_+,\ell_-\},
$$
with integer $c$.
For $T=R_i\circ R_j$, construct the following cut lines.
$$
a_\omega\in\{0,-\chi^j_\omega\}.
$$
For every such $a$, include all six pairwise utility-equality lines for agent $i$ at input $x+a$.
$$ x_1=-M,\quad x_1=M,\quad x_2=-M,\quad x_2=M. $$
There are at most
$$
6+4\cdot6+4=34
$$
cut lines. Their constants have $O(\log V)$ bits.
For each linear form, its sorted cutpoints partition the integers into singleton cutpoints and the intervals between them. All these intervals are interpreted as closed integer intervals; empty intervals are discarded. A full cell specifies one such interval for each of the four forms.
Proof. Within a full cell, every pairwise utility comparison for agent $j$ has a fixed sign, including whether equality holds. Its fixed priority therefore selects the same bundle throughout the cell. Thus $R_j(x)=x+a$ for one constant $a$.
The partition also fixes every utility-comparison sign for agent $i$ at $x+a$. Its selected bundle, and hence its displacement from $x+a$, is constant. Their sum is $T(x)-x$, proving the claim. $\square$
Keeping singleton cutpoint cells is essential: this argument handles all allowed tie priorities exactly.
We first describe an elementary operation used throughout the algorithm.
Suppose a region $G$ is given by integer slab constraints
$$
a_\ell\leq \ell(x)\leq b_\ell,
$$
and a nonzero direction $w$ is fixed. Starting from $x\in G$, the largest integer $q\geq0$ such that
$$
x+t w\in G\qquad(0\leq t\leq q)
$$
is obtained by intersecting the following upper bounds:
$$ t\leq \left\lfloor \frac{b_\ell-\ell(x)}{\ell(w)} \right\rfloor; $$
$$ t\leq \left\lfloor \frac{\ell(x)-a_\ell}{-\ell(w)} \right\rfloor. $$
A form with $\ell(w)=0$ supplies no bound. This calculation takes polynomial time in the bit lengths.
If the displacement equals $w$ throughout $G$, then exactly $q+1$ iterations can be performed at once:
$$
x\longmapsto x+(q+1)w.
$$
Every input to these iterations lies in $G$; the output is the first point outside $G$. Accessible cells and regions have bounded coordinate intervals because the bounding lines were included, so these exit calculations are finite.
While the displacement is $(1,-1)$ or $(-1,1)$, use Lemma 4 to jump through the current full cell in that direction.
By Lemma 3, the mixed direction cannot change to its opposite. Along its straight trajectory, each of the four linear forms is monotone or constant. Each form therefore passes through each of its cutpoint intervals at most once.
If $C$ denotes the total number of cut lines, this segment requires only $O(C+1)$ block operations. At its end we either reach a fixed point or enter a monotone segment.
For a nonincreasing segment, reflect the coordinates:
$$
z=-x,\qquad \widehat T(z)=-T(-z).
$$
The reflected map preserves order, its orbit is nondecreasing, and its partition has the same four forms with negated cutpoints. Thus it suffices to count a nondecreasing orbit.
Its nonfixed displacements belong to
$$
\{(1,0),(0,1),(1,1)\}.
$$
A base region specifies intervals only for
$$
x_1,\qquad x_2,\qquad x_1+x_2.
$$
All three quantities are nondecreasing along the orbit. Thus each changes its interval only forwards, and there are at most $O(C+1)$ base-region visits.
Within one fixed base region $G$, Lemma 4 implies that the displacement depends only on the interval containing
$$
d=x_1-x_2.
$$
In particular, whenever two points in $G$ have the same $d$, their displacements agree.
For a nonfixed step, the possibilities are
$$
\begin{array}{c|c}
\text{displacement}&\text{change in }d\\ \hline
(1,0)&1\\
(0,1)&-1\\
(1,1)&0.
\end{array}
$$
This gives the following complete counting procedure within $G$.
The current point is fixed, so counting ends.
The difference $d$ remains constant. Every later input that stays in $G$ therefore has the same displacement. Jump in direction $(1,1)$ to the first output outside $G$ using the slab calculation above.
If the displacement is $(1,0)$ or $(0,1)$, jump through the current full cell in that direction. Continue until:
Before a reversal, $d$ moves monotonically in unit steps. Hence it visits each difference interval at most once, requiring only $O(C+1)$ such blocks.
Suppose two successive displacements, at inputs that both lie in $G$, are $(1,0)$ and $(0,1)$, or the reverse.
Let $x$ be the current input, let $a$ be its displacement, and put
$$
b=(1,1)-a.
$$
The previous input had displacement $b$ and difference $d+b_1-b_2$. The next input $x+a$ has that same difference. Therefore, if $x+a\in G$, its displacement is $b$. Two iterations give
$$
x\longmapsto x+a\longmapsto x+(1,1).
$$
At the two inputs, the difference alternates between the same two adjacent integers. Since displacement within $G$ depends only on the difference, these two steps repeat, translated by $(1,1)$ after every pair, for as long as both inputs remain in $G$.
If $x+a\notin G$, execute the one step that leaves $G$. Otherwise, compute the largest integer $q\geq1$ such that
$$
x+t(1,1)\in G,
\qquad
x+a+t(1,1)\in G
\qquad(0\leq t<q).
$$
This is another application of the slab calculation, now to both starting points. Execute $2q$ iterations at once:
$$
x\longmapsto x+q(1,1).
$$
By maximality, either this output is outside $G$, or one further step leaves $G$.
Thus a reversal requires only a constant number of additional operations.
There are $O(C+1)$ base-region visits. Each requires $O(C+1)$ straight blocks followed, at most, by one diagonal or repeating-pair calculation. Together with the mixed segment, the total is
$$
O((C+1)^2)
$$
block operations.
Here $C\leq34$ is an absolute constant. Each operation evaluates four-bundle demands and performs arithmetic on numbers of polynomial bit length. No operation enumerates the iterations represented by a block.
Maintain a binary counter for the number of completed $T$ iterations and, whenever it is positive, the immediate predecessor of the current point.
The predecessor is available explicitly after every accelerated block.
For a straight block of $r$ iterations,
$$
x\longmapsto x+r w,
$$
it is
$$
x+(r-1)w.
$$
For a repeating-pair block of $q$ pairs whose first displacement is $a$,
$$
x\longmapsto x+q(1,1),
$$
it is
$$
x+(q-1)(1,1)+a.
$$
Single-step exits are handled directly. Any coordinate reflection is also applied to the stored predecessor and undone at the end.
The procedure therefore returns exactly:
Section 1 then determines whether the last update is agent $j$’s or agent $i$’s:
$$
H^{(i)}
=
2k+2+
\mathbf 1_{\{R_j(x^k)\neq y_{\mathrm{old}}\}}.
$$
Every jump is justified by a constant displacement, or by the proved repeating pair, at all inputs it skips. Those displacements are nonzero, so no fixed point is skipped. Boundary outputs are examined again before further acceleration.
This proves exact polynomial-time computation of $H^{(i)}$ for either starting agent, with arbitrary allowed valuation tables, priorities, initial offers, and trade directions.
Apply the algorithm separately to both starting agents in every lane, and define
$$
J_\theta=H_\theta^{(1)}+H_\theta^{(2)}.
$$
Then
$$
\sum_\theta\mu_\theta\mathbb E[H_\theta]
=
\frac12\sum_\theta\mu_\theta J_\theta.
$$
Write the encoded masses and threshold as
$$
\mu_\theta=\frac{a_\theta}{b_\theta},
\qquad
B=\frac{c}{d},
$$
with positive denominators. The required comparison is exactly
$$
d\sum_{\theta=1}^{\tau}
a_\theta J_\theta
\prod_{\eta\neq\theta}b_\eta
\leq
2c\prod_{\theta=1}^{\tau}b_\theta.
$$
Multiplication preserves the inequality because all denominators are positive.
The product of denominators has polynomial bit length: the sum of their encoded bit lengths is bounded by $L$. The stopping counts have $O(\log V)$ bits, and $\log V=O(L)$. All products, sums, and the final comparison consequently require polynomial-time binary arithmetic.
The per-lane block algorithm has a constant-size partition and polynomial arithmetic cost. Processing the explicitly listed $\tau$ lanes and aggregating their counts is therefore polynomial in $\tau$ and $L$, with $m=2$ fixed.
The promised binary-input decision problem is polynomial-time solvable.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned decision problem in substance: its polynomial-time algorithm is valid, subject to one minor sign error in the reversal argument. No major gap was found.
The reduction to two deterministic trajectories is correct.
After the first update, the unsatisfied set contains exactly the other agent, including when the first update changes no offer. Thereafter, a changing update makes the other agent the unique unsatisfied agent, while an unchanged update terminates the process. Thus the only random choice is the first agent, and
$$
\mathbb E[H]=\frac{H^{(1)}+H^{(2)}}2
$$
is justified.
The paired-update invariant
$$
x=R_i(y_{\mathrm{old}})
$$
holds initially and after each completed pair. If the update by agent $j$ is unchanged, then $T(x)=x$. Consequently, whenever $T(x)\neq x$, both updates in the pair occur and change offers.
The stopping-count formula correctly includes the initial update and the final unchanged update:
The distinction between $k=0$ and $k>0$ in reconstructing $y_{\mathrm{old}}$ is necessary and correctly handled.
The cited theorem applies to the stated model. The source uses integer valuations and offers, arbitrary initialization, consistent unique demand selection, the same full-substitutability conditions, and the same unit-step update rule. Its two-agent result covers two trades; the appendix explicitly includes opposite trade directions in its scope. See [Proposition 5 and Appendix A.1](https://arxiv.org/html/2412.13972v2).
Therefore, using convergence to establish termination of both conditional trajectories is justified. The prover uses this theorem only for termination, rather than treating its magnitude-dependent update bound as a polynomial-time algorithm.
The proof is correct.
When one input coordinate increases by one, the possible response values for that same coordinate have ordered ranges, regardless of whether its demand changes.
For the other coordinate, the applications of full substitutability have the correct directions:
The corresponding response formulas convert these demand inclusions into nondecreasing output coordinates. Repeating unit increases establishes the claim for arbitrary comparable integer vectors.
Thus both response maps, and their composition $T$, preserve coordinatewise order.
The calculation is correct. The identity
$$
\chi^j_\omega=-\chi^i_\omega
$$
holds for every bilateral trade, including when the two trades have opposite directions.
Each rejection indicator belongs to $\{0,1\}$, so the displayed difference formula indeed gives
$$
T(x)-x\in\{-1,0,1\}^2.
$$
The trajectory-shape argument is valid.
Once a displacement is coordinatewise nonnegative or nonpositive, order preservation forces all subsequent displacements to have that same weak sign. The only remaining nonzero possibilities are the two mixed vectors. Consecutive opposite mixed vectors return to the previous point, producing a nontrivial two-cycle. Section 1 ensures that both pairs in such a cycle consist of changing updates, so convergence excludes it.
The offer bound is also correct. Adding a buying trade priced below $-2V$ strictly improves any bundle omitting it; adding a selling trade priced above $2V$ does likewise. These strict comparisons avoid any dependence on tie priorities.
With $M=2V+1$, the only possible outward response at the lower boundary is a buyer’s rejection, and the only possible outward response at the upper boundary is a seller’s rejection. The strict-demand observations exclude both. Initial offers satisfy the bound.
The iteration estimate
$$
k\leq 6M
$$
follows from the stated trajectory shape: the mixed part uses at most $2M$ steps, and the monotone part has total coordinate variation at most $4M$. This supports the claimed logarithmic bit length of stopping counts.
The partition construction is correct.
For distinct bundles, the utility-difference coefficient vector is nonzero and has entries in $\{-1,0,1\}$. Up to sign, its boundary therefore uses one of the four listed linear forms. Its constant is an integer.
There are six bundle comparisons for each agent. Including all four possible first-response displacements accounts for every shifted comparison needed by the composition. The bound of $34$ cut lines is correct, and their constants have logarithmic bit length in the numerical magnitude.
Within a full cell, comparison signs and equalities are fixed. Fixed priorities therefore select a constant bundle for agent $j$, followed by a constant bundle for agent $i$ at the shifted input. Lemma 4 follows.
Singleton cutpoint intervals correctly preserve behavior at utility ties. The algorithm does not need to enumerate all feasible cells: it can identify the current intervals directly.
The slab exit calculation has the correct inequality directions, denominators, and floor operations.
If the last in-region input is $x+qw$, then performing $q+1$ iterations is correct: every evaluated input remains in the constant-displacement region, while the final output is outside it.
The accessible regions have finite coordinate bounds. Together with a nonzero direction, this ensures finite exit calculations.
Along the initial mixed segment, each partition form is monotone or constant. Thus interval changes occur only forwards along that straight trajectory, giving the claimed $O(C+1)$ block count.
Reflection correctly converts a nonincreasing orbit into a nondecreasing orbit while preserving order and the partition structure.
For a nondecreasing nonfixed orbit, the three listed displacements are exhaustive. The three base-region forms are nondecreasing, so the total number of base-region visits is $O(C+1)$.
Within a base region, the displacement depends only on the difference interval. In particular, equal differences imply equal displacements. This justifies the diagonal case and the straight blocks before a reversal.
Minor issue — Section 4.3, Case D. The statement that the previous input has difference
$$
d+b_1-b_2
$$
contains a sign error. Since its displacement is $b$ and its output is the current input $x$, the previous input is $x-b$. The displayed difference does not match that relation.
A concrete arithmetic check is $x=(0,0)$ and $b=(0,1)$: the previous input $(0,-1)$ has difference $1$, whereas the written expression gives $-1$.
This is a local calculation error, rather than a failure of the repeating-pair mechanism. The previous input and the next input do have the same difference because $a+b=(1,1)$. The subsequent alternating-displacement conclusion therefore survives.
Minimum required clarification: Correct the sign in the stated previous-input difference and make its equality with the next-input difference explicit.
The remaining repeating-pair calculation is valid. Its constraints ensure that both inputs of every counted pair remain in the base region. Maximality guarantees that the resulting output either leaves the region or leaves after one further step. No additional uncounted sequence inside the region is required.
The total block bound $O((C+1)^2)$ follows.
Both predecessor formulas are correct:
Reflection and its inverse preserve the stored predecessor information. The algorithm can therefore recover the counterpart’s previous offers and apply the stopping-count formula exactly.
No fixed point is skipped: every accelerated input has a specified nonzero displacement, and every boundary output is examined before further acceleration.
The exact aggregation formula is correct. Multiplication by positive denominators preserves the comparison, including when $B$ is negative.
The denominator product has bit length bounded by the sum of the input denominator bit lengths. The stopping counts, partition constants, jump lengths, and stored coordinates also have polynomial bit length.
Since the number of blocks per conditional trajectory is bounded independently of $V$, the algorithm avoids enumerating magnitude-dependent trajectories. Processing both starting agents for each explicitly listed lane and performing exact rational aggregation takes polynomial time in $\tau$ and $L$, with $m=2$ fixed.
The output therefore establishes the claimed polynomial-time classification, with only the local expositional correction identified above.
⟨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.