Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games

Samuel Ieong and Yoav Shoham

Abstract

We present a new approach to representing coalitional games based on rules that describe the marginal contributions of the agents. This representation scheme captures characteristics of the interactions among the agents in a natural and concise manner. We also develop efficient algorithms for two of the most important solution concepts, the Shapley value and the core, under this representation. The Shapley value can be computed in time linear in the size of the input. The emptiness of the core can be determined in time exponential only in the treewidth of a graphical interpretation of our representation.

Details

Publication typeInproceedings
Published inProceedings of ACM Electronic Commerce (ACM-EC)
PublisherAssociation for Computing Machinery, Inc.
> Publications > Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games