On the Ordinal Invariance of Power Indices on Coalitional Games

The opponent wins because the paper contains no numbered result asserting a computational complexity or algorithmic guarantee; Theorem 3 only characterizes stability mathematically. The proposed \(\mathrm{Shapley\text{-}Ordinal\text{-}Stability}_\infty\) is coherent, but it adds a piecewise-affine mass game and an Aumann–Shapley path, making it a new re-modeling rather than a continuization of a computational result from this paper. Therefore bit (a) fails.

The objection that survived

The Aumann–Shapley limit samples only the ray \(t\mapsto t\mu\), while the paper's theorem depends on ordinal relations among all coalitions; the regularity of \(V\) is also additional structure absent from the paper.

What the mirror covers

The proposed model addresses only the stability theme behind \(\mathrm{Theorem\ 3}\); it leaves the paper's other named propositions and theorems without computational mirrors.

Open questions for a prover

The case FOR (proponent)

The paper contains no named complexity result in the strict sense: no theorem states NP-hardness, membership in \(P\), W[1]-hardness, or FPT. Thus there is no honest hardness anchor from which to claim that a discrete difficulty dissolves in the continuum. The strongest positive case is instead an algorithmic mirror of Theorem 3, proved in this paper. Theorem 3 gives an operational characterization of two-player stability for every semivalue, including Shapley and Banzhaf: an ordinal comparison is stable exactly when certain sums of semivalue parameters are nonnegative.

The natural high-multiplicity regime is a large coalition-forming population with finitely many role types. Type \(a\) may represent a voting bloc, institutional role, or class of otherwise interchangeable agents. There are \(r\mu_a\) agents of type \(a\), with \(\mu_a\) fixed and \(r\to\infty\). Agents of the same type have identical voting behaviour, coalition effects, and all other parameters relevant to the game. The number of agents grows, while the number of types \(\tau\) remains small.

A coalition is then represented by its type-mass vector \(x\in[0,\mu]\), and its worth is a function \(V(x)\). To keep the computational problem finite-representable, take \(V\) to be a rational piecewise-affine function on a rational polyhedral subdivision of \([0,\mu]\). This is genuinely population continuization: the object replacing a subset of named players is a vector of coalition masses.

For a Shapley-type index, the high-multiplicity limit gives the per-unit type score \(\Phi_a(V)=\int_0^1 \partial_a V(t\mu)\,dt\). This is the Aumann–Shapley limit of the ordinary Shapley value: in a random ordering of \(r\) agents, the coalition preceding a focal agent has asymptotic composition \(t\mu\), with \(t\) uniformly distributed in \([0,1]\). Ranking the \(\Phi_a(V)\) therefore ranks the individual agents by type.

My lead problem would be:

