Answer: Deterministic additive \(\varepsilon\)-approximation of \(R_r\) is possible in time polynomial in \(m,\tau,L,\log(r+1),\varepsilon^{-1}\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSequential deliberation among a set N of agents, where the decision space S is a median graph, yields E[Distortion(at)] ≤1.208 + 6 2t .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite median graph \(G=(S,E)\), finite bliss-point types \(T\), rational masses \(\mu\), bliss points \(p_t\in S\), initial disagreement point \(a_1\in S\), and horizon \(r\), sample \(I_s,J_s\sim\mu\) independently and update \(A_{s+1}=\operatorname{med}_G(p_{I_s},p_{J_s},A_s)\); compute or \(\varepsilon\)-approximate \(\mathbb{E}[\operatorname{SC}_\mu(A_r)]/\min_{a\in S}\operatorname{SC}_\mu(a)\), where \(\operatorname{SC}_\mu(a)=\sum_t\mu_t d(p_t,a)\).
Let \(G=(S,E)\) be an explicitly listed finite, connected, unweighted, undirected median graph, with \(m=|S|\); write \(d\) for graph distance and \(\operatorname{med}_G\) for its unique ternary median.
A society is given by its support: \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\), and bliss points \(p_t\in S\). Here \(\tau\) is the support size, not the number of possible types.
Given \(a_1\in\{p_t:t\in T\}\) and a binary integer \(r\geq1\), set \(A_1=a_1\); for \(1\leq s<r\), independently sample two types with replacement from \(\mu\) and set \(A_{s+1}=\operatorname{med}_G(p_{I_s},p_{J_s},A_s)\).
Define \(\operatorname{SC}_\mu(a)=\sum_t\mu_t d(p_t,a)\), assume \(\operatorname{OPT}=\min_{a\in S}\operatorname{SC}_\mu(a)>0\), and let \(R_r=\mathbb E[\operatorname{SC}_\mu(A_r)]/\operatorname{OPT}\). Given binary rational \(0<\varepsilon<1\), additive approximation means producing \(\widehat R\) with \(|\widehat R-R_r|\leq\varepsilon\); let \(L\) be the total input bit length.
Can \(R_r\) be additively \(\varepsilon\)-approximated deterministically in time polynomial in \(m,\tau,L,\log(r+1),\varepsilon^{-1}\), or is this approximation problem NP-hard?
For finite uniformly sampled agents, sequential deliberation has the stated distortion guarantee \(\mathbb E[\operatorname{Distortion}(a_t)]\leq1.208+6/2^t\), an approximation guarantee rather than an evaluation algorithm ([source](https://arxiv.org/pdf/1710.00771)). The search identified no evaluation-complexity result for the support-encoded mass problem.
The first alternative holds: \(R_r\) admits deterministic additive \(\varepsilon\)-approximation in time polynomial in \(m,\tau,L,\log(r+1)\), and even \(\log(\varepsilon^{-1})\).
The key is that the graph explicitly lists all possible states. We construct its transition matrix and approximate its large power by repeated squaring with controlled rounding. The proof includes the precision needed when \(\operatorname{OPT}\) is very small.
Enumerate \(S\) as \(\{1,\ldots,m\}\). Compute all graph distances by breadth-first search from every vertex.
For each \(a\in S\) and ordered pair of types \(t,u\), find \(\operatorname{med}_G(p_t,p_u,a)\) by scanning all vertices \(z\) for the three equalities
\(d(p_t,z)+d(z,p_u)=d(p_t,p_u)\),
\(d(p_t,z)+d(z,a)=d(p_t,a)\),
\(d(p_u,z)+d(z,a)=d(p_u,a)\).
These equalities say exactly that \(z\) belongs to all three pairwise shortest-path intervals. The median-graph hypothesis guarantees exactly one such vertex. This computation uses \(O(m^2\tau^2)\) candidate checks.
Write each mass as \(\mu_t=\alpha_t/\beta_t\), with positive integer numerator and denominator. Set
\(Q=\prod_{t=1}^{\tau}\beta_t,\qquad w_t=\alpha_t(Q/\beta_t)\).
Then each \(w_t\) is a positive integer, \(\mu_t=w_t/Q\), and \(\sum_t w_t=Q\). The bit length of \(Q\) is \(O(L)\).
Define the row-stochastic transition matrix \(P\) by
\(P_{ab}=\dfrac{1}{Q^2}\sum_{\substack{t,u\\ \operatorname{med}_G(p_t,p_u,a)=b}}w_tw_u\).
The independent sampling with replacement gives exactly these transition probabilities. For \(n=r-1\), the distribution of \(A_r\) is therefore \(v=e_{a_1}P^n\), where \(e_{a_1}\) is the unit row vector at \(a_1\).
Also compute the integers
\(C_a=\sum_t w_t d(p_t,a),\qquad C_*=\min_{a\in S}C_a\).
Thus \(\operatorname{SC}_\mu(a)=C_a/Q\) and \(\operatorname{OPT}=C_*/Q\). The assumption \(\operatorname{OPT}>0\) implies \(C_*\geq1\), so
\(\operatorname{OPT}\geq Q^{-1}\).
Connectedness gives \(d(a,b)\leq H:=m-1\), hence \(0\leq\operatorname{SC}_\mu(a)\leq H\). In particular, the hypotheses imply \(m\geq2\).
All computations so far use polynomially many operations on integers of polynomial bit length. If \(n=0\), return the exact value \(C_{a_1}/C_*\). Henceforth assume \(n\geq1\).
Fix an integer precision \(B\geq0\), and write \(D=2^B\). For a row-stochastic matrix \(M\), define \(T_B(M)\) row by row:
\((T_B(M))_{ij}=\lfloor DM_{ij}\rfloor/D\quad\text{for }j<m\),
\((T_B(M))_{im}=1-\sum_{j<m}(T_B(M))_{ij}\).
The first \(m-1\) entries are rounded downward. Their sum is at most \(1\), so the final entry is nonnegative. Thus \(T_B(M)\) remains row-stochastic.
For a matrix \(X\), define \(\|X\|_{\mathrm{row}}=\max_i\sum_j|X_{ij}|\). In each row, the final entry increases by exactly the total decrease in the other entries. Consequently,
\(\|T_B(M)-M\|_{\mathrm{row}}\leq\eta,\qquad \eta:=2H/D\).
We will use two elementary norm properties. First, the triangle inequality gives
\(\|XY\|_{\mathrm{row}}\leq\|X\|_{\mathrm{row}}\|Y\|_{\mathrm{row}}\).
Second, a row-stochastic matrix has norm \(1\). For a row vector \(x\) and row-stochastic \(M\), directly summing absolute values gives
\(\|xM\|_1\leq\sum_i|x_i|\sum_jM_{ij}=\|x\|_1\).
These properties prevent stochastic multiplication from amplifying an existing distribution error.
Let \(K=\lfloor\log_2 n\rfloor\). Construct
\(B_0=T_B(P),\qquad B_{k+1}=T_B(B_k^2)\quad\text{for }0\leq k<K\).
Every \(B_k\) is row-stochastic and has denominator \(D\).
Set \(E_k=\|B_k-P^{2^k}\|_{\mathrm{row}}\). The initial rounding gives \(E_0\leq\eta\). Writing \(A=P^{2^k}\), we have
\(B_k^2-A^2=(B_k-A)B_k+A(B_k-A)\).
Both \(A\) and \(B_k\) are stochastic, so submultiplicativity yields \(\|B_k^2-A^2\|_{\mathrm{row}}\leq2E_k\). Adding the next rounding error gives
\(E_{k+1}\leq2E_k+\eta\).
Induction therefore proves
\(E_k\leq(2^{k+1}-1)\eta\).
Write the binary expansion as \(n=\sum_{k=0}^{K}b_k2^k\), with \(b_k\in\{0,1\}\). Starting from \(q=e_{a_1}\), multiply \(q\) by \(B_k\) for each index with \(b_k=1\), in increasing order. Perform these vector multiplications exactly, without further rounding.
To bound their accumulated error, compare each multiplication with multiplication by the corresponding exact power \(A_k=P^{2^k}\). If \(q'\) and \(v'\) are the current approximate and exact distributions, then
\(q'B_k-v'A_k=(q'-v')B_k+v'(B_k-A_k)\).
The first term has norm at most \(\|q'-v'\|_1\). Since \(v'\) is a probability vector, the second has norm at most \(E_k\). Hence the total distribution error is at most the sum of the selected \(E_k\).
The selected exact powers multiply to \(P^n\). Therefore,
\(\|q-v\|_1\leq\sum_{k:b_k=1}E_k\leq\eta\sum_{k:b_k=1}2^{k+1}=2n\eta\).
No independence among graph coordinates is required.
Return the rational number
\(\widehat R=\dfrac{\sum_a q_aC_a}{C_*}\).
Using the cost bound \(H\), the distribution-error bound, and \(\operatorname{OPT}\geq Q^{-1}\), we obtain
\(\left|\widehat R-R_r\right| \leq\dfrac{H}{\operatorname{OPT}}\|q-v\|_1 \leq HQ(2n\eta) =\dfrac{4nH^2Q}{D}\).
Choose \(B\) so that
\(2^B\geq4nH^2Q/\varepsilon\).
Then \(|\widehat R-R_r|\leq\varepsilon\), as required.
This precision can be chosen using exact integer comparisons. Indeed, if \(\varepsilon=\gamma/\delta\), choose the smallest \(B\) satisfying
\(2^B\gamma\geq4nH^2Q\delta\).
Its magnitude satisfies
\(B=O\!\left(\log(r+1)+\log m+L+\log(\varepsilon^{-1})\right)\).
Thus exponentially many rounds require only polynomially many precision bits.
There are \(O(\log(r+1))\) matrix squarings. Each \(B_k\) has denominator \(D\); its square has denominator \(D^2\) before rounding. Since both matrices are stochastic, all entry numerators have \(O(B)\) bits. Each squaring and rounding therefore takes polynomial time in \(m\) and \(B\).
The exact vector accumulation multiplies at most \(K+1\) matrices of denominator \(D\). After \(h\) selected multiplications, its denominator can be represented as \(D^h\). Because the vector remains a probability vector, its numerators have at most \(hB+1\) bits. Thus these exact multiplications also have polynomial bit complexity.
Finally, forming \(\widehat R\) uses integers of bit length polynomial in \(L+\log m+B\log(r+1)\). Together with the exact preprocessing, this proves the claimed deterministic polynomial running time.
The argument completely resolves the approximation question under the stated explicit-input assumptions.
⟨structured verdict parsed — rendered above⟩
The prover’s output correctly resolves the task. It gives a deterministic additive approximation algorithm with polynomial bit complexity under the explicit graph and support encoding. No major or minor gaps were found.
The three distance equalities characterize membership in the three pairwise shortest-path intervals. The median-graph hypothesis guarantees that their intersection contains exactly one vertex, including when arguments coincide.
There are \(m\tau^2\) combinations of a current state and an ordered pair of types. Scanning \(m\) candidate vertices for each gives the stated \(O(m^2\tau^2)\) candidate checks. All distances are computable in polynomial time by breadth-first search.
The transition formula correctly accounts for independent sampling with replacement. Ordered pairs are counted separately, and pairs with identical types are included. Its entries are nonnegative and each row sums to \(1\). Consequently, the distribution identity \(v=e_{a_1}P^{r-1}\) is correct.
The common denominator \(Q=\prod_t\beta_t\) has bit length bounded by the sum of the input denominator lengths, hence \(O(L)\). Each \(w_t=\alpha_t(Q/\beta_t)\) is an integer, and normalization gives \(\sum_t w_t=Q\).
The cost identities \(\operatorname{SC}_\mu(a)=C_a/Q\) and \(\operatorname{OPT}=C_*/Q\) follow directly. Since \(C_*\) is an integer and the assumed optimum is positive, \(C_*\geq1\) and \(\operatorname{OPT}\geq Q^{-1}\).
Connectedness implies the distance bound \(H=m-1\). The positive-optimum assumption excludes \(m=1\). The separate treatment of \(r=1\) correctly returns the exact ratio and avoids taking the logarithm of \(n=0\).
Rounding the first \(m-1\) entries downward leaves their sum at most \(1\), so assigning the residual to the final entry preserves nonnegativity and unit row sum.
The increase in the final entry equals the total decrease in the other entries. Each of those decreases is less than \(D^{-1}\), so the claimed bound
\[
\|T_B(M)-M\|_{\mathrm{row}}\leq 2H/D
\]
is valid.
The stated matrix norm is submultiplicative, stochastic matrices have norm \(1\), and right multiplication by a stochastic matrix contracts the vector norm \(\|\cdot\|_1\). These elementary properties apply to every matrix and vector used subsequently.
The identity
\[
B_k^2-A^2=(B_k-A)B_k+A(B_k-A)
\]
is valid without a commutativity assumption. Because both \(A=P^{2^k}\) and \(B_k\) are stochastic, it gives the bound \(2E_k\) before rounding.
Including the rounding error yields \(E_{k+1}\leq2E_k+\eta\). The stated solution \(E_k\leq(2^{k+1}-1)\eta\) correctly follows from \(E_0\leq\eta\).
Exact vector multiplication preserves the approximate vector’s status as a probability vector. The comparison identity between the approximate and exact updates is correct. Its first term is bounded by the existing distribution error, and its second by \(E_k\), since \(v'\) is a probability vector.
The selected exact powers multiply to \(P^n\). Summing the selected error bounds gives
\[
\|q-v\|_1\leq2n\eta.
\]
The constant and dependence on \(n\) are correct.
Both the returned value and the true value use the same exact, positive denominator \(C_*\). The cost bound and optimum lower bound therefore give
\[
|\widehat R-R_r|\leq
\frac{H}{\operatorname{OPT}}\|q-v\|_1
\leq\frac{4nH^2Q}{D}.
\]
Choosing \(D\geq4nH^2Q/\varepsilon\) establishes the required additive accuracy, including when the optimum is very small.
The integer comparison using \(\varepsilon=\gamma/\delta\) is exact. The stated bound on the required precision \(B\) follows from this threshold.
Repeated squaring uses only \(O(\log(r+1))\) matrix operations. Rounded matrices have denominator \(D\), and their exact squares have denominator \(D^2\); stochasticity bounds their numerators by those denominators.
After \(h\) selected vector multiplications, denominator \(D^h\) and numerator lengths at most \(hB+1\) are valid. Since \(h=O(\log(r+1))\), these lengths remain polynomial in the specified parameters. Forming and outputting the final rational value also has polynomial bit complexity.
Thus the stronger claimed dependence on \(\log(\varepsilon^{-1})\), alongside the input length \(L\), is justified.
No additional clarification or repair is needed. The algorithm establishes the polynomial-time alternative requested by the task.
⟨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.