shapiq.game_theory.ExactComputer

class shapiq.game_theory.ExactComputer(game, n_players=None, *, evaluate_game=False)[source]

Bases: object

Computes a variety of game-theoretic values exactly.

The ExactComputer class computes exact values for cooperative games with a small number of players. Most game-theoretic concepts like the Shapley value, Banzhaf value, or the various interaction indices require the evaluation of the game on all possible \(2^n\) coalitions. This is feasible for small games (e.g. 5-14 players).

Currently, the following game-theoretic concepts are supported:

  • The Moebius Transform (Moebius)

  • The Co-Moebius Transform (Co-Moebius)

  • The Shapley Value (SV) [Sha53]

  • The Banzhaf Value (BV) [Ban64]

  • Shapley Interaction Index (SII) [Gra99]

  • Banzhaf Interaction Index (BII) [Gra99]

  • Chaining Interaction Index (CHII) [Mar99]

  • k-Shapley Interaction Index (k-SII) [Bor23]

  • Shapley Taylor Interaction Index (STII) [Sun20]

  • Faithful Shapley Interaction Index (FSII) [Tsa23]

  • Faithful Banzhaf Interaction Index (FBII) [Tsa23]

  • k-additive Shapley Interaction Index (kADD-SHAP) [Pel23]

  • Shapley Generalized Value (SGV) [Mar00]

  • Banzhaf Generalized Value (BGV) [Mar00]

  • Chaining Generalized Value (CHGV) [Mar07]

  • Internal Generalized Value (IGV) [Mar07]

  • External Generalized Value (EGV) [Mar07]

  • Joint Shapley Value (JointSV) [Har22]

  • Egalitarian Least Core (ELC) [Yan21]

Parameters:

  • n_players (int | None) – The number of players in the game.

  • game (Game | Callable[[ndarray[tuple[Any, ...], dtype[bool]]], ndarray[tuple[Any, ...], dtype[floating]]]) – A callable game that takes a binary matrix of shape (n_coalitions, n_players) and returns a numpy array of shape (n_coalitions,) containing the game values.

  • evaluate_game (bool) – whether to compute the values at init (if True) or first call (False)

Variables:

  • n – The number of players.

  • _game_fun – The callable game function.

Properties:

baseline_value: The baseline value of the game (empty coalition). coalition_lookup: A dictionary mapping coalitions to their indices in the game values. game_values: The game values for all coalitions.

References

[Sha53] (1,2)

Lloyd S. Shapley (1953). A Value for n-Person Games. Princeton University Press, pp. 307-318. https://doi.org/10.1515/9781400881970-018

[Ban64] (1,2)

John F. Banzhaf III (1964). Weighted voting doesn’t work: A mathematical analysis. Rutgers L. Rev., 19, 317.

[Dub81]

Pradeep Dubey, Abraham Neyman, Robert James Weber (1981) Value Theory Without Efficiency. In: Mathematics of Operations Research 6(1):122-128. Value Theory Without Efficiency. Mathematics of Operations Research 6(1):122-128. https://doi.org/10.1287/moor.6.1.122

[Gra99] (1,2,3,4)

Michel Grabisch, Marc Roubens (1999). An axiomatic approach to the concept of interaction among players in cooperative games. In: Game Theory 28:547-565. https://link.springer.com/article/10.1007/s001820050125

[Mar99] (1,2)

Jean-Luc Marichal, Marc Roubens (1999). The Chaining Interaction Index among Players in Cooperative Games. In: Meskens, N., Roubens, M. (eds) Advances in Decision Analysis. Mathematical Modelling: Theory and Applications, vol 4. Springer, Dordrecht. https://link.springer.com/chapter/10.1007/978-94-017-0647-6_5

[Mar00] (1,2,3,4)

Jean-Luc Marichal (2000). The influence of variables on pseudo-Boolean functions with applications to game theory and multicriteria decision making. In: Discrete Applied Mathematics 107(1-3):139-164. https://doi.org/10.1016/S0166-218X(00)00264-X

