Too many orders to list

The rule is an average over every order in which the players could have arrived. For three players that is six orders and the average can be written out; the figures on the rungs below do exactly that.

For seven it is five thousand and forty. For twelve it is four hundred and seventy-nine million. For twenty it is $2.4 \times 10^{18}$, which is more than the number of seconds since the universe began — and twenty players is a small committee.

Why exact computation is hopeless in general #

The obvious improvement on listing $n!$ orders is the closed formula, which sums over coalitions rather than orders:

$$\phi_i = \sum_{S \not\ni i} \frac{|S|!\,(n - |S| - 1)!}{n!}\,\bigl(v(S \cup \{i\}) - v(S)\bigr).$$

That is $2^{n-1}$ terms rather than $n!$, which is a very large saving and not enough. At $n = 50$ it is $10^{14}$ terms, and the game’s value has to be evaluated at each.

Worse, the hardness is not merely arithmetic. Computing the Shapley value of a weighted voting game exactly is #P-hard — as hard as counting the satisfying assignments of a formula — so there is no polynomial algorithm unless a great deal of complexity theory is wrong. Even deciding whether a member is a dummy is hard in general.

There are exceptions and they are worth knowing. Games with structure often have closed forms: unanimity games, the capacity game the rung above uses, and any game whose value depends only on a coalition’s total weight through a simple threshold can be handled by dynamic programming over the weights. But for a game presented as an arbitrary table, the answer is that it cannot be done.

Sampling, and why it is unbiased #

The estimator is the obvious one. Draw an order uniformly at random, walk through it recording what each player adds, and average over the draws. It is the Monte Carlo manoeuvre applied to a sum instead of to an integral.

It is unbiased — the expected value of a single draw is exactly the Shapley value, by definition, since the value is the mean over orders. So the average of $m$ draws has the right expectation for every $m$, and the only question is the spread.

That is the whole design, and it is worth noticing how little it needed. Nothing about the game is used; the estimator works for any game whose value can be evaluated at a coalition, and the cost of one draw is $n$ evaluations. Where the exact computation is exponential, the estimate’s cost per draw is linear.

The figure computes the exact answer by enumeration — possible at seven players — and plots the largest error in the estimated shares against the number of draws. Having the exact answer is what makes the comparison a measurement rather than a hope, and it is available here precisely because the example was chosen small enough for it to be.

The rate, and why it is the reciprocal square root #

The estimate is an average of $m$ independent draws, each with the same finite variance. So its standard deviation is $\sigma/\sqrt m$ — the square-root law that governs every average of independent quantities.

Four consequences, all of them consequences of the exponent rather than of anything about games.

Halving the error costs four times the work. Three decimal places costs a million draws, four costs a hundred million.

The rate does not depend on the number of players. A twenty-player game and a fifty-player game need the same number of draws for the same accuracy, other things being equal — which is the property that makes sampling worth doing at all, and is the same observation that makes Monte Carlo integration beat a grid in high dimensions.

The constant is the variance, and the variance can be attacked. The exponent cannot move; $\sigma$ can, and everything clever in this subject is an attack on $\sigma$.

The error is random. A run can be unlucky, so a single measured error is a sample of a distribution and not a bound. The figure’s assertion is stated accordingly: the measured fall over the whole sweep is required to be within a factor of the square-root prediction rather than equal to it.

What the sweep actually measures #

The figure’s assertion is worth reading carefully, because it is the sort of claim that is easy to state loosely and then to check vacuously.

What is asserted is not that the error is $C/\sqrt m$. A single run’s error at a given $m$ is a random quantity with that scale, and demanding equality would fail on an unlucky run and pass on a lucky one, which is a gate that tests the seed.

What is asserted instead is a ratio: the error at the largest sample, divided by what the square-root law predicts from the error at the smallest, is required to lie between a sixth and six. That is a wide band and it is the right width — a factor of two either way is entirely ordinary for a single run over a sweep of this length — and it would still fail decisively on an estimator with a bias, whose error stops falling at all.

A tolerance that no wrong implementation could pass is the requirement, and one that any implementation passes is decoration. The bias case is the one this band is aimed at: a biased estimator’s error tends to a constant, so over three decades of sample size the measured ratio would be near one rather than near a thirtieth.

Why the exponent cannot be improved #

It is worth saying why no amount of cleverness moves the half, because the temptation to look for a better method is strong and the answer is a theorem rather than a failure of imagination.

The estimator averages independent samples of a quantity with non-zero variance. The variance of an average of $m$ such samples is $\sigma^2/m$ exactly, so the standard deviation is $\sigma/\sqrt m$ exactly. Nothing about the sampling scheme changes that, because it is arithmetic on variances.

What can change is $\sigma$, and what can also change is the assumption of independence. Quasi-random sequences — points chosen to be more evenly spread than random ones — beat the rate for integration over a cube, reaching close to $1/m$ for smooth integrands, and that trade is the subject of its own essay. Whether an analogous construction helps for averaging over permutations is a real question with a partial answer; the space of orders is not a cube and the constructions do not transfer directly.

So the honest statement is that the exponent is fixed for independent sampling and that abandoning independence is the only route past it. That is the same conclusion the integration essay reaches, in a setting where the abandonment is well understood, and it is why this rung stops at variance reduction.

Where the variance is attacked #

Three standard improvements, in increasing order of cleverness.

