| paper | d4-conf-ijcai-1995-0052 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper describes its theorems as giving performance-profile conditions for bounded-rational superadditivity, subadditivity, and core existence; those are game-property results, not computational guarantees. Its abstract's NP-completeness claim concerns the underlying domain problems, while the proposed configuration LP is not a computational result of the paper [IJCAI paper](https://www.ijcai.org/Proceedings/95-1/Papers/087.pdf). The coalition-welfare mirror is coherent, but the paper fails the required computational-result gate.
fails bit a — no named computational result to mirror
The proposed mirror covers aggregate coalition-welfare maximization; it does not cover the paper's results about stability, the core, bounded-rational superadditivity or subadditivity, or its five-center experiments.
I can make a plausible population mirror, but I can’t attach it to a qualifying anchor under your rule. The abstract says “these problems are NP-complete,” but does not name a coalition-structure problem as the object of a numbered result. The paper’s conclusion describes its theorems as conditions on performance profiles for bounded-rational superadditivity, subadditivity, and core existence. For example, the extended technical report’s Theorem 2.1, “BRS (sufficient condition),” says that if every pair of disjoint coalitions \(S,T\) satisfies \(c_{S\cup T}(r_S+r_T)\le c_S(r_S)+c_T(r_T)\) for all \(r_S,r_T\ge0\), then the game is bounded-rational superadditive for every computation price \(c_{\mathrm{comp}}\). That is a welfare condition, not a result that a computational problem is in P, NP-hard, or otherwise classified. So I see no qualifying numbered complexity anchor here; the abstract’s NP-completeness sentence cannot fill that role. ([IJCAI paper](https://www.ijcai.org/Proceedings/95-1/Papers/087.pdf), [extended technical report](https://www.cs.cmu.edu/~sandholm/cs15-892F15/sand95.pdf))
The strongest positive candidate is a high-multiplicity version of bounded-rational coalition-structure welfare maximization. Consider a large population of small dispatch firms that fall into \(\tau\) exact operational types: each type specifies its task bundle, resources, algorithm performance profile, and other attributes used by the model. Let \(\mu_t\) be the fraction of firms of type \(t\), with \(N\gg\tau\). The paper’s five-center experiment is too small to be this regime; a much larger network with repeated dispatch templates is the plausible setting.
For a coalition composition \(q\in Q_K=\{q\in\mathbb{Z}_{\ge0}^{\tau}:1\le\sum_t q_t\le K\}\), let \(c_q(r)\) be the domain cost its shared algorithm achieves after \(r\) units of computation, and let \(R(q)\) be its monetary return. At computation price \(\lambda\), its bounded-rational value is \(\nu(q)=R(q)-\min_{r\ge0}\bigl(c_q(r)+\lambda r\bigr)\). Given rational \(\mu\) and a threshold \(B\), ask whether there are \(y_q\ge0\) such that \(\sum_{q\in Q_K}q_t y_q=\mu_t\) for every type \(t\), and \(\sum_{q\in Q_K}y_q\nu(q)\ge B\). A solution is the vector \(y\): the normalized number of coalitions of each composition. In a discrete population, \(y_q\) would be restricted to multiples of \(1/N\); the continuous problem relaxes those counts while keeping each coalition’s composition integral. The cap \(K\) represents an operational limit on coalition size.
This asks the same welfare question the paper asks—how to partition agents into coalitions given each coalition’s computation-cost tradeoff—while making the population the continuous object. It covers coalition-structure generation and coalition value, not payoff division or core stability. The master problem is an LP when its configurations are explicit; when they are implicit, tractability turns on pricing over \(q\). I would expect tractability if that pricing problem is manageable, but route-cost computation may retain the vehicle-routing hardness mentioned by the paper. This proposed problem is therefore a plausible research question, not a result anchored by the paper’s numbered theorems.
The weakest point is the regime assumption: identical firms must really match in every respect the model uses, including tasks and algorithm performance. If those details make nearly every firm a separate type, then \(\tau\) grows with \(N\) and the population compression disappears.
The strongest negative point is that this paper supplies no qualifying computational result to continuize. Theorem 2.1 cited in the proponent’s own account gives a sufficient condition for bounded-rational superadditivity: it assumes performance profiles and concludes a property of the resulting game. It does not classify the complexity of a computational problem. The abstract’s claim that “these problems are NP-complete” concerns the underlying optimization problems agents solve, such as vehicle routing; the paper does not state a numbered complexity result for coalition-structure generation. Its formal results concern performance profiles, game properties, and core existence. On the requested anchor standard, there is nothing here to mirror.
The proposed mass-firm model is the strongest counterexample to a broader negative claim. It is coherent to group repeated firms by complete operational type and optimize over coalition configurations \(q\), with \(y_q\) recording their mass. I cannot honestly dismiss that as an inherently nonsensical high-multiplicity regime. But the resulting configuration LP is a proposed computational problem, not a continuous version of Theorem 2.1: it optimizes aggregate coalition value, while that theorem concerns superadditivity, and the paper does not give a complexity result for the proposed LP. It also takes \(\nu(q)\) as available input, while the paper notes that deriving performance profiles can itself require costly computation. These are reasons the proposed LP does not establish an anchor in this paper, not proof that the LP is unworthy of study.
So the defensible negative case is narrow but firm: the paper has no named computational-complexity result for which the programme’s mirror exercise is called. The broader claim that no worthwhile continuous question could be built from its coalition-formation model is weaker; the proponent’s configuration LP could be a sensible new project if its inputs and regime are justified.
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.