Neural Payoff Machines: Predicting Fair and Stable Payoff Allocations Among Team Members
Authors: Daphne Cornelisse
Thomas Rood
Yoram Bachrach
Mateusz Malinowski
Tal Kachman
Venue: NeurIPS 2022 Accept (2022)
Keywords: Cooperative games theory
Coalitional games
Shapley values
Bahnhof power index
The Core

Abstract: In many multi-agent settings, participants can form teams to achieve collective outcomes that may far surpass their individual capabilities. Measuring the relative contributions of agents and allocating them shares of the reward that promote long-lasting cooperation are difficult tasks. Cooperative game theory offers solution concepts identifying distribution schemes, such as the Shapley value, that fairly reflect the contribution of individuals to the performance of the team or the Core, which reduces the incentive of agents to abandon their team. Applications of such methods include identifying influential features and sharing the costs of joint ventures or team formation. Unfortunately, using these solutions requires tackling a computational barrier as they are hard to compute, even in restricted settings. In this work, we show how cooperative game-theoretic solutions can be distilled into a learned model by training neural networks to propose fair and stable payoff allocations. We show that our approach creates models that can generalize to games far from the training distribution and can predict solutions for more players than observed during training. An important application of our framework is Explainable AI: our approach can be used to speed-up Shapley value computations on many instances.

