Complexity of Computing the Shapley Value in Partition Function Form Games

被引：0
|
作者：
Skibski, Oskar [1 ]
机构：
[1] Univ Warsaw, Inst Informat, PL-02097 Warsaw, Poland
来源：
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH | 2023年 / 77卷
关键词：
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
相关论文
共 47 条
  • [41] Coalition Structure Generation for Partition Function Games Utilizing a Concise Graphical Representation
    Zha, Aolong
    Nomoto, Kazuki
    Ueda, Suguru
    Koshimura, Miyuki
    Sakurai, Yuko
    Yokoo, Makoto
    PRINCIPLES AND PRACTICE OF MULTI-AGENT SYSTEMS (PRIMA 2017), 2017, 10621 : 143 - 159
  • [42] The core of an economy with a common pool resource: A partition function form approach
    Yukihiko Funaki
    Takehiko Yamato
    International Journal of Game Theory, 1999, 28 : 157 - 171
  • [43] The core of an economy with a common pool resource: A partition function form approach
    Funaki, Y
    Yamato, T
    INTERNATIONAL JOURNAL OF GAME THEORY, 1999, 28 (02) : 157 - 171
  • [44] Consumer Flexibility Aggregation Using Partition Function Games With Non-Transferable Utility
    Pinto, Tiago
    Wooldridge, Michael
    Vale, Zita
    IEEE ACCESS, 2021, 9 (09): : 51519 - 51535
  • [45] Efficiency and Stability in Electrical Power Transmission Networks: a Partition Function Form Approach
    Dávid Csercsik
    László Á. Kóczy
    Networks and Spatial Economics, 2017, 17 : 1161 - 1184
  • [46] The equivalence of the minimal dominant set and the myopic stable set for coalition function form games
    Herings, P. Jean-Jacques
    Koczy, Laszlo A.
    GAMES AND ECONOMIC BEHAVIOR, 2021, 127 : 67 - 79
  • [47] Correlation analysis and threshold value research on the form and function indexes of an urban interconnected river system network
    Dou, Ming
    Yu, Lu
    Jin, Meng
    Zhang, Yan
    WATER SCIENCE AND TECHNOLOGY-WATER SUPPLY, 2016, 16 (06): : 1776 - 1786
12345