| paper | d4-conf-atal-2021-0036 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
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\}}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 6.5
statement extracted from the paper’s text layer
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\)?
A continuum of copies of a fixed finite rooted tree, with mass \(\mu_\alpha\) on each complete branch-profile type. Each copy retains its finite network and integral house assignments; the reported result aggregates those assignments into fractional masses by position and house class.
A unilateral deviation in one branch has zero mass in the continuum aggregate, so this mirror does not establish a nontrivial atomless incentive guarantee; the SP and SC4N claims remain branch-local.
fatal: False
Covers Theorem 6.5 for repeated bounded rooted-tree branches; leaves the general-network impossibilities and the preference-domain and star-network characterizations aside.
The paper has no named theorem establishing NP-hardness, membership in P, or a parameterized complexity result. Theorems 4.3 and 4.7 are mechanism-existence impossibilities, not computational hardness results, so I would not use them as hardness anchors. The strongest constructive anchor is Theorem 6.5, proved in this paper: when the social network is a directed tree rooted at the moderator, Modified TTC satisfies strategy-proofness and the strict core for neighbors (SC4N). In full, no agent can benefit by misreporting their preference or hiding followers, and the outcome has no blocking coalition consisting of a single agent or a parent–child pair, where the coalition reallocates its own endowments so that everyone weakly improves and someone strictly improves. The theorem covers arbitrary strict preferences on that tree.
My lead mirror is Mass-Modified-TTC for repeated tree branches. Fix a finite rooted tree \(R\) with \(d\) exchange positions beneath the moderator. Imagine a large housing system made of many copies of this tree: for example, repeated residential clusters with the same hierarchy, standardized house classes, and a small number of recurring preference profiles. Each branch has one unit of each house class, and a branch profile \(\alpha\) specifies the strict ranking at every position. The continuum instance gives binary-rational masses \(\mu_\alpha\) over a finite support \(A\), with \(\sum_{\alpha\in A}\mu_\alpha=1\). Its types are \((\alpha,v)\), where \(v\) is a position in \(R\); each type has mass \(\mu_\alpha/d\), a ranking, an endowment class, and a network role. The number of branches grows while \(d\) and the number of supported profiles remain moderate.
The input also specifies reported rankings and any hidden outgoing links. The task is to compute the exact assignment produced by Modified TTC and return the mass-allocation table \(y_{\beta,v,w}\): the mass of position-\(v\) agents in reported branch profile \(\beta\) who receive house class \(w\). Each individual still receives one indivisible house copy; \(y\) records cohort averages, which may be fractional. The branch profile distribution preserves which agents are linked within each copy. There is no welfare objective in Theorem 6.5 to optimize: the faithful computational question is the exact mechanism-output problem, with strategy-proofness and SC4N as guarantees of the rule.
I expect this bounded-template problem to be tractable: run Modified TTC once for each supported reported branch profile and aggregate the results, giving time polynomial in \(d\), the support size \(\tau\), and the input bit length \(L\). This is the tractable direction, though not a strong ChoCo result: the finite Modified TTC algorithm is already straightforward, so the continuum mainly gives exact high-multiplicity aggregation. It does not show that discrete hardness dissolves.
The mirror’s plausibility is narrow but real. The authors study exactly a tree network, house exchange, hidden follower links, and Modified TTC; repeated tree-shaped housing clusters give those ingredients a plausible high-multiplicity regime. The mirror covers Theorem 6.5 only. It does not cover the paper’s general-network impossibilities or its preference-domain and star-network characterizations.
The weak point is that the mirror relies on repeated, bounded tree branches with standardized house classes. Modified TTC keeps exchanges within a branch, so the continuous computation amounts to batching a finite mechanism across profile types. A continuum model for one large, irregular, interconnected housing network would be more faithful to a broader market, but Theorem 6.5 does not establish that such a model has finite-time TTC behavior or an efficient solution.
The strongest objection is that the paper has no named complexity result to continue. Theorem 6.5 proves that Modified TTC has strategy-proofness and SC4N on a finite tree. Theorem 4.3 and Theorem 4.7 are impossibility results about mechanisms, while Theorems 5.2 and 6.1 characterize when TTC has a property. None asks for the complexity of computing an optimum or classifies a computational problem. The proponent adds an output-computation problem after the fact: run the stated mechanism and report its assignments.
The repeated-branch version is coherent, and I would not reject it because houses are indivisible or because high-multiplicity housing is implausible. But its tree structure isolates the copies: Modified TTC cannot trade between incomparable branches. For each supported branch profile, run the finite mechanism once and weight its outcome by that profile’s mass. That gives the proposed table in \(O(\tau\,\mathrm{poly}(d,L))\) time. The strategy-proofness and core guarantees apply branch by branch; the mass aggregation does not test how either guarantee changes in a continuous society. It is a compressed way to batch a known finite computation.
A more ambitious mirror would use one growing, interconnected population tree or allow cohorts to split across allocations. Then the input must preserve which agents are linked, and how entire branch profiles are correlated; a distribution over individual preference types does not specify that structure. In an atomless model, ordinary two-agent blocking and an individual’s effect on aggregate mass also need new definitions. Keeping finite nodes whose reports can affect large downstream populations, or making positive-mass groups the strategic actors, could address those issues—but that introduces a new model and new guarantees that Theorem 6.5 does not establish.
So the negative case is strong against this paper as a ChoCo complexity anchor: its best mirror is a narrow aggregation exercise, and a less trivial version would need substantial new modeling before it could claim the theorem’s result. It is not an airtight case that no worthwhile scenario exists. Repeated standardized housing clusters are plausible, and a programme interested in compressed high-multiplicity implementation might value the exercise. I would recommend against prioritizing it under the programme’s computational-results criterion, with limited confidence in the broader claim that no scenario could be worthwhile.
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.