Neural Payoff Machines: Predicting Fair and Stable Payoff Allocations Among Team Members
Daphne Cornelisse'
Thomas Rood
Mateusz Malinowski Tal Kachman 1.2x
Yoram Bachrach 3
Department of Artificial Intelligence, Radboud University, Netherlands Donders Institute for Brain, Cognition and Behavior, Radboud University, Netherlands 3 DeepMindd UK
Abstract
In many multi-agent settings, participants form teams to achieve collective outcomes that may far surpass their individual capabilities. Mcasuring the rela- tive contributions of agents and allocating them shares of the reward that promote long-lasting cooperation are difficult tasks. Cooperative game theory offers so- lution concepts identifying distribution schemes, such the Shapley value, that fairly reflect the contribution individuals to the performance of the team or the Core, which reduces the incentive of agents to abandon their team. Applications of such methods include identifying influential features and sharing the costs of joint ventures or team formation. Unfortunately, using these solutions requires tackling a computational barrier as they are hard to compute, even in restricted settings. In this work, we show how cooperative game- game-theoretic solutions can be distilled into a learned model by training neural networks to propose fair and stable pay- off allocations. We show that our approach creates models that can generalize games far from the training distribution and can predict solutions for more players than observed during training. An important application of our framework is Ex- plainable AI: our approach can be used to speed-up Shapley value computations on many instances.
1 Introduction
The ability of individuals to form teams and collaborate is crucial to their performance in many vironments. The success humans as a species hinges on our capability to cooperate at scale (23]. Similarly, cooperation between learning agents is necessary to achieve high performance in many
environments [28] 7 45 24 and is a fundamental problem artificial intelligence [42 12]. Indi-
vidual agents often not incentivized by the joint reward achieved by team but rather by their share of the spoils. Hence, teams are only likely to be formed when the overall gains obtained by the team are appropriately distributed between its members. However, understanding how collective outcomes arise from subsets of locally interacting parts, or measuring the impact of individuals on the team's performance, remain open problems.
Direct applications exist in multiple domains. One example is identifying the most influential fea- tures that drive model to make certain prediction 44 29 6 27 26); one of the comnestonnss of explainable AI 2 34). Another example is sharing the costs of data acquisition or joint venture
in fair way between participants [8] D. or sharing gains between cooperating agents (20 41). In many legislative bodies individual participants have different weights, and passing a decision re- quires support from a of participants holding the majority of the weight; different states in the US electoral college have different numbers of electors, and different countries in the EU Council
"Conrepondencee to tal. kachman @ @donders.ru.nl
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of Ministers vary in their voting weight. Here, would like to quantify the true political power held by each participant, or allocate common budget between them [2 10.
Cooperative game theory can provide strong theoretical foundations underpinning such applications. The field provides solution concepts that measure the relative impact of individuals on team perfor- mance, or the individual rewards agents are entitled to. Power indices such as the Shapley value [40] or Banzhaf index [9] attempt to divide the joint reward in a way that is fair, and have recently been used to compute feature importance [29]. In contrast, other solutions such the Core (22 attempt to offer a stable allocation payoffs, where individual agents are incentivised to continue working with their team, rather than attempting to break away from their team in favor of working with other agents. Despite their theoretical appeal, these solution concepts are difficult to apply in practice due computational constraints. Computing them is typically hard problem, even in restricted environments 18
Our contribution: We construct models that predict fair stable payoff' allocations among team members, combining solution concepts from cooperative game theory with the predictive power of neural networks. These neural "payoff machines" take representation of the performance or reward achievable by different subsets of agents, and output suggested payoff vector allocating the total reward between the agents. By training the neural networks based on different cooperative solution concepts, the model can be tuned to aim for fair distribution of the payoffs (the Shapley value or Banzhaf index) or to minimize the incentives of agents abandon the team (the Least- Core [22] 33 15). Figure | depicts the two well-studied classes of games which we evaluate our approach: weighted voting games
10
and feature importance games in explainable
AI [4 29
X
tooms
date
yyar
Figure 1: Evaluation domains for our approach. Left: Weighted voting games (WVGs) model de- cision making bodies such as the US Electoral College [3] Right: Applying the Shapley value in Feature Importance Games enables quantifying the relative impact of features on the decisions of a model. In this example, model predicts the price of a house based on several features.
Weighted voting games (WVGs) are arguably the most well-studied class of cooperative games. Each agent is endowed with a weight and a team achieves its goal if the sum of the weights of the team members exceeds certain threshold (quota). We train the neural networks by generating large sets of such games and computing their respective game theoretic solutions. Our empirical evaluation shows that the predictions for the various solutions (the Shapley value, Banzhaf index and Least-Core) accurately reflect the true game theoretic solutions on previously unobserved games. Furthermore, the resulting model can generalize even games that are very far from the training distribution or with more players than the games in the training set.
Feature importance games are a model for quantifying the relative influence of features on the out- come of machine learning model [4 29 Solving these games for the Shapley value (or any other game theoretic measure) provides way reverse-engineer the key factors that drove a model to reach a specific decision. This approach is model-agnostic, thus can be applied to make any "black- box" model more interpretable (2]. One drawback of this approach is the computational complexity of calculating the Shapley value, making such analysis slow even when using approximation algo- rithms. Our approach provides way to significantly speedup Explainable Al analyses, particularly for datasets with large number of instances.
2

---

2
Preliminaries
We provide a brief overview of cooperative game theory (examined in various books [7 11 and briefly discuss how solution concepts in cooperative game theory have been applied in Explainable AI
[4
29
30
13 47..
2.1 Cooperative Game Theory
A (transferable utility) cooperative game consists of a set N = 21, and characteristic function v 2 + R which maps each team of players, coalition C' S N, to a real number. This number indicates the joint reward the players obtained as a team. Games v where v 2 {0,1] (binary range) are simple games.
,n) } of agents, or players,
Weighted voting games (WVGs) are a restricted class of simple cooperative games [.I. where each agent i has a weight w; and a team of agents C C N wins if the sum of the weights of its participants Σ(= W; exceeds quota q. Formally, WVG is defined as the triple (w,g,0 q, u) with weights w = (W1, W2, ................................ Wn) E R2g0 and quota (threshold) E Rzo where for any C S N we have v(C) = if > W; 2 q and otherwise (CC) = O. If ((C)) = 0 we say C' is a losing coalition, and if (CC = we say it is a winning coalitions. WVGs have been thoroughly investigated model of voting bodies, such the US Electoral College or the EU Council of Ministers [3 T0].
The characteristic function defines the joint value of a coalition, but it does not specify how the value should be distributed among the agents. Solution concepts attempt to determine allocation p (pi..... Pn.) of the utility v(N) achieved by the grand coalition of all the agents; an allocation p is called an imputation if for any player we have p; 2 0 and E - P;- = v(N) P This allocation is meant to achieve some desiderata, such as fairly reflecting the contributions of individual agents, or achieving stability in the sense that no subset of agents is incentivized abandon the team and form a new team. We describe three prominent solution concepts that we use in our analysis.
The Core. Rational players may abandon the grand coalition of all the agents if they can increase their individual utility by doing so. The Core is defined as the set of all payoff vectors where no subset of agents can generate more utility, as measured by the characteristic function, than the total payoff they are currently awarded by the payoff vector. As such, the Core is viewed as the set of stable payoff allocations. Formally, the core [22] is defined as the set of all imputations p such that Ei=P; P: = v(N) and that Σiec 2 v(C) for any coalition C' C N.
The s-Core and Least-Core 33 15 Some games have empty cores, meaning that payoff allocations achieves full stability (i.e. for any imputation p there exists at least one coalition such that v(C) > Eiec Pt). In such cases, researchers have proposed minimizing the instability. A relaxation of the core is the E-core, consisting of imputations p where for any value coalition we have p(C) 2 v(C)) E. Given imputation p the difference v(C)- Ei Pa is called the excess of the coalition, and represents the total improvement in utility the members of C' can achieve by abandoning the grand coalition and working on their own. For imputation in the E-core, no agent subset C' can achieve an addition of E in utility over the current total payoff offered to the team (i.e. no coalition has an excess of more than e). The minimal E for which the E-core is non-empty is called the Least-Cor Value (LCV). The Least-Core minimizes the incentive of any agent subset to abandon the grand coalition, and the LCV thus represents the degree of instability (excess) under the imputation that best minimizes this instability. We find the set of payoffs associated with the LVC through linear programming (full details in Appendix ??).
We now discuss two power indices, payoff distributions reflecting the true influence a player has on the performance of the team, that fairly allocate the total gains of the teams among the agents in it.
measures the average marginal contribution of each player across all permutations of the players. The Shapley value is the unique solution concept that fulfills several natural fairness axioms [16]. and has thus found many applications from estimating feature impor- tance [4 29 to pruning neural networks [46. 19 21]. Formally, we denote permutation of the players by _ where π is a bijective mapping of N' to itself, and the set of all such permutations by II. By C= we denote all players appearing before i in the permutation æ. The Shapley value
The Shapley Value
40
Pnn WVG, the value of a coalition is bounded by 1. so if the grand coalition N indeed has a value of <(N)= = 1 then solution would be a payoff vector p (pi.... Po)) where D Pi = L.
3

---

(G) of player i is defined as:
(, 1 N!
Σ mEl
(2.1)
Intuitively, one can consider starting with an empty coalition and adding the players' weights in the order of the permutation; the first player whose addition meets or exceeds the quota is considered the pivotal player in the permutation. The Shapley value then measures the proportion of permutations where a player is the pivotal player.
The Banzhaf index [9] is another method for distributing payoffs according to a players' ability to change the outcome of the game, but it reflects slightly different faimess axioms [3] The Banzhaf index 3, of player is defined as the marginal contribution of player across all subsets not containing that player:
B(G 2N-1
Σ (EM(()
[o(C U (()) - x(C)
(2.2)
In practice, we first compute the set of winning coalitions Crwin C C' and count, for each player, the number of times it is critical or pivotal, that is, v((C))))=0 =..
2.2 Speeding Up Explainable AI In Large Datasets
important application of our work to speedup Shapley/core computations of many data in- stances. In machine learning, we train a model fe to learn a mapping from some set of input features to an outcome. For instance, we can train a model to predict the price of a house based on several features, such as the number of rooms, the year it was built, and so on. In such settings, it is desirable, but challenging, to explain the model outputs terms of the input features. Explainable Al addresses this issue, and recent years showed several applications of game theoretic metrics for measuring feature importance in the machine learning community [44] 2].
The fastest method to approximate Shapley values (also used in the SHAP package) is a Monte- Carlo approach 29 A number of other methods exist whose runtime and accuracy depend on the number of samples used, usually on the order of several thousands 255 14 31 5). In a model setting, the characteristic function takes the value of the trained model output for given instance: fo- (x). The Shapley value of feature in data instance x, Φz.; is the effect that feature has on the model outcome. Sampling based-methods compute the contributions with respect to a base value, which is the average model output across all instances:
So (1) ElSo- (x:)
(2.3)
While effective for obtaining Shapley values of a small set of instances, sampling based methods are not ideal for large datasets because they require large number of re-evaluation samples per com- putation. We show how our approach can be employed to speedup Shapley or Core computations of many instances through models that learn representations of feature attribution schemes.
3 Methods
Our approach uses machine learning to create theorthe estimators. We generate synthetic datasets of games train our models, spending compute up-front to allow for instant solutions afterwards. Our first domain concerns weighted voting games (WVGs) as they provide a generic framework for studying cooperation in multi-agent settings.
Afterwards, we apply our approach to the Shapley-based feature importance setting. The main idea that we can speed-up -up the computations of the relative impact of features on the predictions of machine learning model. We do this by training models to approximate Shapley values of features, and examine their performance on previously unobserved instances.
3.1 Weighted Voting Games
We construct two types of foed-forward neural networks. Fixed-size models are trained on games of a specific number of players. The second type of model can take and predict payoff's for a varying number of players. We refer to these as variable-size models. What follows is a formal description of the data and architectures for both models. We now describe our data generation process, models, training procedure, and evaluation metrics used in weighted voting games.

---

3.1.1 Data and Models: Fixed-Size
For each player game, we generate G independent and identically distributed games. The train- ing dataset is given by Di {X E Rx P E IR [G where K denotes the number of out- puts of interest. Figure depicts the pipeline for generating one data instance. First, we sam- ple weight vector w Beta(a = 1,3 = 1) on the interval from I to 2n, and a quota q ~WW (2n + 1),, o² 2n). To create games where players are dependent on each other to achieve the task at hand, the quota distribution is parameterized such that the average drawn quota half of the sum of the players' weights. We then divide the weights by the quota to get the feature vector = _ w. In other words, we have features which are the weights normalized as the respective proportion of the quota. Thus, value > indicates that player i is winning coalition by itself, and needs other players to meet the quota otherwise.
Sample quota q ER
Get winning coalitions
Compute solution
[coats] Σ 2
allocate(w..) C
(x,p)
Pg
Pw
Sample weights
Nomalize
Pp(C) E
w/q
Figure 2: Procedurally generating and solving one weighted voting game. We obtain weighted voting game by sampling n weights and quota. The weights are divided by the quota to create the inputs We solve the game for each considered solution concept create our targets p.
We train models predict the three solutions: the Least-Core, the Shapley values, and the Banzhaf indices. For the Shapey values and the Banzhaf indices, the model predicts the payoff' allocation (PI....,P,, Pr) so K n. For the Least-Core solution, we train the model to not only predict the payoff allocation P Pn. but also to predict the least core Value Emin (so in this case the model has K = are the model parameters. We use deep feedforward networks for fa. Appendix ?? contains the full details about the experimental setup.
outputs). For each n player game, we produce model fo R R where
3.1.2 Data and Models:
Variable-size
For the variable-size case, we consider maximal number of possible players M and pad the inputs with zeros for games with less than M players. Hence, we generate a single dataset Dear = (X E RR P E RG Similarly to the fixed-size dataset, the feature matrix X con- tains the normalized weights and the corresponding solutions with either = M I or K = M, with the ground truth output vector again padded with zeros when there are fewer than M players. Hence, we allow for the prediction of up to M players, and we shuffle the data so that players are located at random positions. The least core Value (LCV) is not shuffled but stored the last element of each row.
We produce a single model On RRD R that can be used for different number of players n, where 77 are the model parameters. The model learns to allocate the joint payoff among at most M players. During prediction time we pad the input with zeros when there are fewer than Al players, and we redistribute the payoffs allocated to non-player entries among the players according to their original share of the joint payoff. Figure graphically depicts the padding procedure and basic model architecture.
3.1.3 Training and Evaluation
During training we minimize the Mean square error (MSE) between the true and predicted solutions. For the variable-size models we also include the M padded locations so that the model learns not allocate value non-player entries.
Evaluation metrics. Given a predicted payoff vector P = (2i,p2...... Pn.), we consider multiple metrics for assessing the models' performance. First, we quantify the models' predictive perfor- mance via the Mean absolute error (MAE), defined for each game as MAE -E lps - 2.1.
where n is the number of players. For the Least-Core there is another natural game theoretic metric.
5

---

Indices
Least
pover indee
Outsd pnyoils
Oigetimness
Imputs
Softmax
Sofrnax
Bignold
Betore gorenaiing ng trmmy dalani, offcce predect wiudions Than of
Linoar
Uiner
(0, 0) O....
snights
PadLU
PeLLU
Mi
Iiy D
Food Forward
Feed Forward
The pasdiigg slowe in paodic sok done to
skayers
Piuddled inputs
Padided iepurs
Figure 3: Neural architectures for the variable-size game predictions. We add zero-padding to allow one model to predict solutions of games of variable sizes. We choose a maximum length M 20, and add zero-padus sero-padding to games with less than M players. Full details on our data in Section 3.1.2
The goal of the Least-Cort is minimize the incentives of any subset abandon the current team and form its own sub-team. Given suggested payoff vector p. the maximal excess v(C) Eiec P; over all possible coalitions C measures the incentive to abandon the team, and serves as a good measure for the quality of the model.
Test data. We sample weights w ~ Beta(a, 33) with varying parameters for a and / to assess our models' ability generalize to previously unobserved instances their ability generalize to games far outside of the training distribution (full details in Table ??, Figure ??).
3.2 Feature Importance Games
We perform an experiment to show that neural networks can provide a faster alternative for measur- ing feature importance scale. We select dataset (details in Appendix ??), train model, and use those to construct a dataset from features to Shapley values using the SHAP KernelExplainer [29] Following, partition our dataset into train and test, and incrementally change the proportions between the two. For each increment, we train a model for 100 epochs and test it on the remainder of the unseen instances.
Results
We present experimental results that allow us assess how well neural models are able learn a representation of the various solution concepts. We first describe the predictive performance of neural networks in the WVG setting. and consider properties of these solutions that make them hard to learn. We then consider the explainable AI domain, and study the performance and sample complexity of Shapley feature importance prediction.
4.1 Weighted Voting Games: Evaluation
For our WVG analysis train selection of fixed-size neural networks f for each number of players 54 19, 2 G 5. 000 games each. We also train single variable-size model 9n- that trained on one dataset containing G = 17, 500 games in total, consisting of 2, 500 games for each number of players n (4, ... 9, 10) games. The data is padded with zeros to allow for payoff allocation up to M 20 players (see details in Section 3.1)
4.1.1 Predictive performance
Table shows that the ability to handle games of variable numbers of players comes at the cost of having lower accuracy. However, even for variable-size models, and even under significant distribution shift, the errors in predicting all solution concepts are low. We further note that the error in predicting Least-Core based payoffs are generally larger than for the Shapley and Banzhaf
A direct computation of Shapley value requires enumerating through a large of permutations, which becomes computationally very costly when there are many players. Hence, for games with n 9 players or more, we use Monte-Carde Carlo approximations for the Shapley value to obtain the ground ground-truth solution. See full details in Appendix ??)

---

power indices. One possible reason is that for these solutions. there are many cases where a small
perturbation in the weights or quota results in a large perturbation of the Least- Core solution 48
Table 1: Comparison of predictive performance across test datasets and solution concepts.
least core payoffs
least core excess
Shapley values
Banzhaf indices
Dataset
Mcan MAE
MAE
Mean MAE
Mean MAE
Fixed
Variable
Fixed
Variable
Fixed
Variable
Fixed
Variable
In-sample
0.030
0.043
0.015
0.034
0.019
0.022
0.018
0.028
Out-of-sample
0.030
0.044
0.015
0.027
0.018
0.036
0.018
0.056
Slightly out-of-distribution
0.029
0.028
0.015
0.050
0.018
0.019
0.017
0.018
Moderately ousto--distribution
0.030
0.035
0.014
0.029
0.018
0.026
0.018
0.032
Significantly of-iiiiiitibttionn
0.031
0.045
0.014
0.036
0.018
0.029
0.018
0.039
We now highlight several conclusions from our analysis of the results.
Fixed-size models display stable performance across solution concepts. Our first observation is that the fixed-size neural networks are adept at estimating solutions across the three considered concepts. They outperform standard multinomial regression models by 45 to 95 % across solution concepts (full details Appendix ??). The average error per player ranges from 0.005 to 0.087 (least core), 0.004 to 0.069 (Shapley values) and 0.012 to 0.067 (Banzhaf indices). Table ?? provides a complete summary of our models' in-sample performance.
Fixed-size models are robust to shifts in the weight distribution. As shown in Figure the predictive performance (Mean MAE) of the fixed-size models is consistent across test datasets. To account for the natural decrease in the MAE as N increases, we also display the average payoff per player (L/n). As expected, the error scales approximately with the average payoff per player.
(a) least core
(b) Shapley value
(c) Banzhaf index
Figure 4: Performance fixed-size models. We evaluate the performance on five test sets with 1000 samples per n-player game. Figures show the MAE and 95 % confidence intervals for each solution concept. The black dashed line indicates the average payoff per player as a function of n.
Variable-size models are robust to shifts in the weight distribution. Figure 5 shows that the variable-size models are also able generalize outside the training distribution. Across test sets, we observe a stable performance that decays with the number of players, as is expected. For the least core, we see that there is an abrupt decrease in performance for the excess beyond players.
4224
412
(a) least core
(b) Shapley value
(c) Banzhaf index
Figure 5: Performance variable-size models. We evaluate the performance on five test sets with 1000 samples per n-player game. Figures show the MAE and 95 % confidence intervals for each solution concept. The black dashed line indicates the average payoff per player as a function of n.
7

---

Variable-size models generalize to larger number of players. Our main objective is to inves- tigate how to leverage machine learning to perform scalable value estimation in large multi-agent settings. To test this, we train the variable-size models on games up 10 players, and evaluate on n + 1, + 2, ....... n 10 players (full details in section 3.1.2). Figure 5 demonstrates that there is no significant decrease in performance for games with more than ten players across solution concepts: variable-size models are able to extrapolate beyond the number of players seen during training. This suggests that there is be valuable information in the small player games such that games of larger sizes can be inferred.
Fixed-size models outperform variable-size models. Table | contains the Mean MAES across solution concepts and test sets. Corresponding error distributions are showed in Figure 6 From these, we conclude that in almost all settings the fixed-size networks outperform the variabe-ssize networks. Variable-sized networks tend to have larger errors for all predicted variables and display more variance in their predictions.
Shoule
(a) lcast core
(b) Shapley value
(c) Banzhaf index
Figure 6: Comparing overall performance fixed-size vs. variable-size networks.
4.1.2 Discontinuities in the Solution Space
The function mapping from game parameters to solutions contains discontinuities. Discontinuous jumps emerge from the players' interdependence and the effect of the quota and are difficult for a model to learn. We analyze two examples that demonstrate how our models respond to such transitions.
Solution concepts are step-wise constant functions which are difficult to capture. Consider taking a WVG and changing the weight of player. This only changes the game thcoretic solutions when it restructures the subset of winning coalitions. Thus, the function outputs the same value until the weight reaches certain threshold where the structures of winning coalitions change, which point the solution can change drastically. Learning these kind of functions is difficult, as the error around the discontinuity point is often large.
Our analysis examines an n player game with a fixed weight vector w = (w), ....... wp) and considers an array of quotas q (g), 92,... gk) = (min( w), min(w) + c...., En= w.), where e = 0.1. We solve the game for each combination of the fixed weights and the changing quota in to obtain matrix P. Figure shows the fixed-size model predictions for two selected WVGs. The models capture the overall effect of the changes to the quota, but do poorly close to the discontinuity point (where the ground truth solution incurs a large change).
WNCoA 13.23.4
612
Figure/ 7: Capturing step-wise jumps. Individual actual payoffs (green dots) together with the model predictions (blue triangles) as the value of quota increases by 0.1 increments (full de- scription in Appendix ??).
8

---

4.2 Application: Model-based Approach to Explainable AI
Models speedup XAI analyses by more than 8 times. Various domains involve datasets with a large number of features, sometimes containing thousands millions of data instances. A prominent example is language modelling, where large bodies of text are used to perform machine translation, or generate new text [88. Here, explaining features in terms of the model outcome for every data instance, for example by means of the Shapley value, takes an extremely long time.
Our approach is targeted at speeding up feature importance computations of many instances. We perform a simple experiment to demonstrate the effectiveness of a model-based approach for ex- plaining model decisions. We take the Melbourne Housing dataset [9] and obtain 9000 instances by 13 features after preprocessing steps (encoding the categorical features and standardization). First, we generate a ground-truth dataset by setting the number of samples in the SHAP package (KernelExplainer) to 5000 samples. The number of samples in the KernelEExplanner determines the number of times model is re-evaluated for every prediction. A higher number of samples will sult in more accurate (and lower variance in the) Shapley values, but require longer compute time. Computing the Shapley values on our 9000 samples takes 4.13 hours. Figure 8 (left) shows that the inference time scales approximately linearly with the number of re-evaluation samples.
To contrast the difference in computation time, we compute Shapley values 10 % of the data (computation time is 29 minutes) train the neural network in 30 seconds, and predict Shapley values on the remaining 90% of the data (less than a second). All together, this procedure takes roughly 12 % of the time of it took to compute Shapley values for the entire dataset. This speeds-up the whole procedure by 8x while keeping reasonable prediction quality on the remaining unseen data (Figure 8 rright..
Next, we use SHAP again to compute Shapley values for 90% of the data, 8100 instances, this time with the default number of model re-evaluations samples, yielding slightly accurate Shapley values (the default is 2 x number of features + 2048). We quantify the trade-off in prediction quality as the by comparing the model predicted Shapley values to the Shapley values obtained with the default number of samples.
Concretely, we measure the Mean Mean Absolute Error (MMSE) of our model predictions and the SHAP package the ground-truth dataset. We note that speedup does come at slightly reduced empirical performance: the model MSE on the test set is, MSE = 1.15 x 10-3, compared to the MSE with SHAP: MSE 7.4 x 10-5, However, we expect that hyperparameter tuning and better preprocessing will improve the quality of the model predictions.
SHAP Kernelangtaan inaerninngaainerr number sampels va. time
Speedup of Neural Network Shapley Prediction (Durs) versus SHIAP Keenel Expleiter
Spaaud up wolaaiii OU SHAP OK 6m063)
2000
1750
irternnc time 62)
7-
6+
500
3000
5005
0.253
8.3506
Number revevaluation with SHAP Kemniixptainer
Praction dataset used for training
Figure 8: Speeding up Shapley value computations. Left: The inference time, here the time it takes to compute the Shapley values of 9000 instances, scales approximately linearly with the number of samples. Right: The x times speedup provided by our model-based approach contrasted by the fraction of data used for training.
Neural models are sample efficient. We also examine the sample efficiency and performance of neural networks trained to predict Shapley values on sets of features. Here, we consider two well- known datasets: the classical UCI Bank Marketing dataset [35] (17 features, 11,162 observations) and the Melbourne Housing dataset (3 (13 features, 34,857 observations). For the full details, see Appendix ??). Overall, we find that neural networks achieve high performance on the test set with very few training samples. Figure S displays the models' performance (in RMSE) function of samples available for training. We observe that the error decays approximately exponentially with the proportion of data used for training on both the Banking and Melbourne datasets. A model

---

set-based representations (36). The direct applications that we have considered in this paper are also intrinsically valuable on their own, as we allow speeding up explainable AI analysis and political influence estimation. Some questions remain open for future work. Can similar techniques be used for non-cooperative games or for other types of cooperative games? Can this approach be applied to other solutions such the Kernel or Nuclcolous ? Finally, are there better neural network designs, such as graph neural networks or transformers, that can exploit invariances or equivariances trained on just I percent of the Melbourne dataset has an RMSE of 19.72 on the resultant test set. Increasing the number of training samples percent results in a RMSE of less than 0.07, a 99.6 percent decrease in error. We observe a similar trend for the Banking dataset: the RMSE decreases with 93.8 percent (from 4.10 to 0.25) when the available training data increases from 0.5 to percent. These results highlight the strength of this approach: the computational cost of training the Shapley prediction network is very small as compared to the speedup obtained on the vast majority of the data (and any subsequent instances analyzed later).
Figure 9: Root Mean Squared Error as a function of training fraction. The RMSE between the actual and predicted Shapley values scales approximately as power law with the training fraction. Left: UCI Banking dataset Right: Melbourne Housing dataset.
5 Discussion and Conclusion
We considered "neural payoff machines", models that take in a representation of cooperative game and solve it to produce a distribution of the joint gains of a team amongst its members. Our anal- ysis focused on two concise representations of characteristic function: Weighted voting games, and feature importance games for explainable AI. Our analysis shows that neural models capture cooperative game solutions well, and can generalize well outside the training distribution, even ex- trapolating to more players than in the training set. However, we observed that the least core is a harder solution concept to learn than the Shapley value and Banzhaf index. Potentially, the fact that the least core is complex and can only be computed by solving multiple Linear Programs makes a hard concept to grasp from examples.
We showed that, with a dataset 9000 instances, our model-based approach to explainable Al lead to a speed up of more than 8x compared a sampling based approach (SHAP, based on the LIME algorithm). While this comes with a small decrease in prediction quality, we believe that more suitable training procedures can lead to models with performance see how this win in computation translates to larger datasets. Consider a similar dataset with 100,000 million entries. Computing Shapley values the entire dataset with SHAP will take weeks (40 or 400 hours), while the time for our procedure remains relatively the same: building the train set and training the neural network only takes fraction of the time required by the sampling -baed approach: the analysis using our method would take a few hours.
par with SHAP. It is easy to
The methods we discussed can drive better analysis of decision making bodies and for approximating feature importance,
such methods can also be applied to other classes of cooperative games, so long one can generate data consisting of game samples and their solutions. For instance, the same approach can be used for other cooperative representations, such as graph-based games [15] 3
4 or
in the game's representation be better equipped to deal with sharp discontinuities in the solutions?
Acknowledgements
This work was partly supported for T.K. D.C and T.R by ELLIS- the European Laboratory for Learning and Intelligent Systems, the Ethereum foundation, Lineage logistics research grant and Kells Establishment.
10

---

References
[1] A. Agarwal, M. Dahleh, and TT Sarkar. A marketplace for data: An algorithmic solution. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 701-726, 2019.
[2] A. B. Arrieta, N. Díaz-Rodríguez, J. Del Ser, A. Bennetot, S. Tabik, A. Barbado, S. Gareía, S. Gil-López,, D. Molina, R. Benjamins, et al. Explainable artificial intelligence (xai): Con- cepts, taxonomies, opportunities and challenges toward responsible ai. Information fusioii 58: 82-115, 2020.
[3] H. Aziz, O. Lachish, M. Paterson, and R. Savani. Power indices in spanning connectivity games. In International Conference on Algorithmic Applications in Management, pages 55- 67. Springer, 2009.
[4] Y. Bachrach, J. S. Rosenschein, and E. Porat. Power and stability in connectivity games. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2, pages 999-1006, 2008
[5] Y. Bachrach, E. Markakis, E. Resnick, A. D. Procaccia, J. S. Rosenschein, and A. Saberi. Approximating power indices: theoretical and empirical analysis. Autonomous Agents and Mulli-Agent Systems, 20(2):105-13 2010.
[6] Y. Bachrach, T. Graepel, G. Kasneci, M. Kosinski, and J. Van Gael. Crowd iq: aggregat- ing opinions to boost performance. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent pystems-Volume I, pages 535-542, 2012.
[7] B. Baker, I. Kanitscheider, Markov, Y. Wu, G. Powell, B. McGrew, and I. Mordatch. Emer- gent tool use from multi-agent autocurricula. arXiv preprint 19Xiv:190.007528 2019.
[8] E. Balkanski, U. Syed, and S. Vassilvitskii. Statistical cost sharing. Advances in Neural Information Processing Systems, 30, 2017.
[9] J. F. Banzhaf III. Weighted voting doesn't work: A mathematical analysis. Rutgers L. Rev. 19:317, 1964.
[10] J. M. Bilbao, R. Fernandez, N. Jiménez, and J. J. Lopez. Voting power in the european union enlargement. European Journal of Operational Research, 143(1):181-196, 2002.
[11] G. Chalkiadakis, E. Elkind, and M. Wooldridge. Computational aspects of cooperative game theory. Synthesis Lectures Artificial Intelligence and Machine Learning, 5(6):1-168, 201 1.
[12] A. Dafoe, Y. Bachrach, G. Hadfield, E. Horvitz, K. Larson, and T. Graepel. Cooperative ai:
machines must learn to find common ground, 2021.
[13] A. Das and P. Rad. Opportunities and challenges in explainable artificial intelligence (xai): A survey. arXiv preprint arXiv:2006. 1371, 2020.
[14] A. Datta, S. Sen, and Y. Zick. Algorithmic transparency via quantitative input influence: The- ory and experiments with learning systems. In 2016 IEEE symposium security and privacy (SP), pages 598-617. IEEE, 2016.
[15] X. Deng and C. H. Papadimitriou. On the complexity of cooperative solution concepts. Math- ematics of operations research, 19(2):257-266, 1994.
[16] Dubey. On the uniqueness of the shapley value. International Journal of Game Theory, (3):131-139, 1975.
[17] E. Elkind and D. Pasechnik. Computing the nucleolus of weighted voting games. In Proceed- ings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 327-335. SIAM, 2009.
[18) E. Elkind, I.. A. Goldberg, P. W. Goldberg, and M. Wooldridge. Computational complexity of weighted threshold games. In AAAI, pages 718-723 2007.
[19] J. Frankle and M. Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural net- works. arXiv preprint arXiv: 1803 03665, 2018.
[20] D. Gately. Sharing the gains from regional cooperation: game theoretic application to plan- ning investment in electric power. International Economic Review, pages 195-208, 1974.
[21] A. Ghorbani and J. Zou. Neuron shapley: Discovering the responsible neurons. Advances in Neural Information Processing Systems, 33:5922-5932. 2020.

---

[22] D. B. Gillies. Some theorems on n-person games. Princeton University. 1953.
[23] J. Henrich. The secret of our success. In The Secret of Our Success. Princeton University Press, 2015.
[24] M. Jaderberg, W. M. Czarnecki, I. Dunning, L. Marris, G. Lever, A. G. Castaneda, C. Beattie, N. C. Rabinowitz, A. Morcos, A. Ruderman, et al. Human-level performance in 3d mul- tiplayer games with population-baser reinforcement learning. Science, 364(6443):859-886) 2019.
[25] D. Leech. Computation of power indices. 2002.
[26] J. Lorraine, J. Parker-Holder, P. Vicol, A. Pacchiano, L. Metz, T. Kachman, and J. Foerster. Using bifurcations for diversity in differentiable games. In ICML 2021 Beyond First Order Methods Workshop, 2021.
[27] J. Lorraine, P. Vicol, J. Parker-Holder, T. Kachman, L. Metz, and J. Foerster. Lyapunov expo- nents for diversity in differentiable games. arXiv preprint arXiv:2112. 14570, 2021.
[28] R. Lowe, Y. I. Wu, A. Tamar, J. Harb, O. Pieter Abbeel, and I. Mordatch. Multi-agent actor- critic for mixed exoperatiee-omppetiie cessing systems, 30, 2017.
environments. Advances in neural information pro-
[29] S. M. Lundberg and S.-L. Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017,
[30] S. M. Lundberg, G. Erion, H. Chen, A. DeGrave, J. M. Prutkin, B. Nair, R. Katz, J. Himmel- farb, N. Bansal, and S.-I. Lee. From local explanations to global understanding with explain- able ai for trees. Nature machine intelligence. 2(1) (1)::6667, 2020.
[31] S. Maleki, L. Thanh, G. Hines, T. Rahwan, and A. Rogers. Bounding the estimation error of sampling-based shapley value approximation. arXiv preprint 13XKiv:300.4200 2013.
[32] I. Mann and L. S. Shapley. Values of large games. 6: Evaluating the electoral college exactly. Technical report, RAND CORP SANTA MONICA CA, 1962.
[33] M. Maschler, B. Peleg, and L. S. Shapley. Geometric properties of the kernel, nucleolus, and related solution concepts. Mathematics of operations research, 4(4):303-333 1979.
[34] L. Metz, C. D. Freeman, S. Schoenholz, and T. Kachman. Gradients are not all you need. arXiv preprint arXiv:21 11.0503, 2021.
[35] S. Moro, P. Cortez, and P. Rita. A data-driven approach to predict the success of bank telemar- keting. Decision Support Systems, 62:22 31, 2014.
[36] N. Ohta, V. Conitzer, Y. Satoh, A. Iwasaki, and M. Yokoo. Anonymity-prode shapley value: extending shapley value for coalitional games in open environments. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2, pages 927-934, 2008
[37] M. J. Osborne and A. Rubinstein. A course in game theory. MIT press, 1994.
[38] R. Patel, M. Garnelo, I. Gemp, C. Dyer, and Y. Bachrach. Game-theoretie vocabulary selec- tion via the shapley value and banzhaf index. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2789-2798, 2021.
[39] T. Pino. Melbourne housing market data, 2018.
[40] I.. S. Shapley. A value for n-person games. aw kuhn, hw tucker, ed., contributions to the thoery of games ii, 1953.
[41] R. H. I.. 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.
[42] P. Stone and M. Veloso. Multiagent systems: A survey from a machine learning perspective. Autonomous Robots, 8(3):345-383 2000.
[43] P. Straffin jr. "the shapley-shubik and banzhaf power indices as probabilities". The Shapley Value: Essays in Honor of Lloyd S. Shapley, pages 7 71-81, 1988.
[44] M. Sundararajan, A. Taly, and Q Yan. Axiomatic attribution for deep networks, Interna- tional conference on machine learning, pages 3319-3328. PMLR, 2017.
12

---

[45] O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi,
R. Powell, T. Ewalds, P. Georgiev, et al. Grandmaster level in starcraft using multi-agent reinforcement learning. Nature, 575(7782)350-334 2019.
[46] S. Wang. Efficient deep learning. Nature Computational Science, 133):111-82, 2021.
[47] T. Yan and A. D. Procaccia. If you like shapley then you'l '1l love the core. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5751-5759, 2021.
[48] M. Zuckerman, P. Faliszewski, Y. Bachrach, and E. Elkind. Manipulating the quota in weighted voting games. Artificial Intelligence, 180:1-19, 2012.
13


Reviews:
[{"review_id": "iIjiO91lWWB", "reviewer": "Reviewer_qYgj", "summary": "The authors propose a heuristic, deep learning approach to computing agent/feature importance in complex cooperative game theoretic settings. Such setting are known to be hard to solve and understand exactly (for example computing the Shapley value in voting games is #P-complete), motivating the study of the paper. ", "questions": "- Can the authors compare their results to previous work/non deep learning based results? Does the deep learning approach lead to significant improvement which warrants the downsides of having to use a black-box, hard to understand algorithm?", "limitations": "In terms of societal impact, I think it is nice that the authors have applications to interpretability. Limitations are discussed in Section 4.1.2.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The authors’ algorithms seem to perform well according to the experiments\n- The authors’ proposed framework has several proposed and illustrated applications, including solving voting games and understanding feature importance in hard-to-understand models\n- The authors look at several metrics of interest for measure contribution/importance, including shapley values, Banzhaf indexes, and cores. The flexibility provided by the framework seems nice and useful. \n\nWeaknesses:\n- My main question and “issue” with the paper is that I do not get a good sense here of whether the neural net approach is actually necessary, or if it is actually overkill. For example, if the goal were just to compute Shapley values fast, approaches based on sampling are known and seem to be relatively efficient. How does the current work compare to those? \n- Maybe things are more complicated when it comes to compute the actual outcomes rather than just computing shapley values, but this needs to be discussed more. There is indeed motivation for a heuristic approach in that these problems are hard to solve exactly, but it seems the authors jumped to a neural net before exploring simpler heuristics on very structured problems/it is not clear to me why this brings compared to possible simpler approaches. \n- Related to the point above, the paper makes no comparison with previous work, when other heuristics I believe exist for at least some of the questions asked in the paper\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LSJQm8Yq_Ki", "reviewer": "Reviewer_JZrJ", "summary": "The paper discusses using neural computation to compute values of cooperative game theory in weighted voting games and feature importance games.  For weighted voting games, models for both fixed and variable numbers of players are given.  While fixed models outperformed variable models, results on random games indicates that both models do relatively well.  Furthermore, predictions fro feature importance games are quite good after training on only a small amount of training data.", "questions": "See comments in the previous section.", "limitations": "I think further exploration of failure cases would be appropriate at some point", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ The paper does a good job of describing and introducing the problem.\n\n+ The presentation of the paper is clear and clean.\n\n+ This paper implements and tests a good, simple, and useful idea: Can neural computation to computer values of cooperative game theory.  \n\n+ The analysis of the results is good and detailed.\n\nWeaknesses:\n\n- It would be fun to illustrate how well the trained neural networks perform on known problems rather than on just random games.\n\n- (Table 1) Suggestion: I think it would be good to understand how significant the failures are when the neural network fails (e.g., significantly out of distribution).  Is there any way to detect when it would fail?\n\nA few minor nitpicks:\n\n- It’s probably right in front of my eyes, but I could see where p(C) was defined on line 111\n\n- Line 260: fix “at a the cost” — there’s clearly an extra word\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0994enkuQ77", "reviewer": "Reviewer_6UQP", "summary": "This paper applies a multi-layer perceptron to learning to approximate the Shapley value of a weighted voting game (where the input is a description of the voting weights of each player, and the output is a vector of Shapley values for each voter).  The fixed-dimension case (for which the number of voters is constant) and variable dimension case are both considered; the variable dimension case is handled simply by zero-padding (i.e., non-players are added with weight 0 to every empty slot).\n\nAlthough weighted voting games are simple, approximating their Shapley value within a multiplicative factor is known to be intractable in the worst case.\n", "questions": "Do you have performance numbers (both timing and prediction quality) for any scenario where the use of something like SHAP would be intractable?", "limitations": "see strengths/weaknesses", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The basic idea is sound: we sometimes want the Shapley value (to estimate the relative influence of different input features on the output of an ML model, or to estimate the relative power of different voters).  However, it's intractable to compute exactly.  So let's try approximating it by training a neural network on small instances.  It seems to work pretty well on the instances that they test on.\n\nOne of the main motivations for this work is scalability.  It can be exponentially expensive to compute the Shapley value as the number of participants increases, making an approximation approach valuable.  Clearly the network with a fixed number of participants won't be much use in large-scale situations, since the training data needs to be as large as the test data.  On the other hand, the paper shows that you can get decent performance by training on a dataset with about half as many participants as in the test set (using the zero-padding variable-dimension approach).  This is of course better than nothing, but I'm skeptical that an approximate doubling of the feasible size of input is going to be sufficient in settings that actually need scale.\n\nThe paper is clearly written, with the exception of the material on explainable AI.  This domain is an important part of the paper's motivation, but its treatment feels like something of an afterthought.   I can take a guess at what is going on here (the \"value\" created by a given agent is going to be either the average change in a binary classification, or the average change in regression output, averaged over all orderings), but it would be nice if this were somehow made explicit.  Section 3.2 doesn't really give any details about the actual procedure (what is a \"sampled sub-dataset\"?  Are you sampling rows (instances) or columns (features)?  Appendix D.2 doesn't refer to this at all.).  Section 2.2 is similarly vague.\n\nOverall, I don't think this work clears the significance bar for publication at NeurIPS.  It proposes a standard feedforward architecture for prediction in a specific scenario.  The scenario is interesting but not really deeply explored.  There is no explicit comparison to baselines, so it's hard to tell what we actually gain.  In particular, we don't see any performance numbers at all.  How large is the performance difference vs standard techniques?  Are you able to do well on instances that take SHAP weeks, for example?\n\n__minor comments__\n\n- p.5: \"we redistribute the payoffs allocated to non-player entries\": How necessary does this turn out to be?  (I.e., is a substantial fraction of payoff often allocated to non-players?)\n\n- p.6: The first paragraph of s.3.2 is very repetitive\n\n- On a related note, it's not clear from the main text what the ground truth for figure 7 is meant to be.\n\n- Figure 2 is unreadably small, and also seems to make the PDF very slow to render.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept