Answer: Polynomial-time solvable in \(m,\tau,L\); the problem belongs to \(\mathrm{P}\).
Theorem 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateCondition B is necessary and sufficient for an information structure to guarantee the implementation18 of all decision rules.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite explicit set of population states Ω, a finite type set Τ, rational state probabilities and type masses μ_t^ω, and the induced posterior π(ω|t), does there exist a per-capita transfer schedule τ(r,μ) such that ∑_t μ_t^ωτ(t,μ^ω)=0 in every state and ∑_ω π(ω|t)τ(t,μ^ω) > ∑_ω π(ω|t)τ(r,μ^ω) for every type t and false report r? Such a schedule makes truthful reporting strictly Bayesian incentive compatible and permits every public decision rule based on the reported population distribution.
A nonatomic society has a finite type set \(T\), with \(|T|\geq 2\), and an explicit nonempty state set \(\Omega\). State probabilities \(q_\omega>0\) sum to \(1\); each state has masses \(\mu_t^\omega\geq0\) summing to \(1\). All input numbers are binary rationals.
Each state society is given by its support: the list of types with positive mass and their masses. Let \(\tau=|T|\) be the size of the union of these supports, not the number of possible types; let \(m=|\Omega|\) and \(L\) be the total input bit length. State running times in \(m,\tau,L\).
A uniformly sampled individual of type \(t\) has posterior \(\pi(\omega\mid t)=q_\omega\mu_t^\omega/\sum_{\nu\in\Omega}q_\nu\mu_t^\nu\); every type has positive prior mass. Reports may be any \(r\in T\).
Write \(D=\{\mu^\omega:\omega\in\Omega\}\). A transfer schedule is an unrestricted signed real function \(a:T\times D\to\mathbb R\); identical population distributions must use identical transfers. Utility is transferable, with no participation constraint. An individual's report leaves the aggregate distribution, and hence any public decision based on it, unchanged.
The decision problem asks whether such a schedule satisfies \(\sum_{t\in T}\mu_t^\omega a(t,\mu^\omega)=0\) for every \(\omega\in\Omega\), and \(\sum_{\omega\in\Omega}\pi(\omega\mid t)[a(t,\mu^\omega)-a(r,\mu^\omega)]>0\) for every \(t,r\in T\) with \(r\ne t\).
Is this transfer-feasibility problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finitely many agents with consistent beliefs and positive type marginals, existence of ex post balanced transfers strictly rewarding truth is necessary and sufficient for balanced Bayesian implementation of every public decision rule, including strict implementation. [d’Aspremont, Crémer and Gérard-Varet](https://www.di.ens.fr/~aspremon/Claude/PDFs/dAsp04a.pdf)
No result settling this exact mass-based decision problem was identified in the literature search.
The transfer-feasibility problem is solvable in deterministic polynomial time in \(m,\tau,L\). It reduces exactly to rational linear programming feasibility.
Enumerate the distinct population distributions as \(D=\{d^1,\ldots,d^s\}\), where \(s\leq m\). Define
\(Q_j=\sum_{\omega:\,\mu^\omega=d^j}q_\omega.\)
For every \(t\in T\) and \(j\in\{1,\ldots,s\}\), introduce an unrestricted real variable
\(x_{tj}=a(t,d^j).\)
There are \(\tau s\) variables. Using one variable for each type and distinct distribution enforces identical transfers whenever two states have identical population distributions. Variables are included even when \(d_t^j=0\), because every type remains an available report.
The statewise balance constraints are exactly
\(\displaystyle \sum_{t\in T}d_t^j x_{tj}=0\qquad(j=1,\ldots,s).\)
Indeed, all states with distribution \(d^j\) have this same balance equation.
Let
\(\displaystyle p_t=\sum_{\omega\in\Omega}q_\omega\mu_t^\omega=\sum_{j=1}^sQ_jd_t^j.\)
By hypothesis, \(p_t>0\). For distinct types \(t,r\), the expected gain from truthfully reporting \(t\) instead of reporting \(r\) is
\(\displaystyle \sum_{\omega\in\Omega}\pi(\omega\mid t)\bigl[a(t,\mu^\omega)-a(r,\mu^\omega)\bigr]=\frac{1}{p_t}\sum_{j=1}^sQ_jd_t^j(x_{tj}-x_{rj}).\)
Consequently, define the linear form
\(\displaystyle G_{tr}(x)=\sum_{j=1}^sQ_jd_t^j(x_{tj}-x_{rj}).\)
Since \(p_t>0\), the required incentive constraint is equivalent to \(G_{tr}(x)>0\). Thus the original problem is precisely the feasibility of the balance equations together with these \(\tau(\tau-1)\) strict linear inequalities.
Consider the ordinary rational linear system
\(\displaystyle \sum_{t\in T}d_t^j x_{tj}=0\qquad(j=1,\ldots,s),\)
\(\displaystyle G_{tr}(x)\geq1\qquad(t,r\in T,\ t\neq r).\)
Claim. This system is feasible if and only if the original transfer problem is feasible.
Proof. A solution of this system has \(G_{tr}(x)\geq1>0\), so it immediately supplies the required transfer schedule.
Conversely, suppose \(x\) satisfies all balance equations and all strict incentive inequalities. There are finitely many ordered pairs of distinct types, and there is at least one such pair because \(\tau\geq2\). Therefore
\(\displaystyle \delta=\min_{t\neq r}G_{tr}(x)>0.\)
Set \(y=x/\delta\). The balance equations are homogeneous, so they remain satisfied. Each incentive form is also homogeneous, giving
\(\displaystyle G_{tr}(y)=G_{tr}(x)/\delta\geq1.\)
Hence \(y\) solves the ordinary linear system. This scaling is permitted because transfers are unrestricted and no participation constraint is imposed. \(\square\)
The reduction can be constructed using exact rational arithmetic:
All these operations take polynomial time in \(m,\tau,L\).
For completeness, the coefficients also have polynomial bit length. Let \(C\) be the product of the denominators of all input probabilities and supplied masses. Its binary length is \(O(L)\). Every coefficient
\(\displaystyle Q_jd_t^j=\sum_{\omega:\,\mu^\omega=d^j}q_\omega\mu_t^\omega\)
has denominator dividing \(C\). It lies between zero and one, so its numerator when expressed over \(C\) has \(O(L)\) bits as well. The balance coefficients have the same bit-length bound.
There are \(n=\tau s\leq\tau m\) variables. Replacing each balance equality by two inequalities gives
\(k=\tau(\tau-1)+2s\leq\tau(\tau-1)+2m\)
non-strict inequalities. Thus a dense encoding has total bit length
\(\displaystyle B=O\!\left(\tau m(\tau^2+m)(L+1)\right).\)
The standard rational linear-programming feasibility theorem decides whether such a system has a real solution in deterministic time polynomial in its encoding length; it accommodates equalities and unrestricted variables through the usual linear transformations. Polynomial-time feasibility algorithms, including treatment of degenerate systems, are described by [Dadush, Végh, and Zambelli](https://arxiv.org/abs/1611.06427).
Applying that theorem therefore gives running time
\(\displaystyle \operatorname{poly}\!\left(\tau m(\tau^2+m)(L+1)\right)=\operatorname{poly}(m,\tau,L).\)
The equivalence proved above settles the stated decision problem.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned decision problem. It establishes deterministic polynomial-time solvability in \(m,\tau,L\). No major or minor issues were found.
The counts \(n=\tau s\) and \(k=\tau(\tau-1)+2s\) are correct. The stated dense encoding bound accounts for the coefficient matrix and right-hand sides and is polynomial in the requested parameters.
The proof addresses the exact mass-based transfer-feasibility problem, including sparse supports, repeated distributions, signed real transfers, and strict incentives. It does not depend on importing the finite-agent implementation result.
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.