| paper | k-Prize Weighted Voting Game |
| authors | — |
| venue | AAMAS 2023 |
| filed under | coalition · wvg |
| judged by | gpt-5.6-terra / high (triple__gpt-5.6-terra__high__ctx2r8-rejudge1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 6.5
Given finitely many types \(T\), masses \(\mu_t\), strengths \(a_t>0\), current payoff rates \(u_t\geq0\), and ordered prizes \(p_1\geq\cdots\geq p_k>0\), does there exist a mass coalition \(d\) with \(0\leq d_t\leq\mu_t\) that, against every partition of the residual mass \(\mu-d\), is guaranteed a prize \(p_j> \sum_t u_t d_t\)?
An atomless high-multiplicity \(k\)-prize weighted voting game: types have masses, a deviating coalition chooses \(d\), strength is \(A(d)=\sum_t a_t d_t\), and the objective is to find a guaranteed prize exceeding its aggregate incumbent payoff.
The mirror directly covers the deviation-existence question of Theorem 6.5 and leaves the paper's singleton-winner characterisations, efficiency results, and other complexity bounds alone.
The best anchor is Theorem 6.5, proved in the paper: ∃-SCD is NP-hard, by a reduction from Partition. I would mirror that result, rather than the paper’s small-player characterisations. Its reduction exposes exactly the population indivisibility that a high-multiplicity relaxation ought to remove.
Call the continuous problem Continuous SCD-Existence for \(k\)-Prize Capacity Games (the lead mirror). An instance has a finite set \(T\) of supplier/member types. Type \(t\) has mass \(\mu_t\), per-unit coalition strength \(a_t>0\), and current per-unit payoff \(u_t\geq0\). There are \(k\) ordered prizes \(p_1\geq\cdots\geq p_k>0\). A type is complete: agents grouped in it have the same certified capacity, contractual entitlement, and any other feature relevant to strength or payoff. The supplied payoff rates represent a valid current outcome; as in the paper’s Remark 1, stability depends on these payoffs rather than on the historical coalition partition.
A coalition is now a mass vector \(d\), with \(0\leq d_t\leq\mu_t\). Its strength and current aggregate payoff are
\[
A(d)=\sum_t a_t d_t,\qquad U(d)=\sum_t u_t d_t.
\]
The residual society has mass \(\mu-d\), and may partition its mass arbitrarily and adversarially into competing coalitions. The question is whether there is a \(d\) that is a single-coalition deviation in precisely the paper’s pessimistic sense: whatever fractional coalition structure the residual population forms, \(d\) receives a prize worth strictly more than \(U(d)\). A solution is such a mass vector \(d\), together with the guaranteed prize rank.
This is not merely “making the weights real”: the discrete operation “choose a subset of players” becomes “choose a subpopulation of each type,” while coalition strength, prize ranking, prize sharing, externalities, and the universal quantification over residual responses all remain intact. It is the natural high-multiplicity version of their \(\exists\)-SCD problem.
With a tie convention adverse to the deviator, \(d\) can guarantee a prize at least \(p_j\) exactly when its strength exceeds \(W/(j+1)\), where \(W=\sum_t a_t\mu_t\). Otherwise the residual mass can be split into \(j\) coalitions at least as strong as \(d\); if it exceeds that threshold, it cannot. Hence the continuous question is the union, over \(j\in[k]\), of linear feasibility problems:
\[
0\le d_t\le\mu_t,\qquad
\sum_t a_t d_t> \frac{W}{j+1},\qquad
\sum_t u_t d_t<p_j.
\]
Strict rational inequalities can be handled by a standard slack-maximisation LP. So I expect this mirror to be Class A: polynomial-time solvable in the number of types and bit length.
There is a credible regime for it. Think of a very large procurement or platform market: many micro-suppliers, workers, or local affiliates form consortia, and the \(k\) largest-capacity consortia receive a fixed number of framework contracts, licences, or platform placements. Capacity certifications, contribution rates, and incumbent payout contracts create a modest set of types; there might be millions of supplier-hours or members but tens or hundreds of such types. Coalition strength is aggregate capacity, and a prize is contract revenue shared by its members. This is recognisably the paper’s ranked-coalition model, but in a regime where “a coalition of 23% of certified capacity” is the operative object rather than a named set of individual firms.
The connection to Theorem 6.5 is especially clean. Its hardness construction forces a coalition to select an indivisible subset of the \(s_i\)-weighted players with total exactly \(S\). In the continuous market, the corresponding type masses can be split: achieving the required strength is a linear resource-allocation question, not Partition. Thus the theorem’s NP-hardness does not transfer upward; it diagnoses the discrete combinatorics that continuization removes.
I would not claim to mirror the whole paper. In particular, Theorem 4.9’s iterative *singleton* winners is tied to atomic players and would need a separately justified atomless analogue. The weak point of this case is also clear: the paper’s motivating political-party interpretation may have only a few genuinely indivisible parties, and then this is not the right regime. The case survives because the same formal game has a strong large-market consortium interpretation, and because the continuous problem retains the paper’s central strategic question rather than replacing it with an unrelated fractional allocation problem.
I cannot make a convincing universal negative case against this paper, because the proponent’s Theorem 6.5 anchor survives the right high-multiplicity construction.
The only serious attack is that the paper’s natural agents—political parties or firms forming consortia—are often legally and strategically indivisible. In such instances, replacing a coalition of named parties by a fraction of each type is not faithful: contracts, participation, and coalition membership attach to whole entities. The proposed market story is therefore not evidence for continuizing every \(k\)-WVG instance, nor even its main political-party motivation. It requires a genuine large-population regime of substitutable, small capacity holders whose payoff and capacity data are shared within types.
But that is a limitation on the regime, not a defeat of the mirror. If a type \(t\) represents many interchangeable supplier-hours, affiliates, or workers with common capacity and entitlement, a finite high-multiplicity version has many whole agents of that type; selecting a mass \(d_t\) is exactly its limit. Fixed prizes do not cause degeneration: they are coalition-level contract revenues, and the relevant transferable payoff is the coalition’s aggregate payoff, as in the paper’s own SCD definition. A valid incumbent allocation can likewise be represented by per-unit payoff rates whose integrals exhaust the prizes.
Nor is the LP simplification an objection. It is precisely the programme’s question whether discrete subset selection disappears when types become divisible. Theorem 6.5’s Partition reduction is especially susceptible: its combinatorics require selecting an exact indivisible subset, whereas the atomless counterpart permits partial use of a type. The fact that the reduction uses many distinct weights/types weakens any practical claim about a small-type market, but not the legitimacy of the computational continuous problem, whose input may contain many types.
The paper’s singleton-winner characterization in Theorem 4.9 is much less promising as a mirror, since “singleton” is intrinsically atomic. Yet the programme needs only one emphatic computational anchor. On the strongest available reading, Theorem 6.5 supplies one. So the honest verdict is that a blanket “no worthwhile continuous mirror in any scenario” cannot be sustained here; the procurement/platform large-market interpretation is sufficient to green the paper.
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.