[Fui06] (1,2)

Katsushige Fujimoto, Ivan Kojadinovic, Jean-Luc Marichal (2006). Axiomatic characterizations of probabilistic and cardinal-probabilistic interaction indices. In: Games and Economic Behavior 55(1):72-99. https://doi.org/10.1016/j.geb.2005.03.002

[Mar07] (1,2,3,4,5,6,7,8,9)

Jean-Luc Marichal, Ivan Kojadinovic, Katsushige Fujimoto (2007). Axiomatic characterizations of generalized values. In: Discrete Applied Mathematics 155(1):26-43. https://doi.org/10.1016/j.dam.2006.05.002

[Web09]

Robert James Weber (2009). Probabilistic values for games. In: Roth AE, ed. The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge University Press. 1988:101-120. https://doi.org/10.1017/CBO9780511528446.008

[Sun20] (1,2,3)

Mukund Sundararajan, Kedar Dhamdhere, Ashish Agarwal (2020). In: Proceedings of the 37th International Conference on Machine Learning, PMLR 119:9259-9268. https://proceedings.mlr.press/v119/sundararajan20a.html

[Yan21] (1,2)

Tom Yan, Ariel D. Procaccia (2021). If You Like Shapley Then You’ll Love the Core. In: Proceedings of the AAAI Conference on Artificial Intelligence 35(6):5751-5759. https://doi.org/10.1609/aaai.v35i6.16721

[Har22] (1,2,3)

Chris Harris, Richard Pymar, Colin Rowat (2022). Joint Shapley values: a measure of joint feature importance. In: Proceedings of The Tenth International Conference on Learning Representations. https://openreview.net/forum?id=vcUmUvQCloe

[Bor23] (1,2)

Sebastian Bordt, Ulrike von Luxburg (2023). In: Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:709-745. https://proceedings.mlr.press/v206/bordt23a.html

[Tsa23] (1,2,3,4)

Che-Ping Tsai, Chih-Kuan Yeh, Pradeep Ravikumar (2023). Faith-Shap: The Faithful Shapley Interaction Index. In: Journal of Machine Learning Research 24(94):1-42. https://jmlr.org/papers/v24/22-0202.html

[Pel23] (1,2,3)

Guilherme Dean Pelegrina, Leonardo Tomazeli Duarte, Michel Grabisch (2023). A k-additive Choquet integral-based approach to approximate the SHAP values for local interpretability in machine learning. In: Artificial Intelligence 325:104014. https://doi.org/10.1016/j.artint.2023.104014

Initialize the ExactComputer class.

Parameters:

  • game (Game | Callable[[ndarray[tuple[Any, ...], dtype[bool]]], ndarray[tuple[Any, ...], dtype[floating]]]) – A callable cooperative game that expects a binary matrix of shape (n_coalitions, n_players) denoting presence and absence of players and returns a numpy array of shape (n_coalitions,) containing the game values.

  • n_players (int | None) – The number of players in the game (if game is not a shapiq.game.Game object). Defaults to None.

  • evaluate_game (bool) – Flag denoting whether to compute the game values at initialization of the ExactComputer (True) or at its first computation call (False).

static get_n_interactions(n_players)[source]

Pre-computes the number of interactions for all coalition sizes.

Pre-computes an array that contains the number of interactions up to the size of the index (e.g. n_interactions[4] is the number of interactions up to size 4).

Parameters:

n_players (int) – The number of players

Return type:

ndarray

Returns:

A numpy array containing the number of interactions up to the size of the index

Examples

>>> ExactComputer.get_n_interactions(3)
array([1, 4, 7, 8])  # binom(3, 0), binom(3, 0) + binom(3, 1), etc. ...
__call__(index, order=None)[source]

Calls the computation of the specified index or value.

