summaries: This paper studies valuation problems from cooperative game theory. There are $n$ agents and a valuation function $F: [n] \to R$ where $F(S)$ is the collective payoff of the coalition $S \subseteq [n]$. The goal is to use this function $F$ to define an importance vector $\phi(F) \in R^n$. Examples include the Shapley value and Banzhaf index.  The authors introduce a probabilistic treatment of this problem, where they use $F$ to define a probability distribution $p$ where $p(S)$ is the probability that coalition $S$ forms. They then phrase the problem of defining an importance vector $\phi(F)$ as a decoupling problem. Under $p$, the $n$ agents may be correlated in a complicated way, but to assign each of them an individual importance value, one must decouple their interactions, or simplify their correlations. The goal is then to find a product distribution $q$ that is as close to $p$ as possible under the KL divergence. Specifically, the authors define $q$ to be an $n$ independent Bernoulli distribution, where the probability that agent $i$ participates in the coalition is denoted $x_i$. The authors show how to optimize the probabilities $x_1, \dots, x_n$ using coordinate ascent. Finally, they define the importance score of player $i$ as $\log(x_i/(1-x_i))$ (ignoring a temperature $T$ term for simplicity). The authors show that the resulting importance vector satisfies many of the game-theoretic axioms that the Shapley value and Banzhaf index satisfy, like the null player, marginalism, and symmetric axioms.  In the experiments, the authors look at small instances with $n = 25$ where it is actually possible to compute the gradients exactly (as opposed to an approximate sampling method). The applications they look at are for data valuation and feature attribution in the context of machine learning. For these tasks, they show that their proposed approach performs about the same as the Shapley value and Banzhaf index, and sometimes a bit better.

summaries: Valuation criteria based on game-theory (e.g. Shapely value) have been used in the ML literature for analyzing feature importance and for data subset selection. These criteria serve as solution concepts for cooperative games and have been adapted by some works in ML for subset valuation problems.    The present paper presents a probabilistic treatment of cooperative games, and shows that two classical valuation criteria can be seen as a one-step factored approximation to maximum entropy solution to the game. They then propose a new valuation criterion "Variational Index" that uses a multi-step factored approximation and show it satisfies some common axioms for cooperative games. The paper also has experimental results on the proposed criterion.

summaries: The paper studies valuation problems for cooperative games. It proposes a new valuation measure called Variational Index. The idea is to create a coalition probability distribution based on a maximum entropy criterion. Player valuations are then derived by creating decoupled surrogates of this distribution. The authors then present a gradient ascent algorithm to compute this decoupling. Classical valuation criteria like the Shapley value and the Banzhaf index can be recovered as special cases or modifications of the algorithms iterates.

