Answer: Polynomial-time computable, including a batch trace agreeing with every clearing finite lift.
Theorem 6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor given 𝐴, 𝐻, ▷, 𝜃′, the time complexity of YRMH- IGYT for TSSNs is 𝑂(𝑛· 𝑛′), where 𝑛 is the number of agents and 𝑛′ is the number of houses.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of rooted tree templates \(\mathcal G\), each with roles, tenant or newcomer labels, parent-child relations, endowment-house roles, strict rankings over local house classes, and distance-based priority, plus rational masses \(\lambda_G\) of identical copies, compute the exact aggregate assignment masses \(x_{G,r,h}\), residual vacant-house masses, and a valid batch trace of YRMH-IGYT for TSSNs; the trace must agree with the mechanism on every finite lift obtained by clearing denominators.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here a type is a finite rooted tree template \(G\), and \(\tau\) is the support size, not the number of possible types. Let \(m\) be the total number of house roles, \(a\) the total number of agent roles, and \(L\) the total input bit length.
Each template specifies connected agent roles labelled tenant or newcomer, parent–child edges directed away from a moderator root, one distinct endowment-house role per tenant, and initially vacant house roles owned by the moderator. Its mass \(\lambda_G>0\) is a mass of copies, without unit-sum normalization. Require aggregate house mass to be at least aggregate agent mass. House classes are the pairs consisting of a template and one of its house roles; every agent role strictly ranks all classes, with every house preferred to \(\varnothing\).
For every positive integer \(D\) clearing the input mass denominators, the finite lift has \(D\lambda_G\) copies of each template, indexed consecutively, with moderator roots identified. Parent–child edges and endowments stay within copies; currently vacant houses are available globally. Initially order agents lexicographically by distance from the moderator, an input order of template–role pairs within each distance, and copy index. Refine house-class preferences by increasing copy index.
Define YRMH-IGYT for TSSNs as follows. The first remaining agent requests her favourite eligible house: a currently vacant house, an endowment of a remaining tenant child, and, for a tenant only, her own endowment or an endowment of a remaining tenant ancestor. Include \(\varnothing\) among vacant choices, with unlimited availability.
A vacant request is assigned immediately and the agent leaves; a departing tenant releases her endowment. A request for one's own endowment is assigned immediately and the tenant leaves. A request for a child's occupied endowment records a pointer and moves that child to the front, preserving the order of other agents. A request for an ancestor's endowment closes the existing pointer chain into a cycle: assign every cycle member the endowment she requests and remove those members. Continue until no agents remain.
The required outputs are assignment masses \(x_{G,r,h}\), including \(h=\varnothing\), residual vacant masses by house class, and a finite batch trace. A batch record specifies an ordered word of mechanism events, a positive rational multiplicity \(q\), and agent/house copy indices as affine functions of the repetition index and \(D\). Its expansion repeats that word \(Dq\) times. For every clearing denominator \(D\), the expanded trace must be precisely a legal execution of the specified finite lift, with assignment and vacancy counts equal to \(D\) times the reported masses.
Is this exact aggregate computation, including a batch trace agreeing with every finite lift, polynomial-time computable in \(m,a,\tau,L\), or is it NP-hard?
For explicitly listed finite agents and houses, YRMH-IGYT for TSSNs runs in \(O(n n')\), where \(n\) counts agents and \(n'\) counts houses. [Verified discrete result](https://ifaamas.org/Proceedings/aamas2022/pdfs/p1446.pdf).
No result settling this exact rational-mass problem with universal finite-lift agreement was located.
The required aggregate computation is polynomial-time computable, including a batch trace that agrees with every clearing finite lift.
The proof uses two properties of the specified priority order:
The second property makes all batching boundaries compatible with the original mass denominators. Copy-index tie-breaking requires additional bookkeeping, which remains polynomial.
The explicitly listed finite-agent bound appears as Theorem 6 of the [cited paper](https://ifaamas.org/Proceedings/aamas2022/pdfs/p1446.pdf). The argument below establishes the additional compression and universal finite-lift agreement required here.
Fix a clearing denominator \(D\). Call the initial agent order, restricted to agents still present, the baseline order.
An episode starts when there are no outstanding pointers and the first agent in the baseline order is selected. It ends when that agent leaves. Call this agent the episode root.
During an episode, all selected agents belong to the episode root’s template copy. Outstanding pointers form a path from the episode root to the currently selected agent. Every agent on that path except possibly the episode root is a tenant.
At the end of the episode, there are no outstanding pointers, and the remaining agents have their baseline order.
Proof. Initially the path consists only of the episode root. A child request extends the path by one edge, within the same copy, and the requested child is a tenant because only tenant children have occupied endowments.
An own-endowment assignment removes the selected agent. An ancestor request removes a suffix of the path. In either case, if the episode root remains, the preceding path member becomes first again.
A vacant request also removes the selected agent. We will show immediately below that its predecessors then leave successively. Thus every promoted agent leaves before the episode ends. Since promotions preserve the order of all other agents, the remaining order at the end is precisely the restricted baseline order. This also proves that no outstanding pointer remains. \(\square\)
Suppose an agent on the pointer path requests a vacant house. Each preceding path member then receives the endowment she had requested from the next path member and leaves.
Consequently, at episode boundaries:
Proof. Before the first vacant request, the only departures possible are own-endowment assignments and trading cycles. Neither creates a vacancy.
Let the selected tenant be \(t\), and let her pointer predecessor be \(p\). Agent \(p\) previously selected \(t\)’s endowment as her favourite eligible house. Until \(t\) receives the vacant house, the vacancy inventory has not changed. Some occupied choices may have disappeared through cycles or own-endowment assignments, but no better choice has been added.
When \(t\) leaves, her endowment becomes vacant. It therefore remains \(p\)’s favourite eligible house: all other currently eligible houses were available when \(p\) requested it, apart from choices that have disappeared. Agent \(p\) receives that endowment and leaves. The same reasoning applies successively up the pointer path.
Each intermediate released endowment is consumed by its predecessor. Only the episode root’s endowment, if she is a tenant, remains globally vacant. If the selected agent is the episode root, the conclusion holds directly.
A tenant never chooses \(\varnothing\), because her own endowment is eligible and strictly preferred. Thus an episode ending at \(\varnothing\) ends at its newcomer root. \(\square\)
For this argument, the requested child’s endowment is a particular house. Its availability after release cannot make the parent prefer another house of the same class: that other house, if already vacant, was eligible when the parent made the original request.
An episode has a number of mechanism events bounded by a polynomial in \(a\), independently of \(D\).
Proof. Each descent along a parent–child edge occurs at most once during the episode. Indeed, control returns to the parent only after that child has left. Every selected-agent event that is not a descent removes at least one agent. There are at most \(a\) agents in the copy and at most \(a\) relevant edges. Thus there are at most \(2a\) selected-agent events. Listing cycle members, assignments, and releases adds only polynomial, and in fact linear, space. \(\square\)
Order all template–agent-role pairs by the specified distance order and then by the specified input order within each distance.
The stage of a role \(r\) in template \(G\) consists of processing, in increasing copy index, all still-present agents of that role. Each such agent is an episode root.
This is precisely the actual execution at episode boundaries: Lemma 1 restores the baseline order after every episode.
Before an agent role’s stage begins, none of its endowment-house copies is globally vacant at an episode boundary.
During a tenant role’s stage, only that role’s endowment class can gain globally vacant houses. All other vacancy classes can only lose houses.
Proof. By Lemma 2, an endowment becomes globally vacant at an episode boundary only when its original tenant is the episode root. An agent of the given role can be an episode root only during that role’s stage.
During a fixed stage, every episode root has that stage’s role. Hence the only endowment class that can be released into the boundary inventory is its own. \(\square\)
In particular, all ancestors of a stage’s episode root have already left: their distances are strictly smaller. Every occupied ancestor encountered during its episode therefore lies on the active pointer path.
Fix a stage and a set \(S\) of remaining agent roles in one copy. If the episode root is a tenant, write \(h_r\) for her endowment class.
The episode’s removed roles and assigned house classes are determined by:
They do not depend on positive vacancy quantities or concrete copy indices.
For a tenant root, the concrete event word additionally depends on whether the vacancy inventory of \(h_r\) is empty.
Proof. Simulate the episode locally, retaining its occupied endowments and one formal vacant choice for each positive external vacancy class. For a tenant root, omit \(h_r\) from these formal vacant choices.
By Lemma 4, the only class that could simultaneously have a globally vacant house and an eligible occupied endowment is \(h_r\). Every selected agent in this tenant-rooted episode is a tenant and has the root’s endowment eligible, either as her own endowment or as an ancestor’s. Omitting vacant copies of \(h_r\) therefore does not alter the set of eligible classes.
Strict rankings of classes determine every class choice uniquely. Before a vacant request, internal cycles and own-endowment assignments change only the remaining local roles. After a vacant request, Lemma 2 forces the subsequent assignments. Consequently, positive vacancy quantities do not affect this local class outcome.
There is one concrete distinction. If the local simulation ends by assigning the root’s endowment through an own-endowment assignment or a cycle containing the root, and a vacant copy of \(h_r\) exists, the selected agent instead takes the lowest-index vacant copy of \(h_r\). Vacancy propagation gives exactly the same assigned classes and removed roles.
Every such vacant copy has smaller index than the current root: the inventory of \(h_r\) was empty before this stage, and its houses were released by earlier episode roots in increasing index order. Thus copy-index tie-breaking always selects that vacant house.
If the simulated episode ends at an external class different from \(h_r\), its event word never requests class \(h_r\). In this case the appearance of vacant \(h_r\) houses does not change its word. \(\square\)
This lemma permits a polynomial-size local simulation. It also specifies exactly when an occupied-root cycle must be replaced by a vacant request and subsequent assignments.
Let \(Q\) be the least common multiple of the reduced input mass denominators. Every clearing denominator \(D\) is a multiple of \(Q\).
Use rational copy coordinates: an interval \((u,v]\) represents copy indices satisfying \(Du<i\leq Dv\). All endpoints used below belong to \(\frac{1}{Q}\mathbb Z\).
For each template \(G\), maintain a partition of \((0,\lambda_G]\) into intervals. Each interval carries its set \(S\) of remaining agent roles. Initially there is one interval, carrying all roles of \(G\).
Maintain the global vacant mass of each house class. Concrete vacancy indices will be added in Section 5.
At the stage of role \(r\) in template \(G\), traverse these intervals in increasing order, skipping intervals where \(r\notin S\). On an interval where \(r\) remains:
More precisely, let \(t\) be the remaining interval mass.
If the episode consumes an external class \(v\), let \(c_v>0\) be its current vacant mass and choose \(b=\min\{t,c_v\}\). Update \(c_v\) by subtracting \(b\). For a tenant root, add \(b\) to her endowment-class vacancy mass.
If the episode ends through the root’s own endowment, a root-containing cycle, or \(\varnothing\), choose \(b=t\). Its net vacancy masses do not change. A positive root-endowment vacancy inventory may rotate, but its mass stays constant.
Update the remaining-role set on that portion and add \(b\) to every assignment entry specified by the local outcome. Call the resulting portion an aggregate block.
The total number of local state intervals is at most \(\tau+am\). The number \(B\) of aggregate blocks satisfies \(B=O\!\left(a(\tau+am+m)\right)\).
Proof. During one stage, every vacancy class other than the root’s endowment class only decreases, by Lemma 4. Each can therefore become empty at most once during that stage.
Within a local state interval, Lemma 5 gives the same class outcome until the selected external vacancy class becomes empty. Hence a new local state boundary is introduced only when such an exhaustion occurs inside an interval. There are at most \(m\) such boundaries per stage.
The root’s endowment vacancy class causes no additional boundary. Its appearance does not change an external-ending word. For a root-endowment-ending word, an empty inventory remains empty, while a positive inventory retains its mass.
Starting with \(\tau\) intervals and processing \(a\) stages gives at most \(\tau+am\) intervals. Each stage traverses at most that many intervals and has at most \(m\) additional exhaustion boundaries. The stated bound follows. \(\square\)
All block masses and boundaries remain in \(\frac{1}{Q}\mathbb Z\): the algorithm uses only sums, differences, comparisons, and minima of quantities already on that grid.
Therefore, for every clearing \(D\), each positive block mass \(b\) corresponds to an integer number \(Db\) of episodes. No rounding is needed.
It remains to recover the exact house indices without expanding the copies.
Represent each class’s vacant houses by an ordered list of coordinate intervals. An interval \((u,v]\) represents precisely its vacant copy indices satisfying \(Du<i\leq Dv\).
Initially, each initially vacant house class has the interval \((0,\lambda_G]\). Endowment classes have empty lists.
Before their owner’s stage, endowment lists are empty by Lemma 4. During that stage, releases occur in increasing copy-index order and can be appended. After that stage, no further house of that endowment class can be released, because its original tenants have all left.
Consider an aggregate block with root indices \(D\ell+k\), where \(1\leq k\leq Db\), that consumes an external vacancy class.
Its source inventory receives no releases during this stage. Split the block whenever its lowest vacant-house interval is exhausted.
Within a resulting subblock, after resetting the repetition index to \(k\), the root index and the requested external house index have the forms \(D\alpha+k\) and \(D\beta+k\), respectively. All other agents and houses in the word belong to the root’s copy and have index \(D\alpha+k\).
The word of events is fixed by Lemma 5. These indices are affine functions of \(k\) and \(D\), as required.
If the root is a tenant, the block releases her endowment at every processed root index, forming one contiguous interval.
The remaining case is a tenant-rooted block whose class outcome ends at the root’s endowment class.
If that inventory is empty, use the own-endowment or root-containing-cycle word from the local simulation. All indices are those of the current copy.
Suppose instead that its mass is \(c>0\). Every episode consumes the lowest-index vacant root endowment and releases the current root’s endowment. Thus its ordered inventory is a queue undergoing one removal and one append per episode.
Let the block’s root indices be \(D\ell+k\), where \(1\leq k\leq Db\).
For the first \(\min\{Db,Dc\}\) repetitions, the consumed houses are precisely the corresponding initial queue entries. Split this prefix at their interval boundaries.
If \(b>c\), then in every remaining repetition \(k>Dc\), the consumed house has index \(D\ell+k-Dc\).
Justification. The initial queue has exactly \(Dc\) houses. Once these have been consumed, the queue contains houses released by preceding repetitions of this block, in their release order. Each repetition appends exactly one house. Therefore repetition \(k\) consumes the house appended at repetition \(k-Dc\).
Since \(c\in\frac{1}{Q}\mathbb Z\) and \(c>0\), every clearing lift satisfies \(Dc\geq1\). Hence this house was released strictly before the repetition requesting it.
The suffix consequently needs only one additional batch record. Its house index is again affine in the repetition index and \(D\).
The final queue is also easy to update:
These formulas follow directly from the same removal-and-append argument.
Initially there are at most \(m\) vacancy intervals. Each aggregate block creates at most one additional inventory interval.
When a trace block crosses a source-interval boundary, the crossed interval is fully consumed and can be charged to its creation. Each aggregate block also needs at most one partially consumed source interval and, for root-endowment rotation, one additional suffix record.
Thus the number of batch records is \(O(m+B)\). Each record’s event word has polynomial length by Lemma 3.
All splitting masses are sums, differences, or minima of quantities in \(\frac{1}{Q}\mathbb Z\). Every emitted positive multiplicity \(q\) therefore satisfies \(Dq\in\mathbb Z_{>0}\) for every clearing denominator \(D\).
Fix any clearing denominator \(D\). We prove correctness by induction over the constructed blocks and their trace subdivisions.
Initially, every local state interval describes exactly the copies it represents, and every vacant-house interval describes exactly the corresponding houses.
At a block boundary:
The rotation formula also remains valid when a requested house was released by an earlier repetition of the same record, as proved in Section 5.2. Thus every expanded event is legal.
At the end of each episode, Lemma 1 restores the baseline order. This completes the induction. Because requests, priority, and copy-index refinement are deterministic, the expanded trace is precisely the specified execution.
Every role stage processes all agents of that role that remain, so all agents eventually leave. Accumulating each block’s assignment classes with multiplicity \(b\) gives the required \(x_{G,r,h}\), including \(h=\varnothing\). Summing the final vacancy intervals gives the required residual vacant masses. For every clearing \(D\), the corresponding finite counts equal \(D\) times these reported masses.
Finally, \(Q\) has bit length at most the sum of the input denominator bit lengths. All arithmetic stays on the grid \(\frac{1}{Q}\mathbb Z\), with values bounded by polynomial multiples of total input agent and house masses. Hence all intermediate numbers have polynomial bit length.
There are polynomially many aggregate blocks, local simulations, vacancy intervals, and trace records. Each local simulation has polynomial cost in \(a\) and \(m\). The complete algorithm therefore runs in time polynomial in \(m,a,\tau,L\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes a polynomial-time algorithm for the requested assignment masses, residual vacancy masses, and a batch trace agreeing with every clearing finite lift. I found no major or minor mathematical issues.
The proof depends essentially on the specified distance-first priority order and on house classes distinguishing both template and house role. Both assumptions are present in the task.
The prover addresses all required outputs and explicitly handles agreement for every clearing denominator, rather than only one finite lift or a limiting allocation.
The attribution to Theorem 6 is correct: the theorem states the finite-agent running-time bound with agents and houses explicitly listed. It does not establish rational-mass compression, and the prover correctly supplies a separate argument for that part. [Cited paper, Theorem 6](https://ifaamas.org/Proceedings/aamas2022/pdfs/p1446.pdf).
The compression argument does not rely on applying that discrete running-time bound to an exponentially large lift.
The episode invariant is valid.
The appeal to Lemma 2 for vacant-request propagation is a valid forward reference. Lemma 2 uses the path structure established before the vacant request; it does not assume the unproved conclusion that propagation finishes the episode.
Every promoted agent leaves before the episode ends. Since promotions preserve the relative order of other agents, the surviving agents return to the restricted baseline order. This justifies processing episodes independently at their boundaries.
The preference argument is correct at the level of individual houses, including copy-index refinement.
Before the first vacant request, own-endowment assignments and cycles create no globally vacant houses. Thus a waiting predecessor receives no newly available alternative during that part of the episode.
When the requested child leaves after taking a vacancy, the particular endowment previously requested by the predecessor becomes vacant. It remains eligible and remains preferred to every other eligible house. Choices that disappeared cannot invalidate that comparison.
The same reasoning applies successively along the pointer path. Intermediate released endowments are immediately consumed by their predecessors, leaving precisely the boundary effects listed by the prover:
The outside-option restriction is also correct. A selected tenant still has her own endowment eligible and strictly prefers it to the outside option.
The bound is valid.
An edge can be traversed downward at most once in an episode because control returns to its parent only after the promoted child leaves. Every selected-agent event other than a descent removes at least one agent.
A copy contains at most \(a\) agent roles, so the stated bound of \(2a\) selected-agent events is valid. Explicitly listing assignments, cycle participants, and releases does not introduce dependence on \(D\).
The stage decomposition follows from restoration of the baseline order after each episode.
At episode boundaries, an endowment becomes vacant only when its original owner is the episode root. Consequently:
The assertion about ancestors is also justified. All agent ancestors of a stage root have smaller distance and have already left. Any remaining ancestor encountered after descending from that root therefore belongs to the active pointer path.
These facts supply the hypotheses used in Lemma 5.
This central compression lemma is correct.
For a selected agent before the first vacant request, an eligible occupied endowment belongs either to a remaining child, to the agent herself, or to an active ancestor. Classes belonging to descendant roles cannot already have boundary vacancies because their stages have not occurred. Classes belonging to active nonroot ancestors likewise have not reached their owner stages.
Thus the root’s endowment class is the only possible overlap between an eligible occupied class and the boundary vacancy inventory.
For a tenant-rooted episode, every selected agent is a tenant and has the root’s endowment eligible as either her own endowment or an ancestor’s. Omitting vacant copies of that class therefore preserves all eligible class choices.
The concrete-index distinction is handled correctly:
An externally ending simulated episode cannot previously request the root’s endowment class: such a request would already terminate the episode. Hence the appearance of root-endowment vacancies does not change an externally ending event word.
The proposed block multiplicities are correct.
For an external-consuming episode, exactly one house from the selected external class is consumed. Therefore a block can continue for the minimum of its remaining interval mass and that class’s current vacancy mass.
Within a stage, each nonroot vacancy class can become empty at most once. Between such exhaustions, a fixed local-state interval has a fixed class outcome by Lemma 5.
Root-endowment vacancies introduce no additional class-outcome boundary:
The resulting bounds of at most \(\tau+am\) local-state intervals and \(B=O(a(\tau+am+m))\) aggregate blocks are valid.
All updates use sums, differences, comparisons, and minima of quantities in \(Q^{-1}\mathbb Z\). Thus every block boundary and positive multiplicity remains on that grid. Since every clearing \(D\) is a multiple of \(Q\), every expanded repetition count is a positive integer.
No denominator-dependent rounding is hidden in the construction.
The source class receives no releases during the current stage. Consuming its interval list from the lowest index therefore reproduces the specified refinement.
After splitting at source-interval boundaries, both root indices and external-house indices increase by one per repetition. The stated affine forms are correct. All remaining participants and internally requested houses belong to the root’s copy.
The queue calculation is correct.
An initial inventory of mass \(c\) contains exactly \(Dc\) houses. The first \(\min(Db,Dc)\) repetitions consume its initial entries in order. Once those entries are exhausted, repetition \(k\) consumes the house released at repetition \(k-Dc\), giving the stated index \(D\ell+k-Dc\).
Because \(c>0\) lies on the denominator grid, \(Dc\geq1\). The requested house is therefore always released before it is requested, including when both events belong to the same batch record.
The final-inventory formulas also check:
These formulas are uniform across all clearing denominators.
The interval-charging argument is valid. Each aggregate block creates at most one inventory interval. A source interval crossed completely during subdivision is consumed and can be charged once to its creation. Partial consumption and a rotation suffix add only a constant number of records per aggregate block.
Hence the trace has \(O(m+B)\) records, each with a polynomial-length event word.
The arithmetic bounds are sufficient. The least common multiple \(Q\) has polynomial bit length, and quantities remain on its grid with magnitude bounded by polynomial multiples of the input masses. Interval endpoints, multiplicities, and affine coefficients consequently have polynomial bit length.
Together with the polynomial block and simulation counts, this establishes polynomial running time.
The final induction tracks the necessary state: remaining-role intervals, exact vacancy intervals, next baseline root, and concrete indices.
The earlier lemmas justify each component of the induction. In particular, transient releases within an episode are handled by vacancy propagation, while the interval inventory records the state at episode boundaries.
Every stage exhausts its remaining roots, so all agents eventually leave. Assignment accumulation and final vacancy intervals therefore yield all requested masses, including assignments to the outside option. Their finite-lift counts equal \(D\) times those masses.
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.