| paper | d4-conf-aaai-2012-0139 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: The process can run for infinitely many rounds, already with \(m=2\), \(\tau=3\), and \(L=O(1)\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
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?
Represent agents and indivisible houses by types with rational population and supply masses; use type-level preferences, endowments, and priorities to run TTAS, tracking cycle transfers and any residual type splits. The aggregate allocation \(x_{pq}\) records the mass of type \(p\) assigned house type \(q\), with row sums \(\mu_p\) and column sums \(\nu_q\), while each individual still receives one house.
Theorem 5's counter uses a number of distinct preference and endowment roles that grows with the market, and the paper gives no bounded-support construction; preserving individual-house priorities may also make nominal clones behaviorally distinct.
fatal: False
The mirror covers only Theorem 5's execution-time lower bound for TTAS. It leaves the core, strict-core, Pareto-optimality, strategy-proofness, and mechanism-generalization results unexamined.
The strongest mirror is the paper’s result about TTAS’s running time, rather than its claims about stability or efficiency. It targets the same issue the paper settles: how long the TTAS procedure can take.
The anchor is Theorem 5, proved in this paper. It constructs housing markets \(M_k\) with \(|N_k|=|H_k|=2k+1\) and priority orders \(R_k\) such that TTAS takes at least \(2^k=2^{(|N_k|-1)/2}\) steps to terminate. The proof makes the procedure simulate a binary counter. This is an exponential lower bound for that mechanism’s execution; it is not an NP-hardness result for finding a housing allocation by any algorithm.
A continuous counterpart could be called Mass-TTAS Iteration Complexity. An instance has finitely many agent types \(P\) and house types \(Q\), with rational masses \(\mu_p\) and \(\nu_q\) summing to one. Each agent type specifies a complete weak preference order over house types and an initial endowment type; the masses of agents endowed with each house type equal its supply. A strict priority order on house types supplies TTAS’s tie-breaking rule.
The procedure operates on type-level mass. Build the current agent–house graph from the types’ top remaining houses and their current holders. Apply TTAS’s paired-symmetric absorbing-set removals and its priority-based pointing rule. When a cycle is implemented provisionally, move the largest mass that can follow that cycle, splitting a type into residual and moved mass when necessary. An aggregate output \(x_{p,q}\) records what fraction of each agent type receives each house type; its row and column sums match the input masses, while each individual still receives one whole house. The computational question is whether this TTAS mass process always finishes in a number of rounds polynomial in the number of supported types and the input bit length, or whether a family of such markets forces superpolynomially many rounds. There is no welfare objective to optimize: the task is to produce the allocation prescribed by the mechanism.
A plausible regime is a large exchange program or housing pool with many participants drawn from a small set of recurring preference-and-endowment profiles, such as standardized cohorts of residents exchanging comparable units. The mass is the fraction of the population in each profile. This is a high-multiplicity regime when the number of participants is much larger than the number of supported profiles. It is plausible for their problem because it retains the core ingredients of their housing market—endowments, indifferences, priority-based tie-breaking, and the TTAS procedure—while asking whether the exponential behavior survives aggregation.
I would expect the lower-bound phenomenon to persist as the number of types grows: Theorem 5’s counter is driven by a sequence of structural roles and cycles, not by needing one distinct behavior per participant. That makes this a likely hardness-transfer case in the programme’s trichotomy. But the theorem alone does not establish the continuous lower bound. Questions for a prover include whether type-level cycle execution can compress the counter’s rounds, how the bound depends on support size versus mass bit length, and whether producing a compact final allocation can be faster than following TTAS’s full execution.
The mirror covers Theorem 5 only. The paper’s stability and Pareto results may motivate studying aggregate allocations, but they are not needed to make this case.
The weakest point is the type-level definition of TTAS. The original procedure uses individually labelled houses and a priority order over them; the mass version must specify how cycle selection and tie-breaking work when a positive mass of equivalent agents and houses moves together. That is a real extension of the mechanism, not a result already implied by the paper. The mirror remains plausible if the authors accept a class-level priority and mass-cycle semantics as the natural high-multiplicity form of TTAS. If those choices change its behavior too much, Theorem 5 may have no convincing continuous analogue.
The only serious anchor is Theorem 5: it gives an exponential execution-time lower bound for TTAS. That is a computational result, so I cannot dismiss the paper as having no result to mirror. The strongest case against the proposed mirror is that the theorem’s witness is not a high-multiplicity instance. In \(M_k\), the agents have indexed, distinct top-house sets and distinct endowments; the number of behaviorally complete types therefore grows with \(|N_k|\). The binary counter is built from those distinct roles.
Cloning each role into a cohort is the natural repair, but it exposes a modeling choice central to TTAS. The mechanism’s priority order is over individual houses, and its tie-breaking uses an agent’s currently endowed house. Preserve those labels and priority positions, and the clones may behave differently; treating those differences as part of type drives the support size back up. Collapse houses into types and use a priority order over types, and the resulting procedure is a new mechanism. Its graph, absorbing sets, and mass-cycle steps need definitions of their own, and the paper’s counter does not establish that they retain the same sequence of states. In particular, “move the largest mass that can follow the cycle” is a proposed transition rule, not a consequence of TTAS.
That is a substantial weakness in this particular case for a mirror, but it does not defeat the best version. One could study exact TTAS on replicated role templates with a compact priority order and ask whether its exponential execution persists as multiplicities grow. That is a clear high-multiplicity computational question, and the authors could recognize it as their problem. Whether the counter survives would be the result to prove, not a reason the question lacks value.
So the negative case is weak: Theorem 5 does not itself exhibit exponential behavior at small type support, and the proposed mass-TTAS needs a principled definition. But an exact high-multiplicity formulation remains plausible. I cannot honestly argue that no worthwhile continuous mirror survives.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.