Coalitional games allow subsets (coalitions) of players to
cooperate to receive a collective payoff. This payoff is then
distributed ``fairly'' among the members of that coalition
according to some division scheme. Various solution concepts
have been proposed as reasonable schemes for generating fair
allocations. The \emph{Shapley value} is one classic solution
concept: player $i$'s share is precisely equal to $i$'s
expected marginal contribution if the players join the
coalition one at a time, in a uniformly random order. In this
paper, we consider the class of supermodular games
(sometimes called convex games), and give a fully polynomial-time
randomized approximation scheme (FPRAS) to compute the Shapley
value to within a $(1 \pm \varepsilon)$ factor in monotone
supermodular games. We show that this result is tight in several
senses: no deterministic algorithm can approximate Shapley value
as well, no randomized algorithm can do better, and both
monotonicity and supermodularity are required for the existence
of an efficient $(1 \pm \varepsilon)$-approximation algorithm.
We also argue that, relative to supermodularity, monotonicity is
a mild assumption, and we discuss how to transform supermodular
games to be monotonic.