shapiq.approximator.ShaplEIG¶

class shapiq.approximator.ShaplEIG(n, *, initial_design_size=None, max_candidates=1024, refit='every_iteration', warmstart=False, show_progress=True, random_state=None)[source]¶

Bases: Approximator[Literal[‘SV’]]

Bayesian experimental design (BED) approximator for Shapley values.

ShaplEIG fits a Gaussian process surrogate with a weighted Hamming product kernel on the queried coalition values and sequentially selects the next coalition to evaluate by maximizing the closed-form expected information gain (EIG) about the Shapley values. The Shapley structure is handled via elementary-symmetric-polynomial (ESP) identities of the kernel’s generating polynomials, so the full 2^n coalition space is never enumerated and each iteration costs only polynomial time in n. (n, shapiq’s number of players, is denoted p in the paper.) For more information, see Rundel et al. (2026) Rundel et al. [2026].

The returned InteractionValues contain the posterior-mean Shapley value estimates (order 1, index "SV"). approximate_with_variance() additionally returns the marginal posterior variances of the Shapley values.

Requires the optional shapleig extra (pip install shapiq[shapleig]) for torch / gpytorch / botorch.

Example

>>> from shapiq_games.synthetic import DummyGame
>>> from shapiq.approximator import ShaplEIG
>>> game = DummyGame(n=7, interaction=(1, 2))
>>> approximator = ShaplEIG(n=7, random_state=42, show_progress=False)
>>> values = approximator.approximate(budget=50, game=game)
>>> values.index, values.max_order
('SV', 1)

Initialize the ShaplEIG approximator.

Parameters:

n (int) – Number of players.
initial_design_size (int | None) – Number of coalitions in the initial design (drawn with the coalition sampler before the BED loop starts). Defaults to n + 1.
max_candidates (int | None) – Maximum size of the sampled candidate set the EIG is optimized over; games with fewer coalitions outside the initial design fall back to the exhaustive candidate set (all not-yet-evaluated coalitions). None forces the exhaustive candidate set (very costly for more than ~16 players). Defaults to 1024, as in the reference paper. Choose this clearly larger than the budget of the approximate call: one candidate is consumed per iteration, so with max_candidates close to the budget (almost) every candidate is evaluated eventually and the adaptive selection degenerates to the candidate sampling distribution.
refit (str) – When to refit the GP hyperparameters: "every_iteration" (default) or the staged schedule "decaying" (every iteration for the first 64, then every 8th for 128, every 16th for 256, every 32nd afterwards) for large budgets. The final surrogate is always refit. Note that for many players and large training sets the hyperparameter refit is the dominant per-iteration cost, so the staged schedule substantially reduces wall-clock time at large budgets.
warmstart (bool) – If True, hyperparameter refits start from the previous iteration’s fitted hyperparameters instead of fresh initial values.
show_progress (bool) – Whether to display a tqdm progress bar over the BED iterations.
random_state (int | None) – Random state seeding both the coalition sampling and the GP hyperparameter fitting. Defaults to None.

approximate(budget, game, **_)[source]¶

Run the BED loop and return posterior-mean Shapley value estimates.

Parameters:

budget (int) – Total number of game evaluations (initial design plus one evaluation per BED iteration).
game (Game | Callable[[ndarray[tuple[Any, ...], dtype[bool]]], ndarray[tuple[Any, ...], dtype[floating]]]) – The game to approximate, as a callable mapping a binary coalition matrix of shape (m, n) to m values.
_ (dict)

Return type:

InteractionValues

Returns:

The estimated Shapley values as InteractionValues.

approximate_with_variance(*, budget, game)[source]¶

Run the BED loop and return SV estimates with posterior variances.

Parameters:

budget (int) – Total number of game evaluations (initial design plus one evaluation per BED iteration).
game (Game | Callable[[ndarray[tuple[Any, ...], dtype[bool]]], ndarray[tuple[Any, ...], dtype[floating]]]) – The game to approximate, as a callable mapping a binary coalition matrix of shape (m, n) to m values.

Return type:

tuple[InteractionValues, ndarray]

Returns:

A tuple of the estimated Shapley values as InteractionValues (the posterior means) and an array of shape (n,) with the marginal posterior variances of the n players’ Shapley values (the diagonal of the SV posterior covariance, on the scale of the game values).

valid_indices: tuple[Literal['SV'], ...] = ('SV',)¶: The valid indices for the base approximator.