Exact power indices for plurality-voting ensembles

AI summary

Overview

• Research area: Machine learning (ensembles, explainability/attribution) combined with cooperative game theory (Banzhaf and Shapley power indices).
• Technical level: Advanced. The paper relies on characteristic-function games, power-index axioms, combinatorial counting, ordinary generating functions, and dynamic programming.
• Scope in one sentence: The paper introduces new cooperative games that model plurality-voting ensembles with random tie-breaking, and derives exact algorithms (collectively called enpower) that compute Banzhaf and Shapley values in linear time for binary classification and low-degree polynomial time for multiclass classification.

What This Paper Is About

Plurality-voting ensembles combine the predictions of several base classifiers by taking the most voted class, breaking ties at random. The core problem is attribution: how much does each base classifier actually contribute to the ensemble's predictions? Simple heuristics such as leave-one-out accuracy or per-model accuracy ignore interactions among classifiers — a single vote can flip the outcome of any sub-ensemble that is tied. The authors' goal is to compute the exact Banzhaf and Shapley values for this specific voting rule, in both binary and multiclass settings, without resorting to approximation.

Key Contributions

1. A new game formulation. The authors define characteristic-function games capturing plurality voting with random tie-breaking: $v_{\mathsf{B}}$ for binary classification (value 1 if the majority is correct, 1/2 on a tie, 0 otherwise) and $v_{\mathsf{MC}}$ for multiclass classification (value $1/|\mathcal{M}(S)|$ if the true label is among the most-voted labels, 0 otherwise).
2. Exact closed-form indices for the binary case. Theorems 4.1 and 4.2 give closed-form solutions for the Banzhaf and Shapley values, computable in time $\mathcal{O}(|\mathcal{D}|n)$ with $\mathcal{O}(n)$ memory, where $|\mathcal{D}|$ is the number of test points and $n$ the number of classifiers.
3. Polynomial-time exact algorithms for the multiclass case. The Banzhaf values are computed in $\mathcal{O}(|U|n\ell^{2}+|\mathcal{D}|n)$ and the Shapley values in $\mathcal{O}(|U|n^{3}\ell+|\mathcal{D}|n)$, where $\ell$ is the number of classes and $|U|$ the number of unique vote profiles ($|U|\le|\mathcal{D}|$, and $|U|\le n+1$ in the binary case). Memory required is $\mathcal{O}(\ell(n+|U|))$.
4. An empirical study of two applications. The authors apply enpower to ensemble pruning and to prompt-based ensembling of vision-language models on a zero-shot image classification task, and compare against several baselines.

Main Findings

• The game resists standard tools. Lemma 3.3 shows that the binary characteristic function $v_{\mathsf{B}}(z,\cdot)$ is neither supermodular, nor superadditive, nor monotone. Because it is not monotone and can take the value 1/2, the game is not a simple game and in particular not a weighted majority game (WMG) — so existing algorithms for WMGs cannot be applied directly.
• Exactness despite apparent intractability. Although computing power indices is intractable in general (the definitions involve a summation over an exponential number of coalitions), Theorem 3.4 establishes that both the Banzhaf and Shapley values for the binary game can be computed in linear time $\mathcal{O}(|\mathcal{D}|n)$.
• Symmetry is the key lever. Base classifiers with identical votes yield the same contributions. In the binary case this produces closed-form solutions; in the multiclass case it lets the authors group test points by unique vote profile $U$.
• Generating functions encode coalition counts. For multiclass Banzhaf values, the polynomial $P_{h}(t)=\prod_{j=2}^{\ell}(A_{j}(h)+B_{j}(h)t)$, of degree at most $\ell-1$, has coefficients $[t^{k}]P_{h}(t)=|\mathcal{S}(k,h)|$ counting coalitions where exactly $k$ incorrect labels receive $h$ votes and all remaining labels receive fewer than $h$ votes. Computing each $P_{h}(t)$ takes $\mathcal{O}(\ell^{2})$ time.
• Shapley needs a second variable. Because the Shapley formula weights each coalition by a function of its size, the authors use a bivariate polynomial $P_{h}(t,u)$, with $[t^{k}u^{m}]P_{h}(t,u)=|\mathcal{S}(k,h,m)|$ counting coalitions of size $m$; degrees are at most $\ell-1$ in $t$ and $n-n_{1}$ in $u$.
• A faster asymptotic variant exists. Polynomial multiplication via the fast Fourier transform reduces the $\mathcal{O}(\ell^{2})$ cost to $\mathcal{O}(\ell\log\ell)$, at the expense of higher constants and a more complex implementation. A variant called enpower-$\mathsf{MC}$-$\phi$++ further improves the Shapley time-complexity bound.
• enpower is fast in practice. In the experiments, enpower methods are among the fastest for binary classification; even on the largest datasets, where the sampling methods Tr-PS and MC require up to hundreds and thousands of seconds respectively, enpower methods terminate in less than one second.
• Faster than prior work, comparable to the fastest approximation. The authors state that their exact methods are much faster than prior work [42, 47] and comparable with the fastest approximate method of Rozemberczki and Sarkar [36], while producing attribution values not captured by existing methods.
• Practical profile counts are small. The authors note that $|U|$ can be much smaller than $|\mathcal{D}|$ in practice (they point to $|U|$ in Table 2), because when most classifiers are accurate many points share the same vote profile.
• Not reported in the provided content. The paper content supplied here is truncated before the results for the ranking comparison (Q2), ensemble pruning (Q3), and prompt ensembling (Q4); the corresponding numeric results are not reported in this excerpt.

