{A Tractable and Expressive Class of Marginal Contribution Nets
and Its Applications
Authors: Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg, and Michael Wooldridge
Abstract:
Coalitional games raise a number of important questions from the
point of view of computer science, key among them being how to
represent such games compactly, and how to efficiently compute solution
concepts assuming such representations. \emph{Marginal contribution
nets} (MC-nets), introduced by Ieong and Shoham, are one of the
simplest and most influential representation schemes for coalitional
games. MC-nets are a rule-based formalism, in which rules take the
form \emph{pattern} $\longrightarrow$ \emph{value}, where
``\emph{pattern}'' is a Boolean condition over agents, and
``\emph{value}'' is a numeric value. Ieong and Shoham showed that,
for a class of what we will call ``basic'' MC-nets, where patterns
are constrained to be a conjunction of literals, marginal
contribution nets permit the easy computation of solution concepts
such as the Shapley value. However, there are very natural classes
of coalitional game that require an exponential number of such basic
MC-net rules. We present \emph{read-once MC-nets}, a new class of
MC-nets that is provably more compact than basic MC-nets, while
retaining the attractive computational properties of basic
MC-nets. We show how the techniques we develop for read-once MC-nets
can be applied to other domains, in particular, computing solution
concepts in network flow games on series-parallel networks.