Answer: Polynomial-time solvable in the stated parameters.
Proposition 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe mechanism is tractable.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of complete report types \(T\) with rational masses \(\mu_t\) summing to \(1\), evaluation scale \(M\), rational \(\varepsilon\in(0,1)\), weight \(\alpha\), per-capita reward \(v\), and tables \(x_{t,u}\in\{1,\ldots,M\}\) and \(y_{t,u}\in\Delta_M\), compute each type’s per-member share to additive error \(2^{-q}\). Here \(x_{t,u}\) is type \(t\)’s evaluation of type \(u\), and \(y_{t,u}\) is its prediction of the ratings received by type \(u\). Define \(X_{u,k}=(1-\varepsilon)\sum_t\mu_t\mathbf{1}[x_{t,u}=k]+\varepsilon/M\), \(Y_{u,k}=\exp(\sum_t\mu_t\ln((1-\varepsilon)y_{t,u,k}+\varepsilon/M))\), and \(R_{t,u}=\sum_k\mathbf{1}[x_{t,u}=k]\ln(X_{u,k}/Y_{u,k})+\sum_kX_{u,k}\ln(((1-\varepsilon)y_{t,u,k}+\varepsilon/M)/X_{u,k})\). With \(a_t=\sum_u\mu_u x_{t,u}\), the requested share is \(g_u=v\sum_t\mu_t x_{t,u}/a_t+\alpha\sum_w\mu_wR_{u,w}\).
A society is an atomless population of total mass \(1\), given by its support: \(\tau\) complete report types \(T\), each with a positive binary rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). The support size \(\tau\) counts listed types, not possible types.
Inputs are an integer evaluation scale \(M\geq1\), binary rationals \(0<\varepsilon<1\), \(\alpha>0\), \(v>0\), and an integer precision parameter \(q\geq0\). All report tables are explicit: \(x_{t,u}\in\{1,\ldots,M\}\) and rational \(y_{t,u}\in\Delta_M\), including entries with \(t=u\), which describe reports about other members of the same type. Excluding an individual's self-report removes zero mass.
Let \(L\) be the total binary input length apart from the precision parameter. Shares may be negative; no equilibrium or truthfulness promise is imposed on reports.
Define \(p_{t,u,k}=(1-\varepsilon)y_{t,u,k}+\varepsilon/M\), \(X_{u,k}=(1-\varepsilon)\sum_{t\in T}\mu_t\mathbf{1}[x_{t,u}=k]+\varepsilon/M\), and \(Y_{u,k}=\exp(\sum_{t\in T}\mu_t\ln p_{t,u,k})\).
Define \(R_{t,u}=\sum_{k=1}^{M}\mathbf{1}[x_{t,u}=k]\ln(X_{u,k}/Y_{u,k})+\sum_{k=1}^{M}X_{u,k}\ln(p_{t,u,k}/X_{u,k})\) and \(a_t=\sum_{u\in T}\mu_u x_{t,u}\).
The per-member share of type \(u\) is \(g_u=v\sum_{t\in T}\mu_t x_{t,u}/a_t+\alpha\sum_{w\in T}\mu_wR_{u,w}\). The computational problem returns rational approximations \(\widehat g_u\) satisfying \(|\widehat g_u-g_u|\leq2^{-q}\) for every \(u\in T\).
Is this share-computation problem solvable in polynomial time in \(M,\tau,L,q\), or is it NP-hard?
For a finite population of \(n\geq3\) agents, the corresponding mechanism has a stated \(O(n^3M)\) arithmetic-operation algorithm; this bound does not specify bit complexity or numerical precision. It does not establish the complexity of the atomless problem with binary rational inputs and prescribed additive error.
The share-computation problem is solvable in deterministic polynomial time in \(M,\tau,L,q\).
The proof uses exact rational arithmetic and a rational approximation algorithm for logarithms. In particular, it never needs to compute \(Y_{u,k}\) by exponentiation.
We use the standard binary encoding of rational numbers by integer numerators and denominators.
First, all denominators and logarithms in the definition are valid. Indeed,
\(a_t=\sum_u\mu_u x_{t,u}\in[1,M]\),
and
\(p_{t,u,k}\geq\varepsilon/M>0,\qquad X_{u,k}\geq\varepsilon/M>0.\)
The simplex constraints on the reports and the identity \(\sum_t\mu_t=1\) give
\(\sum_k p_{t,u,k}=1,\qquad \sum_k X_{u,k}=1.\)
Thus \(p_{t,u,k}\) and \(X_{u,k}\) are positive rationals, at most \(1\).
Define
\(P_{t,u,k}=\ln p_{t,u,k},\qquad Z_{u,k}=\ln X_{u,k},\)
\(H_{u,k}=\sum_s\mu_s P_{s,u,k},\qquad C_u=\sum_k X_{u,k}Z_{u,k}.\)
By the definition of \(Y_{u,k}\), we have exactly \(\ln Y_{u,k}=H_{u,k}\). Writing \(j=x_{t,u}\), the definition of \(R_{t,u}\) therefore becomes
\(R_{t,u}=Z_{u,j}-H_{u,j}+\sum_k X_{u,k}P_{t,u,k}-C_u.\)
Consequently, every share can be computed from rational arithmetic and only \(M\tau^2+M\tau\) logarithms of positive rationals. The component
\(b_u=v\sum_t\mu_t x_{t,u}/a_t\)
is rational and can be computed exactly.
We prove the numerical ingredient explicitly.
Lemma. Suppose \(r=n/d>0\), where the positive integers \(n,d\) each have at most \(B\) bits. For any integer \(s\geq0\), a rational \(\ell\) satisfying \(|\ell-\ln r|\leq2^{-s}\) can be computed in time polynomial in \(B+s\). Its numerator and denominator have polynomially many bits.
Proof. Find the integer \(h\) such that
\(2^h\leq r<2^{h+1}.\)
Since \(n,d\) have at most \(B\) bits, \(|h|\leq B\). Testing the integers in this range by exact integer comparisons already gives a polynomial-time way to find \(h\).
Set
\(m=r\,2^{-h},\qquad z=(m-1)/(m+1).\)
Then \(1\leq m<2\), \(0\leq z<1/3\), and \(m=(1+z)/(1-z)\). The rational \(z\) has \(O(B)\) bits in its numerator and denominator.
For \(N\geq1\), define the rational sum
\(T_N(z)=2\sum_{j=0}^{N-1}z^{2j+1}/(2j+1).\)
The finite geometric-series identity, integrated from \(0\) to \(z\), gives
\(\ln((1+z)/(1-z))-T_N(z)=2\int_0^z t^{2N}/(1-t^2)\,dt.\)
For \(0\leq z\leq1/3\), the remainder is nonnegative and satisfies
\(2\int_0^z t^{2N}/(1-t^2)\,dt \leq 2z^{2N+1}/((2N+1)(1-z^2)) \leq (3/4)\,9^{-N} \leq 2^{-N}.\)
This estimate applies both to \(\ln m\), using \(z\), and to \(\ln2\), using \(z=1/3\). Because \(\ln r=h\ln2+\ln m\), the rational
\(\ell=hT_N(1/3)+T_N(z)\)
satisfies
\(|\ell-\ln r|\leq(|h|+1)2^{-N}.\)
Choose \(N=s+B+2\). Then
\(|\ell-\ln r|\leq(B+1)2^{-(s+B+2)}\leq2^{-s}.\)
For completeness, the exact rational calculations also have polynomial bit complexity. Each summand of \(T_N(z)\) has numerator and denominator length \(O(NB+\log N)\). Adding its \(N\) summands using a product of their denominators produces numerator and denominator lengths \(O(N^2B+N\log N)\). The powers and sums require polynomially many integer operations on integers of these lengths. The calculation of \(T_N(1/3)\) and the final combination obey the same polynomial bounds. Ordinary integer arithmetic therefore proves the claimed running time. \(\square\)
Suppose rational approximations \(\widehat P_{t,u,k}\) and \(\widehat Z_{u,k}\) satisfy
\(|\widehat P_{t,u,k}-P_{t,u,k}|\leq\delta,\qquad |\widehat Z_{u,k}-Z_{u,k}|\leq\delta.\)
Compute, with exact rational arithmetic,
\(\widehat H_{u,k}=\sum_s\mu_s\widehat P_{s,u,k},\qquad \widehat C_u=\sum_kX_{u,k}\widehat Z_{u,k}.\)
Since the masses are nonnegative and sum to \(1\),
\(|\widehat H_{u,k}-H_{u,k}| \leq\sum_s\mu_s\delta=\delta.\)
Likewise, since the \(X_{u,k}\) are nonnegative and sum to \(1\),
\(|\widehat C_u-C_u|\leq\delta,\)
and
\(\left|\sum_kX_{u,k}\widehat P_{t,u,k} -\sum_kX_{u,k}P_{t,u,k}\right|\leq\delta.\)
Define, for \(j=x_{t,u}\),
\(\widehat R_{t,u} =\widehat Z_{u,j}-\widehat H_{u,j} +\sum_kX_{u,k}\widehat P_{t,u,k}-\widehat C_u.\)
The four preceding error bounds give
\(|\widehat R_{t,u}-R_{t,u}|\leq4\delta.\)
Finally, output the rational number
\(\widehat g_u=b_u+\alpha\sum_w\mu_w\widehat R_{u,w}.\)
Its error satisfies
\(|\widehat g_u-g_u| \leq\alpha\sum_w\mu_w\,4\delta =4\alpha\delta.\)
The binary input length bounds \(\alpha\leq2^L\). Choose
\(s=q+L+3,\qquad\delta=2^{-s}.\)
Applying the lemma to every required logarithm then gives, for every type \(u\),
\(|\widehat g_u-g_u| \leq4\cdot2^L\cdot2^{-(q+L+3)} =2^{-(q+1)} \leq2^{-q}.\)
This argument permits negative shares and requires no equilibrium or truthfulness assumption.
It remains to verify that exact rational computations do not cause excessive intermediate sizes.
If \(K\) rationals each have numerator and denominator lengths at most \(D\), their sum can be represented with denominator equal to the product of their denominators. This denominator has at most \(KD\) bits. The numerator has at most \(KD+\lceil\log_2 K\rceil+O(1)\) bits, because it is a sum of \(K\) integers, each of magnitude at most \(2^{KD}\). Products and quotients of a fixed number of rationals similarly have bit lengths bounded by the sum of their operand lengths.
These elementary bounds imply that all \(p_{t,u,k}\), \(X_{u,k}\), and \(a_t\) have bit lengths bounded by some
\(B=O\bigl((\tau+1)(L+\log(M+1)+\log(\tau+1)+1)\bigr).\)
For example, each \(X_{u,k}\) uses a sum of at most \(\tau\) input masses followed by a fixed number of rational operations, and each \(a_t\) uses a sum of \(\tau\) products of an input mass and an integer at most \(M\).
By the lemma, with \(s=q+L+3\), every logarithm approximation has numerator and denominator lengths bounded by a polynomial \(D\) in \(B+q+L\). Subsequent sizes remain polynomial:
There are \(O(M\tau^2)\) logarithm calls and \(O(M\tau^2)\) additional rational operations when \(H\) and \(C\) are precomputed. Every operation acts on integers of polynomially bounded length. Hence the complete algorithm runs in time polynomial in \(M,\tau,L,q\).
The finite-population arithmetic-operation bound is therefore unnecessary for this conclusion: the argument above directly establishes the required bit complexity and additive accuracy for the atomless support representation.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem. The algorithm is deterministic and runs in polynomial time in \(M,\tau,L,q\), including the bit complexity of intermediate rational computations and the prescribed additive accuracy. No major or minor issues were found.
All expressions are well defined under the task’s stated hypotheses.
The identity \(\ln Y_{u,k}=H_{u,k}\) follows exactly from the definition of \(Y_{u,k}\). For \(j=x_{t,u}\), the indicator sum selects precisely coordinate \(j\), and expanding the second logarithmic term gives
\[
R_{t,u}=Z_{u,j}-H_{u,j}+\sum_k X_{u,k}P_{t,u,k}-C_u.
\]
This is an exact identity. The algorithm consequently needs only the stated \(M\tau^2+M\tau\) logarithms; exponentiation is unnecessary.
The rational base term \(b_u\) is also computed exactly. The indices in the final expression correctly use \(R_{u,w}\).
The lemma is correct, with its computational claims justified.
For positive integers of at most \(B\) bits, the integer \(h\) satisfying \(2^h\leq n/d<2^{h+1}\) lies within the stated search range. Exact comparisons, including those involving negative powers of \(2\), use integers of \(O(B)\) bits.
The normalization gives \(1\leq m<2\), hence \(0\leq z<1/3\). Its rational representation has \(O(B)\) bits.
The integrated geometric-series identity is valid. Rechecking the remainder bound gives
\[
\frac{2z^{2N+1}}{(2N+1)(1-z^2)}
\leq \frac{3}{4(2N+1)}9^{-N}
\leq \frac34 9^{-N}
\leq 2^{-N}.
\]
Thus the displayed bound is valid, including at \(z=1/3\), as required for approximating \(\ln 2\).
Combining the approximations incurs error at most \((|h|+1)2^{-N}\). With \(N=s+B+2\), the claimed accuracy follows from \(B+1\leq 2^{B+2}\).
The bit-length estimates for powers, summands, and their exact rational sum are polynomial in \(B+s\). The stated integer-operation argument therefore establishes both polynomial running time and polynomial output length. No unverified numerical theorem is invoked.
Every averaging bound uses coefficients that are nonnegative and sum to \(1\), exactly as required.
Consequently, errors in \(H_{u,k}\), \(C_u\), and the weighted sum involving \(P_{t,u,k}\) are each at most \(\delta\). Together with the direct \(Z_{u,j}\) error, the triangle inequality gives
\[
|\widehat R_{t,u}-R_{t,u}|\leq4\delta.
\]
No independence assumption about approximation errors is needed.
The final weighted score has error at most \(4\alpha\delta\). Under the stated standard rational encoding, \(\alpha\leq2^L\) is valid because its positive integer denominator is at least \(1\) and its numerator has at most \(L\) bits.
The choice \(s=q+L+3\) therefore gives
\[
|\widehat g_u-g_u|\leq2^{-(q+1)}\leq2^{-q}.
\]
This holds simultaneously for every output coordinate. Exact rational arithmetic introduces no further rounding error.
The rational-sum bound is valid: a product denominator has at most \(KD\) bits, and each numerator contribution has magnitude at most \(2^{KD}\). Summing \(K\) such contributions adds only \(O(\log K)\) bits. The argument accommodates signed numerators.
The proposed bound for the rational inputs to the logarithm lemma is sufficient. Each relevant quantity uses at most a sum over \(\tau\) input terms and a fixed number of additional rational operations.
The subsequent computations have explicitly bounded lengths: sums over \(\tau\) or \(M\) terms increase representation size by polynomial factors, and only a fixed number of such stages occurs. The exact base term \(b_u\) likewise involves \(\tau\) rational terms with polynomially bounded lengths.
Precomputing \(H\) and \(C\) yields the stated \(O(M\tau^2)\) rational-operation count, apart from the internal work of the logarithm calls. Both the number of calls and their individual bit costs are polynomial in the requested parameters.
The argument covers \(M=1\), \(\tau=1\), and \(q=0\). Coordinates equal to \(1\) cause no difficulty: their logarithms are zero, and the approximation lemma includes that case.
Negative shares are permitted throughout. Same-type reports remain included, consistently with the atomless formulation. No equilibrium, truthfulness, or finite-population assumption enters the proof.
No additional clarification or repair is needed.
⟨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.