d4-conf-ijcai-2015-0555

The strongest mirror I believe is a high-multiplicity version of the Banzhaf index, with the continuous answer recording its exponential rate of decay.

My anchor is Proposition 1, proved in this paper. It says that computing either the Shapley–Shubik index or the Banzhaf index for a graph-restricted weighted voting game is #P-complete. The paper reduces from the cited #P-hardness for ordinary weighted voting games by using a complete communication graph; membership follows by counting pivotal permutations or coalitions after scaling the normalized indices. I would mirror only the Banzhaf part of this proposition. Its definition already gives a natural bridge: the index is the probability that an agent turns a losing coalition into a winning one when every other agent is independently included with probability \(1/2\).

Consider a large federation organized into recurring blocs. Every member of a bloc has the same vote weight and the same communication role; members within a bloc communicate with one another, and communication between two blocs is uniform. A type \(t\) is therefore a vote weight together with a vertex of the bloc communication graph. The mass \(\mu_t\) is that type’s fraction of the population. This is a restricted but plausible graph regime: the number of agents grows while the number of distinct roles stays fixed or moderate.

I would name the continuous problem Typed Continuum Banzhaf Rate. Its instance is a type graph \(H=(T,F)\), positive rational masses \(\mu_t\) summing to \(1\), positive integer weights \(w_t\), and a rational quota \(q\). Write \(W_C=\sum_{t\in C}\mu_t w_t\) for each connected component \(C\) of \(H\); assume \(\frac12\sum_t\mu_t w_t<q\), and that exactly one component has \(W_C>q\). For each denominator-compatible \(k\), form the paper’s finite game with \(k\mu_t\) agents of type \(t\), a clique within each type, complete links between adjacent types, and quota \(\lceil kq\rceil\). Let \(b_t(k)\) be the normalized Banzhaf index of one agent of type \(t\).

The requested output is the vector of rates \(\rho_t=-\lim_{k\to\infty}k^{-1}\ln b_t(k)\), with \(\rho_t=\infty\) if that type cannot be pivotal. A concrete mass formulation for this question uses a selected coalition mass \(x_t\in[0,\mu_t]\) for each type, plus an active support \(A\subseteq T\). The active support records which types occur in the coalition; it may include types represented by vanishingly small positive mass, since those members can connect otherwise separate components. For a component \(D\), let \(W_D(x)=\sum_{s\in D}w_sx_s\), and let \(C_t(A\cup\{t\})\) be the component containing \(t\) after the target agent joins. The rate candidate is the infimum of
\[ \sum_{s\in T}\mu_s D\!\left(\frac{x_s}{\mu_s}\middle\|\frac12\right), \qquad D(p\|1/2)=p\ln(2p)+(1-p)\ln(2(1-p)), \]
over \(A,x\) such that \(\{s:x_s>0\}\subseteq A\), every component \(D\) of \(H[A]\) has \(W_D(x)\le q\), and \(W_{C_t(A\cup\{t\})}(x)=q\). The first constraint captures a coalition that is losing before \(t\) joins; the last captures a component that reaches the quota after the join. The optimization can be handed to a prover as stated: compute its infimum for every type, to additive error \(\varepsilon\), reporting infinity when infeasible. Establishing the precise equality between this entropy infimum and the finite-game rate, including quota rounding at the boundary, is the first theorem this mirror would need.

The match to the paper is direct at the level of the underlying question: how likely is a representative agent to change the result, given the graph-restricted coalition value? The continuous society is the mass distribution over complete agent types. The mass vector \(x\) is the composition of a random coalition, and the entropy objective is the large-deviation cost of seeing that composition under the Banzhaf experiment. This mirrors only the Banzhaf half of Proposition 1; I would not claim it covers the paper’s Shapley–Shubik result.

I expect the rate problem to be continuum-specifically hard when the type graph is unrestricted. For any fixed support \(A\), the entropy minimization has convex objective and linear constraints. The combinatorial choice of active support and connected components remains as \(\tau=|T|\) grows, even after population size disappears from the input. That is a reason to suspect Class C, not a hardness proof; bounded treewidth is a natural parameterized case to investigate. Further questions are whether the rate formula always holds, whether the rates admit efficient approximation or fixed-parameter algorithms, and how much finite-\(k\) information can be recovered from the rate.

The weakest point is that the continuous output keeps only the leading exponential rate, not the exact Banzhaf index or its subexponential factor. It also assumes repeated bloc roles, rather than arbitrary individual communication graphs. A referee could reasonably ask whether an asymptotic rate still counts as the authors’ power-index problem. I think it is a defensible mirror because it is derived from their exact pivotality experiment and retains the graph-restricted winning condition, but that loss of finite-scale detail is the argument’s main vulnerability.