summaries: This paper proposes an energy-based perspective on cooperative games that permits a gradient-based calculation of Shapley/Banzhaf values, as well as the definition of a new alternative value - the variational index. A quick summary of the paper's key ideas is:  - For a given cooperative game $F$, we can seek an entropy maximizing distribution over coalitions $p(S)$ that satisfies a constraint on the mean coalition value $\mu$ - Solving the entropy maximization problem via its Lagrangian yields the Boltzmann distribution $p(S) \propto \exp(F(S)/T)$, where the temperature $T$ has a one-to-one correspondence with the mean coalition value $\mu$ (this result is in the appendix). This distribution gives more probability mass to coalitions that achieve higher values - We can seek a simpler alternative to $p(S)$ by doing mean-field variational inference, i.e., finding a factorized surrogate $q(S)$ where each player's participation is determined by independent Bernoulli RVs. The result will intuitively assign higher probabilities to players that belong to high-value coalitions, so these probabilities can serve a function similar to Shapley/Banzhaf values - The VI approach suggests a KL divergence minimization (or ELBO maximization) objective for learning $q(S)$, which is parameterized by $x \in [0, 1]^n$. Doing gradient descent on this objective yields a relatively simple update rule, where we repeatedly set $x_i^+ = \sigma(\nabla_i f_{mt}(x) / T)$ for $i = 1, \ldots, n$ - The authors define the "variational index" as a function of the solution to the KL divergence minimization problem: $s^* = T\sigma^{-1}(x^*)$ - The authors find that the Banzhaf value can be found using a single-step update to a particular initialization of the KL divergence minimization problem (luckily the temperature $T$ is not important for single-step updates). Similarly, they find that the Shapley value is the average of the single-step update applied to different initializations (again, the temperature doesn't matter). Finally, the authors point out that any single-step update applied to a symmetric initialization will be a probabilistic value (a class of solution concepts in cooperative game theory, of which Shapley/Banzhaf values are special cases) - Lastly, the authors suggest a practical sampling-based approach to calculating the necessary gradients, which are just as difficult to calculate as the Shapley/Banzhaf values because they require calculating the value for every coalition $S \subseteq N$  The experiments compare the variational index to Shapley and Banzhaf values in data and feature removal tasks, finding that it performs quite favorably in the settings examined.

abstractText: Valuation problems, such as feature interpretation, data valuation and model valuation for ensembles, become increasingly more important in many machine learning applications. Such problems are commonly addressed via well-known game-theoretic criteria, such as the Shapley value or Banzhaf value. In this work, we present a novel energy-based treatment for cooperative games, with a theoretical justification by the maximum entropy principle. Surprisingly, by conducting mean-field variational inference of the energy-based model, we recover classical game-theoretic valuation criteria through conducting one-step fixed point iteration for maximizing the ELBO objective. This observation also verifies the rationality of existing criteria, as they are all attempting to decouple the correlations among players. By running the fixed point iteration for multiple steps, we achieve a trajectory of the variational valuations, among which we define the valuation with the best conceivable decoupling error as the Variational Index. We prove that under uniform initializations, these variational valuations all satisfy a set of game-theoretic axioms. We empirically demonstrate that the proposed Variational Index enjoys lower decoupling error and better valuation performance on certain synthetic and real-world valuation problems.

authors:
M. Ancona
E. Ceolini
C. Öztireli
M. Gross

title: Towards better understanding of gradient-based attribution methods for deep neural networks

venue: arXiv preprint arXiv:1711.06104,

authors:
M. Ancona
C. Öztireli
M. Gross

title: Explaining deep neural networks with a polynomial time algorithm for shapley values approximation

venue: arXiv preprint arXiv:1903.10992,

title: Weighted voting doesn’t work: A mathematical analysis

venue: Rutgers L. Rev.,

authors:
S. Bartunov
J.W. Rae
S. Osindero
T.P. Lillicrap

title: Meta-learning deep energy-based memory models

venue: arXiv preprint arXiv:1910.02720,

authors:
Y.A. Bian
J.M. Buhmann
A. Krause

title: Optimal continuous dr-submodular maximization and applications to provable mean field inference

venue: In Proceedings of the 36th International Conference on Machine Learning,

authors:
G. Calinescu
C. Chekuri
M. Pál
J. Vondrák

title: Maximizing a submodular set function subject to a matroid constraint

venue: In International Conference on Integer Programming and Combinatorial Optimization,

authors:
J. Chen
L. Song
M.J. Wainwright
M.I. Jordan

title: L-shapley and c-shapley: Efficient model interpretation for structured data

venue: arXiv preprint arXiv:1808.02610,

title: A new axiomatization of the shapley value

venue: Games and Economic Behavior,

authors:
S. Cohen
G. Dror
E. Ruppin

title: Feature selection via coalitional game theory

venue: Neural Computation,

authors:
I. Covert
S. Lundberg
S.-I. Lee

title: Explaining by removing: A unified framework for model explanation

venue: arXiv preprint arXiv:2011.14878,

title: Understanding global feature contributions with additive importance measures

venue: arXiv preprint arXiv:2004.00668,

authors:
A. Datta
S. Sen
Y. Zick

title: Algorithmic transparency via quantitative input influence: Theory and experiments with learning systems

venue: IEEE symposium on security and privacy (SP),

authors:
Y. Deng
A. Bakhtin
M. Ott
A. Szlam
M. Ranzato

title: Residual energy-based models for text generation

venue: arXiv preprint arXiv:2004.11714,

authors:
J. Djolonga
A. Krause

title: From map to marginals: Variational inference in bayesian submodular models

venue: In Neural Information Processing Systems (NIPS),

authors:
Z. Fan
H. Fang
Z. Zhou
J. Pei
M.P. Friedlander
C. Liu
Y. Zhang

title: Improving fairness for data valuation in federated learning

venue: arXiv preprint arXiv:2109.09046,

authors:
U. Feige
V.S. Mirrokni
J. Vondrák

title: Maximizing non-monotone submodular functions

venue: SIAM Journal on Computing,

authors:
A. Ghorbani
J. Zou

title: Data shapley: Equitable valuation of data for machine learning

venue: In International Conference on Machine Learning,

title: K-order additive discrete fuzzy measures and their representation

venue: Fuzzy sets and systems,

authors:
M. Grabisch
J.-L. Marichal
M. Roubens

title: Equivalent representations of set functions

venue: Mathematics of Operations Research,

authors:
W. Grathwohl
K.-C. Wang
J.-H. Jacobsen
D. Duvenaud
M. Norouzi
K. Swersky

title: Your classifier is secretly an energy based model and you should treat it like one

authors:
G. Greco
F. Lupia
F. Scarcello

title: Structural tractability of shapley and banzhaf values in allocation games

venue: In Twenty-Fourth International Joint Conference on Artificial Intelligence,

authors:
F.K. Gustafsson
M. Danelljan
R. Timofte
T.B. Schön

title: How to train your energy-based model for regression

venue: arXiv preprint arXiv:2005.01698,

authors:
M. Gutmann
A. Hyvärinen

title: Noise-contrastive estimation: A new estimation principle for unnormalized statistical models

venue: In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics,

authors:
T. Haarnoja
H. Tang
P. Abbeel
S. Levine

title: Reinforcement learning with deep energy-based policies

authors:
P.L. Hammer
S. Rudeanu

title: Boolean methods in operations research and related areas, volume 7

venue: Springer Science & Business Media,

title: Training products of experts by minimizing contrastive divergence

venue: Neural computation,

title: Probability inequalities for sums of bounded random variables

venue: Journal of the American statistical association,

title: Estimation of non-normalized statistical models by score matching

venue: Journal of Machine Learning Research,

title: Information theory and statistical mechanics

venue: Physical review,

venue: ii. Physical review,

authors:
R. Jia
D. Dao
B. Wang
F.A. Hubis
N. Hynes
N.M. Gürel
B. Li
C. Zhang
D. Song
C.J. Spanos

title: Towards efficient data valuation based on the shapley value

venue: In The 22nd International Conference on Artificial Intelligence and Statistics,

authors:
R. Jia
X. Sun
J. Xu
C. Zhang
B. Li
D. Song

title: An empirical and comparative analysis of data valuation with scalable algorithms

venue: arXiv preprint arXiv:1911.07128,

authors:
A. Krause
D. Golovin

title: Submodular function maximization

venue: Tractability,

authors:
I.E. Kumar
C. Scheidegger
S. Venkatasubramanian
S. Friedler

title: Shapley residuals: Quantifying the limits of the shapley value for explanations

venue: In ICML Workshop on Workshop on Human Interpretability in Machine Learning (WHI),

authors:
Y. LeCun
S. Chopra
R. Hadsell
M. Ranzato
F. Huang

title: A tutorial on energy-based learning

venue: Predicting structured data,

authors:
S. Lipovetsky
M. Conklin

title: Analysis of regression in game theory approach

venue: Applied Stochastic Models in Business and Industry,

authors:
W. Liu
X. Wang
J.D. Owens
Y. Li

title: Energy-based out-of-distribution detection

venue: arXiv preprint arXiv:2010.03759,

authors:
S. Lundberg
S.-I. Lee

title: A unified approach to interpreting model predictions

venue: arXiv preprint arXiv:1705.07874,

authors:
S.M. Lundberg
G.G. Erion
S.-I. Lee

title: Consistent individualized feature attribution for tree ensembles

venue: arXiv preprint arXiv:1802.03888,

title: Expectation propagation for approximate bayesian inference

venue: In Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence,

authors:
D. Monderer
D. Samet

title: Variations on the shapley value

venue: Handbook of game theory with economic applications,

authors:
R. Okhrati
A. Lipani

title: A multilinear sampling algorithm to estimate shapley values

venue: In 2020 25th International Conference on Pattern Recognition (ICPR),

title: Sobol’indices and shapley value

venue: SIAM/ASA Journal on Uncertainty Quantification,

title: Multilinear extensions of games

venue: Management Science,

title: The elementary statistics of majority voting

venue: Journal of the Royal Statistical Society,

authors:
V. Petsiuk
A. Das
K. Saenko

title: Rise: Randomized input sampling for explanation of black-box models

venue: arXiv preprint arXiv:1806.07421,

authors:
M.T. Ribeiro
S. Singh
C. Guestrin

title: why should i trust you?" explaining the predictions of any classifier

venue: In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining,

authors:
M. Ridaoui
M. Grabisch
C. Labreuche

title: An axiomatisation of the banzhaf value and interaction index for multichoice games

venue: In International Conference on Modeling Decisions for Artificial Intelligence,

authors:
B. Rozemberczki
R. Sarkar

title: The shapley value of classifiers in ensemble games

venue: arXiv preprint arXiv:2101.02153,

authors:
B. Scellier
Y. Bengio

title: Equilibrium propagation: Bridging the gap between energy-based models and backpropagation

venue: Frontiers in computational neuroscience,

title: A value for n-person games

venue: Contributions to the Theory of Games,

authors:
R.H.L. Sim
Y. Zhang
M.C. Chan
B.K.H. Low

title: Collaborative machine learning with incentiveaware model rewards

authors:
E. Strumbelj
I. Kononenko

title: An efficient explanation of individual classifications using game theory

venue: The Journal of Machine Learning Research,

authors:
M. Sundararajan
A. Taly
Q. Yan

title: Axiomatic attribution for deep networks

authors:
S. Tschiatschek
J. Djolonga
A. Krause

title: Learning probabilistic submodular diversity models via noise contrastive estimation

venue: In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS),

authors:
M.J. Wainwright
M.I. Jordan

title: Graphical models, exponential families, and variational inference

venue: Now Publishers Inc,

authors:
J. Wang
J. Wiens
S. Lundberg

title: Shapley flow: A graph-based approach to interpreting model predictions

venue: In International Conference on Artificial Intelligence and Statistics,

authors:
T. Wang
J. Rausch
C. Zhang
R. Jia
D. Song

title: A principled approach to data valuation for federated learning

venue: In Federated Learning,

title: Probabilistic values for games. The Shapley Value

venue: Essays in Honor of Lloyd S. Shapley,

authors:
M. Welling
Y.W. Teh

title: Bayesian learning via stochastic gradient langevin dynamics

venue: In Proceedings of the 28th international conference on machine learning

authors:
B. Williamson
J. Feng

title: Efficient nonparametric statistical inference on population feature importance using shapley values

title: Monotonic solutions of cooperative games

venue: International Journal of Game Theory,

authors:
M.D. Zeiler
R. Fergus

title: Visualizing and understanding convolutional networks

venue: In European conference on computer vision,