Shapley-Ordinal-Stability\(_\infty\). An instance consists of \(\mu\), a piecewise-affine mass game \(V\), and two types \(i,j\). Let \(\mathcal F(V)\) be the strictly increasing reparameterizations \(f\) of the range of \(V\), normalized by \(\int f'(z)\,dz=1\), and write \(W=f\circ V\). Decide whether the comparison between \(\Phi_i(V)\) and \(\Phi_j(V)\) is unchanged for every \(W\in\mathcal F(V)\). Equivalently, determine whether the sign of \(\Phi_i(W)-\Phi_j(W)\) is always the same as the sign of \(\Phi_i(V)-\Phi_j(V)\). A NO solution must provide an increasing \(f\) witnessing a reversal or a newly created tie; a YES solution must certify invariance. The full ranking problem asks the same question for every pair of types.

This is the continuous analogue of the paper’s ordinal-stability question. The worths are uncertain, but their ordering is trusted: \(V\) and \(W\) induce the same ordering of all coalition-mass vectors. The decision variable is the admissible revaluation \(f\), and the objective is the worst-case type-score difference. By the chain rule, \(\Phi_i(W)-\Phi_j(W)=\int_0^1 f'(V(t\mu))(\partial_iV(t\mu)-\partial_jV(t\mu))\,dt\). Thus ordinal uncertainty becomes a positive reweighting of the marginal-contribution profile, exactly the role played by the unknown positive differences in the proof of Theorem 3.

Under the stated piecewise-affine encoding, I would expect this problem to be Class A. Along the Shapley path \(t\mapsto t\mu\), both \(V(t\mu)\) and \(\partial_iV(t\mu)-\partial_jV(t\mu)\) have finitely many rational pieces. Pushing the signed marginal difference forward through the score \(z=V(t\mu)\) produces a finite signed measure \(H\) such that \(\Phi_i(f\circ V)-\Phi_j(f\circ V)=\int f'(z)\,dH(z)\). Stability for every increasing revaluation is then equivalent to \(H\) having the appropriate sign; exact preservation of a tie requires \(H=0\). For a piecewise-affine input this can be checked by a finite sweep over rational intervals. A reversing \(f\) can likewise be chosen piecewise-affine with positive slopes.

The authors should recognize this as their problem rather than as an unrelated smooth optimization problem. The original question is whether the ranking produced by a linear power index is determined by the ordinal structure of coalition worths. The mirror keeps the same ingredients—coalition worth, ordinal equivalence, semivalue marginal contributions, and player ranking—and replaces individual coalition membership by type mass. It does not merely make outcomes fractional.

The main weakness is substantial: the paper proves no complexity theorem, so this cannot establish that a known NP-hard problem becomes tractable. Moreover, the Shapley limit suppresses atypical coalition compositions: random coalitions concentrate near \(t\mu\). A Banzhaf limit is even more degenerate, concentrating near \(\mu/2\). If the intended mirror must preserve the influence of every exponentially rare finite coalition, this construction may be judged too weak. The representation of \(V\) is also essential; with an unrestricted oracle or arbitrary measurable worth function, there is no meaningful finite computational problem.

Still, this is a defensible positive mirror for one of the paper’s central results. It creates a genuine continuous-population version of Theorem 3, with a concrete adversarial optimization problem and a plausible tractability mechanism. It also raises the right follow-up questions: finite-\(r\) convergence rates, other semivalues, nonsmooth threshold games, and whether retaining nonconcentrated coalition-mass distributions produces a harder continuum-specific problem.

The case AGAINST (opponent, writing after the proponent)

The decisive objection is that this paper supplies no computational anchor for ChoCo. Problem 1 asks for a characterization of stable set functions, but gives no input encoding, algorithm, running-time claim, complexity classification, approximation result, or parameterized result. Theorem 3 is an equivalence between two mathematical conditions, not a computational theorem. Calling its condition “operational” does not change that. Thus the proposed \(\mathrm{Shapley\text{-}Ordinal\text{-}Stability}_\infty\) is a new continuous cooperative-game problem motivated by Theorem 3, not the continuization of a computational result from the paper.

The high-multiplicity story itself is not implausible. Large voting blocs or repeated institutional roles can be represented by finitely many clone types. The problem is the passage from the paper’s arbitrary finite set function to \(V\). A clone-symmetric \(r\)-player game is specified by values \(v_r(k)\) on the integer grid \(k\in\prod_a\{0,\ldots,r\mu_a\}\). The paper imposes no coherence, smoothness, scaling, or limiting condition on these values. A rational piecewise-affine \(V\) therefore does not encode the paper’s game; it adds a strong regularity and interpolation assumption. The derivatives used by the proposed index are information absent from the ordinal input. If \(V\) is taken as primitive, that is a legitimate new model, but not a canonical high-multiplicity version of the theorem.

More seriously, the Aumann–Shapley limit discards the main object that Theorem 3 studies. For clone populations and the paper’s ordinary semivalues, coalition compositions concentrate around their expected type proportions. The limiting type score is therefore sampled along the single ray \(t\mapsto t\mu\), giving \(\Phi_a(V)=\int_0^1\partial_aV(t\mu)\,dt\). The original theorem compares marginal contributions over every coalition \(S\subseteq N\setminus\{i,j\}\), with the ordinal relations among all those coalitions determining the condition \(D^{\pi(q)}_{i,j}\).

In the proposed limit, ordinal uncertainty becomes the signed one-dimensional measure \(H\) induced by the path, with score difference \(\int f'(z)\,dH(z)\). For an explicitly piecewise-affine \(V\), stability is consequently a finite sign test on intervals of the score range. That may be a clean theorem, but it is a theorem about a path functional selected by the limit, not about the paper’s all-coalitions ordinal stability.

The obvious rescue does not restore the anchor. One could define a nonconcentrated mass index such as \(\int_{[0,\mu]}\partial_aV(x)\rho(x)\,dx\), so that all coalition-mass vectors matter. But then \(\rho\) is an additional scoring rule not supplied by the paper’s semivalues. Alternatively, one can retain arbitrary \(v_r\), but then there is no canonical continuum \(V\). Letting the number of types grow to preserve all directions removes the fixed-type high-multiplicity compression.

So the positive case establishes that one can invent a mathematically coherent continuous cooperative-game extension. It does not establish a worthwhile ChoCo mirror of this paper. The negative case is not that high multiplicity is nonsensical, nor that a polynomial answer would be uninteresting. It is that every plausible route either adds a new computational model, loses the theorem’s all-coalition object, or starts from a paper containing no computational result to continuize in the first place.

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.