Energy-Based Learning for Cooperative Games, with Applications to Valuation Problems in Machine Learning
Authors: Yatao Bian
Yu Rong
Tingyang Xu
Jiaxiang Wu
Andreas Krause
Junzhou Huang
Venue: ICLR 2022 Poster (2022)
Keywords: Valuation problems
Shapley value
Model interpretation
Data valuation
Enegy-based learning
Attribution-based feature interpretation
Model valuation for ensembles
Feature attributions

Abstract: 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 solved by well-known game-theoretic criteria, such as 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 framework. Surprisingly, by conducting variational inference of the energy-based model, we recover various game-theoretic valuation criteria through conducting one-step fixed point iteration  for maximizing the mean-field ELBO objective. This observation also verifies the rationality of existing criteria, as they are all attempting to  decouple the  correlations  among  the  players  through the  mean-field approach. By running fixed point iteration for multiple steps, we achieve a trajectory of the 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 experimentally demonstrate that the proposed Variational Index enjoys lower decoupling error and better valuation performance  on certain synthetic and real-world valuation problems. 

Published as a conference paper at ICLR 2022
ENERGY-BASED LEARNING FOR COOPERATIVE GAMES, WITH APPLICATIONS TO VALUATION PROB- LEMS IN MACHINE LEARNING
Yatao Bian'; Yu Rong', Tingyang Xu', Jiaxiang Wu', Andreas Krause", Junzhou Huang
Tencent AT Lab
ETH Zürich
ABSTRACT
Valuation problems, such as feature interpretation, data valuation and model val- uation 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 Banzhaf value. In this work, we present a novel energy-based treatment for cooperative games, with a theo- retical justification via the maximum entropy principle. Surprisingly, through mean-field variational inference in the energy-based model, we recover classical thme-theoretic valuation criteria by conducting one-step fixed point iteration for maximizing the ELBO objective. This observation also further supports existing criteria, as they can be seen as attempting to decouple the correlations among players. By running the fixed point iteration for multiple steps, we achieve trajec- tory of the variational valuations, among which we define the valuation with the best conceivable decoupling error the Variational Index. We prove that under uniform initialization, these variational valuations all satisfy a set of game- theoretic axioms. We empirically demonstrate that the proposed variational valuations enjoy lower decoupling error and better valuation performance on certain synthetic and real-world valuation problems!
INTRODUCTION
Valuation problems are becoming increasingly more significant in various machine learning applications, ranging from feature interpretation (Lundberg and
Energy Based Model for
Shapley Banzhal
C cooperative (.. F(S)):
o[Si x (/8)
KL(g x)] P(S)
Lee, 2017), data valuation (Ghorbani and Zou, 2019) to model valuation for ensembles (Rozemberezki and Sarkar, 2021). They are often formulated a player valuation problem in cooperative games. A cooper- ative game (N, FSS) consists of a grand coalition N (1, m.) of players and value function (a.k.a. characteristic function) F(S)= N > R de- scribing the collective payoff of coalition/coopera- tion S. A fundamental problem in cooperative game theory is assign importance vector (i.e., solution concept) ((F) E Ra to players.
Player valuations cooperative games
Mean field variational purameters
principled player valuations
K-step Varisiional Villnes
P(S)
etS. xc)
Valuntion problems
Feature inserpettaion
2-50
Data
valiation
fixod poins Herrito
Recoveggan
Shupley
Figure 1: energy based treatment of coop- erative games leads to a series of new player valuations: K-step variational values, satis- fying basic valuation axioms: null player, marginalism & symmetry.
In this paper, we explore probabilistic treatment of cooperative games (N, F(S)). Such treatment makes possible to conduct learning and inference in unified manner, and will yield connections with classical valuation criteria. Concretely, we seek probability distribution over coalitions p(S S)², measuring the odds that specific coalition
"Correspondence to: Yatao Bian <yatac. bi an@ i com> Prooeect page & code; https: /val uat ongame .ammm........ g thub. ic
'Note that distributions over subsets of N are equivalent to distributions of [ binary random variables X1,...,X X, (0. 1): We use X; as the indicator function of the event E S, or X; S). With slight abuse of notation, use random variable represented as and often abbreviate p(S S) as p(S).

---

Published as a conference paper at ICLR 2022
S happens. Generally, we consider distributions where the probability of a coalition p(5) grows monotonically with the payoff F(S).
Among all the possible probability mass functions (pmfs), how should construct the proper p(5)? 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 assuming nothing about what is unknown, i.e., choosing the most "uniform" distribution. Now finding proper p(S) becomes the following constrained optimization problem: suppose each coalition S is associated with payoff F(S) with probability p(S). We would like to maximize the entropy H(p) = EscN P(S) log p(S). subject to the constraints that Es PSS) = 1. (S5) 2 and Es P(S) FSS) = i (i.e., the average payoff is known as jt). Solving this optimization problem (derivation in Appendix A), we reach the maximum entropy distribution:
P( = exp(F(S)/T)
7: ESEEN exp (F)))))))/T)
(1)
Z
where 7 >> O is the temperature. This is an energy-based model (EBM, cf. 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 learning of value functions F(S) through efficient training techniques for 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 (Fig. 1). 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, I 1946; Banzhaf III, 1964). This observation also further supports existing criteria, motivating them decoupling the correlations among players via 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 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 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 mulriple steps, which generates a trajectory of valuations. Under uniform initializations, they all satisfy a set of game- theoreetc 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.
2 PRELIMINARIES AND BACKGROUND
Notation. We assume e; R. being the standard :hh basis vector and use boldface letters x E R and x E IR" interchangebly to indicate an n-dimensional vector, where x; is the 8thh entry of x. By default, f(-) is used to denote a continuous function, and F(-) to represent a set function. For a differentiable function (()), V v-()) denotes its gradient. x x|Ir, + A is the operation of setting the 7th element of x to k. while keeping all other elements unchanged, i.c., x|x; + = x I,e; + ke, For two sets S and T. S 5 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 coop- erative 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:
[ |S| 1)!
Sh, = -=SCN_110 |P(S + i) - FFS))
n!
2

---

Published as a conference paper at ICLR 2022
One can see that it gives less weight to n/2-sized coalitions. The Banzhaf value assigns the following importance to player i:
1
Ba;- CFCN_1F(S++ F(S)] 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; Rozemberezki and Sarkar, 2021) use Shapley value 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 al., 2017; Petsiuk et al., 2018; Wang et al., a0) attribution-based interpretation aims to assign importance to the features for a specific data instance (x E IR,, y) given a black-box model M. Here each feature maps model response, such as the predicted probability for classification problems, when feeding a subset of features to MM. The data valuation problem (Ghorbani and Zou, 2019) tries to assign values to the samples in the training dataset N {(x,, }4 for general supervised machine learning: one training sample corresponds to one player, and the value function F(5) indicates the predictor performance 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 ensemble in order to correctly label data points from dataset, where each pre-trained model maps to a player and the value function measures the predictive performance of subsets of models.
player the game (N, FS)), and the value function F(S) is usually the
3 RELATED WORK
Energy-based modeling. Energy based learning (LeCun al., 2006) is a classical learning frame- work that uses energy function E(x) to measure the quality of 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), reinforeement learning (Haarnoja et al., 2017), memory modeling (Bar- tunov et al., 2019), discriminative learning (Grathwohl et al., 2019; Gustafsson et al., 2020) and hhologicallyplaasiin
training (Scellier and Bengio, 2017). Energy based learning admits princi- pled 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) 1). For 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 al., 2019: Sahin et al., 2020; Bian al., 2020).
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), 1), collaborative machine learning (Sim et al., 2020) and recently, model valuation in ensembles (Rozemberezki and Sarkar, 2021). For 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 representation of cooperative games and Okhrati and Lipani (2021) use it to develop sampling algorithms for Shapley values.
4 VALUATION FOR COOPERATIVE GAMES: A DECOUPLING PERSPECTIVE
In the introduction, we have asserted 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 players in game (N, F()) 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 way to simplify their correlations.
3

---

