Marginal contribution nets: a compact representation scheme for coalitional games
Marginal contribution nets: a compact representation scheme for coalitional games
复制标题
DOI：
10.1145/1064009.1064030
复制
发表时间：
2005-06
期刊：
影响因子：
--
通讯作者：
Samuel Ieong;Y. Shoham
中科院分区：
文献类型：
--
作者：
Samuel Ieong;Y. Shoham
我们提出了一种新的方法来表示联盟博弈，该方法基于描述代理的边际贡献的规则。该表示方案以自然、简洁的方式刻画了智能体之间的交互特征。在这种表示下，我们还为两个最重要的解概念Shapley值和核开发了有效的算法。Shapley值可以在输入大小的时间中线性计算。核心的空白性只能在我们表示的图形解释的树宽中以时间指数的形式确定。
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.