Stratify by position. A player’s marginal contribution depends heavily on how many players arrived before them, so sample each of the $n$ possible positions equally often rather than letting the random orders decide. That removes the largest single source of variance and costs nothing.

Use antithetic pairs. Draw an order and also its reverse. The two marginal contributions of a given player are negatively correlated — a player arriving early in one arrives late in the other — so the pair’s average has smaller variance than two independent draws.

Reweight the draws. Sample orders in which a player is likely to be pivotal more often, and divide by the probability of having drawn them. That is importance sampling, it is the general technique, and it needs a proposal that covers everything — a proposal assigning zero probability to an order the answer depends on gives a biased estimate rather than a noisy one.

All three leave the estimator unbiased and shrink $\sigma$. None of them moves the exponent, and no method does, because the exponent is a property of averaging independent things rather than of what is being averaged.

What is checked when there is nothing to check against #

At seven players the exact answer is available and the estimate can be compared with it. At fifty it is not, and something else has to be checked, because an estimator with a bug looks exactly like an estimator with a large variance.

Three checks that do not need the answer.

Efficiency. The estimated shares must sum to the value of the whole coalition. That holds for every single draw, since a marginal vector telescopes — so it holds exactly for the average, and a violation is a bug rather than noise. The figure asserts it.

Symmetry. Two players known to be interchangeable must get estimates that agree to within the sampling error. Interchangeability can often be checked cheaply from the game’s description even when the value cannot be computed.

Null players. A player known to add nothing must get exactly zero from every draw. Again exact, not statistical.

Those three are the first three of the four conditions, used as diagnostics rather than as axioms — and it is worth noticing that they are exactly the conditions every marginal vector satisfies, which is why they survive averaging exactly rather than approximately. The fourth condition, additivity, cannot be checked on one game and is the one the diagnostics have nothing to say about.

The games where none of this is needed #

Intractability in general is compatible with easiness in every case anybody meets, and a good deal of the subject is a search for structure that makes the exact answer available.

Unanimity games. The value is one when a coalition contains a fixed group and zero otherwise. Each member of the group gets one over its size; everybody else gets nothing. No computation at all.

Games depending only on total weight. A weighted voting game’s value depends on the coalition through one number, so the count of coalitions of each total weight can be built up by dynamic programming — one pass over the members, carrying a table indexed by weight — and the answer is exact in time proportional to the number of members times the total weight. That is polynomial in the numbers and exponential in their length, which is why the hardness result and the practical algorithm coexist without contradiction.

Games with a tree structure. Where the players sit at the leaves of a tree and a coalition’s value depends only on which subtrees it fills, the value can be computed by working up the tree.

Convex games. Where every player’s contribution grows as the coalition does, the value is the centre of gravity of the marginal vectors and lies inside the set of splits nobody can walk away from. That does not make it cheaper to compute and it does make it easy to bound.

The pattern is that hardness is a statement about the worst case and the worst case is an arbitrary table. A game specified by a rule rather than by a table almost always has structure, and finding it is usually a better investment than sampling harder.

The same problem in a different vocabulary #

The Shapley value has had a second life since about 2017 as a way of attributing a prediction to the things it was computed from — which is a cooperative game in which the players are the inputs and a coalition’s value is what the prediction becomes when only those inputs are supplied.

Everything in this essay applies unchanged and the sizes are much worse: the number of inputs is in the hundreds, exact computation is out of the question, and the sampled estimator with stratification is what is used. The condition that the shares sum to the whole becomes the statement that the attributions account for the prediction exactly, which is the property that makes the method attractive.

Two cautions belong with that, and both are visible from this rung. The estimate is noisy and the noise is rarely reported — an attribution quoted to three figures from a few hundred draws is quoting sampling error, and how far from the average a quantity can be is the right way to bound it. And what a coalition is worth has to be defined, which for this application means deciding what a prediction means when some inputs are absent; there is no canonical answer, and different answers give different games and therefore different values.

What the picture cannot show #

The figure plots one run. The error at a given sample size is a random quantity, so the points are a single draw from a distribution and the curve’s wobble is that randomness rather than structure. A picture of the distribution of the error would need many runs and would say more.

It cannot show the intractability, which is the reason for the whole exercise. Seven players is small enough that the exact answer is on the page; the situation the method exists for is one where it is not, and no drawing of a tractable case demonstrates an intractable one.

And it cannot show what the sampling misses. The estimate is unbiased, so nothing is missed in expectation — but a particular run visits five thousand of $10^{18}$ orders, and if the value were concentrated on a rare set of orders the estimate would be reliably wrong for a long time. That the game drawn is not like that is a fact about the game, checked by having the exact answer, and unavailable in the cases that matter.

Where the ladder goes next #

Above: the same rule dividing a cost rather than a gain, where a family of games turns out to have a closed form and none of this is needed.

One debt. Stratification by position is described here as removing the largest source of variance and is not measured. It would be a good figure — the same sweep with and without stratifying, on the same game — and it would put a number on how much the improvement is worth, which is the only honest way to recommend it.

What was given up #

An average over $n!$ things is estimated by averaging a few thousand of them, and the error falls like the reciprocal square root of however many are drawn.

The exchange is a definite one: exactness for a rate. What makes it acceptable is that three of the four properties the rule was characterised by survive it exactly — the shares still add up, null players still get nothing, interchangeable players still agree in expectation — so what is lost is precision in the numbers rather than the structure they were chosen for.