Exact power indices for plurality-voting ensembles

Ilie Sarpe; Theofanis Georgakopoulos; Aristides Gionis

cs.LGOct 13, 2026

Exact power indices for plurality-voting ensembles

Authors: Ilie Sarpe, Theofanis Georgakopoulos, Aristides Gionis

Organizations: KTH Royal Institute of Technology, Stockholm, Sweden · Ericsson BCSS, Stockholm, Sweden · Digital Futures, Stockholm, Sweden

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.

Figures & tables

Panel of Figure 1 — Figure 1: Runtime (mean and standard deviation) on our largest datasets, binary classification.

Figure 2: For each pair (dataset, baseline) encoded by a pair (shape, color), we display the Kendall’s $\tau$ with respect to the exact rankings obtained by enpower - $\phi$ and enpower - $\beta$ on the $x$ -axis, and $y$ -axis respectively, averaged over five splits. Each plot corresponds to a different ensemble.

Panel of Figure 3 — Figure 3: Generalization metrics for sub-ensemble selection, averaged over five random splits.

Panel of Figure 4 — Figure 4: Accuracy and $F_{1}$ -score test metrics for the prompt ensembling of CLIP on $\mathcal{D}_{\text{test}}$ (see Sec. 5.4 ), for varying $k$ . We report mean and standard deviation (over multiple splits).

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset (Label)	$\|\mathcal{D}_{\text{val}}\|+\|\mathcal{D}_{\text{test}}\|$	Classes ( $\ell$ )	$y=1$	$y=0$
Blood Transfusion ( BTSC )	187	2	143	44
Credit-G ( CR )	250	2	179	71
CNAE-9 ( C9 )	270	9	38	232
Titanic ( TT )	328	2	210	118
Bank Marketing ( BM )	11 303	2	9 994	1 309
Covertype ( CT )	145 253	7	70 628	74 625

Appendix

Table 1: Datasets used for binary and multiclass classification settings in Sec. 5 . Classes (

\ell

), denotes the original number of labels, which are also retained for the multiclass experiments. The last two columns display the number of points in

\mathcal{D}_{\text{val}}\cup\mathcal{D}_{\text{test}}

with label

y=1

and

y=0

after binarization.

Dataset	Total images	Classes ( $\ell$ )	$\|\mathcal{D}_{\text{val}}\|$	$\|\mathcal{D}_{\text{test}}\|$	$\|U\|$
CIFAR (Cifar-100)	10 000	100	5 000	5 000	$675.2\pm 6.6$
PETS (Oxford-IIIT Pets)	3 669	37	1 834	1 835	$123.6\pm 5.4$
IMAGENET-A (ImageNet-A)	7 500	200	3 750	3 750	$861.0\pm 11.6$

Appendix

Table 2: Dataset statistics for the zero-shot multiclass classification experiment. For each dataset we display its total number of images, and the number of possible classes. We also show

|\mathcal{D}_{\text{val}}|

, used to compute the ranking metrics, and

|\mathcal{D}_{\text{test}}|

used to evaluate the generalization of model selection. Column

|U|

reports the number of unique vote profiles observed on

\mathcal{D}_{\text{val}}

(the ensemble has

n=22

base predictors), averaged over five splits. Other columns do not depend on the split.

Dataset	Classes ( $\ell$ )	$\min$	$\max$	$IR$	CV (%)	$H_{\text{norm}}$
CIFAR (Cifar-100)	100	100	100	1.00	0.0	1.000
PETS (Oxford-IIIT Pets)	37	88	100	1.14	2.6	1.000
IMAGENET-A (ImageNet-A)	200	3	100	33.33	78.2	0.946

Appendix

Table 3: Class-imbalance statistics for the multiclass datasets of Sec. 5.4 (computed on

\mathcal{D}_{\text{val}}\cup\mathcal{D}_{\text{test}}

, hence equal on every split).

\ell

is the number of classes. “

\min

\max

” are the smallest/largest number of points (images) with the same class;

