PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact power indices for plurality-voting ensembles

Ilie Sarpe, Theofanis Georgakopoulos, Aristides Gionis

arXiv:2610.17980v1cs.LGcs.DScs.GT

TL;DR

Attributing each classifier’s contribution is challenging because its effect depends on the votes of other classifiers, while power-index computation is generally intractable. The paper introduces ENPOWER to compute exact Banzhaf and Shapley values for plurality voting with random tie-breaking. It reports efficient practical computation and applications to ensemble pruning and prompt-based ensembling.

  • Problem

    Classifier attribution must account for interactions among votes, while common heuristics inspect only a single sub-ensemble and power-index computation generally sums over exponentially many coalitions.

    Source: §1 · p. 1

  • Method

    ENPOWER models binary and multiclass plurality voting with random tie-breaking as cooperative games and computes exact Banzhaf and Shapley values using closed forms and ordinary generating functions.

    Source: §1 · p. 2, §4.2 · p. 5

  • Results

    ENPOWER computes exact binary values in O(|D|n) time and multiclass values in polynomial time, with exact indices produced in a few seconds on most practical instances.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The resulting attributions are not captured by existing methods and are applied to ensemble pruning and prompt-based ensembling of vision-language models.

    Source: §1 · p. 2, §6 · p. 10

    The methods apply only to ensembles whose base models provide hard classifications; the prompt-ensembling experiment therefore forces hard classifications, whereas the original work used soft votes.

    Source: Limitations · p. 14

Abstract

from arXiv · show

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.

1 Introduction

Attributing a base classifier’s contribution is difficult because its effect depends on other classifiers’ votes, while common heuristics inspect only a single sub-ensemble. The paper introduces ENPOWER for exact Banzhaf and Shapley attribution in plurality-voting ensembles with random tie-breaking, including binary and multiclass settings.

1 Introduction

  • Attribution heuristics such as leave-one-out accuracy or per-model performance ignore interactions across the Θ(2^n) sub-ensembles.A vote can change the prediction of any sub-ensemble tied for the most-voted class.Source: §1 · p. 1
  • Prior approximations and restricted weighted-majority games do not capture plurality voting with random tie-breaking and do not readily extend to multiclass settings.Computing power indices is generally intractable because it sums over exponentially many coalitions.Source: §1 · pp. 1–2
  • ENPOWER computes exact Banzhaf and Shapley values in O(|D|n) time for binary classification and polynomial time for multiclass classification.The multiclass bounds are O(|D|nℓ2) for Banzhaf values and O(|D|n3ℓ) for Shapley values; votes are unweighted and classifiers provide hard votes.Source: §1 · p. 2
  • ENPOWER uses structural symmetry: classifiers with identical votes receive equal contributions, with closed forms for binary values and low-degree ordinary generating functions for multiclass values.The multiclass generating functions are computed efficiently with dynamic programming.Source: §1 · p. 2
  • In practice, ENPOWER computes exact indices in a few seconds on most instances and yields attributions not captured by existing methods in ensemble pruning and prompt-based vision-language ensembling.The prompt-based application uses a zero-shot image-classification task.Source: §1 · p. 2

2 Related work

Prior work studies ensemble attribution and power indices, but the cited approaches do not fully model plurality voting with random tie-breaking across binary and multiclass settings. The paper positions ENPOWER as a direct attribution method for this setting and reports values not captured by existing methods.

2 Related work

  • The paper presents its work as the first to address attribution in plurality-voting ensembles with random tie-breaking for both binary and multiclass settings.It frames attribution as a challenge in explainable AI and notes prior use of power indices for models and features.Source: §2 · p. 2
  • Weighted majority games and prior binary-classification approaches cannot be used effectively for the paper’s plurality-voting setting.Earlier methods include an approximate Shapley method for soft binary classifiers under majority voting and diversity scores that do not match the ensemble aggregation rule.Source: §2 · p. 2
  • The authors report that ENPOWER yields attribution values not captured by existing methods and is specifically designed for multiclass settings where prior work cannot be adapted.They also report that ENPOWER is much faster than prior work and comparable with the fastest approximate method.Source: §2 · pp. 2–3