Parameters:

  • index (Literal['SII', 'BII', 'CHII', 'Co-Moebius', 'SGV', 'BGV', 'CHGV', 'IGV', 'EGV', 'k-SII', 'STII', 'FSII', 'kADD-SHAP', 'FBII', 'SV', 'BV', 'JointSV', 'Moebius', 'ELC']) – The index or value to compute

  • order (int | None) – The order of the interaction index. If not specified the maximum order (i.e. n_players) is used. Defaults to None.

Return type:

InteractionValues

Returns:

The desired interaction values or generalized values.

Raises:

ValueError – If the index is not supported.

base_aggregation(base_interactions, order)[source]

Transform Base Interactions into Interactions satisfying efficiency, e.g. SII to k-SII.

Parameters:

  • base_interactions (InteractionValues) – InteractionValues object containing interactions up to order order.

  • order (int) – The highest order of interactions considered.

Return type:

InteractionValues

Returns:

InteractionValues object containing transformed base_interactions

base_generalized_value(index, order)[source]

Compute Base Generalized Values.

Base Generalized Values are probabilistic generalized values that do not depend on the order. According to the underlying representation using marginal contributions from [Mar07], the following indices are supported:

  • SGV: Shapley Generalized Value [Mar00]

  • BGV: Banzhaf Generalized Value [Mar00]

  • CHGV: Chaining Generalized Value [Mar07]

  • IGV: Internal Generalized Value [Mar07]

  • EGV: External Generalized Value [Mar07]

Parameters:

  • order (int) – The highest order of interactions

  • index (Literal['SGV', 'BGV', 'CHGV', 'IGV', 'EGV']) – The generalized value index

Return type:

InteractionValues

Returns:

An InteractionValues object containing generalized values.

base_interaction(index, order)[source]

Computes interactions based on representation with discrete derivatives.

Interactions based on the discrete derivative are base interactions like SII or BII.

Parameters:

  • index (Literal['SII', 'BII', 'CHII', 'Moebius', 'Co-Moebius']) – The interaction index

  • order (int) – The interaction order

Return type:

InteractionValues

Returns:

An InteractionValues object containing the base interactions.

compute_egalitarian_least_core()[source]

Computes the egalitarian least core (ELC) of the game.

The egalitarian least core (ELC) is a solution concept in cooperative game theory that distributes the total value of the grand coalition among the players in a way that minimizes the maximum excess of any coalition. It is a refinement of the core and represents a fair distribution of the total value of the grand coalition. The ELC is implemented after [Yan21].

Return type:

InteractionValues

Returns:

The egalitarian least core of the game.

compute_fii(index, order)[source]

Compute the FSII or FBII indices up to order order after [Tsa23].

Parameters:

  • order (int) – The highest order of interactions

  • index (Literal['FSII', 'FBII']) – FSII for Shapley or FBII for Banzhaf

Return type:

InteractionValues

Returns:

InteractionValues object containing FSII or FBII

compute_game_values()[source]

Evaluates the game on the powerset of all coalitions.

Return type:

tuple[float, ndarray[tuple[Any, ...], dtype[floating]], dict[tuple[int], int]]

Returns:

  • The baseline value of the game (empty coalition).

  • A numpy array of shape (2**n_players,) containing the game values for all coalitions.

  • A dictionary mapping coalitions (as tuples of player indices) to their corresponding

    index in the game values array.

compute_joint_sv(order)[source]

Computes the JointSV index up to an order according to [Har22].

Parameters:

order (int) – The highest order of interactions

Return type:

InteractionValues

Returns:

An InteractionValues object containing kADD-SHAP values

compute_kadd_shap(order)[source]

Computes the kADD-SHAP index up to order “order”.

The kADD-SHAP index is similar to FSII except that the coalition matrix contains the Bernoulli weights. The implementation is according to [Pel23].

Parameters:

order (int) – The highest order of interactions

Return type:

InteractionValues

Returns:

An InteractionValues object containing kADD-SHAP values

compute_stii(order)[source]

Compute the STII index up to order order after [Sun20].

Parameters:

order (int) – The highest order of interactions

Return type:

InteractionValues