venue: condition; Following (Chun,

title: MORE CONFIGURATION DETAILS AND EXPERIMENTAL RESULTS G.1 SYNTHETIC EXPERIMENTS ON SUBMODULAR (FLID) GAMES Here we define a synthetic game with the value function as a FLID (Tschiatschek et al., 2016) objective F (S), which is a diversity boosting model satisfying the submodularity property

heading: 1 INTRODUCTION

text:
Valuation problems are becoming increasingly more significant in various machine learning applications, ranging from feature interpretation (Lundberg and Lee, 2017), data valuation (Ghorbani and Zou, 2019; Sim et al., 2020) and model valuation for ensembles (Rozemberczki and Sarkar, 2021). They are often formulated as an importance assignment problem in cooperative games. A cooperative game (N,F (S)) consists of a grand coalition N = {1, ..., n} of n players and a value function (a.k.a. characteristic function) F (S) : 2N → R describing the collective payoff of a coalition/cooperation S. A fundamental problem in cooperative game theory is to assign an importance vector (solution concept) φ(F ) ∈ Rn to n players. In this paper, we explore a probabilistic treatment of cooperative games (N,F (S)). Such a treatment makes it possible to conduct learning and inference in a unified manner, and will yield connections with classical valuation criteria. Concretely, we seek a probability distribution over coalitions p(S = S)1, measuring the odds that a specific coalition S happens. Generally, we consider distributions where the probability of a coalition p(S) grows monotonically with the payoff F (S).
Among all the possible probability mass functions (pmfs), how should we construct the proper p(S)? We advocate to choose the pmf with the maximum entropy H(p). This principle makes sense since maximizing the entropy minimizes the amount of prior information built into the distribution. In other words, it amounts to assume nothing about what is unknown, i.e., choosing the most “uniform” distribution. Now finding a proper p(S) becomes the following constrained optimization problem: suppose each coalition S is associated with a payoff F (S) with probability p(S). We would like to maximize the entropy H(p) = − ∑ S⊆N p(S) log p(S), subject to the constraints that
1Note that distributions over subsets of N are equivalent to distributions of |N | = n binary random variables X1, ..., Xn ∈ {0, 1}: We use Xi as the indicator function of the event i ∈ S, or Xi = [i ∈ S]. With slight abuse of notation, we use S as a random variable represented as sets and often abbreviate p(S = S) as p(S).
∑ S p(S) = 1, p(S) ≥ 0 and ∑ S p(S)F (S) = µ (i.e., the average payoff is known as µ). Solving this optimization problem (derivation in Appendix A), we reach the maximum entropy distribution:
p(S) = exp(F (S)/T )
Z , Z := ∑ S′⊆N exp(F (S′)/T ), (1)
where T > 0 is the temperature. This is an energy-based model (EBM (LeCun et al., 2006)) with −F (S) as the energy function. The above energy-based treatment admits two benefits: i) Where supervision is available, it enables learnable value functions F (S) through efficient training techniques of energy-based learning, such as noise contrastive estimation (Gutmann and Hyvärinen, 2010) and score matching (Hyvärinen, 2005). ii) Approximate inference techniques such as variational inference or sampling can be adopted to solve the valuation problem. Specifically, it enables to perform mean-field variational inference where parameters of the inferred surrogate distribution can be used as principled player valuations.
Below, we explore mean-field variational inference for the energy-based formulation. Perhaps surprisingly, by conducting only one-step fixed point iteration for maximizing the mean-field (ELBO) objective, we recover classical valuation criteria, such as the Shapley value (Shapley, 1953) and the Banzhaf value (Penrose, 1946; Banzhaf III, 1964). This observation also verifies the rationality of existing criteria, as they are all trying to decouple the correlations among players through the mean-field approach. By running the fixed point iteration for multiple steps, we achieve a trajectory of valuations, among which we define the valuation with the best conceivable decoupling error as the Variational Index. Our major contributions can be summarized as below:
i) We present a theoretically justified energy-based treatment for cooperative games. Through mean field inference, we provide a unified perspective on popular game-theoretic criteria. This provides an alternative motivation of existing criteria via a decoupling perspective, i.e., decoupling correlations among n players through the mean-field approach. ii) In pursuit of better decoupling performance, we propose to run fixed point iteration for multiple steps, which generates a trajectory of valuations. Under uniform initializations, they all satisfy a set of game-theoretic axioms, which are required for being suitable valuation criteria. We define the valuation with the best conceivable decoupling error as the Variational Index. iii) Synthetic and real-world experiments demonstrate intriguing properties of the proposed Variational Index, including lower decoupling error and better valuation performance.

heading: 2 PRELIMINARIES AND BACKGROUND

text:
Notation. We assume ei ∈ Rn being the standard ith basis vector and use boldface letters x ∈ RN and x ∈ Rn interchangebly to indicate an n-dimensional vector, where xi is the ith entry of x. By default, f(·) is used to denote a continuous function, and F (·) to represent a set function. For a differentiable function f(·), ∇f(·) denotes its gradient. x|xi←k is the operation of setting the ith element of x to k, while keeping all other elements unchanged, i.e., x|xi←k = x− xiei + kei. For two sets S and T , S + T and S − T represent set union and set difference, respectively. |S| is the cardinality of S. i is used to denote the singleton {i} with a bit abuse of notation. Existing valuation criteria. Various valuation criteria have been proposed from the area of cooperative games, amongst them the most famous ones are the Shapley value (Shapley, 1953) and the Banzhaf value, which is extended from the Banzhaf power index (Penrose, 1946; Banzhaf III, 1964). For the Shapley value, the importance assigned to player i is:
Shi = ∑
S⊆N−i [F (S + i)− F (S)] |S|!(n− |S| − 1)! n! . (2)
One can see that it gives less weight to n/2-sized coalitions. The Banzhaf value assigns the following importance to player i:
Bai = ∑
S⊆N−i [F (S + i)− F (S)] 1 2n−1 , (3)
which uses uniform weights for all the coalitions. See Greco et al. (2015) for a comparison of them.
Valuation problems in machine learning. Currently most classes of valuation problems (Lundberg and Lee, 2017; Ghorbani and Zou, 2019; Sim et al., 2020; Rozemberczki and Sarkar, 2021) use
Shapley value as the valuation criterion. Along with the rapid progress of model interpretation in the past decades (Zeiler and Fergus, 2014; Ribeiro et al., 2016; Lundberg and Lee, 2017; Sundararajan et al., 2017; Petsiuk et al., 2018; Wang et al., 2021a), attribution-based interpretation aims to assign importance to the features for a specific data instance (x ∈ RN , y) given a black-box modelM. Here each feature maps to a player in the game (N,F (S)), and the value function F (S) is usually the model response, such as the predicted probability for classification problems, when feeding a subset S of features toM. The data valuation problem (Ghorbani and Zou, 2019) tries to assign values to the samples in the training dataset N = {(xi, yi)}n1 for general supervised machine learning: one training sample corresponds to one player, and the value function F (S) indicates the predictor performance on some test dataset given access to only a subset of the training samples in S. Model valuation in ensembles (Rozemberczki and Sarkar, 2021) measures importance of individual models in an ensemble in order to correctly label data points from a dataset, where each pre-trained model maps to a player and the value function measures the predictive performance of subsets of models.

heading: 3 RELATED WORK

text:
Energy-based modeling. Energy based learning (LeCun et al., 2006) is a classical learning framework that uses an energy functionE(x) to measure the quality of a data point x. Energy based models have been applied to different domains, such as data generation (Deng et al., 2020), out-of-distribution detection (Liu et al., 2020), reinforcement learning (Haarnoja et al., 2017), memory modeling (Bartunov et al., 2019), discriminative learning (Grathwohl et al., 2019; Gustafsson et al., 2020) and biologically-plausible training (Scellier and Bengio, 2017). Energy based learning admits principled training methods, such as contrastive divergence (Hinton, 2002), noise contrastive estimation (Gutmann and Hyvärinen, 2010) and score matching (Hyvärinen, 2005). For approximate inference, sampling based approaches are mainly MCMC-style algorithms, such as stochastic gradient Langevin dynamics (Welling and Teh, 2011). For a wide class of EBMs with submodular or supermodular energies (Djolonga and Krause, 2014), there exist provable mean field inference algorithms with constant factor approximation guarantees (Bian et al., 2019).
Shapley values in machine learning. Shapley values have been extensively used for valuation problems in machine learning, including attribution-based interpretation (Lipovetsky and Conklin, 2001; Cohen et al., 2007; Strumbelj and Kononenko, 2010; Owen, 2014; Datta et al., 2016; Lundberg and Lee, 2017; Chen et al., 2018; Lundberg et al., 2018; Kumar et al., 2020; Williamson and Feng, 2020; Covert et al., 2020b; Wang et al., 2021b), data valuation (Ghorbani and Zou, 2019; Jia et al., 2019b;a; Wang et al., 2020; Fan et al., 2021), collaborative machine learning (Sim et al., 2020) and recently, model valuation in ensembles (Rozemberczki and Sarkar, 2021). For a detailed overview of papers using Shapley values for feature interpretation, please see Covert et al. (2020a) and the references therein. To alleviate the exponential computational cost of exact evaluation, various methods have been proposed to approximate Shapley values in polynomial time (Ancona et al., 2017; 2019). Owen (1972) proposes the multilinear extension purely as a representation of cooperative games and Okhrati and Lipani (2021) use it to develop sampling algorithms for Shapley values.

