Answer: \(\mathrm{NP}\text{-complete}\), already for \(\tau=1\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateBENEFICIAL-MISREPORT is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite distribution of rational masses \(\lambda_r\) over exchange-cell templates, each with \(n\) roles and an independent ATTC run, choose a reported ranking \(\hat\succ_r\) for the designated role in each template to maximize \(G=\sum_r (\lambda_r/n)\mathbf{1}[\phi_i(E_r[\hat\succ_r])\,P_i^r\,\phi_i(E_r)]\); decide whether \(G\ge\theta\) for a supplied rational threshold \(\theta\).
A society is given by its support: a list of \(\tau\) exchange-cell types with positive binary rational masses \(\lambda_r\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type specifies a template \(E_r=(e^r,\succ^r,i_r)\) with the same \(n\ge1\) roles, a nonempty set \(K_r\) of indivisible goods, an endowment partition \(e^r\) of \(K_r\), strict rankings \(\succ_j^r\) of all goods, and a designated role \(i_r\). Preferences over bundles are lexicographic, with every good desirable; write \(P_j^r\) for strict bundle preference. There are no monetary transfers.
ATTC keeps each good's original owner \(\delta_r(k)\) fixed. In each round, every remaining good \(k\) points to its owner's highest-ranked remaining good. For every directed cycle, assign each successor good to the original owner of its predecessor, then remove all cycle vertices simultaneously; repeat until no goods remain. Denote the resulting bundle of role \(j\) by \(\phi_j(E_r)\).
Choose a separate strict ranking \(\hat\succ_r\) of \(K_r\) for each designated role; \(E_r[\hat\succ_r]\) replaces only that role's ranking. Each template runs independently, and its entire designated mass \(\lambda_r/n\) uses that report. Endowments and other roles' reports stay fixed.
For an input binary rational threshold \(\theta\in[0,1/n]\), define \(G=\sum_{r=1}^{\tau}(\lambda_r/n)\mathbf{1}[\phi_{i_r}(E_r[\hat\succ_r])\,P_{i_r}^r\,\phi_{i_r}(E_r)]\). Let \(m=\max_r|K_r|\) and \(L\) be the total input bit length; state running times in \(m,\tau,n,L\).
Is deciding whether some collection of reports achieves \(G\ge\theta\) solvable in polynomial time, or is it NP-hard?
For a single finite exchange, finding a beneficial ATTC misreport is NP-hard ([Fujita et al., 2015](https://ojs.aaai.org/index.php/AAAI/article/view/9318)); the later decision formulation is NP-complete even when reports are restricted to lexicographic preferences ([Fujita et al., 2018](https://www.jair.org/index.php/jair/article/download/11254/26450)).
No result for exactly this distribution-over-independent-templates problem was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete, already when the support size is \(\tau=1\). Thus a polynomial-time algorithm for unrestricted inputs would imply \(\mathrm{P}=\mathrm{NP}\).
The boundary case \(\theta=0\) always has answer yes. If \(n=1\), every report assigns all goods to the sole role, so the answer is yes exactly when \(\theta=0\). The hardness result concerns the general input family.
Write \(q_r=|K_r|\), so \(q_r\le m\). A certificate consists of one permutation of \(K_r\) for each designated role. Using indexed goods, its length is
\[ O\!\left(\sum_{r=1}^{\tau}q_r\log(q_r+1)\right) \]
bits, which is polynomial in the explicit input length \(L\).
For completeness, an ATTC execution on \(q\) goods can be computed using \(O(nq+q^2)\) elementary operations:
Every nonempty finite functional graph contains a directed cycle: repeatedly following successors must revisit a vertex. Consequently each round removes at least one good, and there are at most \(q\) rounds. Pointer maintenance, including checking all roles each round, costs \(O(nq)\); graph construction and cycle processing cost \(O(q^2)\).
For each template, the verifier computes both the truthful outcome and the reported outcome. To compare bundles \(A\) and \(B\) under the designated role’s true lexicographic preference, it scans that role’s true ranking. If \(A\ne B\), let \(g\) be the first good belonging to their symmetric difference. Then
\[ A\,P_{i_r}^r\,B \quad\Longleftrightarrow\quad g\in A. \]
This follows directly from lexicographic comparison with every good desirable. The scan costs \(O(q_r)\).
Finally, the verifier computes \(G\) and compares it with \(\theta\) using exact rational arithmetic. To bound its cost, write \(\lambda_r=a_r/b_r\) and let \(D=\prod_r b_r\). The binary length of \(D\) is \(O(L)\), because the denominator encodings are part of the input. For the verified improvement indicators \(c_r\in\{0,1\}\), put
\[ S=\sum_{r=1}^{\tau}c_r a_r(D/b_r). \]
Since the masses sum to one, \(0\le S\le D\), and \(G=S/(nD)\). If \(\theta=u/v\), the threshold test is exactly \(vS\ge unD\). All these integers have \(O(L)\) bits; schoolbook arithmetic takes \(O(\tau L^2)\) bit operations.
Including input processing and indexing, a conservative polynomial verification bound is
\[ O\!\left(\tau(nm+m^2+1)L^2\right). \]
Thus the problem belongs to \(\mathrm{NP}\).
We use the following known decision result: given a finite exchange with strict lexicographic true preferences and a designated agent, deciding whether that agent has a beneficial strict lexicographic ATTC report is \(\mathrm{NP}\)-hard. Fujita et al.’s decision formulation is Definition 6 and Theorem 2; the construction in Appendix B specifies lexicographic true rankings as well. [Fujita et al., 2018](https://www.jair.org/index.php/jair/article/download/11254/26450).
The mechanism matches the one in this task. In the paper’s Algorithm 1, ownership is the initial ownership, and an edge’s successor is assigned to its predecessor’s owner. Under lexicographic rankings, the selected successor is the highest-ranked remaining good. Moreover, two goods with the same owner have the same successor, so they cannot both be cycle vertices: within the union of directed cycles, each vertex has exactly one cycle predecessor. Hence the paper’s assignment and removal instructions implement the simultaneous cycle operations specified here. [Algorithm 1 and Section 4](https://www.jair.org/index.php/jair/article/download/11254/26450).
Take an instance of that single-exchange decision problem, with exchange \(E=(e,\succ,i)\) and \(n\) agents. Construct the society
\[ \tau=1,\qquad E_1=E,\qquad \lambda_1=1,\qquad \theta=\frac1n. \]
This is a valid input: its sole mass is positive and sums to one, its goods and rankings are unchanged, and its threshold belongs to the required interval. Copying the exchange and encoding the additional rational values takes polynomial time; the encoding of \(1/n\) uses \(O(\log(n+1))\) bits.
For every permitted report \(\hat\succ_1\),
\[ G=\frac1n\, \mathbf{1}\!\left[ \phi_i(E[\hat\succ_1])\,P_i\,\phi_i(E) \right]. \]
Therefore \(G\) takes only the values \(0\) and \(1/n\), and
\[ G\ge\theta \quad\Longleftrightarrow\quad \phi_i(E[\hat\succ_1])\,P_i\,\phi_i(E). \]
The constructed society is a yes-instance exactly when the original exchange admits a beneficial report. This proves \(\mathrm{NP}\)-hardness even for \(\tau=1\). Together with Section 1, it proves \(\mathrm{NP}\)-completeness.
Independence also gives a useful structural characterization. Define \(b_r=1\) if template \(r\) admits a beneficial report for its designated role, and \(b_r=0\) otherwise. Then
\[ \max_{\hat\succ_1,\ldots,\hat\succ_\tau}G = \frac1n\sum_{r=1}^{\tau}\lambda_r b_r. \]
Indeed, every report’s improvement indicator is at most \(b_r\), giving the upper bound. For each template with \(b_r=1\), choose a witnessing beneficial report; for the other templates, choose the truthful ranking. These choices can be made simultaneously because reports and executions are independent. Their indicators are exactly the \(b_r\), attaining the bound.
This yields an exact algorithm: compute each truthful outcome once, enumerate the \(q_r!\) strict rankings for its designated role, and test whether any is beneficial. Then compare the displayed maximum with \(\theta\). A conservative bit-operation bound is
\[ O\!\left( \tau\,m!\,(nm+m^2+1)L^2 \right). \]
In particular, the problem is polynomial-time solvable for fixed \(m\), and fixed-parameter tractable when parameterized by \(m\). The dependence on the explicitly listed support size \(\tau\) is linear in this bound. Bounding \(\tau\) alone does not remove the hardness, since it already holds for one support type.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: it establishes \(\mathrm{NP}\)-completeness even for support size \(\tau=1\). I found no major or minor mathematical issues.
Each nonempty functional graph contains a cycle, so at least one vertex disappears per round and there are at most \(q\) rounds. Across the execution, ranking pointers advance at most \(nq\) times; checking all roles each round also costs at most \(O(nq)\). Graph construction and cycle detection cost \(O(q)\) per round, hence \(O(q^2)\) overall. The bound \(O(nq+q^2)\) elementary operations is valid. Exhausted pointers for roles with no remaining endowment need no outgoing edges.
Positivity and normalization imply \(0\le S\le D\). The numerator and denominator of \(\theta\), as well as \(n\), have encodings included in \(L\), so the cross-products also have \(O(L)\) bits. Consequently, \(vS\ge unD\) is an exact threshold test, and the schoolbook arithmetic bound \(O(\tau L^2)\) is valid. The overall verification bound is conservative and polynomial.
Algorithm 1 uses initial ownership. With ordinary lexicographic rankings, its chosen successor is the highest-ranked remaining good. Its assignment and removal rules agree with this task. [Fujita et al., Algorithm 1 and Section 4](https://www.jair.org/index.php/jair/article/download/11254/26450).
The prover’s cycle argument is correct: two distinct goods of the same owner have the same successor and therefore cannot both lie in the union of cycles, where each vertex has exactly one cycle predecessor.
For every report, \(G\) is either \(0\) or \(1/n\). Meeting the threshold is therefore equivalent to strict beneficial manipulation in the source exchange. Both directions of the yes-instance equivalence hold. Together with polynomial verification, this establishes the claimed completeness result.
Enumerating \(q_r!\) rankings per template exhausts the permitted reports. The bound using \(m!\) correctly dominates every template’s enumeration and includes simulation, comparison, and rational arithmetic. It yields polynomial time for fixed \(m\) and fixed-parameter tractability in \(m\), since the remaining factors are polynomially bounded by the explicit input length. Hardness for \(\tau=1\) also correctly shows that bounding support size alone does not remove hardness.
No additional lemma, 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.