IR=\max/\min

is the imbalance ratio;

CV

is the coefficient of variation computed over the cardinality of all classes; and

H_{\text{norm}}\in(0,1]

is the normalized Shannon entropy of the class distribution (

1

corresponds to a uniform distribution).

Panel of Figure 5 — Figure 5: Sample images from the three datasets considered in Sec. 5.4 . CIFAR consists of tiny, low resolution (32 $\times$ 32 pixel) images. PETS consists of high quality images of different pets with fine-grained classes, and IMAGENET-A is a notorious challenging dataset for image classification.

Dataset	Ensemble	Index	$\varepsilon_{\text{abs}}$	$\varepsilon_{\text{rel}}$	Kendall’s ( $\tau$ )	Spearman ( $\rho$ )
BTSC	RF	$\phi$	$0.0045\pm 0.0007$	$0.42\pm 0.15$	$0.720\pm 0.036$	$0.889\pm 0.027$
	RF	$\beta$	$0.0003\pm 0.0000$	$3.34\pm 4.51$	$0.967\pm 0.004$	$0.997\pm 0.001$
	AB	$\phi$	$0.0013\pm 0.0002$	$0.26\pm 0.18$	$0.819\pm 0.030$	$0.930\pm 0.017$
	AB	$\beta$	$0.0007\pm 0.0001$	$0.07\pm 0.02$	$0.794\pm 0.036$	$0.917\pm 0.023$
	HET	$\phi$	$0.0111\pm 0.0021$	$0.51\pm 0.10$	$0.515\pm 0.094$	$0.676\pm 0.105$
	HET	$\beta$	$0.0005\pm 0.0002$	$13.72\pm 25.07$	$0.886\pm 0.073$	$0.964\pm 0.034$

Appendix

Table 4: Approximation error of the MC baseline. For each dataset and power index we report the maximum absolute

(\varepsilon_{\text{abs}})

and the maximum relative approximation error

(\varepsilon_{\text{rel}})

, over all models from

\mathcal{C}

. We further report the Kendall’s (

\tau

) and Spearman (

\rho

) ranking coefficients, with the exact scores computed by enpower . The results are the average and standard deviation over five random splits.

Ensemble	Method	C9	CT
RF ( $n=50$ )	enpower - $\beta$	$(3.7\pm 0.4)\cdot 10^{-3}$	$0.10\pm 0.01$
	enpower - $\phi$	$0.14\pm 0.02$	$2.6\pm 0.2$
	enpower ${}_{\mathsf{MC}}\text{-}\phi$ ++	$(2.8\pm 0.4)\cdot 10^{-2}$	$0.48\pm 0.04$
AB ( $n=150$ )	enpower - $\beta$	$(5.0\pm 0.9)\cdot 10^{-2}$	$1.9\pm 0.4$
	enpower - $\phi$	$7.8\pm 1.4$	$265\pm 50$
	enpower ${}_{\mathsf{MC}}\text{-}\phi$ ++	$2.7\pm 0.5$	$77\pm 14$

Appendix

Table 5: Runtime (seconds) of enpower on

\mathcal{D}_{\text{val}}

in the multiclass setting. The results are the average and standard deviation over five random splits. enpower

{}_{\mathsf{MC}}\text{-}\phi

++ corresponds to the refined algorithm of App. H .

Panel of Figure 6 — Figure 6: Runtime comparison (mean and standard deviation) on the missing datasets from Table 1 not reported in Sec. 5 due to space constraints.

Ensemble	BTSC	CR	C9	TT	BM	CT
RF	$0.697\pm 0.033$	$0.648\pm 0.035$	$0.979\pm 0.014$	$0.884\pm 0.032$	$0.868\pm 0.003$	$0.886\pm 0.005$
AB	$0.510\pm 0.251$	$0.505\pm 0.176$	$0.534\pm 0.376$	$0.535\pm 0.156$	$0.545\pm 0.311$	$0.519\pm 0.025$
HET	$0.745\pm 0.032$	$0.700\pm 0.036$	$0.940\pm 0.062$	$0.834\pm 0.121$	$0.895\pm 0.008$	$0.768\pm 0.068$

