Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 2 — class: hardness
Given finite good classes \(K\), complete types \(T\), rational mass vector \(\mu\), type endowments \(e_t\subseteq K\), and true LP-trees \(\tau_t\), run a fixed deterministic maximal-feasible-mass quotient of ATTC on supplies \(s_g=\sum_t\mu_t\mathbf{1}[g\in e_t]\), with each bundle \(B\subseteq K\) integral. For designated type \(t^\star\), compare the truthful output \(\nu^0\) with the output \(\nu^p\) when all mass \(\mu_{t^\star}\) reports a path \(p\); decide whether some \(p\) admits a coupling \(\pi\) with the two outcome marginals, support only on \(B'\succeq_{\tau_{t^\star}}B\), and positive mass on \(B'\succ_{\tau_{t^\star}}B\).
A society is given by its support: the list of the \(\tau\) complete types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(K\) contain \(m\) good classes; type \(t\) specifies an endowment \(e_t\subseteq K\) and an explicitly encoded true LP-tree \(\tau_t\). Require \(K=\bigcup_t e_t\); supplies are \(s_g=\sum_t\mu_t\mathbf1[g\in e_t]\). Empty endowments are allowed; there are no payments.
An LP-tree is a rooted tree whose node labels visit every class exactly once on each root-to-leaf path; a node has either a single unconditional child or two children selected by presence or absence of its label. To compare distinct bundles, follow their common traversal until the first label on which membership differs: the bundle containing that label is strictly preferred. Write \(\succeq_{\tau_t}\) for this strict order together with equality. Every person's bundle is a subset of \(K\), with at most one good from each class.
Fix the following deterministic maximal-mass ATTC quotient. A state \(a=(t,R,B)\) has mass \(w_a\), untraded endowment \(R\), and acquired bundle \(B\); initialize \((t,e_t,\varnothing)\) with mass \(\mu_t\). Merge identical states and omit zero masses. Order states lexicographically by support-list index and the incidence vectors of \(R,B\) in the input class order.
For each active state \(a\), meaning \(R_a\ne\varnothing\), let \(f_a\) be the first label on its reported tree's traversal for \(B_a\) belonging to \(V\setminus B_a\), where \(V=\bigcup_{a\text{ active}}R_a\). If \(f_a\in R_a\), point to itself; otherwise point to the least active state whose untraded endowment contains \(f_a\).
Choose the lexicographically least directed cycle, encoding each cycle by its state sequence starting at its least state. Trade \(q=\min_{a\text{ in the cycle}}w_a\). For each cycle state \(a\), let \(h\) be its predecessor: move mass \(q\) from \((t_a,R_a,B_a)\) to \((t_a,R_a\setminus\{f_h\},B_a\cup\{f_a\})\), simultaneously. Merge states, recompute pointers, and repeat until all states are terminal. Terminal masses define bundle measures \(\nu_t\), of total mass \(\mu_t\).
For designated \(t^\star\), let \(\nu^0\) be its truthful bundle measure and \(\nu^p\) its measure when all its mass reports the same path \(p\), a permutation of \(K\); other types report truthfully. A beneficial report admits a nonnegative coupling \(\pi(B,B')\) with marginals \(\nu^0,\nu^p\), supported on \(B'\succeq_{\tau_{t^\star}}B\), with strictly positive mass on \(B'\succ_{\tau_{t^\star}}B\).
Is deciding whether a beneficial path report exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard, where \(L\) is the total binary input length, including the explicit LP-trees?
Discrete ATTC Beneficial-Misreport is NP-complete, even with path reports; ATTC itself is polynomial-time computable ([Fujita et al.](https://jair.org/index.php/jair/article/view/11254)).
Continuum TTC has been defined for school choice with single-school assignments ([Leshno–Lo](https://economics.yale.edu/sites/default/files/leshnolo_-_simple_ttc.pdf)); that model does not settle this bundle-manipulation problem. No result settling the specified quotient was located.
The specified decision problem is \(\mathrm{NP}\text{-hard}\). This holds even when all true LP-trees are paths, all endowments are nonempty and pairwise disjoint, and all support types have the same dyadic mass.
The proof transfers discrete ATTC hardness, but requires verifying that the prescribed sequential cycle rule reproduces discrete ATTC.
We use the following known result: deciding whether a designated agent can obtain a strictly better bundle through a path report under discrete ATTC is \(\mathrm{NP}\text{-hard}\), already for ordinary lexicographic preferences. The discrete endowments partition the goods, and ordinary lexicographic preferences are represented by paths. This is the setting of [Fujita et al., Theorem 2 (2015)](https://cdn.aaai.org/ojs/9318/9318-13-12846-1-2-20201228.pdf); the decision formulation and an additional hardness construction appear in [Theorem 2 and Appendix B of the 2018 paper](https://www.jair.org/index.php/jair/article/download/11254/26450).
Write a discrete instance as agents \(\{1,\ldots,n\}\), goods \(G\), endowments \(e_i\), true paths \(\rho_i\), and designated agent \(i^\star\). Let \(\Phi_i\) denote its discrete ATTC bundle.
We may use instances with every endowment nonempty. Indeed, an empty-endowment agent contributes no goods or pointers and always receives the empty bundle. Deleting a nondesignated such agent changes no allocation; a designated such agent cannot benefit. The cited hardness constructions themselves have nonempty endowments.
Consider a quotient instance satisfying these hypotheses:
Because nonempty disjoint endowments are distinct, the listed complete types are distinct.
Lemma 1. Throughout the quotient execution, each type has exactly one state, of mass \(c\). The remaining endowments and acquired bundles jointly partition \(K\).
Proof. Initially, each type has one state of mass \(c\), the endowments partition \(K\), and all acquired bundles are empty.
Suppose these properties hold before a trade. Each remaining class therefore has a unique active owner. Moreover, \(B_i\cap V=\varnothing\), so the requested class \(f_i\) is simply the first class of the reported path that belongs to \(V\). It exists because an active type has a nonempty \(R_i\subseteq V\).
Write the selected state cycle as \((i_1,\ldots,i_r)\), with indices read cyclically. Its pointers imply \(f_{i_j}\in R_{i_{j+1}}\). Thus its requested classes are distinct: they belong to distinct remaining endowments. This also covers a self-cycle.
Every cycle state has mass \(c\), so its maximal trade mass is \(q=c\). Each entire old state disappears and is replaced by exactly one state of the same type and mass. No splitting occurs, and states of different types cannot merge.
Type \(i_j\) gives up \(f_{i_{j-1}}\) and acquires \(f_{i_j}\). Consequently, the trade removes each traded class from exactly one remaining endowment and adds it to exactly one acquired bundle. The partition property is preserved. This proves the induction. \(\square\)
In particular, the quotient becomes a finite procedure on the pairs \((R_i,B_i)\). Each trade decreases \(\sum_i |R_i|\) by the cycle length, so every execution terminates after at most \(|K|\) trades.
For this section, temporarily allow the procedure to select any currently available directed cycle.
Lemma 2. Under the hypotheses of Lemma 1, every such sequential execution has the same terminal bundles.
Proof. At any configuration, every active type has exactly one outgoing pointer. Hence distinct directed cycles have disjoint type sets.
Let \(C\) and \(D\) be distinct cycles currently available. Executing \(C\) changes only the states of types in \(C\), and removes only classes owned by those types.
For every type \(i\) in \(D\), its requested class \(f_i\) belongs to the remaining endowment of its successor in \(D\). Therefore executing \(C\) does not remove \(f_i\). Since \(f_i\) was the first remaining class in \(i\)'s path, deleting other classes leaves it first. Its owner also remains unchanged. Thus every pointer of \(D\) persists after executing \(C\).
The same argument applies with \(C\) and \(D\) exchanged. Furthermore, the trades modify disjoint type states and use disjoint classes. Executing \(C\) followed by \(D\) therefore produces exactly the same configuration as executing \(D\) followed by \(C\).
We now prove uniqueness of the terminal configuration by induction on \(H=\sum_i |R_i|\). If \(H=0\), the configuration is terminal. Otherwise, compare any two terminating executions.
If their first cycles coincide, they reach the same successor, whose remaining count is smaller than \(H\); the induction hypothesis applies.
If their first cycles are distinct, say \(C\) and \(D\), the preceding argument gives a common configuration reached by executing both, in either order. Every successor has smaller remaining count. By the induction hypothesis, every completion after \(C\) agrees with the completion that next executes \(D\), and every completion after \(D\) agrees with the completion that next executes \(C\). These two completions reach the common configuration and have the same terminal outcome.
Thus all terminating executions agree. Termination was established after Lemma 1. \(\square\)
This proves, in particular, that the input ordering and lexicographically least-cycle convention do not affect terminal bundles on these instances.
For path preferences, discrete ATTC uses a graph on the remaining goods. If \(\delta(g)\) is the original owner of good \(g\), its outgoing edge is \(g\to f_{\delta(g)}\), where \(f_i\) is agent \(i\)'s most preferred remaining good. Discrete ATTC executes all current cycles simultaneously.
Lemma 3. With partition endowments, equal masses, and path reports, the quotient produces exactly the discrete ATTC bundles.
Proof. By Lemma 1, each remaining class still lies in its original owner's remaining endowment. The quotient pointer is therefore \(i\to\delta(f_i)\).
A quotient cycle \((i_1,\ldots,i_r)\) corresponds to the goods cycle \((f_{i_1},\ldots,f_{i_r})\): good \(f_{i_j}\) belongs to \(i_{j+1}\), so its goods-graph successor is \(f_{i_{j+1}}\).
Conversely, a goods cycle cannot contain two distinct goods with the same owner. Those two vertices would have the same successor, whereas successor mapping on a directed simple cycle is injective. Its sequence of owners therefore gives a quotient cycle. Different goods cycles also cannot share an owner, because both would contain that owner's requested good.
The trades agree exactly. In the goods cycle, the vertex \(f_{i_{j-1}}\), owned by \(i_j\), points to \(f_{i_j}\); discrete ATTC assigns \(f_{i_j}\) to \(i_j\). The quotient likewise removes \(f_{i_{j-1}}\) from \(R_{i_j}\) and adds \(f_{i_j}\) to \(B_{i_j}\).
Thus a simultaneous discrete round can be executed sequentially in the quotient: its corresponding cycles are disjoint, persist, and commute by Lemma 2. Repeating this for every discrete round gives a valid sequential quotient execution with the discrete terminal bundles. Lemma 2 then implies that the prescribed lexicographically least-cycle execution has those same bundles. \(\square\)
Choose \(N\) to be the least power of two satisfying \(N\geq n\). Add \(N-n\) fresh classes \(D=\{d_1,\ldots,d_{N-n}\}\), and one dummy type for each \(d_j\).
Construct the society as follows:
There are exactly \(\tau=N\) support types. Their endowments are nonempty, distinct, and partition \(K\). Their masses sum to one, and \(1/N\) is dyadic. In particular, \(K=\bigcup_t e_t\), and each class has supply \(1/N\).
Since \(N<2n\), except for the harmless equality case \(N=n\), this construction has polynomially many types and classes. Every tree is an explicit path. The entire construction, including all path encodings and masses, has polynomial binary length.
Lemma 4. For any designated path report \(p\) on \(K\), let \(\bar p\) be its restriction to \(G\). Every original type receives exactly its discrete ATTC bundle under report \(\bar p\).
Proof. Initially, every dummy type requests its own class and therefore forms a self-cycle, regardless of \(p\).
Consider the permitted sequential execution that executes all dummy self-cycles first. Each dummy consumes its own endowment and receives its own class. Every original state remains unchanged. After these trades, the remaining classes are exactly \(G\), and all original acquired bundles are empty.
For the remainder of this execution, the effective designated report is \(\bar p\), while every other original report restricts to \(\rho_i\). Lemma 3 identifies its terminal bundles with the discrete ATTC bundles.
By Lemma 2, the prescribed cycle-selection rule gives the same result as this execution. \(\square\)
Every permutation of \(G\) extends to a permutation of \(K\). Conversely, Lemma 4 shows that an arbitrary report on \(K\) has precisely the effect of its restriction to \(G\). Thus padding neither creates nor destroys an original beneficial report.
By Lemma 1, the designated type finishes with a single bundle in each execution. Let these bundles be \(X^0\) truthfully and \(X^p\) under report \(p\).
Its bundle measures are \(\nu^0=(1/N)\delta_{X^0}\) and \(\nu^p=(1/N)\delta_{X^p}\), where \(\delta_X\) denotes unit mass concentrated at \(X\).
Any nonnegative coupling with these marginals must place all its mass \(1/N\) on the single pair \((X^0,X^p)\). Consequently, it satisfies the stated beneficialness condition exactly when \(X^p\succ_{\tau_{t^\star}}X^0\).
Lemma 4 ensures that both bundles contain only original classes. Appending dummy labels to the true path does not change the comparison between such bundles. Therefore this strict comparison is exactly the original designated agent's discrete strict improvement.
We have proved that the constructed society admits a beneficial path report if and only if the original discrete instance admits one. This is a polynomial many-one reduction.
The specified quotient problem is therefore \(\mathrm{NP}\text{-hard}\), even under the restrictions stated at the start. A polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
On the restricted family used in the reduction, the problem is also in \(\mathrm{NP}\): a path report is a polynomial-size certificate, each execution has at most \(m\) cycle trades, and pointer computation, cycle selection, and final bundle comparison take polynomial time. Hence that restricted problem is \(\mathrm{NP}\text{-complete}\).
The proof establishes the requested hardness classification without requiring a polynomial bound on state splitting for general rational-mass instances.
⟨structured verdict parsed — rendered above⟩
The proof establishes the claimed hardness classification. The polynomial reduction is valid, the prescribed quotient agrees with discrete ATTC on the constructed instances, and the coupling condition becomes exactly discrete strict improvement.
I found no major or minor mathematical issues. No additional clarification is needed to verify the conclusion.
The required source problem is the following decision problem: given partition endowments, true ordinary lexicographic preferences, and a designated agent, determine whether some reported permutation gives that agent a strictly preferred ATTC bundle.
The cited 2015 paper formulates beneficial misreporting as a search problem. The prover also cites the 2018 paper, whose Definition 6 explicitly gives the existential decision formulation and whose Theorem 2 establishes NP-completeness. Its Appendix B construction uses ordinary lexicographic preferences, one manipulator with a nonempty endowment, and other agents owning individual goods. Thus the decision hardness and the restrictions needed here are supported. [2015 paper, Definition 6 and Theorem 2](https://cdn.aaai.org/ojs/9318/9318-13-12846-1-2-20201228.pdf), [2018 paper, Definition 6, Theorem 2, and Appendix B](https://www.jair.org/index.php/jair/article/download/11254/26450).
The observation about deleting empty-endowment agents is also valid under the stated discrete procedure: their goods contribute no vertices, and they receive no assignments. A designated empty-endowment agent cannot strictly improve. The reduction can therefore use the asserted nonempty-endowment instances.
Assessment: The external theorem is applicable with the required hypotheses.
The induction correctly maintains the two claimed invariants:
The second invariant implies \(B_i\cap V=\varnothing\). For path reports, the quotient request is therefore the first remaining class in the reported permutation. It exists whenever \(R_i\ne\varnothing\).
For a selected cycle, the requested class of each member belongs to its successor’s remaining endowment. Distinct cycle members have disjoint remaining endowments, so their requested classes are distinct. A self-cycle satisfies the same reasoning.
Every participating state has mass \(c\), hence \(q=c\). The entire participating state is replaced, without a residual state or a split. Different types cannot merge because type identity is part of the state.
The simultaneous update removes and acquires each traded class exactly once. This preserves the partition invariant and prevents repeated acquisition of a class.
Finally, every trade decreases \(\sum_i |R_i|\) by the positive cycle length. Consequently there are at most \(|K|\) trades.
Assessment: Correct, including self-cycles, terminal types, and termination.
The pointer graph has one outgoing edge per active type. Distinct directed cycles consequently have disjoint type sets.
If \(C\) and \(D\) are available cycles, executing \(C\) cannot remove a requested class of a member of \(D\): that class is owned by another member of \(D\). Deleting other classes cannot change which surviving class comes first in a fixed permutation. The owner of the requested class also remains unchanged. Thus \(D\) remains available.
The symmetric argument applies to \(C\). The two trades modify disjoint type states and transfer disjoint classes, so their updates commute.
The induction on the remaining class count is valid. When first cycles differ, their commuting executions give a common successor; the induction hypothesis applies to each intermediate configuration because its remaining count is strictly smaller. Termination rules out any unfinished infinite execution.
Assessment: The argument establishes uniqueness of the terminal configuration for every permitted sequential cycle order. It therefore covers the prescribed lexicographically least-cycle rule.
The stated discrete goods graph matches the published ATTC definition: each remaining good points to its original owner’s most preferred remaining good, and cycle assignments are performed simultaneously. [2015 paper, Definition 5](https://cdn.aaai.org/ojs/9318/9318-13-12846-1-2-20201228.pdf).
Lemma 1 ensures that a remaining class stays with its original owner until traded. Hence the quotient pointer is exactly \(i\to\delta(f_i)\).
Both directions of the cycle correspondence are correct:
The assignment orientation also matches: type \(i_j\) gives up \(f_{i_{j-1}}\) and receives \(f_{i_j}\) in both procedures.
Lemma 2 justifies serializing every simultaneous discrete round. It then identifies that execution’s terminal allocation with the deterministic quotient’s allocation.
Assessment: The mechanism correspondence is established exactly.
The designated source agent guarantees \(n\geq 1\), so the least power of two \(N\geq n\) exists and satisfies \(N<2n\).
The construction has exactly \(N\) support types, each with positive dyadic mass \(1/N\). The masses sum to one. Original partition endowments together with the fresh singleton endowments partition \(K\), satisfy the union requirement, and distinguish all complete types.
The number of added classes and types is linear in \(n\). Each path explicitly lists all constructed classes, and each mass requires only polynomially many bits. Thus the total output length is polynomial in the source input length.
For any designated report, every dummy initially requests its own class and has a self-cycle. Executing those cycles first is a permitted sequential execution and leaves every original state unchanged. Thereafter, requests depend only on the restriction of the designated report to \(G\).
Lemma 2 transfers this outcome to the prescribed execution. Lemma 3 then yields the discrete allocation under the restricted report.
Every permutation of \(G\) has an extension to \(K\), and every permutation of \(K\) restricts to a permutation of \(G\). Both directions required for the reduction are therefore covered.
Assessment: The padding is valid even for reports that place dummy classes ahead of original classes.
Lemma 1 gives one terminal bundle for the designated type in each execution, with mass \(1/N\).
A nonnegative coupling of the two point measures must concentrate entirely on \((X^0,X^p)\). The beneficialness requirements therefore hold exactly when \(X^p\) is strictly preferred to \(X^0\).
Lemma 4 ensures that both bundles contain only original classes. Appended dummy labels cannot affect their true lexicographic comparison. The quotient improvement condition thus agrees exactly with the source improvement condition.
Assessment: The reduction preserves both yes-instances and no-instances.
The polynomial many-one reduction establishes NP-hardness of the specified continuous quotient problem, including all restrictions claimed at the beginning.
The restricted-family NP-membership claim is also justified: the certificate is a permutation; each execution has at most \(m\) trades; the pointer graph has at most \(\tau\) vertices; and cycle selection and bundle comparison are polynomial computations.
The proof appropriately limits NP-completeness to that restricted family. General NP-membership or a polynomial bound on general state splitting is unnecessary for the requested hardness conclusion.
There are no identified issues and no blocking steps. The output resolves the assigned target as an NP-hardness result.
⟨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.