3 Preliminaries

The paper models classifier coalitions as cooperative games whose value reflects correct predictions under plurality voting and random tie-breaking. It defines dataset-level values by averaging point-wise games and establishes exact computation bounds for binary and multiclass settings.

3 Preliminaries

  • A classifier maps an input to a label, and the ensemble need not use one model family or require access to training data.The paper represents a coalition’s votes as a profile and defines its majority set as the labels tied for the highest vote count.Source: §3 · p. 3
  • Banzhaf and Shapley values measure player contributions through changes in coalition values; Shapley satisfies efficiency, while Banzhaf does not.The paper describes Banzhaf values as more robust to noise and easier to estimate, and Shapley values as the choice when values must sum to the grand-coalition value.Source: §3 · p. 3
  • For binary classification, a coalition receives value 1 for a correct majority, 1/2 for a tie, and 0 for an incorrect majority.The empty coalition is assigned value 0 for technical purposes, and dataset values average the point-wise coalition values.Source: §3 · p. 3
  • The binary game is neither monotone nor a simple game, yet both Banzhaf and Shapley values are computable in O(|D|n) time.The game’s possible values include 1/2, unlike the {0,1}-valued simple-game definition.Source: §3 · pp. 3–4
  • For multiclass classification, a coalition receives value 1/|M(S)| when the correct label is among the plurality labels, and 0 otherwise.The dataset game averages these point-wise values; this characteristic function generalizes the binary game.Source: §3 · p. 4
  • Exact multiclass computation takes O(|U|nℓ2 + |D|n) for Banzhaf values and O(|U|n3ℓ + |D|n) for Shapley values.|U| is the number of unique vote profiles, each ordered with the correct-class vote count first; |U| is at most |D| and can be much smaller in practice.Source: §3 · p. 4

4 Methods

ENPOWER computes exact Banzhaf and Shapley power indices for plurality-voting ensembles by exploiting symmetry and counting coalitions with closed forms or generating functions. The binary algorithms run in O(|D|n) time, while multiclass algorithms use low-degree polynomial-time computations.

4.1 Binary classification

  • The binary algorithm computes exact Banzhaf and Shapley values over the dataset in O(|D|n) time and O(n) memory.It counts correct predictions per data point and uses closed-form solutions for each classifier’s value.Source: §4.1 · p. 5

4.2 Multiclass classification

  • The multiclass method uses ordinary generating functions because the relevant coalitions have a more complex structure than in the binary case.For Banzhaf values, coefficients count coalitions by how many incorrect labels receive exactly h votes; Shapley values additionally track coalition size.Source: §4.2 · p. 5

4.2.1 Computation of Banzhaf values in the multiclass setting

  • In multiclass settings, the Banzhaf algorithm computes exact values in O(|U|nℓ^2 + |D|n) time and O(ℓ(n+|U|)) memory.It uses generating-function coefficients to count relevant coalitions and exploits classifier symmetries.Source: §4.2 · pp. 5–6, §4.2.1 · p. 6

4.2.2 Computation of Shapley values in the multiclass setting

  • For multiclass Shapley values, a bivariate generating function tracks both coalition structure and size, enabling exact computation in O(|U|n^3ℓ + |D|n) time.Dynamic programming computes the polynomial coefficients; ENPOWERMC-ϕ++ further improves the stated time-complexity bound.Source: §4.2 · p. 5, §4.2.2 · pp. 6–7

5 Experiments

The experiments assess ENPOWER’s efficiency, ranking differences, use in sub-ensemble selection, and prompt ensembling. ENPOWER is fast for binary instances, produces rankings not fully captured by prior methods, and supports competitive selections in both applications.