Appendix

Table 6: Accuracy on

\mathcal{D}_{\text{val}}

of the base classifiers of each ensemble, binary classification. Each entry is the mean

\pm

the standard deviation over the base classifiers of the ensemble, both averaged over five random splits.

Panel of Figure 7 — Figure 7: Generalization metrics for sub-ensemble selection, missing results from Sec. 5.3 .

Panel of Figure 8 — Figure 8: Accuracy and $F_{1}$ -score test metrics for the prompt ensembling of CLIP on $\mathcal{D}_{\text{test}}$ (see Sec. 5.4 ), as a function of $k$ . Missing results from Sec. 5.4 .

Dataset	Ranking	best acc.	$k$	avg. acc.	best $F_{1}$	$k$	avg. $F_{1}$
CIFAR100	Acc	$0.648\pm 0.005$	14	$0.645\pm 0.004$	$0.641\pm 0.004$	16	$0.637\pm 0.003$
	enpower - $\beta$	$0.649\pm 0.004$	10	$0.646\pm 0.004$	$0.641\pm 0.003$	16	$0.638\pm 0.003$
	enpower - $\phi$	$0.649\pm 0.004$	8	$0.646\pm 0.004$	$0.641\pm 0.004$	17	$0.638\pm 0.003$
	$\mathtt{Tr\text{-}PS}$	$0.647\pm 0.005$	15	$0.643\pm 0.006$	$0.639\pm 0.004$	15	$0.635\pm 0.004$
	$\mathtt{Tr\text{-}MLE}$	$0.648\pm 0.004$	14	$0.643\pm 0.005$	$0.640\pm 0.003$	14	$0.636\pm 0.003$
IMAGENET-A	Acc	$0.308\pm 0.004$	4	$0.302\pm 0.004$	$0.288\pm 0.005$	1	$0.279\pm 0.003$

Appendix

Table 7: Prompt ensembling of CLIP, metrics on

\mathcal{D}_{\text{test}}

of the sub-ensemble for varying

k

(see Sec. 5.4 ). Columns report, best: the maximum over

k

of the average over the five random splits, and the

k

attaining it. Avg.: the average over

k\in[n]

. Bold marks the best value for each configuration.

Method	CIFAR100	IMAGENET-A	PETS
enpower - $\beta$	$(1.17\pm 0.01)\cdot 10^{-2}$	$(1.37\pm 0.04)\cdot 10^{-2}$	$(1.64\pm 0.09)\cdot 10^{-3}$
enpower - $\phi$	$(3.61\pm 0.07)\cdot 10^{-1}$	$(5.14\pm 0.18)\cdot 10^{-1}$	$(3.45\pm 0.20)\cdot 10^{-2}$
$\mathtt{Tr\text{-}PS}$	$(1.33\pm 0.13)\cdot 10^{0}$	$(8.64\pm 0.44)\cdot 10^{-1}$	$(3.77\pm 0.04)\cdot 10^{-1}$
$\mathtt{Tr\text{-}MLE}$	$(2.37\pm 0.05)\cdot 10^{-2}$	$(1.84\pm 0.08)\cdot 10^{-2}$	$(1.26\pm 0.02)\cdot 10^{-2}$

Appendix

Table 8: Runtime (seconds) of the ranking methods on

\mathcal{D}_{\text{val}}

for the prompt ensembling of CLIP, average

\pm

standard deviation over five random splits.

