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?

  • $\begingroup$ 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. $\endgroup$ – Holger I. Meinhardt Jun 19 '15 at 12:32
  • 1
    $\begingroup$ @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. $\endgroup$ – Meni Rosenfeld Jun 19 '15 at 13:15
  • $\begingroup$ 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. $\endgroup$ – Holger I. Meinhardt Jun 19 '15 at 13:49
  • $\begingroup$ @HolgerI.Meinhardt: That's the general idea. Of course, if possible, I'd prefer an exact simple expression rather than an approximation. $\endgroup$ – Meni Rosenfeld Jun 19 '15 at 14:25
  • 1
    $\begingroup$ @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). $\endgroup$ – Meni Rosenfeld Jun 19 '15 at 15:21

I think you will find the article "The asymptotic shapley value for a simple market game" by Liggett, Lippman and Rumelt (2007) interesting and relevant for your question.

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.