k -Prize Weighted Voting Game

The strongest positive case is a single anchor: Theorem 6.5, proved in this paper, which shows that \(\exists\)-SCD is NP-hard. I would mirror the paper’s beneficial-deviation problem, not its whole stability theory.

Consider a large federation of interchangeable delegates. Each delegate has one of \(\tau\) constitutional weight classes, and delegates of the same class have the same weight and the same tie-breaking status. The population contains fractions \(\mu_t\) of the classes, with \(\sum_t\mu_t=1\) and \(\tau\ll N\). This could represent many constituency delegates, shareholder representatives, or local political organisations competing for \(k\) cabinet positions or institutional prizes. The paper’s political-party example has too few players; this is the more convincing high-multiplicity regime.

The continuous problem, which I would call Anonymous-SCD\(_\infty\), is as follows. An instance consists of a finite type set \(T\), rational masses \(\mu_t\), rational per-agent weights \(w_t\), \(k\) rational prizes \(p_1\ge\cdots\ge p_k>0\), a type-symmetric tie-breaking rule, and an anonymous current payoff \(r_t\) for each unit of type \(t\). The payoff field is assumed to describe a feasible anonymous outcome. A proposed deviating coalition is a mass vector \(y\in\mathbb{R}^{T}\) with \(0\le y_t\le\mu_t\). Its aggregate weight and current payoff are \(W(y)=\sum_t w_ty_t\) and \(R(y)=\sum_t r_ty_t\).

The residual mass \(\mu-y\) may form any measurable partition. We say that \(y\) is \(i\)-attaining if, under every such residual partition and the prescribed tie-breaking rule, the deviating coalition ranks among the top \(i\) coalitions and therefore receives a prize of at least \(p_i\). The decision question is whether there exist \(i\in\{1,\ldots,k\}\) and \(y\) such that \(y\) is \(i\)-attaining and \(R(y)<p_i\). Equivalently, the optimization version maximizes the deviation gain \(p_i-R(y)\) over all \(i\) and all \(i\)-attaining mass coalitions.

This is recognisably the paper’s problem. The action is still coalition formation, the coalition strength is still the sum of player weights, the deviators still face the paper’s maximally pessimistic residual response, and the improvement test is still current payoff versus the prize guaranteed in every residual partition. Only the population representation changes from integer multiplicities to rational mass.

In the atomless high-multiplicity regime, the residual partition has a simple characterization. Away from tie boundaries, a residual population can form \(i\) coalitions each strictly heavier than \(y\) exactly when \(W(\mu-y)>iW(y)\). Hence \(y\) is \(i\)-attaining precisely when \((i+1)W(y)>W(\mu)\), with a finite boundary case for the chosen tie rule. For each \(i\), Anonymous-SCD\(_\infty\) therefore reduces to linear feasibility, or to the LP

\(\max\{p_i-R(y):0\le y\le\mu,\ (i+1)W(y)>W(\mu)\}\).

Thus I expect Anonymous-SCD\(_\infty\) to be in Class A: polynomial-time solvable in \(\tau\), \(k\), and the encoding length of the rational data. The strict inequalities and equality cases can be handled by standard rational LP procedures and the finite type-level tie rule.

This prediction illustrates exactly why the mirror is interesting. Theorem 6.5 reduces from Partition by asking whether a coalition contains a subset of item players with total weight exactly \(S\). In the continuous regime, a mass of a weight type can be divided, so the subset-sum combinatorics becomes a linear filling problem. The hardness is driven by population multiplicity and indivisibility, while the weight-ranking and prize structure remain intact. This is the kind of Class-A collapse that continuization is supposed to expose.

The high-multiplicity bridge is direct for rational data. Clearing denominators turns \(\mu_t\) into repeated clones of type \(t\); conversely, integer coalition counts normalize to mass vectors. A continuous solution with a strict improvement margin can be rounded to sufficiently many clones while preserving the deviation. The resulting algorithm would therefore give a useful preprocessing or additive approximation method for large finite federations, even though the original finite problem remains NP-hard.

I would not claim that Theorem 4.9 or Corollary 4.12 transfers literally. Their “iterative singleton winner” structure is tied to indivisible players: in an atomless population, a singleton has zero mass and cannot win a prize by itself. That is a real limitation, not something to hide. The proposed mirror covers Theorem 6.5 and the paper’s \(\exists\)-SCD question only; it does not cover the paper’s full core-existence theory, MCD/wMCD variants, or arbitrary identity-based tie-breaking.

The weakest point is therefore clear: the paper’s coalitions are sets of indivisible players, whereas Anonymous-SCD\(_\infty\) permits fractional participation by a type. If the authors regard indivisibility as essential rather than as the population-multiplicity source of hardness, they may call this an extension rather than a direct mirror. The case remains persuasive because the paper’s central SCD quantifier and weighted-prize semantics survive exactly, and because large populations of exchangeable delegates provide a credible setting in which mass coalition formation is the natural resolution.

The immediate follow-up questions are whether the continuous SCD-core can be characterized by LP duality, whether MCD and wMCD also collapse to polynomial-time mass optimization, and how much discrete hardness remains when clone counts are integral but the number of weight types \(\tau\) is small.