{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:12:03Z","timestamp":1767237123328,"version":"3.37.3"},"reference-count":14,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2009,7,17]],"date-time":"2009-07-17T00:00:00Z","timestamp":1247788800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["GR\/T10671\/01"],"award-info":[{"award-number":["GR\/T10671\/01"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000269","name":"ESRC","doi-asserted-by":"crossref","award":["ES\/F035845\/1"],"award-info":[{"award-number":["ES\/F035845\/1"]}],"id":[{"id":"10.13039\/501100000269","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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. <jats:italic>Marginal contribution nets<\/jats:italic> (MC\u2010nets), introduced by Ieong and Shoham, are one of the simplest and most influential representation schemes for coalitional games. MC\u2010nets are a rulebased formalism, in which rules take the form <jats:italic>pattern<\/jats:italic> \u2192 <jats:italic>value<\/jats:italic>, where \u201c<jats:italic>pattern<\/jats:italic> \u201d is a Boolean condition over agents, and \u201c<jats:italic>value<\/jats:italic> \u201d is a numeric value. Ieong and Shoham showed that, for a class of what we will call \u201cbasic\u201d MC\u2010nets, 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 games that require an exponential number of such basic MC\u2010net rules. We present <jats:italic>read\u2010once<\/jats:italic> MC\u2010<jats:italic>nets<\/jats:italic>, a new class of MC\u2010nets that is provably more compact than basic MC\u2010nets, while retaining the attractive computational properties of basic MC\u2010nets. We show how the techniques we develop for read\u2010once MC\u2010nets can be applied to other domains, in particular, computing solution concepts in network flow games on series\u2010parallel networks (\u00a9 2009 WILEY\u2010VCH Verlag GmbH &amp; Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200810021","type":"journal-article","created":{"date-parts":[[2009,7,18]],"date-time":"2009-07-18T07:49:09Z","timestamp":1247903349000},"page":"362-376","source":"Crossref","is-referenced-by-count":20,"title":["A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications"],"prefix":"10.1002","volume":"55","author":[{"given":"Edith","family":"Elkind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul W.","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Wooldridge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2009,7,17]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.2.257"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"S.Ieong andY.Shoham Marginal contribution nets: A compact representation scheme for coalitional games. In: Proceedings of the Sixth ACM Conference on Electronic Commerce (EC'05) (Vancouver Canada 2005).","DOI":"10.1145\/1064009.1064030"},{"key":"e_1_2_1_4_2","unstructured":"E.Malizia L.Palopoli andF.Scarbello Infeasibility certificates and the complexity of the core in coalitional games. In: Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI\u201007) (Hyderabad India 2007)."},{"key":"e_1_2_1_5_2","unstructured":"E.Elkind andM.Wooldridge Hedonic coalition nets. In: Proceedings of the Eighth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS\u20102009) (Budapest Hungary 2009)."},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"J.Uckelman Y.Chevaleyre U.Endriss andJ.Lang Representing utility functions via weighted goals. To appear in Math. Log. Quart. (2009).","DOI":"10.1002\/malq.200810024"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"Y.Bachrach andJ. S.Rosenschein Computing the Banzhaf power index in network flow games. In: Proceedings of the Sixth International Joint Conference on Autonomous Agents andMultiagent Systems (AAMAS\u20102007) (Honolulu Hawaii 2007) pp. 335\u2013341.","DOI":"10.1145\/1329125.1329433"},{"key":"e_1_2_1_8_2","unstructured":"M. J.Osborne andA.Rubinstein A Course in Game Theory (The MIT Press 1994)."},{"key":"e_1_2_1_9_2","first-page":"317","article-title":"Weighted voting doesn't work: A mathematical analysis","volume":"19","author":"Banzhaf J. F.","year":"1965","journal-title":"Rutgers Law Review"},{"key":"e_1_2_1_10_2","unstructured":"V.Conitzer andT.Sandholm Computing Shapley values manipulating value division schemes and checking core membership in multi\u2010issue domains In: Proceedings of the Ninteenth National Conference on Artificial Intelligence (AAAI\u20102004) (San Jose CA 2004) pp. 219\u2013225."},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/138027.138061"},{"key":"e_1_2_1_12_2","unstructured":"E.Kalai andE.Zemel On totally balanced games and games of flow. Discussion Paper 413 Northwestern University Center for Mathematical Studies in Economics and Management Science (1980)."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.30.5.998"},{"key":"e_1_2_1_14_2","unstructured":"E.Elkind L.Goldberg P.Goldberg andM.Wooldridge Computational complexity of weighted threshold games. In: Proceedings of the Twenty\u2010Second AAAI Conference on Artificial Intelligence (AAAI\u20102007) (Vancouver British Columbia Canada 2007)."},{"key":"e_1_2_1_15_2","unstructured":"P. E.Dunne S.Kraus W.van der Hoek andM.Wooldridge Cooperative boolean games. In: Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS\u20102008) (Estoril Portugal 2008)."}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200810021","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200810021","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200810021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T23:18:47Z","timestamp":1699917527000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200810021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,17]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1002\/malq.200810021"],"URL":"https:\/\/doi.org\/10.1002\/malq.200810021","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"type":"print","value":"0942-5616"},{"type":"electronic","value":"1521-3870"}],"subject":[],"published":{"date-parts":[[2009,7,17]]}}}