Returns:

InteractionValues object containing STII

get_jointsv_weights(order)[source]

Pre-compute JointSV weights for all coalition sizes (0, ..., n - order).

Parameters:

order (int) – The highest order of interactions

Return type:

ndarray

Returns:

An array of pre-computed weights

probabilistic_value(index)[source]

Computes common semi-values or probabilistic values depending on the index.

These semi-values are special forms of interaction indices and generalized values for order = 1. According to the underlying representation using marginal contributions; cf. semi-values [Dub81], or probabilistic values [Web09] for the following indices are supported:

Parameters:

index (Literal['SV', 'BV']) – The interaction index

Return type:

InteractionValues

Returns:

An InteractionValues object containing probabilistic values

Raises:

ValueError – If the index is not supported

shapley_base_interaction(index, order)[source]

Computes Shapley Base Interactions, i.e. probabilistic interaction indices not depending on the order.

According to the underlying representation using discrete derivatives from [Fui06], the following indices are supported:

  • SII: Shapley Interaction Index [Gra99]

  • BII: Banzhaf Interaction Index [Gra99]

  • CHII: Chaining Interaction Index [Mar99]

  • Moebius: Moebius Transform [Ras02]

  • Co-Moebius: Co-Moebius Transform [Mar07]

Parameters:

  • order (int) – The highest order of interactions

  • index (Literal['SII', 'BII', 'CHII', 'Moebius', 'Co-Moebius']) – The interaction index

Return type:

InteractionValues

Returns:

An InteractionValues object containing interaction values

References

[Ras02]

Rota, G.-C. (1964). On the foundations of combinatorial theory I. Theory of Möbius functions. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 2, 340-368. doi: https://doi.org/10.1007/BF00531932

shapley_generalized_value(order)[source]

Computes Shapley Generalized Values.

The underlying representation of Shapley Generalized Values (i.e. Generalized Values that satisfy efficiency) is presented in [Mar07]. The following indices are supported:

Parameters:

order (int) – The highest order of interactions.

Return type:

InteractionValues

Returns:

An InteractionValues object containing generalized values

Raises:

ValueError – If the index is not supported.

shapley_interactions(index, order)[source]

Computes k-additive Shapley Interactions, i.e. probabilistic interaction indices that depend on the order k.

According to the underlying representation using discrete derivatives from [Fui06], the following indices are supported:

  • k-SII: k-Shapley Values [Bor23]

  • STII: Shapley-Taylor Interaction Index [Sun20]

  • kADD-SHAP: k-additive Shapley Values [Pel23]

  • FSII: Faithful Shapley Interaction Index [Tsa23]

Parameters:

  • order (int) – The highest order of interactions

  • index (Literal['k-SII', 'STII', 'kADD-SHAP', 'FSII']) – The interaction index

Return type:

InteractionValues

Returns:

An InteractionValues object containing interaction values

Raises:

ValueError – If the index is not supported

property baseline_value: float

Return the baseline value of the game (empty coalition).

property coalition_lookup: dict[tuple[int, ...], int]

Return the coalition lookup dictionary.

property game_values: ndarray

Return the game values for all possible coalitions.

property moebius_transform: InteractionValues

Computes and returns the Moebius transform of the game.

property n_players: int

Return the number of players in the game.

valid_indices: tuple[Literal['SII', 'BII', 'CHII', 'Co-Moebius', 'SGV', 'BGV', 'CHGV', 'IGV', 'EGV', 'k-SII', 'STII', 'FSII', 'kADD-SHAP', 'FBII', 'SV', 'BV', 'JointSV', 'Moebius', 'ELC'], ...] = ('SII', 'BII', 'CHII', 'Co-Moebius', 'SGV', 'BGV', 'CHGV', 'IGV', 'EGV', 'k-SII', 'STII', 'FSII', 'kADD-SHAP', 'FBII', 'SV', 'BV', 'JointSV', 'Moebius', 'ELC')

The valid indices for the exact computer.