Prompt template	Accuracy		Banzhaf		Shapley		$\Delta_{\beta}$	$\Delta_{\phi}$
Prompt template	Value	Rank	Value	Rank	Value	Rank	$\Delta_{\beta}$	$\Delta_{\phi}$
A pixelated photo of a {}.	0.6338	1	0.00296	1	0.03285	1	$-$	$-$
A heavily compressed JPEG photo of a {}.	0.6308	2	0.00262	2	0.03226	2	$-$	$-$
A high-resolution, crisp photo of a {}.	0.6248	3	0.00113	5	0.03047	4	$\downarrow$ 2	$\downarrow$ 1
A cropped photo of a {}.	0.6242	4	-0.00003	15	0.02941	10	$\downarrow$ 11	$\downarrow$ 6
A photo of a {}, cluttered background.	0.6238	5	0.00161	3	0.03077	3	$\uparrow$ 2	$\uparrow$ 2

Appendix

Table 9: Prompt ensemble evaluation for LLM zero-shot multiclass image classification (CIFAR100). Each prompt corresponds to a different model of

\mathcal{C}

. All values and rankings are computed on the validation split

\mathcal{D}_{\text{val}}

. Columns

\Delta_{\beta}

and

\Delta_{\phi}

display the difference in the validation rankings induced by the power indices

\beta(G_{\mathsf{MC}})

and

\phi(G_{\mathsf{MC}})

with respect to validation accuracy.

Prompt template	Accuracy		Banzhaf		Shapley		$\Delta_{\beta}$	$\Delta_{\phi}$
Prompt template	Value	Rank	Value	Rank	Value	Rank	$\Delta_{\beta}$	$\Delta_{\phi}$
A poor quality, grainy photo of a {}.	0.8648	1	0.00434	1	0.04529	1	$-$	$-$
A blurry photo of a {}.	0.8539	2	0.00328	2	0.04335	2	$-$	$-$
A close-up photo of a {}.	0.8522	3	0.00327	3	0.04312	3	$-$	$-$
A cropped photo of a {}.	0.8506	4	0.00188	4	0.04175	4	$-$	$-$
A heavily compressed JPEG photo of a {}.	0.8462	5	0.00095	9	0.04059	7	$\downarrow$ 4	$\downarrow$ 2

Appendix

Table 10: Prompt ensemble evaluation for LLM zero-shot multiclass image classification (PETS). Each prompt corresponds to a different model of

\mathcal{C}

. All values and rankings are computed on the validation split

\mathcal{D}_{\text{val}}

. Columns

\Delta_{\beta}

and

\Delta_{\phi}

display the difference in the validation rankings induced by the power indices

\beta(G_{\mathsf{MC}})

and

\phi(G_{\mathsf{MC}})

with respect to validation accuracy.

Prompt template	Accuracy		Banzhaf		Shapley		$\Delta_{\beta}$	$\Delta_{\phi}$
Prompt template	Value	Rank	Value	Rank	Value	Rank	$\Delta_{\beta}$	$\Delta_{\phi}$
A poor quality, grainy photo of a {}.	0.3136	1	0.00359	1	0.01936	1	$-$	$-$
A pixelated photo of a {}.	0.3029	2	0.00242	3	0.01738	3	$\downarrow$ 1	$\downarrow$ 1
A photo of a {}, with a watermark.	0.2989	3	0.00096	8	0.01581	6	$\downarrow$ 5	$\downarrow$ 3
A blurry photo of a {}.	0.2989	4	0.00184	4	0.01656	4	$-$	$-$
An unusual, hard to recognize photo of a {}.	0.2981	5	0.00295	2	0.01750	2	$\uparrow$ 3	$\uparrow$ 3

Appendix

Table 11: Prompt ensemble evaluation for LLM zero-shot multiclass image classification (IMAGENET-A). Each prompt corresponds to a different model of

\mathcal{C}

. All values and rankings are computed on the validation split

\mathcal{D}_{\text{val}}

. Columns

\Delta_{\beta}

and

\Delta_{\phi}

display the difference in the validation rankings induced by the power indices

\beta(G_{\mathsf{MC}})

and

\phi(G_{\mathsf{MC}})

with respect to validation accuracy.

