A tractable and expressive class of marginal contribution nets and its applications

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. 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 pattern → value, where "pattern" is a Boolean condition over agents, and "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 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.

REFERENCES

• 1: Yoram Bachrach , Jeffrey S. Rosenschein, Computing the Banzhaf power index in network flow games, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329433]
• 2: V. Conitzer and T. Sandholm, Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In Proc. AAAI-2004, pp. 219--225, 2004
• 3: Xiaotie Deng , Christos H. Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research, v.19 n.2, p.257-266, May 1994 [doi>10.1287/moor.19.2.257]
• 4: E. Kalai and E. Zemel, On totally balanced games and games of flow. Discussion Papers 413, Northwestern University, Center for Mathematical Studies in Economics and Management Science, Jan. 1980, available at http://ideas.repec.org/p/nwu/cmsems/413.html
• 5: E. Kalai and E. Zemel, Generalized network problems yielding totally balanced games. Operations Research, 30:998--1008, September 1982
• 6: Samuel Ieong , Yoav Shoham, Marginal contribution nets: a compact representation scheme for coalitional games, Proceedings of the 6th ACM conference on Electronic commerce, p.193-202, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064030]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

General Terms:
Algorithms, Economics, Theory

Keywords:
coalitional games, complexity, marginal contribution nets, representation