Published as a conference paper at ICLR 2022
We therefore consider surrogate distribution g(;) x) governed by parameters in has to be simple, given our intention to decouple the correlations among the n players. natural choice is to restrain ((S)x) to be fully factorizable, which leads to mean-field approximation of p(S). The simplest form of ((S; x) would be a n independent Bernoulli distribution, i.e., g(S; x) == m Ta T Kz),x x E [0, 1 Given divergence measure D(-II-) for probability distributions, we can define the best conceivable decoupling ervor be the divergence between p and the best possible q.
Definition (Best Conceivable Decoupling Error). Considering a cooperative game (N, F())), and given divergence measure D(-1I-) for probability distributions, the decoupling error is defined as the divergence between and p: D(glip), and the best conceivable decoupling error is defined as the divergence between the best possible q and p:
D == min D(glp)).
(4)
Note that the best conceivable decoupling eroor D is closely related to the intrinsic coupling amongst players: if all the players are already independent with each other, then D could be zero
4.1 MEAN FIELD OBJECTIVE FOR EBMS
If we consider the decoupling error D(gllp) to be the Kullback- divergence between q and p, then recover the mean field approach'. Given the EBM formulation in Eq. (1), the classical mean-field inference approach aims to approximate p(5) by a fully factorized product distribution x): Iaas z; [1 æz); E 1J" by minimizing the distance measured w.r.t. the Bellback-Leibler divergence between g and p. Since (Ll()))) non-negative, we have:
0 < (g = Σ SCN ((5)x) log ((;xx)
p(S)
- By(S:x) PSS] x()(Sx)))
(5)
F(S)
BB(ssx)
log Z] - H[(
(6)
T
- Σ F(S)
(1 - (1-x,) + Σ i=1 Ein [r, log 24 + (1 x;) log(1 - xx)] + log Z.
(7)
T
SEN
iES
j&8
In Eq. (6) we plug in the EBM formulation that log p(S)
F(S) TT
loo 7. Then one can get
log Z 2
F(S)
II
I[ - 2z)) - [ log x. + (1 - xx.) log(1 zz)]
T
SCN
N
XS
JES
fu
(x)
H[((S; x)) == (ELBO)
(8)
T
where HH(()) is the entropy, ELBO stands for the evidence lower bound, and
(x))
Σ SCN F(S) II.
(1- 2,), E [0, 1]"
(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-Leitn Leibler divergence between and p. If one solves this optimization problem to optimality, one can obtain the ((;xx") with the best conceivable decoupling error. Here x; 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 = To (x") ) to be the variational index of the game. Formally,
x = arg min MaliinnKK(ggi [T[((((; x) ()p(()))
(10)
where x* can be obtained by maximizing the ELBO objective in Eq. (8), and o (-) is the inverse of the sigmoid function, i.e. o (z) = log - For vector it is applied element-wise.
Notably, one could also apply the reverse KI. divergence (L which would lead to expectation propagation (Minka, 2001) treatment of cooperative games.
4

---

Published as a conference paper at ICLR 2022
4.2 ALGORITHMS FOR CALCULATING THE VARIATIONAL INDEX
Equilibrium condition. For coordinate i, the partial derivative of the multilinear extension is V. V. (x), and for the entropy term, it is v,H(g(S;x)) = logg 1_x,, By setting the partial derivative of ELBO in Eq. (8) be O, have the equilibrium condition: zn
x oV (x*)((()))))) (1 exp(-V..f(x>)/7)) ViE,,
(11)
where a 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. also implics the fixed point iteration I; < o vV. (x)/"). When updating each coordinate sequentially, we recover the classic naive mean field algorithm as shown in Appendix C.
Instead, here suggest to the full- full-gradient method shown in Alg. 1 for maximizing the ELBO objective. As we will see later, the resultant valuations satisfy certain game- thee--th axioms. needs an initial marginal vector x" [0, 1J" and the number of epochs K. After K steps of fixed point iteration, it returns the estimated marginal K
Algorithm 1: Mean Field Inference with Full Gradient: (FI K)
Input: cooperative game (N, F(S)) with n players. Initial marginals x² +- x E [0,0]] 1)a. #epochs K.
Output: Marginals after steps iteration: x"
for k - K do
+ (V (x*
(x
(xxx-)//T))))))) /)) = (1 + exp( ( S 1//T)
In case Alg. solves the optimization problem to optimality, we obtain the Variational Index. How- ever, maximizing ELBO is in general non-convex/non-concas ensure reaching a stationary solution. Below, when we say Variational Index, we therefore refer to its approximation obtained via Alg. by default. Mcanwhile, the MFI 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).
problem, and hence one can only
Definition 3 (K-Son -tet Variational Values). Considering cooperative game (N, F(S)) and its mean field appreximation by Alg. 1, we define the K K-Step Variational Values initialized at x
To (MFI(X; K)),
(12)
where o 10 is the inverse of the sigmoid function (o (x:) log
Notice when running more steps, the K-Step variational value will be more close to the Variational Index. The gradient V fx((x) itself is defined with respect 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,
V vifmi (x)
(ugtS((((orr)))(((())) [F()] - (x((s(((a (F(S))
(13)
f + fm 22 0)
Σ F(S)
II Dj II
(1-xz)
Σ
F(S)
II xj II (1-4,) xzy) JES
SCN
jES-i
J'ES
SCN-i
Σ
[F(S
F(5) II Ø3
II
SCN-i
JES
JSE
= Σ
[F(S - - xx - 0)) Es=g(S:(x(err [F(S + 11))-F(5 F(S)).
SCN-i
All of the variational criteria are based on the calculation of the partial derivative Vi (x), which can be approximated by Monte Carlo sampling since V, v (x) = (s (x)))))) [F(S + F(S)]: we first sample m coalitions S₁, 1, ..., m from the surrogate distribution ((; (x|2; < 0)). then approximate the expectation by the average m - [F(Se + F(S+)). According the
5

---

Published as a conference paper at ICLR 2022
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(-me" /2), it holds that 1 ->=1FF [F(s + F(x))] - V. (x)] emaxs [F(S + 2) - F(S)], for all e 0.
Roles of the initializer x and the temperature T. This can be understood in the following respects: 1) The initializer x" represents the initial credit assignments to the n players, so it denotes the prior knowledge/initial belief of the contributions of the players; If one just runs Alg. 1 for one step, x matters greatly to the output. However, if one runs Alg. for many steps, x will converge to the stationary points of the ELBO objective. Empirically, it takes around 5~10 steps to converge. The temperature T controls the "spreading" of importance assigned to the players: A higher I leads to flatter assignments, and lower T leads to more concentrated assignments.
Computational efficiency of calculating Variational Index and variational values. Alg. 1 calcu- lates 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 V (x).. Sampling methods could help with approximating criteria when there are large number of players. The Variational Index can be approximated by the K K-step variational value, where the number K depends on when Alg. 1 converges. One can easily show that, under the setting of maximizing ELBO, x 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. 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.
of the three
4.3 RECOVERING CLASSICAL CRITERIA
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,
1 Ba:- EsEr IF(S +1) F(S) 2n (. 1) To - (MFI 1;1)), (14)
which is the 1-step variational value initialied 0.5 1. We also recover the Shapley value through its connection to the multilinear extension (Owen, 1972; Grabisch et al., 2000):
Sh; 1 1 V (x1)dx = S. To (MF(21
(15)
where the integration denotes integrating the purtial-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 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)), solution á is called probabilistic value, for each player i, there exists a probability p E ACC), such that de is the expected marginal contribution of i w.r.t. p'. Namely, Φ = =ESEcH (S(S)FFS + i) F(S)J, where C" is the set of all subsets of N i, and (CC*) is the set of all probability measures on C³. One can easily see that, for any fixed x, 1-step variational value in Def. 3 is a probabilistic value with (S)) q(S (x|x; + 0)). where q( S: x) 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 To (MFI(x; K)) in Def. 3 satisfy certain game-theoretic axioms (see Appendix B for definitions of five common axioms: Null player,

---

Published as a conference paper at ICLR 2022
synthetic
breast cancer
digits
Variational
Test accuracy (%6
70
20 groups, each sample, T 0.5
Test accuracy 1%6
94
accuracy (%)
True Bandhal (0. (0.0901923)
Shapley 10.1065176)
65
80
92
16 groups, random,
60
70-
10 group
90
kmeans,
Sariational Index 12, 500
Varatiinnal Indes 1a 0C3:920)
True Shapliy 12 034
Frue Shappey (0 (8.2424543)
50
True-Banohaf (2. 7336-033
88
Tramllanohel (0 (011971))
50
20
40
60
Fraction of training data removed (%)
Fraction of training data removed (%)
Fraction of training data removed (%)
68
Test accuracy (8)
lest accuracy (%)
96
Test accuracy (%)
12 groups, random,
64
20 groups, w.
Variatton Index (0 C0R2059)
50 samples, kmeans
95-
The Shappey 0103991)
True Bandi of (000022333)
95
T 0.5
62
14 groups,
kmeans
Varietiona index 12 12811120700 (4)) The Shapley (3 4..4222 041 "renderrterr 83.3150000
T 0.5
Varietional Index (000091351 The Shapley 10. (0.6014224)
94
(6 (0.090577))
20
0
20
40 60
20
40
60
Fraction of training data removed (%)
Fraction of training data removed (%)
Fraction of training data removed (%)
Figure 2: Data removal results. Numbers in the legend are the decoupling errors. Columns: Ist: synthetic data; 2nd: breast cancer data with 569 samples; 3rd: digits data with 1797 samples. Specific configurations (e.g.. temperature) are put inside the figure texts.
Symmetry, Marginalism, Additivity and Efficiency). We prove that all the variational values in the trajectory satisfy three fundamental axioms: null player, marginalism and symmetry. The detailed proof is deferred to Appendix E. We expect of the series of variational values, which we leave for future work. Meanwhile, our methods incur a decoupling and fairness tradeoff by tuning the hyperparameters K and T.
be very difficult to find equivalent axiomatisations
Theorem (Axiomatisation of K- K-Step Variational Values of Def. 3). If initialized uniformly. i.e., x" = =x, E [0, 1), all the variational values in the trajectory To TM-I(MFI(x; k)), 1,2.3... satisfy the null player, marginalism and symmetry axioms.
According to Theorem 1, our proposed K- K-step variational values satisfy the minimal set of axioms often associated with appropriate valuation criteria. Note that specific realizations of the K-step variational values can also satisfy more axioms, for example, the 1-step variational value initialized at 0.5 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 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 argued by Ridaoui et al. (2018), 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.
5 EMPIRICAL STUDIES
Throughout the experiments, we are trying to understand the following: 1) Would the pro- posed Variational Index have lower decoupling error compared 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, is necessary to rule out the influence of approximation errors when estimating their values. So we focus small-sized problems where one can compute the exact values of these criteria reasonable time. Usually this requires the number of players to be more than 25. Mcanwhile, 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 x was intialized to be 0.5 x 1. Code is available at ht //vaaaalatttt oongame gi thub ic.
We first conduct synthetic experiments on submodular games (details defered to Appendix G.1), in order verify the quality of solutions in terms of the true marginals p(i S). One conclude
7

---

Published as a conference paper at ICLR 2022
Varistional
Shupley
Banchaf
10
*gboosco3
Hod S0N6 F=00
Duta idl 24009
0.2
GT Glibeel: True
Number of resert
Ingistic 9. regressiona.
20.
7:10.1
Duta 1977 GT libd: Tiue
lunder aeporreteeent
MLP
ancrosieee pamnt
I- D.5
Elass kd: 16:19
GT
Number IOSEEERREEEE
Figure 3: 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 's rank correlation compared to the one- one-point solutions (Shapley value and Banzhaf value) in all experiments. More experimental results on data point and feature valuations are deferred Appendix G.
5.1 EXPERIMENTS ON DATA VALUATIONS
We follow the setting of Ghorbani and Zou (2019) and reuse the code of https: : / / thub. com/ ami 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; <) The digits dataset, that is 10-class classification dataset with 1797 samples. both from UCI Machine Learning repository (https: / /archiiee viee. ics. uci. edu/mm/ fttt/mm//ndexx windixixxx..//// ahd) 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. 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 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 where the rankings of the three criteria are not very distinguishable, however, the specific values are also very different since the decoupling error differs.
The above two datasets
5.2 EXPERIMENTS ON FEATURE VALUATIONS/AFTRIIUTION
We follow the setting of Lundberg and Lee (2017) and reuse the code of https: / com/ slundberg/ shap with an MIT License. We train classifiers on the Adult dataset', which predicts whether an adult's 's income exceeds 50k dollar per year based on census data. It has 48,842 instances and 14 features such as age, workelass, 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. 3 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
httpps:/arccii iss uci edd/ml /ttt//tttataaaaaaaaeaa
8

---

Published as a conference paper at ICLR 2022
True
True
True
Secorion-Huu
Rack
Quality
A
Variational
Shopley
Banchal
GT Labels: True
10
11
12
Var, Index
Capiall Gain Rekosinndy
Blaction Stor
Occopation
Marial Somus
Capial Lose
Nosn per week
Sea
Race
Workelon
Count
Shapley
Oopisa Gain Rekeiondap
Age
Occopatoo
Mariol Somus
|laars per sarak
Capiol Lasa
Sea
Workslsss
Bran
Country
Banzhaf
Gein, Rekziendei Blacdiinn-
Occupation
Marial
(orliclas
Figure 4: Statistics on valuations with the xghoost classifier. First row: box plot of valuations. We always consider the predicted probability of the ground truth label. "True" means the samples with positive ground truth label and "False" means with the negative ground truth label. Second row: Average ranking of the 12 features. Colored texts denote different rankings among the three criteria.
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 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".
Average results. We further provide the bar plots and averaged ranking across the adult datasets in Fig. 4. 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".
5.3 EMPIRICAL CONVERGENCE RESULTS OF ALG.
Table I shows convergence results of Alg. on feature and data valuation experiments. The value in the cells are the stepwise difference of x ||x"-x*-11 which is classical criterion to measure the convergence of iterative algorithms. One can clearly see that Alg. converges in 5 to 10 iterations.
x
Table 1: Stepwise difference
of Alg. for different experiments.
n
Step/Iteration Num
2
3
5
9
10
Data Val (breast cancer)
0.0023
3.6le-6
1.53e-7
2.77e-10
9.12c-16 16
Data Val (digits)
0.00099
5.93e-7
1.46e-8
8.92e-12
9.25e-18
Data Val (synthetic)
0.00059
2.49e-8
3.13e-10
6.06e-14
0
Feature Val (xgboost)
0.0066
1.68e-5
8.71e-7
2.35e-9
1.75e-14
9,25e-16
Feature Val (LR)
0.0092
2.63e-5
1.44c-6
4.31c-9
2.14c-15
1.28c-16
Feature Val (MLP)
0.0040
4.86c-6
1.86e-7
2.84c-10
6.82c-16
3.20c-17
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 explore more in the following directions: 1) Choosing the temperature T. The temperature controls the level of fairness since, when 7 + co, all players have equal importance, when T - O. whereas a player has either 0 or 1 importance (assuming no ties). Perhaps one can use an annealing-sti
algorithm in order to control the fairness level: starting with a high temperature and gradually decreasing it, one can obtain 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 consider conditioning and marginalization in light of practical applications. 3) It is very interesting to explore the interaction of a group of players in the energy-basee framework, which would result in an "interactive" index among size-k coalitions.
9

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT AND BROADER IMPACT
Besides the valuation problems explored in this work, cooperative game theory has already been applied to wide range of disciplines, name few, economics, political science, sociology, biology, so this work could potentially contribute to broader domains as well.
Meanwhile, have be aware of possible negative societal impacts, including: 1) negative side effects of the technology itself, for example, possible unemployment issues due to the reduced amount of the need of valuations by human beings; applications in negative downstream tasks, for instance, the data point valuation technique could make 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 code as supplementary material. 2) Provide self-contained proofss of the main claims in Appendices D and E; 3) Provide more details on experimental configurations and experimental results Appendix G.
REFERENCES
M. Ancona, E. Ceolini, C. Öztireli, and M. Gross. Towards better understanding of gradient- attribution methods for deep neural networks. arXiv preprint arXiv: 2017.
M. Ancona, C. Öztireli, and M. Gross. Explaining deep neural networks with a polynomial time algorithm for shapley values approximation. arXiv preprint arXiv: 2019.
J. F. Banzhaf III. Weighted voting doesn't 't work: A mathematical analysis. Rutgers L. Rev., 19:317, 1964.
Bartunov, W. Rae, Osindero, and T. Lillierap. Meta-learning deep energy-based memory
models. arXiv preprint arXiv: 190.0027700 2019.
Y. Bian, J. M. Buhmann, and A. Krause. Continuous submodular function maximization. arXiv preprint arXiv:2006. 1..0006.34777 13474, 2020.
Y. A. Bian, J. M. Buhmann, and A. Krause. Optimal continuous dr-submodular maximization and applications to provable mean field inference. In Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 644 653, Long Beach, California, USA, 09-15 Jun 2019, PMLR.
G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing a submodular set function subject to matroid constraint. In International Conference Integer Programming and Combinatorial Optimization, pages 182-196. Springer, 2007.
Chen, Song, M. J. Wainwright, and M. Jordan. L-shapley and e-shapley: Efficient model interpretation for structured data. arXiv preprint arXiv: 1 888.02610, 2018.
Y. Chun. A new axiomatization of the shapley value. Games and Economic Behavior, (2)::119-13)) 1989.
S. Cohen, G. Dror, and E. Ruppin. Feature selection via coalitional game theory. Neural Computation, 1937):199-1191, 2007.
I. Covert, Lundberg, and S.-I. Lee. Explaining by removing: A unified framework for model explanation. arXiv preprini arXiv:2011.14878, 2020a.
I. Covert, S. Lundberg, and S.-I. Lee. Understanding global feature contributions with additive importance measures. arXiv preprint arXiv:2004.006663 2020b.
A. Datta, S. Sen, and Y. Zick. Algorithmic transparency via quantitative input influence: Theory and experiments with learning systems. In 2016 IEEE symposium on security and privacy (SP), pages 598-617. IEBE, 2016.
10

---

Published as a conference paper at ICLR 2022
Y. Deng, A. Bakhtin, M. Ott, A. Szlam, and M. Ranzato. Residual energy- based models for text generation. arXiv preprint arXiv:2004.17714. 2020.
J. Djolonga and A. Krause. From map marginals: Variational inference in bayesian submodular models. In Neural Information Processing Systems (NIPS). 2014.
Z. Fan, H. Fang, Z. Zhou, J. Pei, M. P. Friedlander, C. Liu, and Y. Zhang. Improving fairness for data valuation federated learning. arXiv preprint urXiv:2109.00 09046, 2021.
U. Feige, V. S. Mirrokni, and J. Vondrák, Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40(4): 1193::133-1155: 2011.
A. Ghorbani and J. Zou. Data shapley: Equitable valuation of data for machine learning. In International Conference Machine Learning, pages 2242-2251. PMLR, 2019.
M. Grabisch. K-order additive discrete fuzzy measures and their representation. Fuzzy sets and systems, 92(2):167-189, 1997.
M. Grabisch, J.-L. Marichal, and M. Roubens. Equivalent representations of set functions. Mathe- matics of Operations Research, 25(2):157-178, 2000.
W. Grathwohl, K.-C, Wang, J.-H. Jacobsen, D. Duvenaud, M. Norouzi, and K. Swersky. Your classifier secretly an energy based model and you should treat like one. arXiv preprint arXiv:1912.03263 2019.
G. Greco, Lupia, and Scarcello. Structural tractability of shapley and banzhaf values in allocation games. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
F. K. Gustafsson, M. Danelljan, R. Timofte, and T. B. Schön. How train your energy- model for regression. arXiv preprint arXiv:2005.01699, 2020.
M. Gutmann and A. Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 297-304, JMLR Workshop and Conference Proceedings, 2010.
T. Haarnoja, H. Tang, P. Abbeel, and S. Levine. Reinforcement learning with deep meeryy-based policies, In International Conference on Machine Learning, pages 1352-1361. PMLR, 2017.
P. L.. Hammer and S. Rudeanu. Boolean methods in operations research and related areas, volume 7. Springer Science & Business Media, 2012.
G. E. Hinton. Training products of experts by minimizing contrastive divergence. Neural computation, 1478):1771-1800, 2002.
W. Hoeffding. Probability incqualities for sums of bounded random variables. Journal of the American statistical association, 58(301):13-30, 1963.
A. Hyvärinen. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005.
E. T. Jaynes. Information theory and statistical mechanics. Physical review, 106(4):620, 1957a.
E. T. Jaynes. Information theory and statistical mechanics. ii. Physical review, 108(2):171, 1957b.
R. Jia, D. Dao, B. Wang, F. A. Hubis, N. Hynes, N. M. Gürel, B. Li, C. Zhang, D. Song, and C. J. Spanos. Towards efficient data valuation based the shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1167-1176. PMLR, 2019a.
R. Jia, X. Sun, J. Xu, C. Zhang, B. Li, and D. Song. An empirical and comparative analysis of data valuation with scalable algorithms. arXiv preprint arXiv.1911.07128. 2019b.
A. Krause and D. Golovin. Submodular function maximization. Tractability, 3:71-104, 2014.

---

Published as a conference paper at ICLR 2022
1. E. Kumar, C. Scheidegger, S. Venkatasuubramanian, and S. Friedler. Shapley residuals: Quantifying the limits of the shapley value for explanations. In JCML Workshop on Workshop on Human Interpretability in Machine Learning (WHI), 2020.
Y. LeCun, S. Chopra, R. Hadsell, M. Ranzato, and Huang. tutorial on energy-based learning. Predicting structured data, 1(0), 2006.
Lipovetsky and M. Conklin. Analysis regression in game theory approach. Applied Stochastic Models in Business and Industry, 17(4):319-330 2001.
W. Liu, X. Wang. D. Owens, and Li. Energy Energy-based diittiitiitiiiitoonnn detection, arXiv preprint arXiv:2010.03759, 2020.
S. Lundberg and S.-I. Lee. unified approach to interpreting model predictions. arXiv preprint arXiv:1705.07874, 2017.
S. M. Lundberg, G. G. Erion, and S.-I. Lee. Consistent individualized feature attribution for tree ensembles. arXiv preprint arXiv:/800 03888, 2018.
T. P. Minka. Expectation propagation for approximate bayesian inference. In Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence, pages 362-369, 2001.
D. Monderer and D. Samet. Variations on the shapley value. Handbook of game theory with economic applications, 3:2055-2076 2002.
R. Okhrati and A. Lipani. A multilinear sampling algorithm to estimate shapley values. In 2020 25th International Conference on Pattern Recognition (ICPR), pages 7992-7999. IEEE, 2021.
A. B. Owen. Sobol'indices indices and shapley value. SIAM/ASA Journal on Uncertainty Quantification, (1):245 251, 2014.
G. Owen. Multilinear extensions of games. Management Science, 186--part-2):64-79, 1972.
I. S. Penrose. The elementary statistics of majority voting. Journal of the Royal Statistical Society, 109(1):53-57, 1946.
V. Petsiuk, A. Das, and K. Saenko. Rise: Randomized input sampling for explanation of black-box models. arXiv preprint 1rXiv:1806. 806.07421, 2018.
M. T. Ribeiro, S. Singh, and C. Guestrin. why should trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135-1144, 2016.
M. Ridaoui, M. Grabisch, and C. Labreuche. axiomatisation of the banzhaf value and interaction index for multichoice games. In International Conference on Modeling Decisions for Artificial Intelligence, pages 143-155. Springer, 2018.
B. Rozemberczki and R. Sarkar. The shapley value of classifiers in ensemble games. arXiv preprint arXiv:2 153, 2021.
A. Sahin, Y. Bian, J. Buhmann, and A. Krause. From sets to multisets: provable variational inference for probabilistic integer submodular models, In International Conference on Machine Learning. pages 8388-8399 PMLR, 2020.
B. Scellier and Y. Bengio. Equilibrium propagation: Bridging the gap between energy-based models and backpropagation. Frontiers in computational neuroscience, 11:24, 2017.
L. S. Shapley. A value for n-person games. Contributions the Theory of Games, 2(28):307-317, 1953.
R. H. L. Sim, Y. Zhang, M. C. Chan, and B. K. H. Low. Collaborative machine learning with incentive- aware model rewards. In International Conference on Machine Learning, pages 8927-8936. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2022
E. Strumbelj and Kononenko. An efficient explanation of individual classifications using game theory. The Journal of Machine Learning Research, 11:1-18, 2010.
M. Sundararajan, A. Taly, and Q. Yan. Axiomatic attribution for deep networks. In International Conference Machine Learning, pages 3319-3328. PMLR, 2017.
Tschiatschek, Djolonga, and Krause. Learning probabilistic submodular diversity models via noise contrastive estimation. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), 2016.
M.J. Wainwright and M. Jordan. Graphical models, exponential families, and variational inference. Now Publishers Inc, 2008.
Wang, Wiens, and S. Lundberg. Shapley flow: A graph-based approach to interpreting model predictions. In International Conference on Artificial Intelligence and Statistics, pages 721-729. PMLR, 2021a.
R. Wang, X. Wang, and D. I. Inouye. Shapley explanation networks. arXiv preprint arXiv:2104.0229; 2021b.
T. Wang, J. Rausch, C. Zhang, R. Jia, and D. Song. A principled approach to data valuation for federated learning. In Federated Learning, pages 153-167. Springer, 2020.
R. J. Weber. Probabilistic values for games. The Shapley Value. Essays in Honor of Lloyd S. Shapley, pages 101-119, 1988.
M. Welling and W. Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-II), pages 681-688. Citeseer, 2011.
B. Williamson and J. Feng. Efficient nonparametric statistical inference on population feature importance using shapley values. In International Conference Machine Learning, pages 10282-10291. PMLR, 2020.
H. P. Young. Monotonic solutions of cooperative games. International Journal of Game Theory, 14 (2):65-72, 1985.
M. Zeiler and R. Fergus. Visualizing and understanding convolutional networks. European conference on computer vision, pages 318-833. Springer, 2014.
13

---

Published as a conference paper at ICLR 2022
Appendix of "Energy-Based Learning for Cooperative Games, with Applications to Valuation Problems in Machine Learning"
CONTENTS
Derivations of the Maximum Entropy Distribution
14
Common Axioms of Valuation Criteria
15
C The Naive Mean Field Algorithm
16
Proof of Recovering Classical Criteria
16
Proof of Theorem
17
Miscellaneous Results Sec.
18
G More Configuration Details and Experimental Results
19
G.1 Synthetic Experiments on Submodular (FLID) Games
19
G.2 Details of the Models for Feature Valuations
20
G.3 More Results on Feature Valuations
20
G.4 More Average Results Feature Valuations
20
G.5 Experiments with More Players....
21
G.6 Effect of Number Samples MCMC Sampling
22
A DERIVATIONS OF THE MAXIMUM ENTROPY DISTRIBUTION
One may wonder why do 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())/T) Because one may also formulate it as something else, say, P(S) & (1 + [FS)))?
In 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 understand is that: Since the distribution with the maximum entropy 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 move towards maximal entropy configurations over time (Jaynes, 1957a;b).
the following we will give a derivation to show that p(S) x exp(F(S)/T) is indeed the maximum entropy distribution for 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 maximize the entropy Hl(p) Σscr P(S) log P(S), subject to the constraints that Es p(S) 1, p(S) and (()) (i.e., the average payoff is known as (4).
Writing down the Lagrangian
14

---

Published as a conference paper at ICLR 2022
A1))
Σ log((s) + Ao Σ - +
E
((S))(())
(16)
SCN
SCN
Setting
OL(p, do, A1)
= [ogr(S) +1+ -1
(17)
Op(S)
=0
(18)
get:
p(S) = expl- -1-
(19)
A + 1 log
Σ cxp(A)F(5)) log
(20)
SCN
is the log-partition function. So,
(S5) exp[A)
(21)
Z
Note that the maximum value of the entropy is
Hmax
Σ p(S) logp(s)
(22)
SCN
λy 1 Σ ((S)F(S)
(23)
SCN
An + 11 A1p
(24)
So one can get,
0H Oy
A
(25)
T
which defines the inverse temperature.
So reach the exponential form of p(S) as:
expl exp[F(S)/TT)
p(S) - ESSN expl F(S)/T]
(26)
B COMMON AXIOMS OF VALUATION CRITERIA
Following the definitions in Covert et al. (2020a), the five common axioms are listed as bellow. di(F)
denotes the value assigned to player in the game (N, F(S)). Note that the notions might be slightly different classical literature of game theory.
Null player: For player in the cooperative game (N, F(S)), + F(S) holds for all SCN N - i, then its value should be (F) O.
Symmetry: For any two players i.j in the cooperative game (N, F(S)), if i) = F(S + j) holds for all S C N - -j. j. then holds that (.()) = (F)).
Marginalism:
For two games F(S)) and (N, G(S)) where all players have identical marginal contributions, the players obtain equal valuations: F(S + 1) F(S) = G(S + - G(S) holds for all S), then it holds that o, (F) (G).
Additivity: For two games (N, F(S)) and (N, G(S)). if they are combined, the total contribution of player is equal to the sum of its individual contributions each game: (, (F(F))
Efficiency: The values add up to the difference in value between the grand coalition and the empty coalition: ΣieN (F) F(N)- F(O).
15

---

Published as a conference paper at ICLR 2022
Remark 1 (The notion of "marginalism") Specifically, the marginalism axiom was first mentioned by (Young, 1985. Equation 7 on page 70), where was called the "independence" condition; Following (Chun, 1989, page 121), it 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 players. Initial marginal x" E [0, 1J"; #epochs K. Output: The Variational Index s* a-'00'" (x*)
+ x":
for epoch from to K do for i > n do
let Dú be the player being operated;
Fe. o (m))) (1 + -
X:
C THE NAIVE MEAN FIELD ALGORITHM
The naive mean field algorithm is one of the most classical algorithm for mean field inference. is summarized in Alg. 2.
D PROOF OF RECOVERING CLASSICAL CRITERIA
For Banzhaf value, by comparing its definition in Eq. (2) with Eq. (13) it reads,
Ba: ESCNN, F(S + F(S)) 2n (0.5 1) To 1(MFI 1;1)), (27)
1
which is the 1-step variational value initialied at 0.5 1.
For Shapley value, according Grabisch al. (2000), here we prove stronger conclusion regarding the generalization of Shapley value: Shapley interaction index, which is defined for any coalition S
Shs Σ
(n T (n
ISD!T S + I)!
- +T).
(28)
TCN
LGS
Given Hammer and Rudeanu (2012), we have a second form of the multilinear extension as:
f = Σ a(S)
II
x E 10,
(29)
SCN
ÉS
where a(S) = E is the Mobius transform of F(S).
Then, one can show the S-derivative f (x) is (suppose S = (1st))
@I f (x)
A A (x)
Σ (( II Fi-
(30)
Dr, Origsl
T2S
1ET-9
So,
A Asff(11 Σ
(TT))
(31)
T2S
Then holds,
[rd Asttf '' Σ
aT)) 7
11
(32)
T2S
16

---

Published as a conference paper at ICLR 2022
a(T) /" x 2121-11ida dx
[((T)
(33)
728
Σ (TT) - 111 1)
(34)
T2$
According to Grabisch (1997), we have Shs = Erss a (TT)(T) - + 1) then we reach the conclusion:
//'
Shg
As Afffi(r1ddz
(35)
When SS| = 1, we recover the conclusion for Shapley value.
E PROOF OF THEOREM 1
Theorem (Axiomatisation of K-Step Variational Values of Def. 3). initialiized uniformly, i.e. x æ1, E [0, 1], all the variational values in the trajectory To TMFI(x;( k)), 1.2. satisfy the null player, marginalism and symmetry axioms.
Proof of Theorem 1. In step k. know that the value player i is:
To (MFI(X)) Σ [F(S F(S) II xz II (1 (1-xz)
(36)
SCN-i
jES
J'EN-S-1
For the null player property, since F(S + i) = F(S) always holds, it is easy to see that holds for all i N.
To-1 (MFI((x
Now we will show that the symmetry property holds. The value to player is:
To To (MFI(x k))x
Σ [F(' +1') F(S')) II Ø
II
(1 (1-1z)
(37)
S'CN-V
JES'
J'EN-S'-i
Now let us compare different terms the summands Eq. (36) and Eq. (37). We try match the summands one by one. There are two situations:
Situation I: For any S S
V' we choose S' S.
In this case we have F(S + i)
F(S) F(S' + 1') - -(SS). For the products of x we have:
II
Ø
II
(1- (1-2z)) - II
II
(1-xz))
(38)
JES
J'EN S i
jES'
J'EN
II JES
II
(1 (1- [(1 - xx)
xx,)
(39)
J'EN-S---
We know that 2y x, holds from step 0, by simple induction, we know that xy = holds for step as well. in this situation, summands equal to each other.
Situation H: For any S == A + f', we choose S' ====4 A + where A AC N - holds that F(S + i) - F(S) = F(S +1)) - F(S'). For the products of x we have:
i. In this case, it still
II m. jES
II
(1 2z) II áj
II
(1- x-=x)=
(40)
VVN----
jES
J'
I
II
(1 -1-2 Fz (ov m.).
(41)
JEA
J'EN TEN-A-i-?"
Again, by the simple induction, we know that Ty. = 2; 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.
17

---

Published as a conference paper at ICLR 2022
F MISCELLANEOUS RESULTS IN SEC. 4
Gradient of entropy in Sec. 4.2 Note that q a fully factorized product distribution (S:
Thes Z; E [0, 10" so its entropy ())( can be written the sum of entropy of n independent Bernoulli distributions. And the entropy of one Bernoulli distribution with parameter T2 is
2z log - (1 -x;) log(1 2z)
So have,
"
V,H((((;:)) = V.
Σ --x; log v; - (1 x;) 1og(1 - xi)]
(42)
i=1
Vi Ty log 24 (1 log(1 (1 x;)]
(43)
Iz
log
(44)
Satisfying axioms is not essential for valuation problems. Notably, in cooperative game theory, one line of work to seek for solution concepts that would satisfy more axioms. However, for valuation problems in machine learning, this arguably not essential. For example, similar as what Ridaoui et al. (2018) argues, efficiency does not make sense for certain games.
For simple illustration, let consider a voting game from a classification model with 3 binary features x E {0, 133 with weights w = [2, 1]] f(x) := [wTxx23 3x333. Now we are trying to find the valuation of each feature in N = {x11 I3. Naturally, the value function in the corresponding voting game shall be F(S)
fxx) 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 21, there are three situations: F(f1,2)) F((2)), F((1,3)) F((3)) and F((1,2,3)) F({2, for feature there are one situation: 2((1,2)) (((1,2))-P(( P({1)) feature 23, there are one situation: F(11,3) ratio. By simple calculations, one can see that the Banzhaf 1 1. which consistent with the ratio of the expected voting power. However, the Shapley values of them are 6 6 5, which is not consistent due to satisfying the efficiency axiom.
F((1)). Then the voting power (or valuation)
of each feature shall follows 3
values of the three features are 4
By the above example we are trying to explain that for valuation problems, satisfying more axioms 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.
The "one-shot sampling trick" to accelerate Alg. 1. Indeed, Variational Index needs 5 to 10 iterations to converge. In each iteration one has to evaluate the gradient of multilinear extension ffl(())) which needs MCMC sampling to estimate the exponential sum.
Here we suggest a "one-shot sampling trick", when is expensive to evaluate the value function F(S). This trick could reuse the sampled values in each iteration, such that Alg, I could run with the similar cost as calculating Banzhaf values.
The she- sampling trick is built upon formulation taken from Eq. (13):
(x) = Σ [F(S +) (000-F((5)) (S))))(SS(((xe)))) + 0))
SCN-1
For coordinate of (x)),, we can firstly sample m coalitions uniformly randomly from N and evaluate their marginal contributions. Then in each of the following iterations, could reuse the one-shot sampled marginal contributions to estimate the gradient according to the above equation. In this way, could make the cost of multi-step running of Alg. similar that of Banzhaf value in
18

---

Published as a conference paper at ICLR 2022
terms of the number of F(S) evaluations. Compared the original iterative sampling from q, this one-shot sampling might come with a variance- complexxy tradeoff, for which we will explore as future work.
G MORE CONFIGURATION DETAILS AND EXPERIMENTAL RESULTS
G.1 SYNTHETIC EXPERIMENTS ON SUBMODULAR (FLID) GAMES
1.2
Sydpley. MSS 0.008669, 0429
71
Banchal. MSe
005833, AL936
6
Variatoonal MS 5 0,003967, 0000
True Karginals
-22
Shapley. MSE: 0.007181,
Barzhat. NSE: 0.001851, 0,8286
-13
True Marginals
-14
Shapley. MSE: 0.011854, P 0.9762
Benzhaff MSE: 0,006144, 0.9762
Variational. MSE: 0.001339, #: 1.0000
True Marginals
8
MSB. boggrs, 0.9286
-02
Banzhat: MsE 0012300 p: 0.9286
Variational, MSE b 0002877 1.0000
True Marginals nais
-03
MSE: 0.009392, 0.9758
Barzhaf. MSE: o 0.00099,, p. 0.9758 -
Variational. MSE: 0.000110,
True Marainals
66.1
10
-02
-13 Shapley. MSE: 010549 0.9152
0.003706,
Variational. MSE: 0.000371, 1.0000
Marginals
-55
Indee plaves
D 4
D=8
Figure 5: Comparison of different importance measures for FLID games. Hidden dimensions: First column D=4, second column D=8. n denotes of players. Vertical lines means (marginals- 0.5) since we would like to clearly show positive players (marginal 0.5) and negative players (marginal < 0.5).
Here we define a synthetic game with the value function as a FLID (Tschiatschek et al., 2016) objective F(S), which is diversity boosting model satisfying the submodularity property. We know that its multilinear extension admits polynomial time algorithms (Bian et al., 2019). Let W RR. D be the weights, each row corresponds the latent representation of item, with D as
19

---

Published as a conference paper at ICLR 2022
the dimensionality. Then
F(S) :=))==Em
==E u4 + Σ (max Wi, - EiES Wi,)) = - ui iES
d=
=dd=1
max Wi,d, (45)
'ES
which models both coverage and diversity, and uz un uu ---EE Wi,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(ú E S) since they represent the probability that player participates in all coalitions, which is hard to compute in general. The distance to the true marginals is also 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 (p) to the ground truth marginals p(i E S) and report them in the figure legend. Fig. 5 collects the figures, one better performance terms MSE and Spearman's rank correlation compared to the one-poine one-point solutions (Shapley value and Banzhaf value) in all experiments.
that the Variational Index clearly obtains
G.2 DETAILS OF THE MODELS FOR FEATURE VALUATIONS
For xgboost, the train accuracy is 0.89333079114776099 the specific configuration with the xghoost package is:
XGB baliaasiifferbbasssoooooooo 05 booster=
gbtree', "rester='gbtree',,
pelsample_bylevelle
colsample_bynode--.. bynode=l, bessample_bytree-tee gamma=0, gpu id=-1,
colsample
importance_lype=='aa
interaction interaattion_coostttinnsss
learning Baamiing_rate==030000000
max max_delta deltaastee=O,, max max_depth=0,
missing-nan, monotone ponootoe_coossttainnsssssss ()', 0_estimators=100. n_jobs=56. num_parallei_tree==
fiin_child_wetee
random statommmsstt=0_._. reg_alpha=0, reg_lamba==,,
scale poleepos__tte wwwghtsswwhhsll.... subsample=1, tree arce_method== " exact",
validate_paramcterssll. verbosity=None)
We used the sklearn package for the logistic regression and MLP classifiers. For logistic regression, the accuracy 0.84118977766428857, the specific configuration is:
Logistic (raneessssiioonn.nnn..noo (randon
solver=" solver="liblineer" liblinear". C=0.5)
For the MLP, its accuracy is 0.6.G06680000166602888668822222 and the configuration is:
MLPClassifier (randea_stadaaaaaee max_iter=300
learning_ratee D =0002
(50 ,50))
G.3 MORE RESULTS ON FEATURE VALUATIONS
In this part we provide more results feature removal in Figures 6 and 7. Fig. shows similar behavior as that shown in the main text. Fig. 7 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. 9) and logistic regression model (Fig. 10). Meanwhile, we also put the full statisties on the xgboost model in Fig. 8 since in the main text the table of the samples with "False" grouthtruth label is skipped due to space limit. From Fig. 9 one can observe that Variational Index induces different rankings of the features compared Shapley and Banzhaf: Variational Index ranks "Marital Status" the second, while Shapley and Banzhaf put in the third location.
It is also very interesting to that the logistic regression model (with the lowest training accuracy among the three models, shown in Fig. 10) 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 MI. and xgboost.
20

---

Published as a conference paper at ICLR 2022
Date ID: 31485, Label: Thue
Deta ID: 13485 Lubet True, Variationall IrceS Data ID: 13425, Labet TrUN, TrunStap
Data ID: 11485, Label: Trus, Truncdancnal
xeboostox
0.2
Data (D:
(9-55755 1975, Libel True
Data D: 1975, Label Trus, Variationl hoee
Date ID: 1975, Label Trus, Trunshaplyy
Data ID: 1975, Labal: Tran Trum
logistic 03
regressson
0.2
T=0.1
Data Labet True
Data 3785, Labe: Variational mox
Dara Labe: True, True Stspey
Data True.
MLP
T=05
02:
16
Figure 6: First column: Change of predicted probabilities when removing features. The decoupling error included in the legend. Last three columns: waterfall plots of feature importance from Variational Index, Shapley and Banzhaf.
Data 13025, Label Trus
Duta ID: 12025, Label Trux, Variatignal Indix Data 11023, Label: True Trus Shapley Data ID 11021, Label: True. Trus Barahal
xghood!
cove tabo 2010
Murser Inddum
Daca I. 26335, Labdl FaSE
Dot2 26535, Label False. Varioiinnal Index Data ID: 15952, Label Fabse True Shapley Data 16962. Label Fasce Trus Barzhaf
logistic uzs-
regrossonn
2oss
T=0.1
23147, Label True
Data 21147. Label Variatigna
21147, True
Data 21147,
MLP
T=05
Muroer FRACCM
Figure 7: 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.5 EXPERIMENTS WITH MORE PLAYERS
Furthermore, we experiment with 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.
21

---

Published as a conference paper at ICLR 2022
False
False
Na Saioo Dicspttin la Saadors
Coda
-1
2
-02
-C1
6.0
0.1
0.2
6. X2
-B1
02
03
Labels: True
Index
Cipiall Gzit Reainnoki
Age
Nan
Occupation
Caphall Loss
Hours per
Workllas
Counyy
Shapley
Gait
Sare
Age
Occupation
Marial
Capizil
Workslas
Rice
Banzhuf
Oapial Gain
Diaattonn Nars
Age
Oxcopation
Marial State
Capita Lios
Houn per wark
Sex
Ras
Workchas
County
False
Var. Index
Expital Gain Rekuienday
Edantioon Ntar
Ocespotion
Martal
Capttll
Sex
Race
Workeloos
County
Shupley
Cupital Gain, Rekansnder
Capeal Lom
Age
Edusziion-
Num
Marial Suaue
Bours per week
Occupation
Work
Counzyy
Rice
Sex
Banzhaf
Caphtal Gain Rehziendip
Capiaal Low
Educotionn
Sum
Martal
Occupation
Councry
Roce
Figure 8: Full statistics on valuations with the xgboost classifier (in the main text the last row is skipped due space limit). First row: box plot of valuations returned by the three criteria. We always consider the predicted probability of the ground truth label. "True" means the samples with positive ground truth label and "False" means with the negative ground truth label. Second and third rows: Average ranking of the
12 features. Colored texts denote different rankings among the three criteria.
Age
Fabse
Fatse
Fatoe
Education Num
Workclass
True
True
True
Feature Name
Marital Status
Occupation
Relationshlp
Race
Sex
Capital Gain
Capital Loss
Hours per week
Country
2
-0.2
-0.1
0.0
0.1
0.2
0.3
-0,2
-0.1
0.0
0.1
0.2
0.3
Varlational Index
Shapley Value
Banzhaf Value
GT Labels: True
11
12
Var. Index
Capial Gaiz
Stesa
Education Nar
Age
Hours per week
Occupation
Capuaa Loss
Sex
Country
Race
Workelass
Shupley
Cipial Gait
Nan
Muital Steas
Relationdh
Age
Hours per
Occupation
Capii
County
Workdass
Banzhaf
Opiaal Guin
Elaation Nun
Mortel Strre
Rebeiunehip
Age
Huun per work
Oasupation
Sex
Cipial
Loss
Race
Country
Workdaoc
GT Labels: False
2
4
5
10
11
12
Var. Index
Capital Gain, Rehsiendip
Rduceion- Nam
Copkal
Age
Marial State
Bours per week
Sex
Occupation Cuunty
Workelas
Race
Shapley
Caphal Gain, Webstandep
Ditaatio Nare
Ciptal Loss
Martal State
Age
Hours per week
Sex
Occupation
Wockelass
Countr
Race
Ranzhaf
Caphal Gain Rehaicudds
Maciaal Suaus
Educotion
Aae
Bours per week
Occupation
Wookklass
Country
Race
Figure 9: Statistics on valuations with the MLP classifier. First row: box plot of valuations returned by the three criteria. We always consider the predicted probability of the ground truth label. "True" means the samples with positive ground truth label and "False" means with the negative ground truth label. Second and third rows: Average ranking of the 12 features. Colored texts denote different rankings among the three criteria.
G.6 EFFECT OF NUMBER OF SAMPLES MCMC SAMPLING
Here we illustrate the accuracy sampling tradeoff when estimating the gradient of multilinear ex- tension using MCMC sampling. The results shown in Fig. 11. One can observe that with more samples, Alg. I will converge faster (in fewer number of epochs).
22

---

Published as a conference paper at ICLR 2022
Age
Fatso
Fa
Fa
Feature Naiee
Education-Num
Woskclass
Status
True
Trae
True
Occupation
Relationship
Race-
Sex
Capital Gain
Capital Loss
Hours week
Country
-0.2
0.0
0.2
-0.2
0.0
0.2
Variational Index
Shapley Value
Value
GT Labels:
Var. Index
Edhration
Hoars
Capiual
Warkelass
Shapley
Education
Nan
Captal Caan
Rehttmmii
Houss per
week
Matual Stms
Age
Sex
Occopatins
Race
Captad Loss
Countyy
Warkdass
Banzhaf
Fahration-
Relttinnii
Hears
Age
Sex
Occipotion
Race
Capial
Counry
Workdass
Labels: False
10
Index
Rebeiondhip Capkal
Edactton Nam
Lastal
Ago
Hours ger
Somt
Workebes
Raen
Ormpation
County
Shupley
Relatsmshiip Lupeal
Capial
Lona
Hours Marial
Workches
Banzhaf
Rehaismship Capesl Liee
Esuasios
Nam
Capita Lowe
Age
Hours work
Marial Statn
Sex
Workehaes
Occopation
Rase
County
Figure 10: Statistics valuations with the logistic regression classifier. First row: box plot of valuations returned by the three criteria. We always consider the predicted probability the ground truth label. "True" means the samples with positive ground truth label and "False" means with the negative ground truth label. Second and Third rows: Average ranking of the 12 features. Colored texts denote different rankings among the three criteria.
Table 2: Indices of the top 15 ranked players returned by different methods.
Rank of players
2
3
6
7
8
9
10
11
12
14
15
Variational Index
9
13
11
54
7
18
36
32
42
46
40
18
23
Banzhaf value
9
13
11
54
18
7
32
46
36
2
27
40
10
Shaplay Value
52
33
27
4
58
32
14
42
46
40
6
18
23
47
0.0035
-+-
10n
Stunetie Diffrurce
0.0025
0.0020
0.0010
0.0005
10
Figure 11: Stepwise difference with difference number of samples when estimating the gradient of multilincar extension using MCMC sampling. The three curves: m = n, m = 5n, m 10n.
23


Reviews:
[{"review_id": "J6zOmJXcwuh", "reviewer": "Reviewer_LgG5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "P. S. I'm somewhat of an outsider to this topic, with minimal familiarity with cooperative games. \n\nPros:\n- I find the observation that classical criteria such as Shapely value can be seen as one-step \"decoupling\" approximation to the maximum entropy probabilistic assignment to be quite interesting. In hindsight this seems like a natural connection, although I'm not sure if an expert on this topic would be equally excited about this result.\n- The multi-step approximation criterion that the authors propose also seems like a natural extension to existing game-theoretic criteria\n\nCons:\n- I don't find the experimental results to be compelling. They do not convincingly demonstrate that the proposed new criterion has some additional value over existing criteria for ML applications. I understand that the authors have chosen to make the mean-field perspective the central focus of the paper, but I think its important to also have a strong empirical section showcasing utility to an ML audience. \n- The feature selection experiments in Sec 5.2 show some improvements over two classical game-theoretic criteria, but the field of subset selection is now quite mature (e.g. https://arxiv.org/pdf/2006.15412.pdf), and comparing to just the two closest game-theoretic criteria doesn't seem to make a strong empirical case. \n- The new criterion comes with the added cost of Monte Carlo sampling to approximate exponential sums over multiple rounds, but I'm not entirely sure if the experiments justify this added cost needed.\n- The writing is accessible, but can be improved to better motivate the subset/feature selection applications, especially for an ML audience, and provide more elaborate intuition early on for the \"decoupling\" approximations that the classical criteria seek to compute.\n\nOther comments/questions:\n- Alg 1: You refer to this algorithm as performing gradient ascent. To me it appears more like a fixed point iteration algorithm, and not necessarily performing a gradient-based ascent step on the ELBO objective. Please correct me if I'm missing something here.\n- Sec 5: Might be good to mention how the decoupling error is computed in all your experiments, given that it requires calculating (an approximation of) the Boltzmann distribution.\n- Sec 5.1: I didn't quite understand the role of the data clustering in the experiment. On the x-axis in Fig 1, do you add clusters of data points instead of individual data points?\n- Sec 5.2: In Fig 2, you plot the predicted probabilities as you drop features. Is this the average probability predicted by the model across all test examples? Might be good to elaborate why this is a good evaluation metric to look at.\n- Sec 1/Intro: I think your mention of a solution concept \\phi(F) needs elaboration for audience not necessarily familiar with cooperative games. Similarly, in Sec 2, it wasn't initially clear to me how the importance weights you write out in (2) and (3) relate to the solution concept \\phi(F).", "summary_of_the_paper": "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.  \n\nThe 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.\n\n", "summary_of_the_review": "The paper presents some interesting theoretical connections, but does not provide sufficiently compelling empirical results showcasing utility for applications in ML.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ib38zxUlvEt", "reviewer": "Reviewer_28es", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The energy-based perspective is, to my knowledge, a novel perspective for Shapley values and player valuation in ML, and I found it quite cool to see these tools (EBMs, mean-field VI) applied in this way. The variational index is an interesting and it appears to perform well in the experiments relative to Shapley/Banzhaf values.\n\nI have a couple questions/comments that I hope the authors will consider for improving the paper.\n\n**Premise of EBMs for cooperative games.** The idea of using EBMs to analyze cooperative games was a bit confusing and could probably be introduced better. To be specific, the paper starts by saying we should learn a probability distribution over coalitions, but this does not begin to sound like a worthwhile endeavor until several sections in. When we're using Shapley/Banzhaf values, we control the distribution over coalitions/orderings, so learning a distribution sounds (at least initially) like a somewhat pointless idea. Similarly, the idea of finding an entropy-maximizing coalition distribution (constrained to a mean value, which it's not clear how to choose!) does not initially sound useful. Of course it's not pointless, but what ultimately connects these EBM ideas to player valuation is the crucial step of doing mean-field VI. Because of the important role mean-field VI plays here, I wonder if it doesn't deserve a bit more attention and emphasis.\n\nAppendix A attempts to explain this a bit more, but I didn't find these reasons compelling (particularly the second paragraph). Unless I'm missing something, the real reason to use EBMs + mean-field VI is that it enables us to learn a factorized distribution over players that places higher probabilities on players that contribute more value, and this gives us a new perspective for defining player valuations, which happens to connect to existing ideas like Shapley/Banzhaf/probabilistic values.\n\n**Connection with multilinear extensions.** The idea of learning a factorized distribution over players is most similar to the idea of multilinear extensions in cooperative game theory (as in Okhrati and Lipani). In that work, Shapley values are defined as the expected marginal contribution where the preceding coalition is determined by a factorized distribution over players (integrated over a probability value); here, the probabilities of the factorized distribution are learned, but they can still coincide with Shapley values. I wonder if the authors can provide any more commentary on the implicit connection between these ideas, where the probabilities in a factorized distribution can induce player valuations vs. act as player valuations.\n\n**Cooperative game theory in ML.** The paper gives a nice overview of the use of Shapley values in ML, including uses in feature-based explanations, data valuation, and model ensemble valuation. However, a couple key papers are perhaps overlooked and could be cited: Lipovetski & Conklin (2001) and Strumbelj & Kononenko (2010) were some of the first papers to analyze statistical models using Shapley values, and Covert et al. (2020) (already cited) also provides an overview of other papers that use Shapley values, including SPVIM, SAGE and Shapley Effects, and it shows that many other ML explanation methods are also tied to cooperative game theory.\n\n**Entropy gradient.** In section 4.2, the gradient $\\nabla_i H(q) = \\log \\frac{1 - x_i}{x_i}$ is given but the result is not derived. It could be helpful to provide a derivation in the appendix because this result seems non-trivial, and it is important for the subsequent gradient descent routine.\n\n**Gradient descent derivation.** The update rule in algorithm 1 does not immediately look like gradient descent, and I expect it will be confusing to many readers. Where, for example, is the learning rate? I tried to derive this result and if I understand correctly, it comes from taking a gradient step on $\\sigma^{-1}(x_i)$ and then applying the sigmoid operation to get $x_i^+$, where the learning rate is chosen as a function of the current value $x_i$. I'm not sure if that's right or if there's a simpler explanation, but there is too much work left to the reader here.\n\n**Practical impact.** I found the ideas in this work very interesting and will view the paper favorably regardless of the answer to this question, but I just wanted to clarify the practical impact. Am I correct in understanding that this energy-based approach does not necessarily offer a more efficient algorithm to calculating Shapley/Banzhaf values? Is the main practical impact, then, proposing the variational index as an alternative to Shapley/Banzhaf values for valuation problems?\n\n**Applying existing Shapley value approximations to the variational index.** In section 3, it's stated that existing Shapley value estimation ideas can be applied directly (\"can be seamlessly lifted\") to calculating the variational index. That point didn't come up later in the paper and I don't see how that is the case. How, for example, could we use a permutation-based or weighted least squares-based Shapley value estimator to calculate the variational index? Or how could we use a model-specific Shapley value approximation like TreeSHAP? How could these things be integrated into algorithm 1, or be adapted into different routines for optimizing the KL divergence? I don't get this, some clarification on this point would be helpful.\n\n**Role of temperature.** It might be worth noting explicitly for eqs. 14-15 that the specific temperature value does not matter, and that it does not matter for any single-step update; currently, the reader must figure this out for themselves. Aside from that, it's a bit unsatisfactory that different temperatures yield different variational indices, and that we don't know much about the properties of the different solutions, but I suppose it's fine to leave further investigation to future work. It could also be nice to have either a footnote or brief appendix section showing why $T = 0$ and $T \\to \\infty$ induce even spread and 0/1 probabilities, respectively, as this is also currently left to the reader.\n\n**Role of initializer.** In section 4.2, there's a brief section discussing the initializer's role w.r.t. variational values. It seems mostly right, but I'm confused by the claim that the initializer doesn't matter if you plan on running GD to convergence. How can that be, given that the problem is non-convex (stated earlier in the paper)? These seem like contradictory ideas, please clarify if possible.\n\n**Additivity and efficiency properties.** In section 4.4, there's a paragraph discussing why variational values don't satisfy the additivity and efficiency properties satisfied by Shapley values. I found this paragraph a bit odd: in addressing this \"why\" question, your explanation addresses why they *shouldn't* (reasons why these properties might be unappealing), as if you had some choice in the matter, rather than the mathematical/mechanistic reasons why they don't. I would ask that you adjust this paragraph to clarify whether you're explaining i) why those properties aren't satisfied or ii) why it's okay that they're not satisfied.\n\nA couple things about the experiments:\n\n- In section 5.3 where we look at the convergence of algorithm 1, we can clearly see that it converges. But does it converge to the same point regardless of the initialization? This may be worth looking into due the problem's non-convexity.\n- Is it worth looking into whether algorithm 1 can yield efficient, low-variance Shapley/Banzhaf value estimates relative to existing estimators? Do you have any intuition about how the variance might compare for a fixed number of game evaluations?\n\nThere were a couple specific phrases that I thought could be improved:\n\n- The introduction says that you explore a \"probabilistic treatment\" of games. That's true, but it's not very specific because cooperative game formulations are sometimes probabilistic, there's work considering stochastic cooperative games, and Shapley/Banzhaf values have probabilistic formulations. It might be better to say that you propose learning a factorized distribution over players to arrive at player valuations, because that's what's unique here. The same paragraph says something like this later, but it leaves out the bit about learning a factorized surrogate distribution and the fact that the original distribution is encouraged to put more mass on players that contribute more value.\n- Also in the introduction, you state that you \"conduct learning and uncertainty analysis in a unified Bayesian manner.\" I'm not sure this is correct, your method of course does VI, but not uncertainty analysis or Bayesian inference (where's the prior, what's the data?).", "summary_of_the_paper": "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:\n\n- 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$\n- 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\n- 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\n- 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$\n- The authors define the \"variational index\" as a function of the solution to the KL divergence minimization problem: $s^* = T\\sigma^{-1}(x^*)$\n- 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)\n- 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$\n\nThe 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.", "summary_of_the_review": "This paper introduces some very interesting ideas about the use of EBMs and mean-field VI in the context of player valuation for cooperative games. Their new perspective is connected to Shapley/Banzhaf/probabilistic values, it permits approximate optimization (the gradients require sampling), and they define a new value (the variational index) that performs quite well in their experiments.\n\nI had a couple questions and comments about the writing, but I expect these will be easy to address.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Fahtqdh7ZKC", "reviewer": "Reviewer_Jn7f", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Regarding strengths, to the best of my knowledge the proposed valuation of the framework is novel. It is well motivated and the connections with existing classical methods are very interesting. It also opens the door for further extensions as different surrogate models or application specific priors can be easily incorporated. While it is hard to argue (both in theory and in practice) that one valuation method is better than the alternatives, the empirical results seem to be reasonable. I believe that this paper can have significant impact in the area in the immediate future.\n\nRegarding weaknesses, the paper could be improved in terms of approachability to practitioners. Firstly, reporting the run times of the experiments and/or the accuracy-time trade-offs for MCMC methods would be useful for practitioners. Additionally, any advice on how users should interpret the absolute scores of the Variational Index (especially since $T$ affects their scaling) could be useful. This is especially true for cases where the rankings of different valuation methods are similar but the absolute scores are not. Moreover, the paragraph on why additivity or efficiency does not make sense for some games is very important for practitioners to understand. Practitioners may be easily tricked into thinking that the more properties a valuation measure satisfies the better regardless of the game they try to understand. Right now the paragraph is a bit dense and hard to follow for audiences not familiar with prior work on axiomatization of valuations in cooperative games. Toy numerical examples to demonstrate why additivity or efficiency can result in unintuitive/not-useful valuations could also help practitioners grasp what is the problem.\n\nThese weaknesses are minor so I am in favor of accepting this work. I have read the responses of the authors. I find that these additions are going to improve the paper. I thus maintain my score.", "summary_of_the_paper": "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.", "summary_of_the_review": "A well written and novel work on a variational framework for player valuations in cooperative games. While approachability to practitioners could be improved, I am in favor of accepting this work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "D00PG334eKf", "reviewer": "Reviewer_5RYD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The authors show that one can derive the Shapley value and Banzhaf index using one step of gradient ascent using specific initializations. I think it’s nice that these two criteria can be unified under this model.\n- The paper seemed polished and was easy to read.\n\nWeaknesses:\n- I think that the main way this paper could be improved is that I couldn’t quite understand the benefit of this approach to defining the importance scores over classic approaches like the Shapley value and the Banzhaf index. It’s not any easier to compute and at least according to what’s written in the paper thus far, it doesn’t seem to satisfy any additional game-theoretic axioms than the Shapley value or Banzhaf index. Lastly, in the experiments, it seems to perform about as well as these other two indices; the experiments don’t seem illustrate its superiority as decisively as one might hope.\n- There are a few ways that the model choices could be further justified. The paper is really built around the specific choice $p$ of the distribution over coalitions, which is justified in a few sentences in the third paragraph of the introduction. However, since the reader really has to buy in to this choice of $p$ to appreciate the rest of the paper, I think that a bit more justification would be useful. One other thing I couldn’t quite follow is why the importance score ends up being defined in terms of the inverse sigma functions.\n\nSmaller comments:\n- 3rd paragraph of Section 1: How is mu chosen? Why doesn’t it show up in Equation (1)?\n- 4th paragraph of Section 1: At first, I was confused about what the “valuation problem” is. Then I realized it’s the problem of defining the importance vector; it would be helpful to clarify this.\n- Last paragraph of Section 1: I have a few suggestions:\n   - I didn’t know what was meant by a “decoupling perspective” until I got to Section 4, so I wasn’t able to understand this sentence.\n   - “Intriguing properties” is a bit too vague, in my opinion. After reading Section 5, I’m not really sure what these intriguing properties would be, so it would definitely help to spell these out.\n", "summary_of_the_paper": "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.\n\nThe 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.\n\nIn 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.", "summary_of_the_review": "Overall, I think that this paper was nicely written and I like that it unifies the Shapley value and Banzhaf index, but I don’t yet see why the proposed approach is necessarily better than using either of these two existing criteria, so I’m leaning towards rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the valuation problem for a cooperative game, and shows that some classical metrics (e.g. Shapley value), can be considered as approximations to the maximum entropy.

Reviewers were generally very positive. They especially praised the novelty and writing quality, while having some concerns about the quality of the empirical results. The authors did an excellent job responding to the reviewers, and resolved their main concerns. A few quibbles remain, however, and while the manuscript is very good as-is, please consider the reviewer criticisms in creating an updated version.
Decision: Accept (Poster)