5 Experiments

  • The experiments evaluate efficiency, ranking comparisons, pruning, and vision-model prompt ensembling across binary and multiclass settings.The setup uses six UCI datasets, five random splits unless otherwise stated, and RF, AB, and heterogeneous ensembles.Source: §5 · pp. 7–8

5.1 Efficiency and scalability

  • Under one second on the largest binary datasets, ENPOWER outpaces sampling methods taking hundreds or thousands of seconds and is 1–3 orders faster than WMG on AB.The AB ensemble has n = 150 classifiers; multiclass Shapley computation on CT with AB has high runtime due to an O(n^3) term.Source: Figure 1 · p. 8, §5.1 · p. 8

5.2 Comparison of rankings of base classifiers

  • Ranking agreement depends strongly on the baseline and dataset, and ENPOWER rankings are not fully captured by prior methods.ISCG agreement is low on RF and HET but high on AB except BTSC; WMG and ISCG correlations range from negative to above 0.9 for a fixed ensemble across datasets.Source: Figure 2 · p. 8, §5.2 · p. 9

5.3 Sub-ensemble selection

  • ENPOWER rankings often yield sub-ensembles among those with the largest accuracy and F1-score, despite not being optimized directly for selection.On CT with HET, ENPOWER matches or outperforms all baselines for every k; on BM with AB, it matches ACC across k.Source: §5.3 · p. 9, Figure 3 · p. 9

5.4 Large vision model prompt ensembling

  • On all three prompt-ensembling datasets, ENPOWER selections attain higher accuracy and F1-score than Tr-MLE and Tr-PS at the best k and averaged across k.ENPOWER matches or improves on ACC; best-performing ensembles generally contain 1–17 of 22 prompts.Source: §5.4 · p. 10, Figure 4 · p. 10

6 Conclusions

The paper introduces games for plurality voting with random tie-breaking and exact polynomial-time algorithms for Banzhaf and Shapley values. It reports practical efficiency and applications to pruning and prompt ensembling.

6 Conclusions

  • ENPOWER computes exact Banzhaf and Shapley values using new polynomial-time algorithms for binary and multiclass plurality-voting games.The approach uses combinatorial identities and ordinary generating functions for the multiclass case.Source: §6 · p. 10
  • The indices are reported as efficient in practice and not captured by previous methods.Source: §6 · p. 10
  • The paper applies the indices to ensemble pruning and LLM prompt ensembling, and identifies data validation and other power indices as future directions.Source: §6 · p. 10

Limitations

The methods apply only to ensembles whose base models provide hard classifications. The authors also report baseline mismatches and note that the prompt-ensembling experiment forces hard classifications despite the original work using soft votes.

Limitations

  • The methods require base models that provide hard classifications.For prompt ensembling, the experiment forces hard classifications although the original work used soft votes.Source: Limitations · p. 14
  • Some inputs yield results that do not match baseline methods, including high accuracy but low F1-score or the reverse in ensemble sub-selection.The authors describe these cases and related trade-offs in Section 5.Source: Limitations · p. 14

LLM usage

This material records the authors’ use of LLMs, discusses related game formulations, and provides background definitions and auxiliary results. It contrasts plurality-voting attribution with approaches that restrict coalitions or fail to represent multiclass interactions.

LLM usage

  • LLMs assisted proofreading, proof-idea exploration, implementation, data analysis, and literature exploration; the authors verified the technical results, proofs, experiments, and conclusions.The authors state that they assume full responsibility for the manuscript.Source: LLM usage · p. 14

A Extended discussion on related work

  • Under unitary weights, WMG indices depend only on coalitions of size q−1, whereas this paper’s game can depend on coalitions of any size.For pruning to k < ⌊n/2⌋ models, majority-quota WMG indices ignore coalitions of size at most k.Source: A Extended discussion on related work · p. 16
  • Prior formulations often cannot extend to multiclass settings without high cost and information loss, and pairwise binary games miss interactions among class predictions.The cited multiclass method instead models induced-clique volume, which differs from ensemble aggregation mechanisms.Source: A Extended discussion on related work · p. 16

