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 条
  • [21] Expectation formation rules and the core of partition function games
    Bloch, Francis
    van den Nouweland, Anne
    GAMES AND ECONOMIC BEHAVIOR, 2014, 88 : 339 - 353
  • [22] The Shapley function for multi-choice games on matroids
    Meng, F. Y.
    Zhan, J. Q.
    JOURNAL OF INTERDISCIPLINARY MATHEMATICS, 2015, 18 (04) : 321 - 338
  • [23] The Shapley function for fuzzy games with fuzzy characteristic functions
    Meng, Fanyong
    Zhao, Jinxian
    Zhang, Qiang
    JOURNAL OF INTELLIGENT & FUZZY SYSTEMS, 2013, 25 (01) : 23 - 35
  • [24] The Tractability of the Shapley Value over Bounded Treewidth Matching Games
    Greco, Gianluigi
    Lupia, Francesco
    Scarcello, Francesco
    PROCEEDINGS OF THE TWENTY-SIXTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2017, : 1046 - 1052
  • [25] Partially ordered cooperative games: extended core and Shapley value
    J. Puerto
    F. R. Fernández
    Y. Hinojosa
    Annals of Operations Research, 2008, 158 : 143 - 159
  • [26] Shapley value for TU-games with multiple memberships and externalities
    Sokolov, Denis
    MATHEMATICAL SOCIAL SCIENCES, 2022, 119 : 76 - 90
  • [27] Consistency of the Shapley NTU value in G-hyperplane games
    Hinojosa, M. A.
    Romero-Palacios, E.
    Zarzuelo, J. M.
    REVIEW OF ECONOMIC DESIGN, 2015, 19 (04) : 259 - 278
  • [28] Partially ordered cooperative games:: extended core and Shapley value
    Puerto, J.
    Fernandez, F. R.
    Hinojosa, Y.
    ANNALS OF OPERATIONS RESEARCH, 2008, 158 (01) : 143 - 159
  • [29] A reformulated Shapley-like value for cooperative games with interval payoffs
    Feng, Wenrui
    Han, Weibin
    Pan, Zheng
    OPERATIONS RESEARCH LETTERS, 2020, 48 (06) : 758 - 762
  • [30] The non-emptiness of the core of a partition function form game
    Takaaki Abe
    Yukihiko Funaki
    International Journal of Game Theory, 2017, 46 : 715 - 736
12345