Research map / Label-efficient and robust learning / Recognition and long-tail

Exact power indices for plurality-voting ensembles

NeurIPS 2026 · Label-efficient and robust learning › Recognition and long-tail · approach: Group-robust classification

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces a plurality-voting ensemble game with random tie-breaking and ENPOWER algorithms that compute exact Banzhaf and Shapley power indices of base classifiers in linear time (binary) and polynomial time (multiclass), applied to ensemble pruning and CLIP prompt ensembling.

Problem

Attributing each base classifier's contribution to a plurality-voting ensemble's predictions is hard because its impact depends on ties with other votes; exact power indices are intractable in general and existing games do not model plurality voting with random tie-breaking, especially for multiclas

Approach

Defines new characteristic-function games for plurality voting with random tie-breaking (binary and multiclass), derives closed-form Banzhaf and Shapley values for the binary case, and uses ordinary generating functions with dynamic programming over vote profiles for exact multiclass indices.

Key results

• ENPOWER computes exact binary Banzhaf/Shapley values in linear time, finishing in under one second on the largest datasets where sampling methods Tr-PS and MC take hundreds to thousands of seconds.
• Sub-ensembles chosen by ENPOWER rankings match or exceed baselines on CT with HET and match ACC on BM with AB in sub-ensemble selection.
• For CLIP prompt ensembling, ENPOWER-based sub-ensembles reach higher accuracy and F1 than Tr-MLE and Tr-PS for the best k and on average over k on all three datasets.

Surprising findings

• Rankings from ENPOWER correlate poorly with WMG-based Banzhaf rankings on several ensembles, showing existing games capture different attributions.

Limitations

• Only unweighted votes are handled; extending to weighted plurality voting is non-trivial.
• Analysis considers only hard votes of base classifiers.
• Sub-ensemble selection is not directly optimized for generalization, so gains are not uniform across datasets.

Experimental setup

Datasets: UCI TT UCI BM UCI BTSC UCI C9 UCI CR UCI CT CIFAR100 IMAGENET-A

Benchmarks: CIFAR100 IMAGENET-A UCI datasets (TT, BM, BTSC, C9, CR, CT)

Metrics: runtime Kendall's tau accuracy macro F1-score

Baselines: ISCG Tr-MLE Tr-PS WMG-β WMG-ϕ MC-β MC-ϕ ACC

Builds on: Banzhaf value Shapley value weighted majority games ordinary generating functions

Closest papers by meaning

• An urn model for majority voting in classification ensembles (NeurIPS 2016 · similarity 0.86)
• How many classifiers do we need? (NeurIPS 2024 · similarity 0.86)
• On Margins and Generalisation for Voting Classifiers (NeurIPS 2022 · similarity 0.86)
• Explaining Probabilistic Models with Distributional Values (ICML 2024 · similarity 0.84)
• Individual Fairness In Strategic Classification (NeurIPS 2025 · similarity 0.84)
• Strategic Classification With Externalities (ICLR 2025 · similarity 0.84)