B.1 Cooperative game theory

  • The background defines Banzhaf and Shapley values through coalition contributions and describes sum games as pointwise sums of characteristic functions.A WMG assigns a win when a coalition’s total weight reaches a fixed quota.Source: §B.1 · p. 17

B.2 Combinatorics

  • Ordinary generating functions encode a sequence as a power series, and [xℓ]P(x) extracts its coefficient of xℓ.These are among the combinatorial tools recalled for the analysis.Source: §B.2 · p. 17

C.1 Auxiliary technical results

  • The auxiliary proofs characterize binary marginal gains around ties and one-vote gaps, and multiclass gains when adding a vote changes the set of tied leaders.The multiclass cases distinguish whether the added classifier is correct and how its vote changes the tied-majority set.Source: §C.1 · pp. 18–19

C.2 Proofs of Sec. 3

The binary characteristic-function game lacks several standard structural properties. Counterexamples establish that it is neither supermodular, superadditive, nor monotone, and therefore is non-convex.

C.2 Proofs of Sec. 3

  • The binary characteristic function vB is neither supermodular, superadditive, nor monotone.The paper also states that the resulting game is non-convex.Source: §C.2 · pp. 19–20
  • A five-classifier example violates supermodularity by reversing the marginal contribution of a classifier across two coalitions.The example compares the addition of C5 to S4 and S3.Source: §C.2 · p. 19
  • The same example violates superadditivity and monotonicity: vB(S1 ∪ S2) is below the sum of values, and vB(S) is below vB(S1).These inequalities are given for the constructed coalitions.Source: §C.2 · pp. 19–20

C.3 Proofs of Sec. 4.1

The proofs reduce binary power-index calculations to marginal-gain cases over coalitions and exploit symmetry among classifiers with identical votes. They describe linear-time computation per data point and linear memory in the binary setting.

C.3 Proofs of Sec. 4.1

  • For Banzhaf values, an incorrect classifier has nonzero marginal gain only when correct and incorrect vote counts differ by zero or one.The proof averages these gains over uniformly random subsets of the other classifiers.Source: §C.3 · pp. 20–21
  • For a correct classifier, the Shapley proof identifies nonzero gains from the singleton coalition, tied votes, and coalitions where the correct vote trails by one.The proof represents the other classifiers as a uniformly random subset.Source: §C.3 · pp. 20–21
  • Identical classifier votes imply equal Banzhaf and Shapley values, allowing values to be computed once per vote group.The proof states that this symmetry supports linear-time computation per data point.Source: §C.3 · p. 22
  • Storing values for all binary vote profiles and the final output requires O(n) memory.The proof uses |U| ≤ n + 1 for the number of binary vote profiles.Source: §C.3 · p. 23

C.4 Proofs of Sec. 4.2.1

These proofs count coalitions that make a classifier pivotal by organizing them around vote ties. They also use symmetry to reuse Banzhaf values for repeated vote profiles.

C.4 Proofs of Sec. 4.2.1

  • Coalition counts fix which incorrect labels receive h votes, then count choices for remaining labels with fewer than h votes.The proof sums over the size-k label subsets and uses products of per-label choice counts.Source: §C.4 · p. 23
  • Pivotal coalitions are separated by whether a correct or incorrect classifier joins a coalition tied among the leading labels.The proof partitions these cases by the number of tied labels and the vote-count relationships that the classifier changes.Source: §C.4 · p. 24
  • Identical vote profiles yield reusable Banzhaf values, so the algorithm computes each unique profile once and caches its result.After caching, retrieving the value for a matching profile takes O(1) time.Source: §C.4 · p. 25

C.5 Proofs of Sec. 4.2.2

The proofs extend coalition counting to Shapley values by tracking coalition size as well as vote ties. The accompanying algorithms exploit symmetry and dynamic programming for binary and multiclass computation.

