| paper | d4-conf-aaai-2026-3857 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 1
statement extracted from the paper’s text layer
For a market with
The initial type distribution does not describe how private reward histories diverge over time, and the case does not fully specify how aggregate rationing preserves decentralized information and TTC behavior.
fatal: False
The mirror concerns Corollary 1’s decentralized, single-cycle regret lower bound. It leaves the decentralized upper bound, the centralized anytime guarantee, and the paper’s broader lower-bound theorem unmirrored.
The strongest honest mirror is the decentralized lower bound, because it asks whether learning one population’s preferences imposes regret on other members of the market.
The lead anchor is Corollary 1, proved in this paper. It states that there is a single-top-trading-cycle bandit instance with Bernoulli rewards on which a player’s regret is at least \(\Omega(N\log T/\Delta_{\min}^2)\), for decentralized uniformly consistent algorithms. The paper derives this from an instance where many other players must explore the focal player’s core-matched arm; that exploration causes regret for the focal player. This is a regret lower bound, not an NP-hardness result.
A plausible regime is a large housing exchange with many households but relatively few recurring preference and endowment archetypes—for example, cohorts trading among standardized house categories. A type \(t\) would specify the household’s strict ranking of categories, its Bernoulli reward law for each category, its endowed category, and its feedback and communication rights. Its mass \(\mu_t\) is the fraction of households of that type. Each household still receives one whole house; category supplies scale with the population. This is a setting-level claim: \(M\) households can be much larger than the number \(\tau\) of types.
I would pose the mirror as the type-mass cycle regret lower-bound problem. An instance consists of rational masses \(\mu_t\) summing to one, \(\tau\) house categories with supplies \(q_h\), and for each type an endowment category, a strict category ranking, and Bernoulli reward distributions \(\nu_{t,h}\). Restrict first to equal-mass types arranged in a single TTC cycle: type \(t\)’s core assignment is its successor’s endowed category, and the category supplies balance those assignments. In each round, a decentralized policy induces a proposal flow \(x_{t,h}\), with \(\sum_h x_{t,h}=\mu_t\). Category \(h\) matches up to its supply \(q_h\); unmatched applicants get no reward. Individuals observe only their own reward or rejection and cannot share observations. The benchmark is the type-level TTC core flow, and \(R_t(T)\) is the expected regret per member of type \(t\).
The question is whether every uniformly consistent decentralized policy must satisfy a mass-weighted KL lower bound. For a focal type \(t_0\), the natural candidate is
\[
\liminf_{T\to\infty}\frac{R_{t_0}(T)}{\log T}
\ \geq\
\sum_{s\ne t_0}\frac{\mu_s}{\mu_{t_0}}\,
\frac{\Delta_{t_0}}
{D_{\inf}\!\left(\nu_{s,h^*(t_0)},\,U(s,h^*(s)),\,\mathcal P\right)}.
\]
Here \(h^*(t)\) is type \(t\)’s core house category, \(\Delta_{t_0}\) is its relevant core-regret gap, and \(D_{\inf}\) is the information cost of distinguishing the source type’s reward law from one that changes its preferred category. The solution would be a proof of this bound, or a uniformly consistent policy and instance that violate it. With equal masses, the bound predicts a \(\tau\log T\) term, echoing Corollary 1’s \(N\log T\) term. I expect the weighted version to be approachable by adapting the paper’s change-of-measure argument; it would also test whether the bound is tight under aggregate capacity matching.
The authors should recognize the question’s core: stochastic preference learning, decentralized proposals, the TTC benchmark, and regret imposed on one group by another group’s exploration all remain. The scope is only the decentralized single-cycle lower-bound result; this does not mirror the centralized anytime algorithm or the paper’s other claims.
The soft spot is substantial: the paper’s multiplier comes from distinct, named players and individually owned arms. Aggregation replaces those with type masses and category capacities, so the collision process changes. For fixed \(\tau\), the proposed bound depends on \(\tau\), not on the total household count \(M\); if one insists on recovering the full \(N\) factor, the support may need to grow with \(N\), weakening the high-multiplicity case. This is a credible continuous research question, but the original lower bound does not automatically transfer.
Corollary 1 is the proponent’s strongest anchor, but its lower bound measures the information needed to learn unknown rewards, not the computational complexity of a social-choice problem. The \(N\log T\) term comes from distinguishing reward distributions; once preferences are known, the paper computes the core with TTC. Theorems 1 and 3 likewise bound regret for learning algorithms. A continuous version would be a problem about regret in decentralized bandit markets. That could be worthwhile on its own, but it does not fill ChoCo’s stated gap in the complexity of computational social choice.
The strongest version of the proposed mirror is coherent: take a large market with \(\tau\) recurring types, each fully specified by its preferences, endowment category, reward laws, and information rights, and scale house-category capacities with the population. But Corollary 1’s proof ranges over \(N-1\) separately changeable player–arm reward distributions. With repeated types, copies share those distributions and can explore concurrently. Recovering \(N\) independent experiments requires almost every person to differ in a problem-relevant characteristic, so the support grows with the population. The support-sensitive question that remains—how type masses and capacities affect regret—is a new statistical learning question, not the lower bound’s original computational question.
There is a deeper modeling cost. To preserve distinct houses and the paper’s all-or-nothing collision rule, the model retains named owners and does not compress naturally to a few types. To aggregate houses into categories with mass capacities, the model needs a rule for rationing oversubscribed mass and a core concept for that market. It also needs to represent private learning histories: identical initial types acquire different observations, so a finite list of initial types does not by itself describe who knows what over time. Giving agents shared information can keep the state compact, but changes the decentralized learning problem. These choices can define a sound mass-market bandit model; the paper’s result does not supply a compact computational problem for it.
I would therefore reject Corollary 1 as a strong ChoCo anchor, while recording the type-mass regret problem as a plausible adjacent research lead. The negative case is not airtight: large markets with recurring types are credible, and a support-sensitive regret theorem could be useful. Its weakness is that defeating the proposed model requires showing a mismatch of research object, not that the continuous market is incoherent or uninteresting.
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.