Answer: Polynomial-time solvable: simulate each of the \(\tau\) supported profiles and set \(y_{\alpha,v,w}=\mu_\alpha\mathbf{1}_{\{f_\alpha(v)=w\}}\).
Theorem 6.5 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe modified TTC satisfies both SP and SC4N for a networked housing market (𝑁, Π,𝑟) when 𝑟 is a tree network.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a fixed finite rooted tree \(R\) with \(d\) positions and a finite-support distribution with binary-rational masses \(\mu_\alpha\) over complete within-branch reported profiles \(\alpha\), including rankings and reported links, compute the exact mass \(y_{\alpha,v,w}\) of position-\(v\) agents in profile cohort \(\alpha\) assigned house class \(w\) by Modified TTC run within each branch. Can this table be computed in time polynomial in \(d\), the support size, and the input bit length \(L\)?
Let \(R\) be an input directed tree with \(d\geq 1\) agent positions, whose root is directly linked from a moderator with no house; there are \(m=d\) house classes, indexed by positions.
A society is given by its support: a list of \(\tau\) complete branch-profile types \(\alpha\), each with positive binary-rational mass \(\mu_\alpha\), where \(\sum_\alpha\mu_\alpha=1\). Here \(\tau\) is the support size, not the number of possible profiles; \(L\) is the total input bit length.
Each profile specifies, at every position, a strict ranking of all house classes and a reported subset of its children in \(R\). The moderator's link is always present.
The society consists of an atomless mass of separate copies of \(R\), with profile \(\alpha\) on mass \(\mu_\alpha\) of copies. Each position initially owns its corresponding house within its copy; links and exchanges stay within that copy.
A position participates exactly when reachable from the moderator through reported links; every disconnected position retains its endowment.
Modified TTC operates on participating positions: each remaining position points to its favorite remaining house owner among itself, its parent, and its descendants in the reported tree. These eligibility relations are fixed before trading; removing positions never creates new relations.
In each round, execute every directed pointing cycle simultaneously, assigning each cycle member the house of its pointed-to owner, then remove those members and houses; continue until none remain.
Let \(y_{\alpha,v,w}\) be the mass of position-\(v\) agents in profile cohort \(\alpha\) whose final house has class \(w\), including disconnected agents.
Can the complete exact table \(y_{\alpha,v,w}\) be computed in time polynomial in \(m,d,\tau,L\), or is its exact computation NP-hard?
For finite tree networks, Modified TTC is strategy-proof and admits no blocking coalition consisting of a singleton or a participating parent–child pair that redistributes its initial houses and weakly benefits every member while strictly benefiting one. [Source](https://aamas.csc.liv.ac.uk/Proceedings/aamas2021/pdfs/p692.pdf)
No result for this exact atomless branch-profile evaluation problem was identified in the literature search.
The complete exact table is computable in polynomial time. It suffices to simulate one finite copy for each of the \(\tau\) explicitly listed profiles.
This conclusion uses the stipulated separation between copies: participation, eligibility, and exchanges are determined entirely within each copy. The atomless population therefore does not introduce an additional allocation problem.
Fix a profile \(\alpha\), and write \(V=\{1,\ldots,d\}\) for the positions. Compute the participating set \(P_\alpha\) by traversing the reported links from the moderator. For every \(v\notin P_\alpha\), record its final house class as \(f_\alpha(v)=v\).
For each participating position \(v\), precompute its fixed eligibility set
\(E_\alpha(v)\subseteq P_\alpha\): itself, its participating parent if that parent is an agent, and its descendants in the reported tree. The moderator contributes no house. These sets are never changed during trading.
Maintain a set \(S\) of remaining participating positions, initially \(S=P_\alpha\). The following invariant holds:
Invariant. At the beginning of every round, the remaining houses are exactly the initial houses of positions in \(S\), and each remaining position still owns its initial house.
Initially this is true. Suppose it holds before a round. In any executed cycle, each member receives the initial house of the next member. Thus the cycle consumes exactly the initial houses of its members. Distinct pointing cycles have disjoint vertex sets, because every vertex has exactly one outgoing edge. Removing all cycle members and their houses therefore preserves the invariant for the remaining positions.
Consequently, for every \(v\in S\), its pointing target is the uniquely determined position
\(p(v)=\operatorname*{arg\,min}_{w\in E_\alpha(v)\cap S}r_{\alpha,v}(w)\),
where \(r_{\alpha,v}(w)\) is the rank of house class \(w\), with smaller ranks preferred. The minimum exists because \(v\in E_\alpha(v)\cap S\), and it is unique because preferences are strict.
Compute all these targets before executing any exchanges. Let \(C\) be the union of all directed cycles of the resulting pointing graph. For every \(v\in C\), record \(f_\alpha(v)=p(v)\); then replace \(S\) by \(S\setminus C\).
Termination. If \(S\) is nonempty, following pointing edges from any vertex must eventually repeat a vertex, since the graph is finite. The segment between the first occurrence of that vertex and its repetition is a directed cycle. Hence \(C\) is nonempty, and each round removes at least one position. There are at most \(|P_\alpha|\leq d\) rounds.
The invariant proves that the recorded assignments use exactly the houses prescribed by the mechanism. Eligibility remains fixed, pointing is computed simultaneously, and every cycle is executed simultaneously. Thus \(f_\alpha\) is precisely the specified Modified TTC outcome, extended by endowment retention for disconnected positions.
Let \(X_\alpha\) denote the measurable set of copies with profile \(\alpha\), of measure \(\mu_\alpha\).
Every copy in \(X_\alpha\) has the same reported tree, rankings, and initial house classes. The preceding simulation is deterministic: each round’s remaining positions determine unique pointing targets and therefore a unique set of executed cycles. Induction over rounds shows that position \(v\) receives class \(f_\alpha(v)\) in every copy of this cohort.
It follows exactly that
\(y_{\alpha,v,w}=\mu_\alpha\,\mathbf{1}_{\{f_\alpha(v)=w\}}\).
In particular, no cohort needs to be split, and no arithmetic combining different cohort masses is required. Each output entry is either zero or an exact copy of the input rational \(\mu_\alpha\).
Here is a direct bound without any specialized TTC implementation.
For each profile:
There are at most \(d\) rounds, giving \(O(d^3)\) combinatorial operations per profile and \(O(\tau d^3)\) across the support. Each operation uses indices and ranks of polynomial bit length.
Writing the dense table takes \(\tau dm\) entries. If \(b_\alpha\) is the encoded bit length of \(\mu_\alpha\), then precisely \(d\) entries in profile \(\alpha\)’s table are nonzero. An ordered table consequently has bit length \(O(\tau dm+d\sum_\alpha b_\alpha)\), which is \(O(\tau dm+dL)\). Copying the masses therefore also takes polynomial time.
The entire algorithm is polynomial in \(m,d,\tau,L\), with exact rational output. The incentive and coalition properties stated in the question are separate properties of the finite mechanism; this computational proof does not require them. See the cited [finite-network paper](https://aamas.csc.liv.ac.uk/Proceedings/aamas2021/pdfs/p692.pdf) for that context.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The algorithm matches the stipulated mechanism, and its running time and exact output size are polynomial. No major or minor mathematical issues were found.
Traversing the reported links from the moderator computes exactly the participating set \(P_\alpha\). Assigning \(f_\alpha(v)=v\) to every disconnected position correctly implements endowment retention.
The set \(E_\alpha(v)\) includes precisely the eligible participating owners: \(v\), its agent parent, and its descendants in the reported tree. Excluding the moderator is correct because the moderator owns no house. Keeping these sets fixed, while restricting available owners to \(S\), respects the requirement that removals create no new eligibility relations.
The invariant holds initially. Under the invariant, a pointing cycle transfers exactly the initial houses belonging to its members. Distinct cycles are vertex-disjoint in a graph with one outgoing edge per vertex, so simultaneous execution consumes exactly the houses of the removed positions. Positions outside those cycles neither trade nor lose their houses. Thus the invariant is preserved.
For every remaining \(v\), the candidate set \(E_\alpha(v)\cap S\) contains \(v\), so it is nonempty. Strict rankings give a unique favorite. The ownership invariant justifies identifying the target owner \(p(v)\) with the class of the house received. Therefore recording \(f_\alpha(v)=p(v)\) for cycle members is correct.
Following edges in a finite, nonempty graph with one outgoing edge per vertex necessarily reaches a directed cycle. Consequently, each nonempty round removes at least one position, and there are at most \(d\) rounds. Computing every target before executing the union of all cycles correctly implements simultaneous execution.
All copies of a given profile have identical rankings, reported links, and endowments by class. The mechanism is deterministic, and exchanges are confined to each copy. The induction over rounds therefore establishes the same outcome in every copy of that cohort. The resulting formula
\[
y_{\alpha,v,w}=\mu_\alpha\,\mathbf{1}_{\{f_\alpha(v)=w\}}
\]
follows directly. No additional allocation or cohort-splitting problem remains.
Participation takes \(O(d)\) graph operations, and computing eligibility sets takes \(O(d^2)\). Each round uses \(O(d^2)\) operations to compute targets and \(O(d^2)\) to identify all cycles by separate edge-following searches. With at most \(d\) rounds, the bound \(O(\tau d^3)\) is valid. Accounting for the bit cost of indices, ranks, and input access preserves polynomial time.
Each position receives exactly one class, so each profile contributes exactly \(d\) nonzero entries. Those entries simply copy the encoded rational \(\mu_\alpha\); all other entries are zero. For the stated ordered dense representation, the bound \(O(\tau dm+dL)\) is valid. No precision growth or nontrivial rational arithmetic is needed.
The argument does not invoke strategy-proofness or coalition stability. The cited finite-network results are contextual and are unnecessary for the computational conclusion.
No additional clarification or repair is required. The polynomial-time conclusion addresses the explicitly listed support representation and the stipulated separation between copies.
⟨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.