| paper | A Complexity Approach for Core-Selecting Exchange under Conditionally Lexicographic Preferences |
| authors | E. Fujita, Julien Lesca, Akihisa Sonoda, Taiki Todo, M. Yokoo |
| venue | JAIR 2018 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
Given finite good classes \(K\), complete types \(T\), rational mass vector \(\mu\), type endowments \(e_t\subseteq K\), and true LP-trees \(\tau_t\), run a fixed deterministic maximal-feasible-mass quotient of ATTC on supplies \(s_g=\sum_t\mu_t\mathbf{1}[g\in e_t]\), with each bundle \(B\subseteq K\) integral. For designated type \(t^\star\), compare the truthful output \(\nu^0\) with the output \(\nu^p\) when all mass \(\mu_{t^\star}\) reports a path \(p\); decide whether some \(p\) admits a coupling \(\pi\) with the two outcome marginals, support only on \(B'\succeq_{\tau_{t^\star}}B\), and positive mass on \(B'\succ_{\tau_{t^\star}}B\).
A distributional exchange market with \(K\) indivisible item classes and finite complete LP-tree/endowment types \(T\); \(\mu_t\) is type mass, \(s_g\) is class supply, the decision variable is a common path report \(p\) by \(t^\star\), and the objective is positive-mass Pareto improvement under \(\tau_{t^\star}\) after deterministic mass-ATTC.
The proposed maximal-mass cycle rule has not been proved to be independent of copy-level tie-breaking or exactly the normalized quotient of finite ATTC, and the coupling may encode coordinated cohort improvement rather than one agent's unilateral gain.
fatal: False
The mirror covers only Theorem 2, Beneficial-Misreport; it leaves Theorem 1, Corollary 1, Proposition 2, and the splitting and hiding results unmirrored.
The strongest positive case is a qualified but genuine one: the paper’s manipulation-hardness result has a natural high-multiplicity exchange-market analogue. My lead anchor is Theorem 2 (Beneficial-Misreport), proved in this paper; its proof is deferred to Appendix B.
The theorem concerns an exchange problem \((e,\tau)\) with indivisible goods, conditionally lexicographic preferences represented by LP-trees, and a designated agent \(i\). Let \(P\) be the subset of LP-trees that are paths, equivalently ordinary lexicographic preferences. The question is whether there exists a report \(\tau_i'\in P\) such that the ATTC outcome gives \(i\) a strictly better bundle under her true preference:
\[ \varphi_i(e,(\tau_i',\tau_{-i}))\succ_{\tau_i}\varphi_i(e,\tau). \]
Theorem 2 states that Beneficial-Misreport is NP-complete. Membership in NP follows because ATTC runs in polynomial time. NP-hardness is proved by a reduction from Monotone 3SAT: the manipulator’s possible reports encode choices of literals, while the ATTC cycles enforce consistency between positive and negative occurrences of variables. Thus the hardness is driven by the good-and-preference gadget, not merely by having many named agents.
I would mirror it with the following problem.
Continuous Beneficial-Misreport for Mass-ATTC. An instance consists of:
A type is complete: its members have the same endowment pattern, conditional preference tree, report space, and all other parameters used by the mechanism. The mass of good class \(g\) is
\[ s_g=\sum_{t\in T}\mu_t\,\mathbf{1}[g\in e_t]. \]
Goods remain indivisible at the individual level. The continuum only records aggregate mass: an allocation is a collection of numbers \(\nu_{t,B}\), where \(B\subseteq K\) is an integral bundle and \(\nu_{t,B}\) is the mass of type \(t\) receiving \(B\). It must satisfy
\[ \sum_B\nu_{t,B}=\mu_t \]
for every \(t\), and
\[ \sum_{t,B:g\in B}\nu_{t,B}=s_g \]
for every good class \(g\).
The rule is the type-level, mass version of ATTC. At each round, remaining good mass owned by agents currently holding bundle \(B\) points to the first still-available good class on the relevant LP-tree path. Directed cycle signatures are executed by their maximal feasible mass, transferring the pointed-to good mass to the corresponding owners; the used mass is removed and the process repeats. A fixed canonical ordering resolves equal cycle signatures. Equivalently, this is the exchangeable quotient of the finite ATTC execution on \(q\) copies of every type, where \(q\) clears the denominators of \(\mu\).
Let \(\nu^0\) be the truthful mass-ATTC outcome. For a path report \(p\in P\), let \(\nu^p\) be the outcome after every member of type \(t^\star\) reports \(p\) instead of \(\tau_{t^\star}\). The decision question is whether there exists \(p\in P\) that is beneficial for the manipulator population. Formally, there must be a coupling \(\pi_{B,B'}\) between the truthful and manipulated bundle distributions of \(t^\star\) such that
\[ \pi_{B,B'}>0\Longrightarrow B'\succeq_{\tau_{t^\star}} B, \]
and some positive mass satisfies \(B'\succ_{\tau_{t^\star}}B\). Thus no member of the manipulated cohort is worse off, and a positive mass is strictly better off. If the mass-ATTC outcome is type-symmetric, this reduces exactly to asking whether the common manipulated bundle is strictly preferred to the truthful bundle.
The regime is a large housing-exchange or allocation market: millions of students or households, but only finitely many recurring combinations of initial entitlement and conditional preference. For example, many students may hold the same room-category entitlement and the same conditional priorities over room, parking, and storage. A plausible regime has \(n\gg\tau\): a very large population, perhaps \(10^6\) participants, but only hundreds or thousands of distinct complete types. Per-capita supplies scale with the population, while each individual still receives an integral bundle.
This is a faithful mirror of the paper’s question. The mechanism is still ATTC; preferences are still LP-trees; the action is still a report restricted to a path; and the objective is still improvement under the true preference. The only forced modification is that a positive-mass cohort uses a common report. That is the natural high-multiplicity version of a manipulation when individual agents of an identical type are exchangeable. It is not an outcome-space relaxation: rooms and other goods remain indivisible.
I would expect this problem to be Class B, with hardness transferring. A rational profile \(\mu\) expands to a finite market with \(q\mu_t\) copies of each type. Conversely, the Appendix B construction can be lifted by replacing every gadget agent and good with many exchangeable copies. The variable-consistency and clause-selection structure remains in the good classes and LP-trees, while increasing the multiplicity merely scales all masses. The key technical obligation is a replication lemma showing that the mass-ATTC cycle flow is the normalized aggregate of those replicated finite executions. Once established, the Monotone 3SAT reduction should survive unchanged.
The further questions are substantial: whether the reduction remains hard when the number of types is fixed; whether minimum manipulator mass is tractable; whether approximate improvement changes the classification; and whether the paper’s split-account and hiding manipulations admit analogous mass formulations.
The weak point is that ATTC is originally defined on a finite graph of individually owned goods, and Theorem 2 concerns one named agent. In an atomless population, one individual has zero influence, so a literal unilateral manipulation disappears. My mirror therefore deliberately studies a coordinated positive-mass type cohort. The opposing reader can reasonably call that a coalition-manipulation problem rather than the exact original problem. The case remains credible because common reporting templates by a large homogeneous cohort are a natural high-multiplicity strategic action, but the replication and mass-ATTC semantics would need to be proved rather than assumed.
This mirror covers Theorem 2 only. It does not claim that the paper already contains a continuous-population result, and it does not claim that the paper’s core-selection theorem automatically extends to atomless coalitions. It is a new computational question anchored directly in the paper’s central NP-completeness theorem.
Theorem 2 is a genuine computational anchor, so the negative case cannot claim that the paper lacks a named complexity result. The objection is instead that its manipulation problem has no faithful high-multiplicity object.
In the paper’s actual model, \(e=(e_1,\ldots,e_n)\) is a partition of a finite set of heterogeneous goods. A complete type must therefore include the agent’s endowment. Two nonempty agents cannot have the same type: if \(e_i=e_j\), disjointness of endowments implies \(e_i=e_j=\varnothing\). Thus the only repeated exact type consists of agents with no goods, who do not participate in ATTC. Theorem 2’s reduction relies precisely on the opposite structure: one uniquely situated manipulator owns many named goods, while the gadget agents own distinct named goods with distinct roles.
The proposed repair—replace goods by classes and scale their supplies—is not merely continuizing the population. If copies remain distinct, their copy-level rankings and ownership labels are part of the LP-trees and endowments, so the copies are not one complete type. If copies are identified, the paper’s ATTC rule has been changed. ATTC points to a particular named good in a graph of individual vertices; a “maximal feasible mass cycle” over good classes is a new capacitated trading mechanism. LP-trees also impose strict comparisons over named goods, so interchangeable copies require a new preference language or an arbitrary tie-breaking convention. A canonical ordering may define a new rule, but it does not make that rule the quotient of ATTC automatically.
There is a second, independent problem with the objective. Theorem 2 asks whether the same agent receives a strictly better bundle. A distribution \(\nu_{t,B}\) records only how much mass receives each bundle; it does not preserve which member of the cohort received which bundle. The proposed coupling can match a manipulated bundle to a different person and call the cohort weakly better, even when some original members are worse off. Preserving identity requires tracking initial good-copy labels and execution histories, which removes the finite-type compression. Requiring a common report and a common outcome avoids that problem only by changing the question into coordinated positive-mass coalition manipulation.
The zero-mass limit does not repair this. A single agent has no effect on the aggregate ATTC state, so every report produces the same continuum outcome. Any nontrivial version must give a positive-mass cohort collective power. That may be an interesting new mechanism-design problem, but it is not the individual incentive problem proved NP-complete in Theorem 2; the paper neither defines nor studies such coalition manipulation.
This leaves the strongest possible positive rescue: introduce interchangeable good classes, define a new mass-ATTC rule, impose symmetric cohort reports, and study Pareto improvement of the cohort. That is a coherent project, but it requires inventing the mechanism, its semantics, and its incentive notion before one can even state the complexity problem. The result would be a new theory of capacitated ATTC, not a continuous mirror of the paper’s theorem. The negative case is therefore strongest as a modelling objection, not a complexity one. If ChoCo is willing to regard that substantial mechanism-and-objective replacement as an admissible mirror, the anchor survives; otherwise Theorem 2 does not provide a worthwhile continuous-population problem.
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.