C.5 Proofs of Sec. 4.2.2

  • The bivariate generating function counts coalitions by the number of tied incorrect labels and total coalition size.Its coefficient indexed by k, h, and m gives the count for coalitions with k incorrect labels tied at h votes and size m.Source: §C.5 · p. 26

D.1 Binary classification

  • Binary computation uses symmetry so all correct classifiers share one power-index value and all incorrect classifiers share another for each point.The implementation therefore calls the binary subroutine twice per data point.Source: §D.1 · p. 29

D.2 Multiclass classification

  • Multiclass dynamic programming computes generating-function coefficients profile by profile and reuses cached values for repeated profiles.For Shapley values, the stated time bound is O(|U|n^3ℓ + |D|n).Source: §C.5 · p. 29, §D.2 · pp. 30–31

E Efficient and numerically stable implementation

The implementation addresses numerical stability and repeated computation in the binary formulas, while multiclass arithmetic uses exact integer coefficients. Exact integer operations retain accuracy but increase arithmetic cost.

E Efficient and numerically stable implementation

  • O(n) Shapley computation uses a recurrence that avoids factorials and binomial terms, making the summation numerically stable.The recurrence evaluates each term with a constant number of operations.Source: E Efficient and numerically stable… · p. 33
  • Multiclass coefficient matrices use fixed-width exact integers from 128 to 1024 bits, supporting ensembles with n ≤ 1023.Only the final weighted sum is evaluated in floating point; long-integer arithmetic increases runtime.Source: E Efficient and numerically stable… · p. 33

F.1 Setup

The setup describes the experimental computing environment, software, and dataset preparation. It also specifies the classifier ensembles and the reported timing scope.

F.1 Setup

  • Experiments ran sequentially on one CPU thread, and reported runtimes exclude ensemble training and base-model prediction evaluation.The machine had four Intel Xeon Gold 6252N CPUs and 3 TB of RAM.Source: §F.1 · pp. 34–35
  • ENPOWER and the WMG, ISCG, and MC baselines used C++17, while Tr-MLE and Tr-PS used Python 3.10.Ensembles were trained with Scikit-learn and CLIP predictions were computed with PyTorch.Source: §F.1 · p. 35
  • For RF and AB, no custom parameters were set beyond ensemble size; HET classifiers used slightly different parameters to enforce heterogeneity.The experiments trained these ensembles using 75% of each dataset's data points.Source: §F.1 · p. 36

F.2 Datasets

The appendix documents dataset preparation and baselines, then adds runtime, sampling, sub-ensemble-selection, and CLIP prompt-ensembling results. Across these experiments, ENPOWER’s rankings and power indices provide practical comparisons, with some exceptions for sub-ensembles and a remaining challenge in efficient sampling.

F.2 Datasets

  • For binary and multiclass experiments, datasets are publicly available and processed with standard preprocessing; binary datasets map the most frequent class to positive, and data are split 75/15/10 for training, validation, and testing.The multiclass class-imbalance table reports class count, min/max class sizes, imbalance ratio, coefficient of variation, and normalized entropy.Source: §F.2 · p. 36, Table 3 · p. 37
  • The prompt-ensembling datasets span balanced CIFAR, nearly balanced PETS, and highly imbalanced IMAGENET-A; each is split equally into Dval and Dtest.The dataset appendix also describes CIFAR as 32×32 pixels, PETS as high-quality images with fine-grained classes, and IMAGENET-A as challenging for image classification.Source: §F.2 · p. 37, Figure 5 · p. 37

F.3 Baselines

  • The baseline comparisons include prior-game methods, but WMG-based baselines do not directly extend to multiclass classification, and the considered reduction cannot distinguish incorrect labels or account for ties.The simple Monte-Carlo baselines had high runtime and poor estimation quality, motivating efficient sampling as an open direction.Source: §F.3 · p. 38