Panel of Figure 9 — Figure 9: Runtime to process a unique vote profile on synthetic instances, where $p=0.1$ (top), $p=0.5$ (middle) and $p=0.9$ (bottom). The y-axis reports the measured time to compute the power indices under a vote profile $\bm{p}\in U$ with $n$ players and $\ell$ labels. See Sec. G.6 for a detailed description of each panel.

Shapley Value Attribution

Shapley value attribution fairly assigns a prediction or outcome among contributing features, data points, agents, or modalities.

See all 103 papers

May 14, 2026

Generalized Priority-Aware Shapley Value

Shapley value and its priority-aware extensions are widely used for valuation in machine learning, but existing methods require pairwise priority to be binary and acyclic, a restriction spectacularly violated in real-data examples such as aggregated human preferences and multi-criterion comparisons. We introduce the generalized priority-aware Shapley value (GPASV), a random order value defined on arbitrary directed weighted priority graphs, in which pairwise edges penalize rather than forbid order violations. GPASV covers a range of classical models as boundary cases. We establish GPASV through an axiomatic characterization, develop the associated computational methods, and introduce a priority sweeping diagnostic extending PASV's. We apply GPASV to LLM ensemble valuation on the cyclic Chatbot Arena preference graph, illustrating that priority-aware valuation is not a one-button operation: different balances of pairwise graph priority versus individual soft priority produce substantively different valuations of the same data.

Kiljae Lee, Ziqi Liu, Weijing Tang +1

The Ohio State University · Carnegie Mellon University

Pairwise Comparison Game Theory Shapley Value Attribution

Ask PDF

Aug 2, 2024

Explaining a probabilistic prediction on the simplex with Shapley compositions

Originating in game theory, Shapley values are widely used for explaining a machine learning model's prediction by quantifying the contribution of each feature's value to the prediction. This requires a scalar prediction as in binary classification, whereas a multiclass probabilistic prediction is a discrete probability distribution, living on a multidimensional simplex. In such a multiclass setting the Shapley values are typically computed separately on each class in a one-vs-rest manner, ignoring the compositional nature of the output distribution. In this paper, we introduce Shapley compositions as a well-founded way to properly explain a multiclass probabilistic prediction, using the Aitchison geometry from compositional data analysis. We prove that the Shapley composition is the unique quantity satisfying linearity, symmetry and efficiency on the Aitchison simplex, extending the corresponding axiomatic properties of the standard Shapley value. We demonstrate this proper multiclass treatment in a range of scenarios.

Paul-Gauthier Noé, Miquel Perelló-Nieto, Jean-François Bonastre +1

Laboratoire Informatique d’Avignon, Avignon Universit´e, France · University of Bristol, United Kingdom

Shapley Value Attribution

Ask PDF

Feb 26, 2026

Fair feature attribution for multi-output prediction: a Shapley-based perspective

In this article, we provide an axiomatic characterization of feature attribution for multi-output predictors within the Shapley framework. While SHAP explanations are routinely computed independently for each output coordinate, the theoretical necessity of this practice has remained unclear. By extending the classical Shapley axioms to vector-valued cooperative games, we establish a rigidity theorem showing that any attribution rule satisfying efficiency, symmetry, dummy player, and additivity must necessarily decompose component-wise across outputs. Consequently, any joint-output attribution rule must relax at least one of the classical Shapley axioms. This result identifies a previously unformalized structural constraint in Shapley-based interpretability, clarifying the precise scope of fairness-consistent explanations in multi-output learning. Numerical experiments on a biomedical benchmark illustrate that multi-output models can yield computational savings in training and deployment, while producing SHAP explanations that remain fully consistent with the component-wise structure imposed by the Shapley axioms.

Umberto Biccari, Alain Ibáñez de Opakua, José María Mato +3

Feature Attribution Shapley Value Attribution Cooperative Game Theory

Ask PDF

Abstract

Shapley Value Attribution

Explore similar work

Generalized Priority-Aware Shapley Value

Explaining a probabilistic prediction on the simplex with Shapley compositions

Fair feature attribution for multi-output prediction: a Shapley-based perspective