未找到相关数据
Complexity of Computing the Shapley Value in Partition Function Form Games
被引：0
|作者：
Skibski, Oskar
[1
]
机构：
[1] Univ Warsaw, Inst Informat, PL-02097 Warsaw, Poland
关键词：
COALITION STRUCTURE GENERATION;
POWER INDEXES;
EXTERNALITIES;
CONNECTIVITY;
CORE;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ;
0812 ;
0835 ;
1405 ;
摘要：
We study the complexity of computing the Shapley value in partition function form games. We focus on two representations based on marginal contribution nets (embedded MC-nets and weighted MC-nets) and five extensions of the Shapley value. Our results show that while weighted MC-nets are more concise than embedded MC-nets, they have slightly worse computational properties when it comes to computing the Shapley value: two out of five extensions can be computed in polynomial time for embedded MC-nets and only one for weighted MC-nets.
引用
收藏
页码：1237 / 1274
页数：38
相关论文