G.1 Monte-Carlo approximation

  • Sampling usually recovers ranking metrics, but some configurations have Kendall ranking metrics below 0.3 and non-negligible relative error.The authors connect relative error to small power-index values and leave efficient sampling, especially for multiclass, as an open direction.Source: §G.1 · p. 39

G.2 Runtime of ENPOWERMC

  • For multiclass runtime, ENPOWER-β takes at most 2 seconds; ENPOWER-ϕ takes at most 8 seconds on C9 and 3 seconds on CT with RF and HET.On CT with AB, ENPOWER-ϕ takes about 4 minutes, while ENPOWERMC-ϕ++ reduces runtime to about 77 seconds.Source: §G.2 · p. 40

G.4 Ensemble sub-selection

  • ENPOWER-selected top-k models consistently rank among the best for accuracy and F1 generalization, with exceptions on CT with AB and CR with HET.On those exceptions, ACC performs better at intermediate k on CT, while WMG-ϕ and WMG-β perform better at small k on CR; the authors note full-ensemble contributions may differ for k < n.Source: §G.4 · p. 41

G.5 CLIP prompt ensembling

  • For PETS, power-index prompt selection yields accuracy and F1-score metrics comparable to ACC and higher than Tr-MLE and Tr-PS.Across the three datasets, ENPOWER-β runs in under 0.02 seconds and ENPOWER-ϕ in under one second; the authors describe the methods as useful for prompt engineering and interpretability.Source: §G.5 · p. 42
  • Power-index prompt rankings can diverge from accuracy rankings: on CIFAR, one accuracy-high prompt has a poor power-index ranking and a negative Banzhaf value.On IMAGENET-A, the watermark prompt ranks high by accuracy but substantially lower by power indices.Source: §G.5 · p. 42

G.6 Synthetic experiments

Synthetic instances vary vote-profile count, ensemble size, class count, and the fraction of correct classifiers to test runtime per unique profile. ENPOWER’s measured scaling broadly follows its theoretical bounds, while some multiclass bounds appear pessimistic.

G.6 Synthetic experiments

  • Synthetic instances vary |U|, n, and ℓ; each profile is generated from the correct-vote count n1 and the number r of incorrect labels receiving votes.Incorrect votes are distributed as evenly as possible over r labels, and profiles are ordered around n1 ≈ pn, with larger r first.Source: §G.6 · pp. 42–43
  • Binary runtime per unique profile grows linearly with n, while multiclass ENPOWER-β is almost linear in n for fixed ℓ.For p = 0.1 and high ℓ, the multiclass Banzhaf runtime appears slightly larger than linear; increasing ℓ at fixed n does not produce the O(ℓ^2) growth in the bound.Source: §G.6 · p. 44
  • ENPOWER-ϕ and ENPOWERMC-ϕ++ are much more efficient in practice than their large-n^3ℓ theoretical bound suggests, and ENPOWERMC-ϕ++ is always faster.The multiclass Shapley runtime appears slightly superlinear in n only for p = 0.1 and high ℓ.Source: §G.6 · p. 44
  • Figure 9 compares runtime per unique profile across p = 0.1, 0.5, and 0.9, with panels covering binary and multiclass algorithms and theoretical bounds.For multiclass panels, lines fix ℓ and vary n; dotted lines show theoretical bounds.Source: §G.6 · p. 44, Figure 9 · p. 46

H A refined multiclass Shapley value computation

The refined multiclass Shapley algorithm reduces dynamic-programming work by storing only relevant coefficients. Its resulting complexity bound is never worse than the original bound and improves in particular vote-profile regimes.

