# Is there a closed-form expression for Shapley value of glove game?

Suppose we have a coalition game with transferable utilities, with $m$ players having a right-handed glove and $n$ players having a left-handed glove. The value of a coalition is equal to the number of complete pairs of gloves in it. Then the Shapley value for a player with a right-handed glove is given by:

$\frac1{(m+n)!}\sum_{i=1}^{m+n}\sum_{j=0}^{\lfloor i/2 \rfloor-1}(m+n-i)!(i-1)!\binom{m-1}{j}\binom{n}{i-j-1}$

Is there a simple (or at least easy to evaluate) closed-form expression for this?

If not, perhaps an approximation for large m,n?

• I don't understand what do you mean by closed form. In principle the stated formula is a closed form. The parameter $m$ and $n$ are exogenous given variables determined by the glove game ($i,j$ are indices). Having these values you can directly calculate the Shapley value. – Holger I. Meinhardt Jun 19 '15 at 12:32
• @HolgerI.Meinhardt: I mean that the number of operations required is bounded as $m$ and $n$ vary. The formula isn't practical when $m$ and $n$ are in the millions; and it's too complicated, and providing little insight about how that value changes with $m$ and $n$. e.g., I'm looking for a formula like $n/(m+n)$ (of course this one is not correct). I'll accept factorial as an elementary operation, because it can be calculated with Stirling's formula. – Meni Rosenfeld Jun 19 '15 at 13:15
• If I understand you correctly, you are looking, in fact, for an approximation of the above formula for very large $m$ and $n$ for doing some differential calculus on the Shapley value. – Holger I. Meinhardt Jun 19 '15 at 13:49
• @HolgerI.Meinhardt: That's the general idea. Of course, if possible, I'd prefer an exact simple expression rather than an approximation. – Meni Rosenfeld Jun 19 '15 at 14:25
• @HolgerI.Meinhardt: That shouldn't be much of a problem, since you can just work in log space on the factorials as long as it is relevant; or arbitrary-precision arithmetic. Mathematica takes a second to calculate 100000! to full precision, but it would be difficult to repeat 10 billion times. (I also don't know for a fact that factorials would have to be involved). – Meni Rosenfeld Jun 19 '15 at 15:21

They analyse a market game with $b$ buyers (in your case, this would be the $m$ players having a right-handed glove) who each seek to purchase 1 unit of an indivisible good form $s$ sellers (the $n$ players with a left-handed glove), each of whom has $k$ units to sell. I think that if $k=1$, this game coincides with the glove game. If $V(b,s)$ denotes the notes the Shapley value for a seller in this game, it turns out that $$V(b,s) = \frac{1}{b+s} \sum_{i=0}^{s+b-1} \sum_{2j > i} \frac{\binom{b}{j} \binom{s-1}{i-j}}{\binom{s+b-1}{i}} \quad .$$ Suppose $b, s \to \infty$, so that $b/ks = b/s \to \alpha$. If $\alpha = 1$, and we assume that $\frac{ks-b}{\sqrt{b+s}} \to u$, then $$V(b,s) \to \frac{k^{2}}{\sqrt{2 \pi}} \int_{0}^{\infty} \frac{x^{2}}{u^{2} + kx^{2}}e^{-x^{2}/2} dx \quad \text{if } u \geq 0.$$ There's a similar formula for the case in which $u \leq 0$.