An Analysis of the Shapley Value and Its Uncertainty for the Voting Game - Agent-Mediated Electronic Commerce - page 85

An Analysis of the Shapley Value and Its Uncertainty
for the Voting Game

Shaheen S. Fatima 1 , Michael Wooldridge 1 , and Nicholas R. Jennings 2

1 Department of Computer Science,
University of Liverpool, Liverpool L69 7ZF, U.K.
{ S.S.Fatima, M.J.Wooldridge } @csc.liv.ac.uk
2 School of Electronics and Computer Science,
University of Southampton, Southampton SO17 1BJ, U.K.
[e-mail]

Abstract. The Shapley value provides a unique solution to coalition games and
is used to evaluate a player's prospects of playing a game. Although it provides
a unique solution, there is an element of uncertainty associated with this value.
This uncertainty in the solution of a game provides an additional dimension for
evaluating a player's prospects of playing the game. Thus, players want to know
not only their Shapley value for a game, but also the associated uncertainty. Given
this, our objective is to determine the Shapley value and its uncertainty and study
the relationship between them for the voting game. But since the problem of de-
termining the Shapley value for this game is # P -complete, we first present a new
polynomial time randomized method for determining the approximate Shapley
value. Using this method, we compute the Shapley value and correlate it with
its uncertainty so as to allow agents to compare games on the basis of both their
Shapley values and the associated uncertainties. Our study shows that, a player's
uncertainty first increases with its Shapley value and then decreases. This implies
that the uncertainty is at its minimum when the value is at its maximum, and that
agents do not always have to compromise value in order to reduce uncertainty.

1 Introduction

Coalition formation is the process of joining together of two or more agents so as to
achieve goals that individuals on their own cannot, or to achieve them more efficiently
[9]. Often, in such situations, there is more than one possible coalition and a player's
payoff depends on the coalition it joins. Given this, a key problem in this area is to
ensure that none of the parties in a coalition has any incentive to break away from it and
join another coalition (i.e., the coalitions are stable ). However, in many cases there may
be more than one solution (i.e., a stable coalition). In such cases, it becomes difficult
to select a single solution from among the possible ones, especially if the parties are
self-interested (i.e., they have different preferences over stable coalitions).
In this context, cooperative game theory deals with the problem of coalition for-
mation and offers a number of solution concepts that possess desirable properties like
stability , fair division of joint gains ,and uniqueness [3,7]. Multiagent systems research
has used and extended these game-theoretic solutions to facilitate automated coalition