| paper | Reducing Optimism Bias in Incomplete Cooperative Games |
| authors | — |
| venue | AAMAS 2024 |
| filed under | coalition · wvg |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper contains computational procedures and named principal problems, but no numbered result asserting a qualifying complexity, algorithmic, parameterized, or approximation theorem. Proposition 3.9 is structural, and the relevant greedy guarantee is external. The proposed typed-mass principal problem is a plausible research extension, but it cannot repair the missing computational anchor.
fails bit a — no named computational result to mirror
The proponent concedes that no numbered result here establishes a computational guarantee; the cited greedy theorem does not belong to this paper.
fatal: True
The candidate covers the offline and online principal's query-selection problems, but leaves the paper's structural propositions, non-supermodularity criteria, and empirical results without qualifying computational mirrors.
The best honest positive case is that the paper has a very natural population-continuous extension, but it does not contain a qualifying named computational-complexity anchor. I would therefore not submit it as a full positive mirror under ChoCo’s strict rule.
The closest anchor is Proposition 3.9, proved in this paper: for \(|N|\le4\), the utopian gap is supermodular. Together with the cited \((1-1/e)\) greedy theorem of Nemhauser, Wolsey, and Fisher, this supports an approximation guarantee for the offline greedy procedure in that bounded-player regime. But Proposition 3.9 itself is a structural statement, not a numbered \(P\), NP-hardness, FPT, or approximation theorem. Theorem 2.5 is a restatement of prior work; Propositions 3.4–3.6 give formulas and monotonicity; Proposition 3.10 gives non-supermodularity. None is a theorem-level computational classification. The \(O(2^{2n})\) and \(O(2^n)\) runtime remarks concern Algorithms 1 and 2 but are not presented as named complexity results.
If the anchor requirement were relaxed, the strongest mirror would be Continuum Principal’s Problem for Incomplete Cooperative Games. Take finitely many complete player types \(\Theta=\{1,\ldots,\tau\}\), such as interchangeable employees with the same role, skills, costs, and contribution behaviour. Let \(\mu_t\) be the fraction of the workforce of type \(t\). A coalition is represented by a composition vector \(z\in[0,\mu]\), where \(z_t\) is the mass of type \(t\) assigned to it. Its value is \(V(z)\), with \(V(0)=0\) and
\[ V(z)+V(z')\le V(z+z') \]
whenever \(z+z'\le\mu\). The principal does not know \(V\), but has a prior \(\mathcal F\) over superadditive, piecewise-linear games. Querying a composition \(z\) reveals \(V(z)\).
For a candidate completion \(W\), define the type-\(t\) Aumann–Shapley claim by
\[ a_t(W;\mu)=\int_0^1 D_tW(\lambda\mu)\,d\lambda, \]
where \(D_t\) is the almost-everywhere derivative in coordinate \(t\). After queries \(Q\) and observations \(y\), let \(\mathcal F(Q,y)\) be the consistent completions and define
\[ G_\mu(Q,y) = \sum_{t=1}^{\tau} \mu_t\max_{W\in\mathcal F(Q,y)}a_t(W;\mu) - V(\mu). \]
The offline problem is to choose \(k\) composition queries minimizing
\[ \mathbb E_{V\sim\mathcal F} \left[ G_\mu(Q,V|_Q) \right]. \]
The online problem asks for a policy selecting each next composition from previous answers. A solution is respectively a query set or an adaptive policy, together with its expected final gap.
This is recognizably the paper’s principal problem: coalition values remain expensive to obtain, optimistic completions generate inflated Shapley claims, and the action is still revelation of coalition values. The continuous object is genuinely the population, not the prior: many exchangeable employees or data sources are represented by \(\mu\), while \(\mathcal F\) remains merely an uncertainty model.
The high-multiplicity bridge is plausible. If \(\mu_t=n_t/q\), create \(n_t\) clones of each type and define
\[ v_q(S)=V\!\left(\frac{|S\cap T_1|}{q},\ldots, \frac{|S\cap T_\tau|}{q}\right). \]
Composition queries correspond to clone coalitions, and the normalized finite Shapley claims converge to the Aumann–Shapley quantities above under the piecewise-linear regularity assumption. This makes the model an extension of the paper’s setting rather than an unrelated divisible-resource problem.
I would expect a structured version with fixed \(\tau\), finite-support piecewise-linear priors, and a finite admissible query catalogue to be tractable by dynamic programming or configuration-style optimization. The unrestricted version may instead be Class C: informative-query selection over a continuous composition space could itself encode hard active-learning problems. Further questions include whether greedy retains a \((1-1/e)\) guarantee beyond the paper’s \(|N|\le4\) result, whether finite clone instances approximate the continuous gap with bounded additive error, and whether the completion envelopes admit polynomial-time separation.
The weakest point is decisive: this mirror requires replacing finite-player Shapley values by their atomless Aumann–Shapley limit, and the paper proves no theorem connecting the two. More fundamentally, because the paper has no named computational result of the required kind, the proposed problem is a compelling author-recognizable research extension, not a valid mirror of a named complexity result.
The decisive objection is the one the proponent already concedes: this paper contains no qualifying named computational result. Proposition 3.9 is a structural fact about supermodularity for at most four players; Proposition 3.10 is a structural non-supermodularity criterion. The \(O(2^{2n})\) and \(O(2^n)\) observations describe implementations, but are not numbered complexity, approximation, or parameterized results. The \((1-1/e)\) guarantee comes from an external theorem and is not established here as a theorem about the paper’s principal problem. Under ChoCo’s source rule, there is therefore no result to mirror.
Proposition 3.9 cannot be rescued by treating it as the anchor. Its proof is a finite case analysis for \(n\le4\), where \(n\) is the number of named players, not the number of repeated types. Keeping \(n\le4\) gives no high-multiplicity regime. Replacing \(n\) by a type count \(\tau\) changes the statement: the query universe is no longer \(2^N\), the characteristic function is no longer an arbitrary function on coalitions, and the gap is no longer the paper’s Shapley gap. One would need a new theorem saying that the aggregate query objective over composition vectors is supermodular. Nothing in Proposition 3.9 implies that, and the Aumann–Shapley construction in the proponent’s model does not supply it. Thus the proposed greedy approximation is a new conjectural result, not a continuous version of the paper’s theorem.
The proposed continuum principal problem is mathematically plausible, but it is a re-modelling rather than a faithful mirror. The paper has a finite set function \(v:2^N\to\mathbb R\), with one query for one coalition of named players. The proposed model replaces this by a function \(V\) on the continuum of mass compositions \(z\). To make that legitimate, it must impose exchangeability: coalitions with the same type-composition must have the same value. That is a substantial restriction on the games in the paper. If it is not imposed, type masses lose precisely the identity information needed to determine coalition values. If it is imposed, the problem becomes an anonymous typed-game or active-learning problem that the paper never formulates.
The Aumann–Shapley replacement deepens the gap. In the finite game, the objective sums the separate maxima of named players’ Shapley values. In the atomless model, individual players have zero mass, so the objective must use a per-unit derivative and integrate along a ray. That may be the right new object, but it is not obtained by merely replacing counts with masses. The claimed clone convergence needs assumptions on \(V\), normalization, query access, and limiting sequences, and none is proved in the paper. Distinguished roles such as the factory owner also expose the issue: a single exceptional player becomes measure zero, while replicating the role changes the game.
The strongest repair would retain indivisible clone coalitions, define a typed characteristic function on integer composition vectors, use the exact finite Shapley value, and then study a carefully specified \(n_t\to\infty\) limit. That is a sensible high-multiplicity research programme. But it is a new extension requiring fresh definitions and convergence theorems; it does not mirror any named computational result here. Allowing arbitrary real compositions instead produces a different continuous query-learning problem with an infinite-dimensional function and an unspecified representation or oracle model. Restricting the queries to a finite catalogue removes that issue but leaves an ordinary finite typed high-multiplicity problem.
So the negative case is strong as a ChoCo screening judgment: there is no qualifying computational anchor, and the apparent anchor and the best proposed replacement both fail the direct-mirror test. It is not an impossibility claim about cooperative games generally. A typed, high-multiplicity theory of incomplete cooperative games could be worthwhile—but it would be a new paper inspired by this one, not a continuous mirror of its results.
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.