| paper | d4-conf-aaai-2016-0758 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The numbered theorems establish incentive-ratio bounds, but assert neither that an object can be computed nor that computing it is hard. The proposed continuum coalition model is coherent, yet extending its bound would be an analytical question, not a computational mirror of a result in this paper.
fails bit a — no named computational result to mirror
The proposed model connects most directly to Theorem 11’s coalition bound and Theorem 4’s unilateral bound; it leaves Theorems 7 and 9 and the unbounded-ratio example aside. These are incentive results, not computational results.
There is a plausible continuous-population mirror here, but I can’t give it a qualifying anchor under your rule. The paper’s numbered theorems establish bounds on strategic incentives, not complexity classifications. For example, Theorem 11, proved here, says that for homogeneous WGS utilities a coalition \(S\)’s incentive ratio is at most \(1/(1-\alpha_S)\), where \(\alpha_S\) is the coalition’s maximum total share of any item across market equilibria. Theorem 4, also proved here, bounds the market’s incentive ratio by \(2\) when all utilities satisfy WGS. Neither theorem says that a computational problem is in \(P\), NP-hard, or otherwise classifies its complexity. The paper’s references to Nash-equilibrium hardness are background results from other papers, not anchors proved here.
The strongest nearby mirror is a continuum coalition incentive-ratio problem. Let a unit-mass society have distribution \(\mu\) over buyer types \(t=(u_t,e_t)\), where a type specifies the buyer’s complete utility and endowment. Normalize per-capita supplies and total endowment to one. A competitive equilibrium consists of prices \(p\) and a measurable allocation \(x(t)\), with each buyer optimizing \(u_t\) subject to \(p\cdot x(t)\le e_t\), and market clearance \(\int x_j(t)\,d\mu(t)=1\) for every item \(j\).
Given a coalition submeasure \(\nu\le\mu\), ask for the supremum utility-improvement factor achievable by measurable reports of coalition members’ utilities and endowments, subject to no coalition member becoming worse off. A solution is a report profile and a resulting equilibrium; the objective is the essential supremum, over coalition members, of reported-outcome utility divided by truthful-outcome utility. This is a natural high-multiplicity regime: a large market of buyers drawn from a relatively small set of utility-and-endowment types. The paper itself discusses replicated large markets and collusion, so its authors would likely recognize the connection.
The natural result to investigate is whether Theorem 11’s bound extends to this model, with \(\alpha_\nu\) defined as the coalition’s maximum aggregate share of any item. I would expect a direct analytical extension under suitable regularity assumptions. But that is not a tractability or hardness prediction in the programme’s sense: the proposed result is still an incentive bound, not a complexity classification.
The main weakness is that a nonatomic population makes any single buyer’s mass zero, so a unilateral deviation cannot affect prices and has incentive ratio \(1\). A nontrivial mirror therefore needs positive-mass coalitions, or a finite-market approximation retaining individual atoms. That makes the coalition result the best fit, but it does not supply the required named computational anchor.
The decisive problem for ChoCo is that this paper proves no computational result. Theorem 4 bounds the incentive ratio for WGS markets; Theorems 7, 9, and 11 refine such bounds under additional assumptions. They do not classify a problem’s complexity or give an algorithm. The paper’s references to Nash-equilibrium hardness are background from other work, not results proved here. So there is no named computational result here to anchor a ChoCo mirror.
Theorem 11 is the proponent’s strongest candidate, and its proposed continuous coalition model is coherent: a positive-mass group of buyers can share utility and endowment types, and its aggregate share of each item can remain nonzero. But that model points toward an analytic question—whether the \(1/(1-\alpha_S)\) bound extends to measurable populations—not a complexity question. Theorem 4’s unilateral version degenerates in an atomless market: a single buyer has zero mass and cannot move prices. Allowing positive-mass coalitions avoids that problem, but it still yields a bound to prove, not an algorithmic result to mirror.
One could make a computational question by restricting utilities to finitely encoded classes and asking for the most profitable coalition reports in a given market. That would be a new problem in algorithmic market design. The paper does not specify an encoding or a report space for this task: its utility class consists of general concave functions, and its theorems bound gains across markets rather than compute an optimal deviation for an instance. Choosing a representation, coalition input, and deviation domain would therefore determine the computational problem, rather than merely continuize one of the paper’s results.
This is a strong case against a *ChoCo mirror of the paper’s results*, not proof that no useful research question could grow out of it. A large-market coalition question may be worthwhile in its own right. But the proponent’s best version remains an analytical extension, while its computational version needs substantial new choices that the paper does not motivate. The absolute claim that no scenario could ever be worthwhile is weaker: the paper’s market setting naturally admits high-multiplicity populations, but that fact alone does not supply the computational anchor the programme requires.
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.