Exact power indices for plurality-voting ensembles

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 individual base classifier to the ensemble's predictions is far from straightforward. That is, a single base classifier's impact depends not only on its own predictions but also on how it interacts with the votes of all other models in the ensemble, for example, in resolving ties. We address the attribution problem using established tools from cooperative game theory, studying the Banzhaf and Shapley power indices for new games that capture plurality voting and random tie-breaking, in both binary and multi-class classification settings. Computing power indices is, in general, exponential in the number of players. Surprisingly, our methods, collectively named ENPOWER, enable the exact computation of Shapley and Banzhaf values in linear time for the binary-classification setting and in low-degree polynomial time for the multi-class setting. The algorithms in ENPOWER rely on new combinatorial formulations of the Shapley and Banzhaf indices, yielding closed-form expressions for the binary case and ordinary generating function expressions for the multi-class case. We validate empirically the methods in ENPOWER and demonstrate that they are highly efficient, providing attribution values not captured by existing methods. We further apply the techniques in ENPOWER to: ensemble pruning and prompt-based ensembling of vision-language models.