heading: 4 VALUATION FOR COOPERATIVE GAMES: A DECOUPLING PERSPECTIVE

text:
In the introduction we have verified that under the setting of cooperative games, the Boltzmann distribution (see Eq. (1)) achieves the maximum entropy among all of the pmf functionals. One can naturally view the importance assignment problem of cooperative games as a decoupling problem: The n players in a game (N,F (S)) might be arbitrarily correlated in a very complicated manner. However, in order to assign each of them an individual importance value, we have to decouple their interactions, which can be viewed as a way to simplify their correlations.
We therefore consider a surrogate distribution q(S;x) governed by parameters in x. q has to be simple, given our intention to decouple the correlations among the n players. A natural choice is to restrain q(S;x) to be fully factorizable, which leads to a mean-field approximation of p(S). The simplest form of q(S;x) would be a n independent Bernoulli distribution, i.e., q(S;x) := ∏ i∈S xi ∏ j /∈S(1− xj),x ∈ [0, 1]n. Given a divergence measure D(·‖·) for probability distributions, we can define the best conceivable decoupling error to be the divergence between p and the best possible q.
Definition 1 (Best Conceivable Decoupling Error). Considering a cooperative game (N,F (S)), and given a divergence measure D(·‖·) for probability distributions, the decoupling error is defined as the divergence between q and p: D(q‖p), and the best conceivable decoupling error is defined as the divergence between the best possible q and p:
D∗ := min q D(q‖p). (4)
Note that the best conceivable decoupling error D∗ is closely related to the intrinsic coupling amongst n players: if all the players are already independent with each other, then D∗ could be zero.

heading: 4.1 MEAN FIELD OBJECTIVE FOR EBMS

text:
If we consider the decoupling error D(q‖p) to be the Kullback-Leibler divergence between q and p, then we recover the mean field approach2. Given the EBM formulation in Eq. (1), the classical mean-field inference approach aims to approximate p(S) by a fully factorized product distribution q(S;x) := ∏ i∈S xi ∏ j /∈S(1 − xj),x ∈ [0, 1]n, by minimizing the distance measured w.r.t. the Kullback-Leibler divergence between q and p. Since KL(q‖p) is non-negative, we have:
0 ≤ KL(q‖p) = ∑
S⊆N q(S;x) log
q(S;x)
p(S)
= −Eq(S;x)[log p(S)]−H(q(S;x)) (5)
= −Eq(S;x)[ F (S)
T − log Z]−H(q(S;x)) (6)
= − ∑ S⊆N F (S) T ∏ i∈S xi ∏ j /∈S (1− xj) + ∑n i=1 [xi log xi + (1− xi) log(1− xi)] + log Z. (7)
In Eq. (6) we plug in the EBM formulation that log p(S) = F (S)T − log Z. Then one can get
log Z ≥ ∑ S⊆N F (S) T ∏ i∈S xi ∏ j /∈S (1− xj)− ∑n i=1 [xi log xi + (1− xi) log(1− xi)]
= fFmt(x)
T + H(q(S;x)) := (ELBO) (8)
where H(·) is the entropy, ELBO stands for the evidence lower bound, and fFmt(x) := ∑
S⊆N F (S) ∏ i∈S xi ∏ j /∈S (1− xj),x ∈ [0, 1]n, (9)
is the multilinear extension of F (S) (Owen, 1972; Calinescu et al., 2007). Note that the multilinear extension plays a central role in modern combinatorial optimizaiton techniques (Feige et al., 2011), especially for guaranteed submodular maximization problems (Krause and Golovin, 2014).
Maximizing (ELBO) in Eq. (8) amounts to minimizing the Kullback-Leibler divergence between q and p. If one solves this optimization problem to optimality, one can obtain the q(S;x∗) with the best conceivable decoupling error. Here x∗i describes the odds that player i shall participate in the game, so it can be naturally used to define the importance score of each player.
Definition 2 (Variational Index of Cooperative Games). Consider a cooperative game (N,F (S)) and its mean field approximation. Let x∗ be the variational marginals with the best conceivable decoupling error, we define s∗ := Tσ−1(x∗) to be the variational index of the game. Formally,
x∗ = arg minxKL(q(S;x)‖p(S)), (10)
where x∗ can be obtained by maximizing the ELBO objective in Eq. (8), and σ−1(·) is the inverse of the sigmoid function, i.e. σ−1(x) = log x1−x . For a vector it is applied element-wise.
2Notably, one could also apply the reverse KL divergence KL(p‖q), which would lead to an expectation propagation (Minka, 2001) treatment of cooperative games.

heading: 4.2 ALGORITHMS FOR CALCULATING THE VARIATIONAL INDEX

text:
Equilibrium condition. For coordinate i, the partial derivative of the multilinear extension is ∇ifFmt(x), and for the entropy term, it is ∇iH(q(S;x)) = log 1−xixi . By setting the partial derivative of ELBO in Eq. (8) to be 0, we have the equilibrium condition:
x∗i = σ(∇ifFmt(x∗)/T ) = ( 1 + exp(−∇ifFmt(x∗)/T )−1 , ∀i ∈ N, (11)
where σ is the sigmoid function. This equilibrium condition implies that one cannot change the value assigned to any player in order to further improve the overall decoupling performance. It also implies the fixed point iteration xi ← σ(∇ifFmt(x)/T ). When updating each coordinate sequentially, we recover the classic naive mean field algorithm as shown in Appendix C.
Instead, here we suggest to use the full-gradient method shown in Alg. 1 for maximizing the ELBO objective. As we will see later, the resultant valuations satisfy certain game-theoretic axioms. It needs an initial marginal vector x0 ∈ [0, 1]n and the number of epochs K. After K steps of fixed point iteration, it returns the estimated marginal xK .
Algorithm 1: Mean Field Inference with Full Gradient: MFI(x;K) Input: A cooperative game (N,F (S)) with n players. Initial marginals x0 ← x ∈ [0, 1]n. #epochs K. Output: Marginals after K steps of iteration: xK
1 for k = 1→ K do 2 xk ← σ(∇fFmt(xk−1)/T ) = ( 1 + exp(−∇fFmt(xk−1)/T )−1 ;
In case Alg. 1 solves the optimization problem to optimality, we obtain the Variational Index. However, maximizing ELBO is in general a non-convex/non-concave problem, and hence one can only ensure reaching a stationary solution. Below, when we say Variational Index, we therefore refer to its approximation obtained via Alg. 1 by default. Meanwhile, the MFI(x;K) subroutine also defines a series of marginals, which enjoy interesting properties as we show in the next part. So we define variational valuations through intermediate solutions of MFI(x;K).
Definition 3 (K-Step Variational Values). Considering a cooperative game (N,F (S)) and its mean field approximation by Alg. 1, we define the K-Step Variational Values initialized at x as:
Tσ−1(MFI(x;K)), (12)
where σ−1() is the inverse of the sigmoid function (σ−1(x) = log x1−x ).
Notice when running more steps, the K-Step variational value will be more close to the Variational Index. The gradient∇fFmt(x) itself is defined with respect to an exponential sum via the multilinear extension. Next we show how it can be approximated via principled sampling methods.
Sampling methods for estimating the partial derivative. The partial derivative follows,
∇ifFmt(x) = Eq(S;(x|xi←1))[F (S)]− Eq(S;(x|xi←0))[F (S)] (13) = fFmt(x|xi←1)− fFmt(x|xi←0)
= ∑
S⊆N,S3i
F (S) ∏ j∈S−i xj ∏ j′ /∈S (1− xj′) − ∑ S⊆N−i F (S) ∏ j∈S xj ∏ j′ /∈S,j′ 6=i (1− xj′)
= ∑
S⊆N−i [F (S + i)− F (S)] ∏ j∈S xj ∏ j′∈N−S−i (1− xj′)
= ∑
S⊆N−i
[F (S + i)− F (S)]q(S; (x|xi←0)) = ES∼q(S;(x|xi←0)) [F (S + i)− F (S)].
All of the variational criteria are based on the calculation of the partial derivative∇ifFmt(x), which can be approximated by Monte Carlo sampling since ∇ifFmt(x) = ES∼q(S;(x|xi←0)) [F (S + i)− F (S)]: we first sample m coalitions Sk, k = 1, ...,m from the surrogate distribution q(S; (x|xi ← 0)), then approximate the expectation by the average 1m ∑m k=1 [F (Sk + i)− F (Sk)]. According to the
Chernoff-Hoeffding bound (Hoeffding, 1963), the approximation will be arbitrarily close to the true value with increasingly more samples: With probability at least 1 − exp(−m 2/2), it holds that | 1m ∑m k=1[F (Sk + i)− F (Sk)]−∇ifFmt(x)| ≤ maxS |F (S + i)− F (S)|, for all > 0.
Roles of the initializer x0 and the temperature T . This can be understood in the following respects: 1) The initializer x0 represents the initial credit assignments to the n players, so it denotes the prior knowledge/initial belief of the contributions of the players; 2) If one just runs Alg. 1 for one step, x0 matters a lot to the output. However, if one runs Alg. 1 for many steps, xk will converge to the stationary points of the ELBO objective. Empirically, it will take around 5∼10 steps to converge. The temperature T controls the “spreading” of credits/importance assigned to the players: A higher T leads to more flat assignments, and a lower T leads to more concentrated assignments.
Computational efficiency of calculating Variational Index and variational values. Alg. 1 calculates the K-step variational values, 1-step variational value has the same computational cost as that of Banzhaf value and of the integrand of the line integration of Shapley value in Eq. (15) below, since they all need to evaluate∇fFmt(x). Sampling methods could help with approximating all of the three criteria when there are a large number of players. Variational Index can be approximated by K-step variational value, the number K depends on when Alg. 1 will converge. One can easily show that, under the setting of maximizing ELBO, xk will converge to some stationary point x∗, based on the analysis of mean field approximation in Wainwright and Jordan (2008). We have also empirically verified the convergence rate of Alg. 1 in Sec. 5.3, and find that it converges within 5 to 10 steps. So the computational cost is roughly similar as that of Shapley value and Banzhaf value.