H A refined multiclass Shapley value computation

  • The algorithm exploits the fact that coefficients with m < kh are zero, avoiding their computation and further reducing the matrix size.The implementation stores columns indexed m ≥ kh for each row k.Source: H A refined multiclass Shapley value… · pp. 47–48
  • For fixed h, the refined matrix has K(h) + 1 rows and Φ(h) + 1 columns instead of ℓ rows and n − n1 + 1 columns.K(h) counts incorrect labels with at least h votes, while Φ(h) counts retained incorrect classifiers after limiting each label to at most h.Source: H A refined multiclass Shapley value… · p. 47
  • The refinement reduces ENPOWERMC-ϕ’s dynamic-programming matrix, and its runtime bound is never worse than the original bound for any vote profile.It retains only nonzero coefficients; coefficients with m < kh are zero and need not be visited.Source: H A refined multiclass Shapley value… · p. 47
  • When n − n1 = O(1) or n1 = O(1), the refined analysis yields smaller complexity bounds, avoiding the O(n^3ℓ) term in the latter regime.The first regime has N* = O(1); the second has N* = O(min{n, ℓ}).Source: H A refined multiclass Shapley value… · p. 48

H.1 ENPOWERMC-ϕ++: an improved algorithm

This section presents ENPOWERMC-ϕ++ as an improved polynomial-multiplication algorithm for computing Shapley contributions, preserving the prior algorithm’s output while reducing computation and improving asymptotic time. The improvement comes with higher memory use for the top-down pass.

H.1 ENPOWERMC-ϕ++: an improved algorithm

  • ENPOWERMC-ϕ++ matches Algorithm 4’s output while restricting each iteration to a smaller matrix and loop ranges containing only potentially nonzero coefficients.It limits h to H⋆, sizes the matrix to (K(h)+1) × (Φ(h)+1), and bounds k and m using K(h), Φ(h), and the vote counts.Source: §H.1 · pp. 48, 52
  • For N⋆≥ℓ, ENPOWERMC-ϕ++ improves the per-profile time bound by a factor ℓn^3/(N⋆)^3; its O((N⋆)^3) bound is tight.The bound is never worse than Algorithm 4’s, and when a fraction α of classifiers predicts the correct label, the improvement is Ω(ℓ/(1−α)^3), reaching a factor 10^3ℓ for α=9/10.Source: §H.1 · p. 53

H.2 A fast polynomial multiplication-based algorithm

  • A fast-polynomial-multiplication alternative is outlined with per-iteration cost O(K(h)(Φ(h−1)+1) log(K(h)(Φ(h−1)+1)) log ℓ), but is not implemented.The authors focus on exact arithmetic and note that the alternative requires products modulo primes followed by Chinese remainder reconstruction.Source: §H.2 · p. 53
  • Each iteration h’s bottom-up pass costs O(M(K(h)(Φ(h − 1) + 1)) log ℓ) operations, or O(K(h)(Φ(h − 1) + 1) log(K(h)(Φ(h − 1) + 1)) log ℓ) using FFT multiplication.The balanced product tree combines label factors while reducing the generating function’s degree in u; coefficients are recovered after the implicit index shift.Source: §H.2 · pp. 54–55
  • Each of the two top-down passes costs O(M(K(h)(Φ(h − 1) + 1)) log ℓ) operations and obtains the incorrect classifiers’ Shapley contributions without explicitly computing each removed-factor polynomial Qj.The passes propagate linear-functional matrices through the product tree; a node’s child matrices are computed by polynomial multiplication in O(M((Kv + 1)(Φv + 1))) operations.Source: §H.2 · pp. 56–59
  • The improved bound is faster than Theorem H.7 by a factor Θ((eN + ℓ)/(log(ℓeN) log ℓ)), with both bounds retaining O(|D|n) classifier-evaluation cost.The improved bound is O(|U|(eN)^2 log(ℓeN) log ℓ + |D|n).Source: §H.2 · p. 59
  • Memory complexity is O(|U|ℓ + ℓeN log ℓ), because the top-down pass retains matrices at all O(log ℓ) levels.For a fixed iteration h, the tree uses O(K(h)(Φ(h − 1) + 1) log ℓ) memory; the Λv functionals add no asymptotic memory complexity.Source: §H.2 · p. 59
Loading 2610.17980v1…