The first source of computational load comes from computing the Shapley value of each party. Computing the Shapley value exactly incurs \(\mathcal {O}(n!)\)  time, which is intractable if the number of parties \(n\)  is large. To circumvent this issue of large \(n\) , we can follow the recent work of [1]} by considering the Shapley value to be the expected marginal contribution based on a uniform distribution over permutations of parties and estimating it via Monte Carlo sampling which incurs \(\mathcal {O}(mn)\)  time where \(m\)  is the number of permutations sampled. The value of \(m\)  required to achieve a small estimation error with high probability can be bounded when either the variance or the range of the marginal contributions is known [2]}. After we have the Shapley values, we compute the reward values using the LP. The LP has only 2 variables and \(2n + 2\)  constraints, which can be solved in \(\mathcal {O}(n^{1.5})\)  time using interior point methods [3]}.
