| paper | Approximating the Core via Iterative Coalition Sampling |
| authors | — |
| venue | AAMAS 2024 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given rational type weights \(w_a>0\), masses \(\mu_a\) with \(\sum_a\mu_a=1\), quota \(q\), and accuracy \(\eta>0\), let mass coalitions be \(z\in\prod_a[0,\mu_a]\) with \(\nu_\mu(z)=1\) exactly when \(\sum_a w_a z_a\ge q\). Find a payoff density \(y\ge0\) with \(\sum_a\mu_a y_a=1\) and an \(\eta\)-accurate estimate of \(\min_y\max_{z}(\nu_\mu(z)-\langle y,z\rangle)\), together with a payoff whose every mass-coalition deficit is within \(\eta\) of optimal.
A high-multiplicity weighted voting game with \(\tau\) exchangeable agent types, type masses \(\mu_a\), and per-unit voting weights \(w_a\). The decision variable is the payoff density \(y_a\); the objective minimizes the worst deficit over mass coalitions, with exact separation for the robust least-core LP given by fractional knapsack.
The proposed fractional-knapsack separator handles worst-case least-core deficits but does not directly maximize the mass-normalized loss used in Theorem 2, so the claimed transfer of that theorem's computational certification is incomplete.
fatal: False
The mirror covers the least-core approximation framework, Theorems 2 and 3 as mass-normalized guarantees, and weighted voting games; it leaves induced subgraph games, marginal contribution networks, and the XAI experiments untreated.
The strongest positive case is a high-multiplicity mirror of the paper’s weighted voting and least-core problems. The paper contains no named theorem classifying a problem as \(P\), NP-hard, W[1]-hard, or FPT; its named results are convergence and approximation guarantees. I would therefore anchor the case on Theorem 2 and Theorem 4, both proved in the paper using standard results from elsewhere.
My lead is the following problem, which I would call \(\textsc{WeightedVoting-LeastCore}_{\infty}\).
There are \(\tau\) agent types \(a\in[\tau]\). Type \(a\) has voting weight \(w_a>0\), and occupies mass \(\mu_a\), where \(\sum_a\mu_a=1\). A coalition is no longer an integer subset of named agents, but a mass vector \(z\in Z_\mu:=\prod_a[0,\mu_a]\). Its value is exactly the paper’s weighted-voting value applied to mass:
\[ \nu_\mu(z)= \begin{cases} 1 & \text{if }\sum_a w_a z_a\ge q,\\ 0 & \text{otherwise.} \end{cases} \]
A payoff density \(y_a\ge0\) is paid to each unit of type-\(a\) mass, with \(\sum_a\mu_a y_a=1\). Coalition \(z\) receives \(\langle y,z\rangle=\sum_a z_a y_a\). Its least-core value is
\[ \varepsilon_\infty^\star = \min_{y\ge0:\,\sum_a\mu_a y_a=1} \; \max_{z\in Z_\mu} \bigl(\nu_\mu(z)-\langle y,z\rangle\bigr). \]
Given rational \((w,\mu,q)\) and an accuracy parameter \(\eta>0\), the problem asks for a type-level payoff density \(y\) and an estimate \(\widehat\varepsilon\) such that \(y\) violates no coalition constraint by more than \(\widehat\varepsilon+\eta\), and \(\widehat\varepsilon\) is within \(\eta\) of \(\varepsilon_\infty^\star\).
This is recognisably the same problem as the paper’s Definition 4: the same threshold characteristic function, the same transferable utility, the same core stability condition. The only change is the high-multiplicity regime. A plausible setting is a large federation of resource units, local authorities, data providers, or compute providers. There may be millions of units, but only a small number of standard capacity classes. Units of the same class have the same voting weight, outside options, and payment rules. Thus \(N\) is enormous while \(\tau\) may be at most a few dozen or a few hundred. Mass is the honest quantity: the contract is about what fraction of each resource class can form a successful coalition, not about identifying a particular unit.
This is not merely making the payoff vector fractional. The continuous object is the society: \(\mu_a\) records the fraction of the population of each type. The payoff is still an allocation required to stabilize every coalition.
The expected classification is Class A. Although there are infinitely many possible mass coalitions \(z\), separation is easy. Given \(y\), the most threatening winning coalition solves
\[ \min\left\{\sum_a y_a z_a: \sum_a w_a z_a\ge q,\; 0\le z_a\le\mu_a\right\}. \]
This is a fractional knapsack problem: sort types by \(y_a/w_a\), fill them in order, and use at most one partially filled type. Hence a violated core constraint can be found in polynomial time in \(\tau\) and the input length. The least-core problem is therefore a finite-dimensional LP with a polynomial separation oracle, despite its continuum of coalition constraints.
The strongest named anchor is Theorem 2. The paper proves there that if every coalition loss satisfies \(\ell_c(\varepsilon,p)\le\gamma^2\), then \(p\) belongs to the \((\varepsilon+\sqrt{2n}\gamma)\)-core. In the continuous problem, define for a mass coalition \(z\)
\[ d_z=\max\{0,\nu_\mu(z)-\varepsilon-\langle y,z\rangle\} \]
and
\[ \ell_z(y,\varepsilon) = \frac{d_z^2}{2\|z\|_1}. \]
Because the total population mass is \(1\), \(\|z\|_1\le1\). Thus the direct mass-normalised analogue of Theorem 2 is: if \(\ell_z(y,\varepsilon)\le\gamma^2\) for every \(z\), then every deficit satisfies \(d_z\le\sqrt{2}\gamma\), so \(y\) lies in the \((\varepsilon+\sqrt{2}\gamma)\)-core. The population-size factor disappears because the model measures coalitions by mass rather than by their number of members.
That is a meaningful continuization result: the guarantee scales with the number of types and the approximation accuracy, rather than with the number \(N\) of interchangeable agents. It is exactly the kind of high-multiplicity gain the programme is looking for.
A second, narrower anchor is Theorem 4, which is proved in the paper using Lemma 1 and the stochastic mirror-prox guarantee cited from [43]. Its continuous counterpart is \(\textsc{SoftLeastCore}_{\infty}\). In addition to \((w,\mu,q)\), the instance specifies a distribution \(\mathcal D_\mu\) over mass coalitions \(z\in Z_\mu\), a tolerance \(\gamma>0\), and a sampling oracle for \(\mathcal D_\mu\). The task is
\[ \min_{y,\varepsilon}\ \varepsilon \quad\text{subject to}\quad \int_{Z_\mu}\ell_z(y,\varepsilon)\,d\mathcal D_\mu(z) \le\gamma^2, \]
with \(y\) in the payoff simplex and \(\varepsilon\in[0,1]\). A solution is an approximate saddle point of
\[ L(y,\varepsilon,\lambda) = \varepsilon + \lambda\left( \int_{Z_\mu}\ell_z(y,\varepsilon)\,d\mathcal D_\mu(z)-\gamma^2 \right), \]
with duality gap at most \(\eta\).
This is not the exact least core; it is the paper’s own soft relaxation, with the finite sum over coalitions replaced by an integral over coalition masses. Under bounded-variance sampling and the same convexity assumptions, Theorem 4 suggests an \(O(T^{-1/2})\) stochastic mirror-prox algorithm. Its expected classification is also Class A, but in a sampling-oracle model. The important further question is how to choose \(\mathcal D_\mu\) so that rare but highly blocking coalitions are not missed. A sampling guarantee alone is not an all-coalition certificate; the fractional-knapsack separator above supplies that missing certification for weighted voting.
I would not make Theorem 3 a separate anchor. It gives an \(O(T^{-1/4})\) expected convergence guarantee for stochastic subgradient descent, and it naturally suggests sampling mass coalitions rather than discrete subsets. But without an additional coverage or separation argument, convergence of sampled losses does not guarantee that every coalition satisfies the core constraint. It is useful support for the mirror, not as strong an independent case.
This mirror covers the paper’s central least-core approximation problem and its weighted voting games. It does not claim to continuize every experiment in the paper. Induced subgraph games would require a graphon-like type interaction model; marginal contribution networks would require a continuous representation of local contribution rules; and the XAI applications would need a defensible notion of fractional training mass. Those are separate questions.
The main weakness is semantic. In the original finite game, an indivisible pivotal player may matter greatly. In the continuum mirror, a coalition may take \(0.37\) of a type, and that destroys some indivisibility effects. The paper’s motivating examples are also often small committees, where high multiplicity would be artificial. The positive case depends on the alternative resource-pool regime being accepted as a legitimate instance family of their weighted voting problem.
I think that weakness is real but contained. The resource-pool setting preserves the paper’s threshold technology, coalition value, payoff interpretation, and stability question while making type-level mass genuinely operational. It also exposes a clean boundary: with fixed \(\tau\), fractional separation is tractable; when every named agent becomes its own type, the model collapses back toward the discrete problem and the original hardness concerns can return. That is not a defect of the mirror; it is precisely the high-multiplicity boundary the programme is meant to chart.
The strongest negative case is that the proponent has not actually mirrored either of its named theorems.
Theorem 2 is not an algorithmic or complexity result. It is a deterministic inequality: from \(\ell_c\le\gamma^2\), one immediately obtains \(d_c\le\sqrt{2n}\gamma\). Replacing \(|c|\) by \(\|z\|_1\le1\) gives \(d_z\le\sqrt{2}\gamma\) by the same one-line calculation. That is a valid identity, but it contributes no computational content.
More importantly, the proposed fractional-knapsack separator finds a coalition minimizing \(\langle y,z\rangle\). Theorem 2’s premise instead requires controlling
\[ \frac{\bigl(1-\varepsilon-\langle y,z\rangle\bigr)_+^2}{2\|z\|_1} \]
over all winning \(z\). The denominator means that maximizing the loss is not simply the minimum-cost winning-coalition problem. The proponent has therefore not shown that its claimed separator certifies the continuous analogue of Theorem 2. A stronger formulation could abandon the loss surrogate and solve the robust least-core LP directly, but that is a new optimization problem, not a continuization of the theorem’s algorithm or guarantee.
Theorem 4 fares worse. The paper’s formulation uses a sum over all discrete coalitions, and its sampling interpretation is essentially uniform sampling of subsets. There is no canonical corresponding distribution \(\mathcal D_\mu\) over the continuum of mass coalitions. Under the natural clone limit, a uniformly random subset of \(N\mu_a\) agents contains approximately half of each type:
\[ \frac{1}{N}\operatorname{Binomial}(N\mu_a,1/2) \longrightarrow \frac{\mu_a}{2}. \]
Thus the induced distribution collapses to a point mass, rather than producing the proposed nontrivial distribution over \(Z_\mu\). Lebesgue measure over the mass box gives a different game; any other \(\mathcal D_\mu\) is an additional modelling choice absent from the paper.
There is also a semantic problem. A small but catastrophic blocking coalition may have probability zero, or negligible probability, under \(\mathcal D_\mu\). An average-loss saddle point therefore need not approximate the core at all. The proposed fractional-knapsack oracle repairs this by certifying every coalition, but once that oracle is used, the distributional mirror-prox problem is merely a heuristic for solving a robust LP. Theorem 4’s sampling result is no longer doing the substantive work.
The paper has no theorem asserting a \(P\), NP-hardness, or parameterized-complexity classification. That strict objection is not quite decisive, because Theorems 2–4 are nevertheless named algorithmic convergence and approximation statements. But the paper’s real contribution is a scalable sampling-based solver for arbitrary compactly represented cooperative games. The proposed weighted-voting mirror removes precisely the difficulty that motivates the paper: fractional coalition separation becomes a routine knapsack calculation, while the original discrete separation problem is an indivisible knapsack problem. This is a meaningful new fractional game, but it is not convincingly a mirror of the paper’s computational contribution.
The same issue blocks better mirrors of the XAI results. Features are not a population of interchangeable agents, and data points are generally distinguished by their feature vectors, labels, and effects on retraining. Making them “types” either changes the learning problem into a fractional training model or requires enough type information to make nearly every data point its own type. A graph-game mirror has the analogous problem: preserving neighborhoods and edge interactions generally makes agents position-specific, while collapsing them into graphon-like types creates a new mean-field cooperative game.
That said, the universal negative claim is genuinely weak here. Weighted voting is unusually well suited to high multiplicity: agents with equal weights really are exchangeable, and a clone limit with threshold \(q_N=Nq\) does converge naturally to mass coalitions. The exact continuous least-core problem may well be a legitimate Class A problem solved by fractional-knapsack separation. I would therefore reject the proponent’s Theorem 2 and Theorem 4 anchors, but I could not honestly claim that no worthwhile continuous mirror exists in any scenario. The resource-pool weighted-voting model remains a credible counterexample to that universal conclusion.
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.