heading: 4.3 RECOVERING CLASSICAL CRITERIA

text:
Perhaps surprisingly, it is possible to recover classical valuation criteria via the K-step variational values as in Def. 3. Firstly, for Banzhaf value, by comparing with Eq. (13) it reads,
Bai = ∑
S⊆N−i [F (S + i)− F (S)] 1 2n−1 = ∇ifFmt(0.5 ∗ 1) = Tσ−1(MFI(0.5 ∗ 1; 1)), (14)
which is the 1-step variational value initialied at 0.5 ∗ 1. We can also recover the Shapley value through its connection to the multilinear extension (Owen, 1972; Grabisch et al., 2000):
Shi = ∫ 1 0 ∇ifFmt(x1)dx = ∫ 1 0 Tσ−1(MFI(x1; 1))dx, (15)
where the integration denotes integrating the partial-derivative of the multilinear extension along the main diagonal of the unit hypercube. A self-contained proof is given in Appendix D.
These insights offer a novel, unified interpretation of the two classical valuation indices: both the Shapley value and Banzhaf value can be viewed as approximating the variational index by running one step of fixed point iteration for the decoupling (ELBO) objective. Specifically, for the Banzhaf value, it initializes x at 0.5 ∗ 1, and runs one step of fixed point iteration. For the Shapley value, it also performs a one-step fixed point approximation. However, instead of starting at a single initial point, it averages over all possible initializations through the line integration in Eq. (15).
Relation to probabilistic values. Probabilistic values for games (Weber, 1988; Monderer and Samet, 2002) capture a class of solution concepts, where the value of each player is given by some averaging of the player’s marginal contributions to coalitions, and the weights depend on the coalitions only. According to (Monderer and Samet, 2002, Equation (3.1)), a solution φ is called a probabilistic value, if for each player i, there exists a probability pi ∈ ∆(Ci), such that φi is the expected marginal contribution of i w.r.t. pi. Namely, φi = ∑ S∈Ci p
i(S)[F (S + i)− F (S)], where Ci is the set of all subsets of N − i, and ∆(Ci) is the set of all probability measures on Ci. One can easily see that, for any fixed x, 1-step variational value in Def. 3 is a probabilistic value with pi(S) = q(S; (x|xi ← 0)), where q(S;x) is the surrogate distribution in our EBM framework.
4.4 AXIOMATISATION OF K-STEP VARIATIONAL VALUES
Our EBM framework introduces a series of variational values controlled by T and the running step number K. We now establish that the variational values Tσ−1(MFI(x;K)) in Def. 3 satisfy certain game-theoretic axioms (see Appendix B for definitions of five common axioms: Null player,
Symmetry, Marginalism, Additivity and Efficiency). We prove that all the variational values in the trajectory satisfy three fundamental axioms: null player, marginalism and symmetry. Detailed proof is deferred to Appendix E. Note that it might be very difficult or even impossible to find equivalent axiomatisations of the series of variational values, which will be left for future work. Meanwhile, our methods incur a decoupling and fairness tradeoff by tuning the hyperparameters K and T .
Theorem 1 (Axiomatisation of K-Step Variational Values of Def. 3). If initialized uniformly, i.e., x0 = x1, x ∈ [0, 1], all the variational values in the trajectory Tσ−1(MFI(x; k)), k = 1, 2, 3... satisfy the null player, marginalism and symmetry axioms.
According to Theorem 1, our proposed K-step variational values satisfy the minimal set of axioms in order to being an appropriate valuation criterion. Note that specific realizations of the K-step variational values could also satisfy more axioms, for example, the 1-step variational value initialied at 0.5 ∗ 1 also satisfies the additivity axiom. Furthermore, we have the following observations: Satisfying more axioms is not essential for valuation problems. Notably, in cooperative game theory, one line of work is to seek for solution concepts that would satisfy more axioms. However, for valuation problems in machine learning, this is arguably not essential. For example, similar as what Ridaoui et al. (2018) argues, efficiency does not make sense for certain games. We give a simple illustration in Appendix F, which further shows that whether more axioms shall be considered really depends on the specific scenario being modeled, which will be left for important future work.

heading: 5 EMPIRICAL STUDIES

text:
Throughout the experiments, we are trying to understand the following: 1) Would the proposed Variational Index have lower decoupling error compared to others? 2) Could the proposed Variational Index gain benefits compared to the classical valuation criteria for valuation problems?
Since we are mainly comparing the quality of different criteria, it is necessary to rule out the influence of approximation errors when estimating their values. So we focus on small-sized problems where one can compute the exact values of these criteria in a reasonable time. Usually this requires the number of players to be no more than 25. Meanwhile, we have also conducted experiments with a larger number of players in Appendix G.5, in order to show the efficiency of sampling methods. We choose T empirically from the values of 0.1, 0.2, 0.5, 1.0. We choose K such that Alg. 1 would converge. Usually, it takes around 5 to 10 steps to converge. We give all players a fair start, so x0 was intialized to be 0.5× 1. Code will be released soon. We first conduct synthetic experiments on submodular games (details defered to Appendix G.1), in order to verify the quality of solutions in terms of the true marginals p(i ∈ S). One can conclude
logistic regression
xgboost
MLP
𝑇 = 0.8 Data id: 24038 GT label: True
𝑇 = 0.5 Data id: 16139 GT label: True
𝑇 = 0.1 Data id: 7977 GT label: True
Variational BanzhafShapley
Figure 2: First column: Change of predicted probabilities when removing features. The decoupling error is included in the legend. Last three columns: waterfall plots of feature importance.
that Variational Index obtains better performance in terms of MSE and Spearman’s rank correlation compared to the one-point solutions (Shapley value and Banzhaf value) in all experiments. More experimental results on data point and feature valuations are deferred to Appendix G.

heading: 5.1 EXPERIMENTS ON DATA VALUATIONS

text: We follow the setting of Ghorbani and Zou (2019) and reuse the code of https://github.com/ amiratag/DataShapley. We conduct data removal: training samples are sorted according to the valuations returned by different criteria, and then samples are removed in that order to check how much the test accuracy drops. Intuitively, the best criteria would induce the fastest drop of performance. We experiment with the following datasets: a) Synthetic datasets similar as that of Ghorbani and Zou (2019); b) The breast cancer dataset, which is a binary classification dataset with 569 samples; c) The digits dataset, that is a 10-class classification dataset with 1797 samples. The above two datasets are both from UCI Machine Learning repository (https://archive. ics.uci.edu/ml/index.php). Specifically, we cluster data points into groups and studied two settings: 1) Grouping the samples randomly; 2) Clustering the samples with the k-means algorithm. For simplicity, we always use equal group sizes. The data point removal corresponds to singleton groups. Fig. 1 shows the results. One can observe that in certain situations the Variational Index achieves the fastest drop rate. It always achieves the lowest decoupling error (as shown in the legends in each of the figures). Sometimes Variational Index and Banzhaf show similar performance. We expect that this is because the Banzhaf value is a one-step approximation of Variational Index, and for the specific problem considered, the ranking of the solutions does not change after one-step of fixed point iteration. There are also situations that the rankings of the three criteria are not very distinguishable, however, the specific values are also very different since the decoupling error differs.

heading: 5.2 EXPERIMENTS ON FEATURE VALUATIONS/ATTRIBUTIONS

text:
We follow the setting of Lundberg and Lee (2017) and reuse the code of https://github.com/ slundberg/shap with an MIT License. We train classifiers on the Adult dataset3, which predicts whether an adult’s income exceeds 50k dollar per year based on census data. It has 48,842 instances and 14 features such as age, workclass, occupation, sex and capital gain (12 of them used).
Feature removal results. This experiment follows a similar fashion as the data removal experiment: we remove the features one by one according to the order defined by the returned criterion, then observe the change of predicted probabilities. Fig. 2 reports the behavior of the three criteria. The first row shows the results from an xgboost classifier (accuracy: 0.893), second row a logistic regression
3https://archive.ics.uci.edu/ml/datasets/adult
classifier (accuracy: 0.842), third row a multi-layer perceptron (accuracy: 0.861). For the probability dropping results, Variational Index usually induces the fastest drop, and it always enjoys the smallest decoupling error, as expected from its mean-field nature. From the waterfall plots, one can see that the three criteria indeed produce different rankings of the features. Take the first row for example. All criteria put “Capital Loss” and “Relationship” as the first two features. However, the remaining features have different ranking: Variational Index and Banzhaf indicate that “Marital Status” should be ranked third, while Shapley ranks it in the fourth position. It is hard to tell which ranking is the best because: 1) There is no golden standard to determine the true ranking of features; 2) Even if there exists a ground truth ranking of some “perfect model”, the trained xgboost model here might not be able to reproduce it, since it might not be aligned with the “perfect model”. The feature removal experiments nevertheless demonstrate the intriguing behavior of Variational Index.
Average results. We further provide the bar plots and averaged ranking across the adult datasets in Fig. 3. From the bar plots one can see that different criterion has slightly different values for each feature on average. Average rankings in the table demonstrate the difference: The three methods do not agree on the colored features, for example, “Age”, “Education-Num” and “Captical Loss”.

heading: 5.3 EMPIRICAL CONVERGENCE RESULTS OF ALG. 1

text:
Table 1 shows convergence results of Alg. 1 on feature and data valuation experiments. The value in the cells are the stepwise difference of xk , ‖x
k−xk−1‖2 n , which is a classical criterion to measure the
convergence of iterative algorithms. One can clearly see that Alg. 1 converges in 5 to 10 iterations.
DISCUSSIONS AND FUTURE WORK. We have presented an energy-based treatment of cooperative games, in order to improve the valuation problem. It is very worthwhile to explore more in the following directions: 1) Choosing the temperature T . The temperature controls the level of fairness since when T →∞, all players have equal importance, when T → 0, a player has either 0 or 1 importance. Perhaps one can use an annealing-style algorithm in order to control the fairness level: starting with a high temperature and gradually decreasing it, one can obtain a series of importance values under different fairness levels. 2) Given the probabilistic treatment of cooperative games, one can naturally add priors over the players, in order to encode more domain knowledge. It may also make sense to consider conditioning and marginalization in light of practical applications. 3) It’s very interesting to explore the interaction of a group of players in the energy-based framework, which would result in an “interactive” index among size-k coalitions.
ETHICS STATEMENT AND BROADER IMPACT
Besides the valuation problems explored in this work, cooperative game theory has already been applied to a wide range of disciplines, to name a few, economics, political science, sociology, biology, so this work could potentially contribute to broader domains as well.
Meanwhile, we have to be aware of possible negative societal impacts, including: 1) negative side effects of the technology itself, for example, possible unemployment issue due to the reduced amount of the need of valuations by human beings; 2) applications in negative downstream tasks, for instance, the data point valuation technique could make it easier to conduct underground transactions of private data.
REPRODUCIBILITY STATEMENT
All the datasets are publicly available as described in the main text. In order to ensure reproducibility, we have made the efforts in the following respects: 1) Provide a sampled code as the supplementary material. 2) Provide self-contained proofs of the main claims in Appendices D and E; 3) Provide more details on experimental configurations and experimental results in Appendix G.

heading: A Derivations of the Maximum Entropy Distribution 14

heading: B Common Axioms of Valuation Criteria 15

heading: C The Naive Mean Field Algorithm 16

heading: D Proof of Recovering Classical Criteria 16

heading: E Proof of Theorem 1 17

heading: F Miscellaneous Results in Sec. 4 17

heading: G More Configuration Details and Experimental Results 18

text:
G.1 Synthetic Experiments on Submodular (FLID) Games . . . . . . . . . . . . . . . . 18
G.2 Details of the Models for Feature Valuations . . . . . . . . . . . . . . . . . . . . . 20
G.3 More Results on Feature Valuations . . . . . . . . . . . . . . . . . . . . . . . . . 20
G.4 More Average Results on Feature Valuations . . . . . . . . . . . . . . . . . . . . . 20
G.5 Experiments with More Players . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
G.6 Effect of Number of Samples in MCMC Sampling . . . . . . . . . . . . . . . . . 21

heading: A DERIVATIONS OF THE MAXIMUM ENTROPY DISTRIBUTION

text:
One may wonder why do we need energy-based treatment of valuation problems in machine learning? Specifically, under the setting of cooperative games (N,F (S)), why we have to take the exponential form of EBM p(S) ∝ exp(F (S)/T )? Because one may also formulate it as something else, say, p(S) ∝ (1 + |F (S)|)? In one word, because EBM is the maximum entropy distribution. Being a maximum entropy distribution means minimizing the amount of prior information built into the distribution. Another lens to understand it is that: Since the distribution with the maximum entropy is the one that makes the fewest assumptions about the true distribution of data, the principle of maximum entropy can be seen as an application of Occam’s razor. Meanwhile, many physical systems tend to move towards maximal entropy configurations over time (Jaynes, 1957a;b).
In the following we will give a derivation to show that p(S) ∝ exp(F (S)/T ) is indeed the maximum entropy distribution for a cooperative game. The derivation bellow is closely following Jaynes (1957a;b) for statistical mechanics. Suppose each coalition S is associated with a payoff F (S) with probability p(S). We would like to maximize the entropy H(p) = − ∑ S⊆N p(S) log p(S), subject
to the constraints that ∑ S p(S) = 1, p(S) ≥ 0 and ∑
S p(S)F (S) = µ (i.e., the average payoff is known as µ).
Writing down the Lagrangian
L(p, λ0, λ1) := − ∑ S⊆N p(S) log p(S) + λ0( ∑ S⊆N p(S)− 1) + λ1(µ− ∑ S⊆N p(S)F (S))  (16)
Setting ∂L(p, λ0, λ1)
∂p(S) = − [log p(S) + 1 + λ0 − λ1F (S)] (17)
= 0 (18) we get:
p(S) = exp[−(λ0 + 1− λ1F (S))] (19)
λ0 + 1 = log ∑ S⊆N exp(λ1F (S)) =: log Z (20)
is the log-partition function. So,
p(S) = exp[λ1F (S))]
Z (21)
Note that the maximum value of the entropy is Hmax = − ∑ S⊆N p(S) log p(S) (22)
= λ0 + 1− λ1 ∑ S⊆N p(S)F (S) (23)
= λ0 + 1− λ1µ (24)
So one can get,
λ1 = − ∂Hmax ∂µ =: 1 T (25)
which defines the inverse temperature.
So we reach the exponential form of p(S) as:
p(S) = exp[F (S)/T )]∑ S⊆N exp[F (S)/T ] . (26)

