Answer: The process can run for infinitely many rounds, already with \(m=2\), \(\tau=3\), and \(L=O(1)\).
Theorem 5 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a family of housing markets {Mk = (Nk, Hk, ωk, ⪯k) : k ∈N>0} with |Nk| = |Hk| = 2k + 1, and corresponding priority rankings {Rk : k ∈N>0} such that if the TTAS mechanism receives input Mk and chooses R as its priority ranking in step 0, then the TTAS mechanism runs for at least 2k = 2(|Nk|−1)/2 steps until it terminates. This theorem shows thus that the TTAS mechanism, accord- ing to its current description, does not run in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite agent-type and house-type sets \(P,Q\), rational masses \(\mu_p\) and supplies \(\nu_q\) summing to one, weak preference orders over \(Q\), an endowment type \(e(p)\) satisfying \(\sum_{p:e(p)=q}\mu_p=\nu_q\), and a strict priority order on \(Q\), define mass-TTAS by the corresponding paired-symmetric absorbing-set deletions and priority-driven cycle updates, moving the maximum feasible mass along each implemented cycle and splitting residual types as needed. Does every such instance terminate in a number of rounds polynomial in the support size \(\tau\) and input bit length \(L\), or can some instances require superpolynomially many rounds?
Let \(P\) be a finite set of agent types and \(Q\) a finite set of house types, with \(m=|Q|\). A society is given by its support: the list of the \(\tau=|P|\) types with positive mass, each mass encoded as a binary rational; \(\tau\) is the support size, not the number of possible types. Each type has a complete, transitive weak preference order over \(Q\) and an endowment type \(e(p)\). Positive rational masses and supplies satisfy \(\sum_p\mu_p=\sum_q\nu_q=1\) and \(\sum_{p:e(p)=q}\mu_p=\nu_q\). A strict priority order on \(Q\) is supplied. Let \(L\) be the total input bit length; state bounds in \(m,\tau,L\).
Maintain active holdings \(x_{pq}\), initially \(x_{p,e(p)}=\mu_p\) and zero elsewhere; a positive entry represents a block of type \(p\) currently holding type \(q\). Merge blocks with identical \((p,q)\).
At the start of each round, construct a bipartite digraph with positive blocks and house types having positive active supply. Each block points to every maximally preferred active house type; each house type points to all blocks holding it. An absorbing set is a strongly connected component with no outgoing edge. It is paired-symmetric if every vertex has a neighbor joined to it in both directions.
Finalize and delete all paired-symmetric absorbing sets, assigning their blocks their current holdings. In each other absorbing set identified at the start of the round, retain for each block holding \(q\) only its edge to the first maximally preferred house type strictly after \(q\) in the priority order, wrapping to the first maximally preferred type if necessary; retain all house-to-holder edges.
Batch trades using this frozen graph: give each block residual capacity equal to its current mass, repeatedly choose the lexicographically first simple directed cycle under the input label order (represent cycles by their least cyclic rotation), and reserve \(\delta\), the minimum residual block capacity on that cycle. Reduce each participating block's residual capacity by \(\delta\), discard exhausted blocks, and continue until no cycle remains. Apply all reserved trades simultaneously: on a cycle with blocks \((p_i,q_i)\) pointing to \(q_{i+1}\), subtract \(\delta\) from each \(x_{p_iq_i}\) and add it to \(x_{p_iq_{i+1}}\), with cyclic indices. Newly received holdings participate only in the next round. Include cycles whose participants are indifferent between their old and new holdings. Termination means no active mass remains; one round comprises this deletion and trading batch.
Does every instance of this mass-TTAS process terminate within a number of rounds polynomial in \(m,\tau,L\), or can instances require superpolynomially many rounds, possibly infinitely many?
Discrete TTAS terminates, but for suitable supplied priorities there are markets with \(n=2k+1\) agents requiring at least \(2^k\) rounds ([Aziz–de Keijzer](https://comsoc-community.org/assets/proceedings/comsoc-2012/Aziz.pdf)). No result settling the round complexity of the mass process specified here was located.
Proven claim. The specified process can run forever, already with \(m=2\), \(\tau=3\), and constant input bit length \(L\). The following instance has a period of two rounds.
Construction. Let \(Q=\{a,b\}\) and \(P=\{u,v,w\}\), with the following data:
| Agent type | Mass | Endowment | Preference order |
|---|---:|---|---|
| \(u\) | \(1/4\) | \(a\) | \(a\sim_u b\) |
| \(v\) | \(1/4\) | \(b\) | \(a\sim_v b\) |
| \(w\) | \(1/2\) | \(a\) | \(b\succ_w a\) |
Set \(\nu_a=3/4\) and \(\nu_b=1/4\). These supplies equal the total endowed masses of their respective house types, and both total mass and total supply equal \(1\).
Supply the house priority \(a\prec b\). Choose input labels so that the vertex order used for cycle comparison is
\(a\prec b\prec(u,a)\prec(u,b)\prec(v,a)\prec(v,b)\prec(w,a)\prec(w,b)\).
This can be induced by placing house labels before agent labels and ordering block labels first by agent type, then by house type.
Define two holding states, specifying their only positive entries:
The initial state is \(S_0\). We prove that each round maps \(S_0\) to \(S_1\) or \(S_1\) to \(S_0\), without finalizing any mass.
Absorbing-set check. In either state, both house types have positive active supply. The blocks of \(u\) and \(v\) each point to both houses, whereas \((w,a)\) points only to \(b\).
Each house holds one of the indifferent types \(u,v\). Consequently, from either house there is a directed path through its indifferent holder to the other house. Both houses therefore reach every block through house-to-holder edges. Conversely, every block points to a house and thus reaches both houses and every block. The entire graph is strongly connected, so its only absorbing set is the entire graph.
The vertex \((w,a)\) has no paired-symmetric neighbor: it points only to \(b\), but \(b\) does not point to \((w,a)\), because that block holds \(a\). Thus the absorbing set is not paired-symmetric. No mass is finalized in either state.
The batch from \(S_0\). After priority pruning, the block-to-house edges are
\((u,a)\longrightarrow b,\qquad (v,b)\longrightarrow a,\qquad (w,a)\longrightarrow b\).
The first edge selects the maximal house strictly after \(a\); the second wraps from \(b\) to \(a\); and the third selects \(w\)'s unique maximal house.
Together with the house-to-holder edges, the frozen graph has exactly two simple directed cycles, represented by their least cyclic rotations:
\(C_0=(a,(u,a),b,(v,b))\),
\(D_0=(a,(w,a),b,(v,b))\).
Indeed, there is no cycle using just one house, since no block points to its current holding. A simple cycle can use at most the two available house vertices. It must therefore use the unique holder of \(b\), namely \((v,b)\), and one of the two holders of \(a\), giving precisely the cycles listed.
Both representations begin with \(a\), and \((u,a)\prec(w,a)\). Hence the batch selects \(C_0\) first. Its reservation is
\(\delta=\min\{x_{ua},x_{vb}\}=1/4\).
This exhausts both participating blocks. The only remaining block is \((w,a)\), which points to \(b\); no residual block holds \(b\). Thus no further cycle remains in the frozen graph.
Applying the sole reserved trade exchanges the holdings of \(u\) and \(v\), producing exactly \(S_1\). Both participants are indifferent, so this trade is explicitly allowed by the question.
The batch from \(S_1\). The pruned block-to-house edges now are
\((u,b)\longrightarrow a,\qquad (v,a)\longrightarrow b,\qquad (w,a)\longrightarrow b\).
The frozen graph again has exactly two simple directed cycles:
\(C_1=(a,(v,a),b,(u,b))\),
\(D_1=(a,(w,a),b,(u,b))\).
The same enumeration argument applies: every simple cycle uses both houses, their unique holder \((u,b)\) at \(b\), and either holder at \(a\).
Since \((v,a)\prec(w,a)\), the batch selects \(C_1\) first and reserves \(\delta=1/4\). Both indifferent blocks are exhausted. Again, the sole residual block \((w,a)\) cannot form a cycle because no residual block holds \(b\).
Applying this reservation produces exactly \(S_0\). Newly received holdings are unavailable during the batch, as required by the specified frozen-graph rule.
Induction and round complexity. We have proved both transitions, including their deletion and complete trading batches:
\(S_0\longrightarrow S_1\longrightarrow S_0\).
By induction, the state at the start of every odd round is \(S_0\), and the state at the start of every even round is \(S_1\). Every round leaves total active mass equal to \(1\). Therefore termination never occurs.
This fixed instance uses only dyadic rational masses and has \(m=2\), \(\tau=3\), and \(L=O(1)\). Consequently, there is no finite universal round bound, and in particular no bound polynomial in \(m,\tau,L\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The supplied instance satisfies the input requirements, and the two trading batches produce the claimed periodic orbit without finalizing any mass. No mathematical gaps or false statements were found.
This resolves the stated round-complexity question: the specified process need not terminate, even for fixed \(m=2\), \(\tau=3\), and constant input bit length.
All three masses are positive binary rationals, and
\[
\frac14+\frac14+\frac12=1.
\]
The endowed mass at \(a\) is \(\frac14+\frac12=\frac34=\nu_a\), and the endowed mass at \(b\) is \(\frac14=\nu_b\). Thus supplies are positive, sum to \(1\), and satisfy the required endowment consistency.
Both indifference orders and the strict order stated for \(w\) are complete and transitive over the two-house domain. The supplied house priority is strict.
The chosen input label order is admissible. Its relevant comparisons are that \(a\) precedes every other vertex, that \((u,a)\) precedes \((w,a)\), and that \((v,a)\) precedes \((w,a)\). The construction explicitly supplies all these comparisons.
The initial holdings are exactly \(S_0\). In both \(S_0\) and \(S_1\), the total holdings at \(a\) and \(b\) are respectively \(\frac34\) and \(\frac14\). Therefore both houses remain active in both states.
Every positive entry represents one block, with no duplicated \((p,q)\) pairs requiring an additional merge. The construction respects the distinction between support types and holding blocks.
In either state, each house has an indifferent holder whose block points to both houses. Consequently, each house reaches the other house. Since every block is reached from its current house, both houses reach every block. Every block also points to an active house, so every block reaches both houses and then every other block.
The entire graph is therefore strongly connected. As it contains all vertices, it has no outgoing edge and is the unique absorbing set.
The block \((w,a)\) points only to \(b\). House \(b\) does not point back to that block, because its current holding is \(a\). Although \(a\) points to \((w,a)\), the block does not point back to \(a\). Thus this vertex has no neighbor joined in both directions.
The unique absorbing set fails paired symmetry in both states. The conclusion that no mass is finalized is correct.
With priority \(a\prec b\), an indifferent block holding \(a\) selects \(b\), the first maximal house strictly after \(a\). An indifferent block holding \(b\) wraps to \(a\). The block of \(w\) selects its unique maximal house \(b\).
These rules give exactly the three pruned edges displayed for each state. All blocks belong to the unique non-paired-symmetric absorbing set, so applying pruning to all of them is justified.
No block points to its current holding after pruning, so there is no simple cycle using only one house.
A simple directed cycle cannot repeat a house vertex. With only two houses, every remaining possible cycle therefore uses both houses and exactly two blocks. The unique holder of \(b\) is \((v,b)\); the holder selected at \(a\) is either \((u,a)\) or \((w,a)\). This verifies the exhaustive enumeration of \(C_0\) and \(D_0\).
Their least cyclic rotations begin at \(a\), the least vertex. Comparing their next vertices makes \(C_0\) lexicographically first.
The reserved amount is correctly computed as \(\frac14\). Both participating blocks are exhausted. After their removal, \(b\) has no residual holder, so no directed cycle remains. Hence the batch contains exactly the stated reservation.
The simultaneous updates remove the positive entries for \((u,a)\) and \((v,b)\), create entries of mass \(\frac14\) for \((u,b)\) and \((v,a)\), and leave \((w,a)\) unchanged. The resulting state is exactly \(S_1\).
The same exhaustive cycle reasoning applies, now with \((u,b)\) as the unique holder of \(b\). The displayed \(C_1\) and \(D_1\) are precisely the simple directed cycles.
Their least cyclic rotations again begin at \(a\). Since \((v,a)\prec(w,a)\), \(C_1\) is lexicographically first. Its reservation of \(\frac14\) exhausts both indifferent blocks, leaving no residual holder at \(b\) and therefore no further cycle.
The simultaneous update returns exactly to \(S_0\). The argument correctly excludes newly received holdings from the current batch. Both batches use indifferent trades, which the task expressly permits.
The two verified transitions establish the stated induction: odd rounds start at \(S_0\), and even rounds start at \(S_1\). Neither state causes deletion, and every completed round preserves total active mass \(1\). Thus the termination condition is never reached.
All input data are fixed finite labels, orders, and dyadic rationals, so the claim of constant input bit length is justified. This single nonterminating instance rules out every finite universal round bound, including a polynomial bound in \(m,\tau,L\).
The result concerns termination of the specified process; it establishes neither a polynomial-time algorithm nor a computational hardness classification.
None is required. The write-up checks the complete batches, the deletion condition, and the permitted indifferent trades explicitly.
⟨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.