Methodology in Plain English

The authors treat an ensemble as a cooperative game: the base classifiers are the players, and any subset (sub-ensemble) gets a score for how well it votes on a data point. Two standard ways to divide credit in such games are the Banzhaf value and the Shapley value, which measure a player's average marginal effect when joining coalitions. The paper first writes down the game that exactly matches plurality voting with random tie-breaking, for binary and multiclass labels.

Then, instead of enumerating all $2^{n}$ sub-ensembles, the authors look for structure. They observe that a classifier can only change the outcome in very specific circumstances — creating a tie or breaking a tie — and that classifiers with identical predictions are interchangeable. In the binary case, this reduces everything to counting how many classifiers vote correctly ($n_{+}$) and how many vote incorrectly ($n_{-}=n-n_{+}$), giving closed-form formulas. In the multiclass case, counting the relevant coalitions is harder, so the authors pack the counts into polynomials: the coefficient of $t^{k}$ counts coalitions in which $k$ competing labels reach a threshold $h$. For Shapley values, whose weights depend on coalition size, they add a second variable $u$ to track size and compute the resulting bivariate polynomial with dynamic programming. Finally they test the resulting algorithms on six UCI datasets with three types of ensembles (random forest, AdaBoost, and a heterogeneous ensemble).

Why This Matters

• Research impact: The work shows that exact power indices are tractable for a widely used aggregation rule that prior game-theoretic formulations (most prominently weighted majority games) do not faithfully capture. This opens a research direction for exact attribution in non-monotone games and in multiclass settings where prior methods are inapplicable.
• Explainability: Attribution is described as a key challenge in explainable AI; this work gives an exact, axiomatically grounded answer for plurality-voting ensembles rather than a heuristic.
• Real-world applications discussed by the authors:
  • Ensemble pruning — selecting a smaller sub-ensemble with comparable performance.
  • Prompt-based ensembling of vision-language models on zero-shot image classification.
  • Data validation.
  • Feature selection.
• Industry relevance: Plurality voting is a well-established scheme used by many ensembles and popular software packages, and ensemble methods are widely adopted because they achieve higher accuracy and robustness than individual models. A method that computes exact, low-cost attribution values for these ensembles is directly relevant to practitioners who need to audit or shrink deployed ensembles.
• Reproducibility: The authors state that code to reproduce their results is available at https://github.com/iliesarpe/enpower.

Future Directions

• Weighted plurality voting. The authors consider only unweighted votes and state explicitly that extending enpower to weighted plurality voting is non-trivial.
• Broader applications of the attribution values. The paper lists data validation and feature selection as uses of the indices but evaluates only ensemble pruning and prompt-based ensembling; the others remain open to empirical study.
• Faster and leaner implementations. The FFT-based polynomial multiplication and the enpower-$\mathsf{MC}$-$\phi$++ variant suggest scope for further reducing the $\mathcal{O}(n^{3}\ell)$ Shapley bound and the dynamic-programming memory footprint.
• Comparing against more attribution methods. The paper notes that most alternative methods are not applicable to the multiclass setting or have very high runtime, leaving room for new baselines that can operate in that regime.

Target Audience

Researchers and practitioners in machine learning explainability and ensemble methods who need to quantify the contribution of individual base classifiers; theoretical computer scientists working on cooperative game theory and the computation of power indices; and engineers building or auditing plurality-voting systems (including vision-language prompt ensembles) who want exact rather than approximate attribution. Some familiarity with cooperative game theory and generating functions is required to follow the derivations; the empirical sections are more accessible.

Authors’ abstract

Plurality-voting ensembles aggregate the predictions of multiple base classifiers and output the most voted class, with ties typically broken at random. Despite the simple aggregation rule, attributing the impact of each base classifier to the ensemble's predictions is far from straightforward. That is, a single base classifier's impact depends on how it interacts with the votes of all other classifiers in the ensemble, for example, in resolving ties, and not only on its own predictions. We address the attribution problem using established tools from cooperative game theory, studying the Banzhaf and Shapley power indices for new games modeling plurality voting and random tie-breaking, for binary and multiclass classification settings. Computing power indices is, in general, intractable. Surprisingly, our methods, collectively named ENPOWER, enable the exact computation of Banzhaf and Shapley values in linear time for the binary classification setting and in low-degree polynomial time for the multiclass setting. The algorithms in ENPOWER rely on new combinatorial formulations of the Banzhaf and Shapley indices, yielding closed-form solutions for the binary case and ordinary generating function representations for the multiclass case. We validate empirically the methods in ENPOWER demonstrating their high applicability, providing attribution values not captured by existing methods. We apply the attribution of ENPOWER to: ensemble pruning and prompt-based ensembling of vision-language models.