Answer: Computing the least round is polynomial-time solvable; the threshold decision problem belongs to \(\mathrm{P}\).
Theorem 6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe expected time of convergence is O(k ln n), or more precisely, E(X) < 4k ln n.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(k\) rational, piecewise-linear, nondecreasing concave production functions \(p_i:[0,1]\to\mathbb{Q}_{\ge0}\), with \(p_i(0)=0\), an initial allocation \(x^0\in\Delta_k\), and a resource \(q\) whose marginal output exceeds that of every other resource at every feasible load, determine the least number \(R\) of rounds needed for \(p_q(1)-\sum_i p_i(x_i^R)\le\varepsilon\). In each synchronous round, each infinitesimal unit of mass samples a resource uniformly and switches when its offered marginal output exceeds its current one; offers use the pre-round allocation, and marginal values at kinks use the appropriate one-sided slopes.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here agents are identical, so \(\tau=1\), with total mass \(1\), and there are \(m=k\ge2\) resources.
Input consists of continuous, nondecreasing, concave piecewise-linear functions \(p_i:[0,1]\to\mathbb R_{\ge0}\), specified by binary-rational breakpoints and values with \(p_i(0)=0\); a binary-rational allocation \(x^0\in\Delta_k\); a resource \(q\); and a binary-rational tolerance \(\varepsilon>0\). Every segment slope of \(p_q\) strictly exceeds every segment slope of every \(p_i\) with \(i\ne q\).
At load \(x_i>0\), incumbents receive marginal value \(p'_{i,-}(x_i)\); an arriving unit is offered \(p'_{i,+}(x_i)\) when \(x_i<1\). These are the left and right slopes at kinks, respectively.
In each synchronous round, exactly \(1/k\) of the mass at each resource samples each destination, including its current resource. For distinct resources \(i,j\), mass \(x_i/k\) moves from \(i\) to \(j\) precisely when \(p'_{j,+}(x_j)>p'_{i,-}(x_i)\); otherwise it stays. All comparisons use pre-round loads, all transfers occur simultaneously, and ties retain the current resource. Empty sources and full destinations require no comparison.
Define \(R=\min\{r\in\mathbb Z_{\ge0}:p_q(1)-\sum_{i=1}^k p_i(x_i^r)\le\varepsilon\}\), with \(R=\infty\) if the set is empty. Let \(B\) be the total number of linear segments and \(L\) the total binary input length.
Is computing the least round \(R\), encoded in binary, polynomial-time solvable, or is its threshold decision problem NP-hard?
The threshold problem asks whether \(R\le T\) for an input binary integer \(T\ge0\); state running times in \(m,\tau,B,L\), including the encodings of \(\varepsilon\) and \(T\).
For finite societies with a strictly dominant resource, sequential uniform-sampling marginal-payment dynamics have expected convergence time \(O(k\ln n)\) for \(n>2\). [Bachrach–Rosenschein](https://www.ifaamas.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0037.pdf)
No result settling this exact synchronous mass hitting-time problem was located in the literature search.
Computing the least round \(R\) is polynomial-time solvable. The threshold problem belongs to \(\mathrm{P}\), and thus is not NP-hard under polynomial-time many-one reductions unless \(\mathrm{P}=\mathrm{NP}\).
We use the standard explicit binary encoding of rational numbers: numerators and denominators are written in binary. In particular, their bit lengths contribute to \(L\). For the threshold problem, \(L\) also includes the binary encoding of \(T\).
The key point is that strict dominance gives a polynomial bound on the number of rounds, even though \(\varepsilon\) may be exponentially small. Exact simulation up to that bound then finds the first qualifying round.
Write
\[ \text{ } \]
Let \(s_r=1-x_q^r=\sum_{i\ne q}x_i^r\), and let \(\alpha=(k-1)/k\).
Suppose \(s_r>0\). Then \(x_q^r<1\), so arrivals at \(q\) are permitted. At any positive-load source \(i\ne q\), the incumbent left slope is a segment slope of \(p_i\), while the offered right slope at \(q\) is a segment slope of \(p_q\). Strict dominance therefore forces exactly \(x_i^r/k\) to move from \(i\) to \(q\).
Conversely, no positive mass leaves \(q\): its incumbent left slope strictly exceeds every offered slope at another resource. Transfers between other resources do not affect their total mass. Consequently,
\(x_q^{r+1}=x_q^r+s_r/k,\qquad s_{r+1}=\alpha s_r.\)
If \(s_r=0\), all mass is already at \(q\), and it stays there. Thus, in every case,
\(\displaystyle s_r=\alpha^r s_0.\)
This argument applies at kinks because both one-sided slopes are among the respective resource’s segment slopes.
Define
\(a=\min\{\text{segment slopes of }p_q\},\)
\(M=\max\{\text{segment slopes of }p_q\},\)
\(b=\max\{\text{segment slopes of }p_i:i\ne q\}.\)
The hypotheses imply \(a>b\ge0\), and hence \(M>0\).
For any allocation \(x\in\Delta_k\), put \(s=1-x_q\). Summing slope times interval length over the finitely many segments gives
\(as\le p_q(1)-p_q(x_q)\le Ms.\)
Also, since \(p_i(0)=0\) and every slope of each \(p_i\), \(i\ne q\), is at most \(b\),
\(\displaystyle 0\le\sum_{i\ne q}p_i(x_i)\le b\sum_{i\ne q}x_i=bs.\)
Therefore the welfare gap \(G(x)=p_q(1)-\sum_i p_i(x_i)\) satisfies
\(\displaystyle (a-b)s\le G(x)\le Ms.\)
In particular, \(p_q(1)\) is indeed the maximum welfare, uniquely attained when all mass is at \(q\). Along the trajectory,
\(\displaystyle 0\le G(x^r)\le M\alpha^r s_0\le M\alpha^r.\)
Let \(d\) be the least nonnegative integer satisfying
\(M\le 2^d\varepsilon,\)
and set \(H=kd\).
For every integer \(k\ge2\), the binomial theorem gives
\(\displaystyle \alpha^{-k}=\left(1+\frac1{k-1}\right)^k\ge1+\frac{k}{k-1}>2.\)
Hence \(\alpha^k<1/2\). If \(d>0\), it follows that
\(\displaystyle G(x^H)\le M(\alpha^k)^d\le M2^{-d}\le\varepsilon.\)
If \(d=0\), the same conclusion at round zero follows from \(G(x^0)\le M\le\varepsilon\). Thus
\(\boxed{R\le H=kd.}\)
It remains to bound \(d\) in terms of the input encoding. A segment slope is
\(\displaystyle \frac{v_1-v_0}{t_1-t_0},\)
where \(t_0<t_1\) and all four entries are input rationals. Subtraction and division produce a rational with numerator and denominator of \(O(L)\) bits. Therefore \(M/\varepsilon\) also has \(O(L)\)-bit numerator and denominator, so \(d=O(L)\).
The integer \(d\) can be computed exactly by repeated doubling and rational comparison, using \(O(L)\) iterations. We conclude that
\(\boxed{R=O(kL).}\)
In particular, \(R\) is always finite for the stated positive tolerance.
Choose \(D_0\) to be the product of the denominators of the initial coordinates. Its bit length is \(O(L)\). Represent every coordinate at round \(r\) as
\(\displaystyle x_i^r=\frac{N_i^r}{D_r},\qquad D_r=D_0k^r.\)
For distinct resources \(i,j\), let \(u_{ij}^r\in\{0,1\}\) indicate whether the transfer from \(i\) to \(j\) occurs. Set this indicator to zero for an empty source or full destination; otherwise determine it using the specified strict comparison of the right and left slopes. Let \(h_i^r=\sum_{j\ne i}u_{ij}^r\).
The synchronous update is exactly
\(\displaystyle N_i^{r+1}=(k-h_i^r)N_i^r+\sum_{j\ne i}u_{ji}^rN_j^r,\qquad D_{r+1}=kD_r.\)
Indeed, each outgoing or incoming transfer has mass \(N_i^r/(kD_r)\). This formula computes all transfers from the pre-round numerators.
Since \(h_i^r\le k-1\), the new numerators are nonnegative. Summing the update over all resources cancels outgoing and incoming terms, giving \(\sum_iN_i^{r+1}=kD_r=D_{r+1}\). Thus the representation remains an allocation, and \(0\le N_i^r\le D_r\).
Throughout rounds through \(H\), numerator and denominator bit lengths are therefore
\(O(L+H\log k).\)
All remaining operations are exact rational operations:
For a concrete arithmetic bound, write every segment as \(p_i(t)=A_{i,\ell}t+C_{i,\ell}\). Each coefficient has \(O(L)\)-bit numerator and denominator. A common denominator \(Q\) for all these coefficients, \(p_q(1)\), and \(\varepsilon\) has \(O(BL)\) bits, by taking the product of their denominators.
Consequently, welfare evaluation and its comparison with \(\varepsilon\) can use integer arithmetic with
\(S=O(BL+H\log k)\)
bits. Scanning all breakpoint lists takes \(O(B)\) comparisons per round, and determining all transfers takes \(O(k^2)\) comparisons. With schoolbook integer arithmetic, a conservative total bit-operation bound, including preprocessing, is
\(\displaystyle O\!\left(L+(H+1)(B+k^2)(BL+H\log k)^2\right).\)
To compute \(R\), compute \(H\), then inspect the welfare predicate at rounds \(0,1,\ldots,H\), simulating each intervening round exactly. Return the first successful round. Section 3 guarantees that one exists.
This scan establishes minimality directly; it requires no assumption that synchronous welfare is monotone.
For the threshold problem, if \(T\ge H\), return yes. Otherwise scan rounds \(0,\ldots,T\), returning yes exactly when some inspected round satisfies the welfare predicate. Merely checking round \(T\) is unnecessary.
Substituting \(m=k\), \(\tau=1\), and \(H=O(mL)\), both algorithms have the conservative polynomial running-time bound
\(\displaystyle O\!\left(L+mL(B+m^2)(BL+mL\log m)^2\right).\)
Here \(L\) includes \(\varepsilon\), and includes \(T\) for threshold decision. There is no dependence polynomial in the numerical value of \(T\): at most \(O(mL)\) rounds are simulated. The binary output for \(R\) has \(O(\log(mL+1))\) bits.
The cited finite-agent expected convergence bound is a separate result; this proof uses the deterministic mass recurrence directly. See [Bachrach–Rosenschein, Section 7](https://www.ifaamas.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0037.pdf).
⟨structured verdict parsed — rendered above⟩
The prover’s polynomial-time claim is established. The contraction, hitting-time bound, and exact simulation argument are correct, including at kinks and boundary loads. No substantive gaps were found.
The proof addresses the specified synchronous dynamics with \(m=k\ge2\), \(\tau=1\), explicitly encoded piecewise-linear functions, and positive rational tolerance.
Its encoding convention is appropriate: the binary lengths of rational numerators and denominators contribute to \(L\), including those of \(\varepsilon\). For threshold decision, the encoding of \(T\) also contributes to \(L\).
The proof does not assume welfare is monotone. This matters because the requested answer is the first qualifying round.
The claimed recurrence
\(s_{r+1}=\frac{k-1}{k}s_r\)
is justified.
When \(s_r>0\), the dominant resource has load below \(1\). Every positive-load source distinct from \(q\) therefore compares its incumbent left slope with an available right slope at \(q\). Both are segment slopes, so strict dominance forces the transfer of exactly \(x_i^r/k\).
When \(q\) has positive load, the same dominance condition prevents every outward transfer from \(q\). When \(q\) is empty, it has no outgoing mass. Transfers among the remaining resources preserve their aggregate mass.
The boundary case \(s_r=0\) is also handled correctly: all mass is at \(q\), and no mass leaves. Consequently, the asserted formula \(s_r=\alpha^r s_0\) holds for every nonnegative round.
The argument respects the specified one-sided slopes at kinks. It does not substitute an unspecified derivative.
The definitions of \(a\), \(M\), and \(b\) are valid finite extrema over the explicitly given segments. Nondecreasingness gives nonnegative slopes, and strict dominance gives \(a>b\ge0\), hence \(M>0\).
The bounds
\(as\le p_q(1)-p_q(x_q)\le Ms\)
follow by summing slope times interval length across the relevant segments.
Similarly, the assumptions \(p_i(0)=0\) and segment slopes at most \(b\) justify
\(0\le\sum_{i\ne q}p_i(x_i)\le bs\).
Subtracting these quantities gives exactly the stated inequality
\((a-b)s\le G(x)\le Ms\).
There is no sign error.
The conclusion that all mass at \(q\) uniquely maximizes welfare follows from the strictly positive lower bound whenever \(s>0\). Along the trajectory, the upper bound \(G(x^r)\le M\alpha^r\) is valid because \(s_0\le1\).
The integer \(d\) exists because \(M\) and \(\varepsilon\) are positive. Its definition also handles \(M\le\varepsilon\), giving \(d=0\).
The binomial estimate is correct for every \(k\ge2\):
\(\alpha^{-k}\ge1+k/(k-1)>2\).
Thus \(\alpha^k<1/2\), and the claimed welfare bound at \(H=kd\) follows. The separate treatment of \(d=0\) correctly establishes success at round zero.
The bit-length argument is sound. A segment slope is formed by a fixed number of rational arithmetic operations on input entries, so its numerator and denominator have \(O(L)\) bits. The same holds for \(M/\varepsilon\). Therefore \(d=O(L)\), and repeated doubling with exact comparison computes it in polynomial time.
This establishes \(R\le H=O(kL)\) and rules out \(R=\infty\) under the stated positive-tolerance assumption.
The common-denominator representation is valid initially because the product \(D_0\) is divisible by every initial-coordinate denominator. Its bit length is \(O(L)\).
The numerator update correctly accounts for all synchronous transfers using pre-round loads. In particular, the factor \(k-h_i^r\) retains precisely the mass not sent to another resource.
The checks of nonnegativity and conservation are correct. They establish that every simulated state remains an allocation and that \(0\le N_i^r\le D_r\). Consequently, the claimed \(O(L+H\log k)\) bound on coordinate bit lengths is justified.
The handling of empty sources, full destinations, strict comparisons, and kink segment selection matches the task. No comparison requiring an undefined boundary slope is needed.
The affine coefficients have \(O(L)\)-bit rational representations. Taking a product of their denominators, together with those of \(p_q(1)\) and \(\varepsilon\), yields a common denominator of \(O(BL)\) bits. The stated bound
\(S=O(BL+H\log k)\)
therefore suffices for exact welfare comparison.
Scanning breakpoints uses \(O(B)\) comparisons per round, and examining transfers uses \(O(k^2)\). With schoolbook arithmetic, the displayed total bit-operation bound is conservative and valid, including preprocessing.
Scanning rounds in order and returning the first success establishes minimality directly. The success guarantee at \(H\) makes the computation terminate.
For threshold decision:
Neither branch assumes welfare monotonicity. The algorithm never needs a number of rounds proportional to a potentially enormous numerical value of \(T\).
Substituting \(m=k\) and \(\tau=1\) gives the stated polynomial running time. The binary output-length bound is also correct.
The finite-agent convergence result is identified as separate and is not used to establish any step of the algorithm or its complexity. Its theorem hypotheses therefore do not create an outstanding dependency in this proof.
No mathematical repair or additional clarification is needed. The isolated empty display in Section 1 is merely a cosmetic artifact and has no effect on verification.
⟨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.