heading: B COMMON AXIOMS OF VALUATION CRITERIA

text:
Following the definitions in Covert et al. (2020a), the five common axioms are listed as bellow. φi(F ) denotes the value assigned to player i in the game (N,F (S)). Note that the notions might be slightly different in classical literature of game theory.
Null player: For a player i in the cooperative game (N,F (S)), if F (S + i) = F (S) holds for all S ⊆ N − i, then its value should be φi(F ) = 0. Symmetry: For any two players i, j in the cooperative game (N,F (S)), if F (S + i) = F (S + j) holds for all S ⊆ N − i− j, then it holds that φi(F ) = φj(F ). Marginalism: For two games (N,F (S)) and (N,G(S)) where all players have identical marginal contributions, the players obtain equal valuations: F (S + i)− F (S) = G(S + i)−G(S) holds for all (i, S), then it holds that φi(F ) = φi(G).
Additivity: For two games (N,F (S)) and (N,G(S)), if they are combined, the total contribution of a player is equal to the sum of its individual contributions on each game: φi(F+G) = φi(F )+φi(G).
Efficiency: The values add up to the difference in value between the grand coalition and the empty coalition: ∑ i∈N φi(F ) = F (N)− F (∅). Remark 1 (The notion of “marginalism”). Specifically, the marginalism axiom was first mentioned by (Young, 1985, Equation 7 on page 70), where it was called the “independence” condition; Following (Chun, 1989, page 121), it was formally called the “marginality”. This axiom requires a player’s payoffs to depend only on his own marginal contributions – whenever they remain unchanged, his payoffs should be unaffected.
Algorithm 2: NAIVE MEAN FIELD FOR CALCULATING THE VARIATIONAL INDEX Input: A cooperative game (N,F (S)) with n players. Initial marginal x0 ∈ [0, 1]n; #epochs K. Output: The Variational Index s∗ = σ−1(x∗)
1 x← x0; 2 for epoch from 1 to K do 3 for i = 1→ n do 4 let vi be the player being operated; 5 xvi ← σ(∇vifFmt(x)/T ) = ( 1 + exp(−∇vifFmt(x)/T )−1 ;
6 x∗ ← x;

heading: C THE NAIVE MEAN FIELD ALGORITHM

text: The naive mean field algorithm is one of the most classical algorithm for mean field inference. It is summarized in Alg. 2.

heading: D PROOF OF RECOVERING CLASSICAL CRITERIA

text:
For Banzhaf value, by comparing its definition in Eq. (2) with Eq. (13) it reads, Bai = ∑
S⊆N−i [F (S + i)− F (S)] 1 2n−1 = ∇ifFmt(0.5 ∗ 1) = Tσ−1(MFI(0.5 ∗ 1; 1)), (27)
which is the 1-step variational value initialied at 0.5 ∗ 1. For Shapley value, according to Grabisch et al. (2000), here we prove a stronger conclusion regarding the generalization of Shapley value: Shapley interaction index, which is defined for any coalition S:
ShS = ∑
T⊆N−S
(n− |T | − |S|)!|T |! (n− |S|+ 1)! ∑ L⊆S (−1)|S|−|L|F (L+ T ). (28)
Given Hammer and Rudeanu (2012), we have a second form of the multilinear extension as: fFmt(x) = ∑ S⊆N a(S) ∏ i∈S xi,x ∈ [0, 1]n, (29)
where a(S) := ∑
T⊆S(−1)|S|−|T |F (T ) is the Mobius transform of F (S).
Then, one can show the S-derivative of fFmt(x) is (suppose S = {i1, ..., i|S|}),
∆Sf F mt(x) :=
∂|S|fFmt(x) ∂xi1 , ..., ∂xi|S| = ∑ T⊇S a(T ) ∏ i∈T−S xi. (30)
So,
∆Sf F mt(x1) = ∑ T⊇S a(T )x|T |−|S|. (31)
Then it holds, ∫ 1 0 ∆Sf F mt(x1)dx = ∫ 1 0 ∑ T⊇S a(T )x|T |−|S|dx (32)
= ∑ T⊇S a(T ) ∫ 1 0 x|T |−|S|dx (33)
= ∑ T⊇S a(T )(|T | − |S|+ 1)−1 (34)
According to Grabisch (1997), we have ShS = ∑
T⊇S a(T )(|T | − |S| + 1)−1, then we reach the conclusion:
ShS = ∫ 1 0 ∆Sf F mt(x1)dx. (35)
When |S| = 1, we recover the conclusion for Shapley value.

heading: E PROOF OF THEOREM 1

text:
Theorem 1 (Axiomatisation of K-Step Variational Values of Def. 3). If initialized uniformly, i.e., x0 = x1, x ∈ [0, 1], all the variational values in the trajectory Tσ−1(MFI(x; k)), k = 1, 2, 3... satisfy the null player, marginalism and symmetry axioms.
Proof of Theorem 1. In step k, we know that the value to player i is:
Tσ−1(MFI(x; k))i = ∑
S⊆N−i [F (S + i)− F (S)] ∏ j∈S xj ∏ j′∈N−S−i (1− xj′) (36)
For the null player property, since F (S + i) = F (S) always holds, it is easy to see that Tσ−1(MFI(x; k))i = 0 holds for all i ∈ N . Now we will show that the symmetry property holds. The value to player i′ is:
Tσ−1(MFI(x; k))i′ = ∑
S′⊆N−i′ [F (S′ + i′)− F (S′)] ∏ j∈S′ xj ∏ j′∈N−S′−i (1− xj′) (37)
Now let us compare different terms in the summands of Eq. (36) and Eq. (37). We try to match the summands one by one. There are two situations:
Situation I: For any S ⊆ N − i− i′, we choose S′ = S. In this case we have F (S + i)− F (S) = F (S′ + i′)− F (S′). For the products of x we have:∏
j∈S xj ∏ j′∈N−S−i (1− xj′)− ∏ j∈S′ xj ∏
j′∈N−S′−i (1− xj′) = (38)∏ j∈S xj ∏ j′∈N−S−i−i′ (1− xj′)[(1− xi′)− (1− xi)] (39)
We know that xi′ = xi holds from step 0, by simple induction, we know that xi′ = xi holds for step k as well. So in this situation, the summands equal to each other.
Situation II: For any S = A+ i′, we choose S′ = A+ i, where A ⊆ N − i− i′. In this case, it still holds that F (S + i)− F (S) = F (S′ + i′)− F (S′). For the products of x we have:∏
j∈S xj ∏ j′∈N−S−i (1− xj′)− ∏ j∈S′ xj ∏
j′∈N−S′−i′ (1− xj′) = (40)∏ j∈A xj ∏ j′∈N−A−i−i′ (1− xj′)[xi′ − xi]. (41)
Again, by the simple induction, we know that xi′ = xi holds for step k.
The above two situations finishes the proof of symmetry.
For the marginalisim axiom, one can see that the update step for the two games are identical, and it is easy to deduce that they produce exactly the same trajectories, given that they have the same initializations.
F MISCELLANEOUS RESULTS IN SEC. 4
Gradient of entropy in Sec. 4.2 Note that q is a fully factorized product distribution q(S;x) :=∏ i∈S xi ∏ j /∈S(1−xj),x ∈ [0, 1]n, so its entropy H(q(S;x)) can be written as the sum of entropy of n independent Bernoulli distributions. And the entropy of one Bernoulli distribution with parameter xi is
−xi log xi − (1− xi) log(1− xi)
So we have,
∇iH(q(S;x)) = ∇i n∑
i=1
[−xi log xi − (1− xi) log(1− xi)] (42)
= ∇i[−xi log xi − (1− xi) log(1− xi)] (43) = log 1− xi xi (44)
Satisfying more axioms is not essential for valuation problems. Notably, in cooperative game theory, one line of work is to seek for solution concepts that would satisfy more axioms. However, for valuation problems in machine learning, this is arguably not essential. For example, similar as what Ridaoui et al. (2018) argues, efficiency does not make sense for certain games.
For a simple illustration, let us consider a voting game from a classification model with 3 binary features x ∈ {0, 1}3 with weights w = [2, 1, 1]>: f(x) := 1{w>x≥3}. Now we are trying to find the valuation of each feature in N = {x1, x2, x3}. Naturally, the value function in the corresponding voting game shall be F (S) = f(xS) where xS means setting the coordinates of x inside S to be 1 while leaving others to be 0. In this game let us count how many times each feature could flip the classification result: for feature x1, there are three situations: F ({1, 2})− F ({2}), F ({1, 3})− F ({3}) and F ({1, 2, 3})− F ({2, 3}); for feature x2, there are one situation: F ({1, 2})− F ({1}); for feature x3, there are one situation: F ({1, 3}) − F ({1}). Then the voting power (or valuation) of each feature shall follows a 3 : 1 : 1 ratio. By simple calculations, one can see that the Banzhaf values of the three features are 34 , 1 4 , 1 4 , which is consistent with the ratio of the expected voting power. However, the Shapley values of them are 46 , 1 6 , 1 6 , which is not consistent due to satisfying the efficiency axiom.
By the above example we are trying to explain that for valuation problems, satisfying more axioms is not necessary, sometimes even does not make sense. Whether more axioms shall be considered and which sets of them shall be added really depend on the specific scenario, which will be left for important future work.

heading: G MORE CONFIGURATION DETAILS AND EXPERIMENTAL RESULTS

text:
G.1 SYNTHETIC EXPERIMENTS ON SUBMODULAR (FLID) GAMES
Here we define a synthetic game with the value function as a FLID (Tschiatschek et al., 2016) objective F (S), which is a diversity boosting model satisfying the submodularity property. We know that its multilinear extension admits polynomial time algorithms (Bian et al., 2019). Let W ∈ R|N |×D+ be the weights, each row corresponds to the latent representation of an item, with D as the dimensionality. Then
F (S) := ∑
i∈S ui + ∑D d=1 (max i∈S Wi,d − ∑ i∈S Wi,d) = ∑ i∈S u′i + ∑D d=1 max i∈S Wi,d, (45)
which models both coverage and diversity, and u′i = ui− ∑D
d=1Wi,d. In order to test the performance of the proposed variational objectives, we consider small synthetic games with 6, 8 and 10 players such that the ground truth marginals can be computed exhaustively. We would like to compare with the true marginals p(i ∈ S) since they represent the probability that player i participates in all coalitions, which is hard to compute in general. The distance to the true marginals is also a natural measure of the decoupling error as defined in Def. 1. We apply a sigmoid function to Shapley value and Banzhaf value in order to translate them to probabilities. We calculate the mean squared error
(MSE) and Spearman’s rank correlation (ρ) to the ground truth marginals p(i ∈ S) and report them in the figure legend. Fig. 4 collects the figures, one can see that the Variational Index clearly obtains better performance in terms of MSE and Spearman’s rank correlation compared to the one-point solutions (Shapley value and Banzhaf value) in all experiments.
G.2 DETAILS OF THE MODELS FOR FEATURE VALUATIONS
For xgboost, the train accuracy is 0.8934307914376094, the specific configuration with the xgboost package is:
X G B C l a s s i f i e r ( b a s e _ s c o r e = 0 . 5 , b o o s t e r = ’ g b t r e e ’ , c o l s a m p l e _ b y l e v e l =1 , co l samp le_bynode =1 , c o l s a m p l e _ b y t r e e =1 , gamma=0 , gpu_ id = −1 , i m p o r t a n c e _ t y p e = ’ g a i n ’ , i n t e r a c t i o n _ c o n s t r a i n t s = ’ ’ , l e a r n i n g _ r a t e =0 .300000012 , m a x _ d e l t a _ s t e p =0 , max_depth =6 , m i n _ c h i l d _ w e i g h t =1 , m i s s i n g =nan , m o n o t o n e _ c o n s t r a i n t s = ’ ( ) ’ , n _ e s t i m a t o r s =100 , n _ j o b s =56 , n u m _ p a r a l l e l _ t r e e =1 , r a n d o m _ s t a t e =0 , r e g _ a l p h a =0 , reg_ lambda =1 , s c a l e _ p o s _ w e i g h t =1 , subsample =1 , t r e e _ m e t h o d = ’ e x a c t ’ , v a l i d a t e _ p a r a m e t e r s =1 , v e r b o s i t y =None )
We used the sklearn package for the logistic regression and MLP classifiers. For logistic regression, the accuracy is 0.8418967476428857, the specific configuration is:
L o g i s t i c R e g r e s s i o n ( r a n d o m _ s t a t e =0 , s o l v e r =" l i b l i n e a r " , C= 0 . 5 )
For the MLP, its accuracy is 0.8614600288688923, and the configuration is:
M L P C l a s s i f i e r ( r a n d o m _ s t a t e =0 , m a x _ i t e r =300 , l e a r n i n g _ r a t e _ i n i t = 0 . 0 0 2 , h i d d e n _ l a y e r _ s i z e s = ( 5 0 , 5 0 ) )
G.3 MORE RESULTS ON FEATURE VALUATIONS
In this part we provide more results on feature removal in Figures 5 and 6. Fig. 5 shows similar behavior as that shown in the main text. Fig. 6 provides not very distinguishable results of the three criteria.
G.4 MORE AVERAGE RESULTS ON FEATURE VALUATIONS
We provide additional statistical results with the MLP model (Fig. 8) and logistic regression model (Fig. 9). Meanwhile, we also put the full statistics on the xgboost model in Fig. 7 since in the main text the table of the samples with “False” grouthtruth label is skipped due to space limit. From Fig. 8 one can observe that Variational Index induces different rankings of the features compared to Shapley and Banzhaf: Variational Index ranks “Marital Status” the second, while Shapley and Banzhaf put it in the third location.
It is also very interesting to see that the logistic regression model (with the lowest training accuracy among the three models, shown in Fig. 9) provides different ranking for the first two features compared to MLP and xgboost. For the samples with “True” groundtruth labels, “Education-Num” is the first important feature for the logistic regression model, while “Captical Gain” was ranked first for the MLP and xgboost.
G.5 EXPERIMENTS WITH MORE PLAYERS
Furthermore, we experiment with a bit larger number of players (n = 80) using MCMC sampling to approximate the partial derivative in Eq. (13). The sampling based approximation works pretty fast. Table 2 shows the top 15 ranked players returned by our method, Shapley value and Banzhaf value for a synthetic data valuation problem. Note that the ranking of Variational Index is more similar to that of Banzhaf value than that of Shapley value.
logistic regression
xgboost
MLP
𝑇 = 0.8
𝑇 = 0.1
𝑇 = 0.5
Figure 6: Not very distinguishable results. First column: Change of predicted probabilities when removing features. The decoupling error is included in the legend. Last three columns: waterfall plots of feature importance from Variational Index, Shapley and Banzhaf.
G.6 EFFECT OF NUMBER OF SAMPLES IN MCMC SAMPLING
Here we illustrate the accuracy sampling tradeoff when estimating the gradient of multilinear extension using MCMC sampling. The results is shown in Fig. 10. One can observe that with more samples, Alg. 1 will converge faster (in fewer number of epochs).