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 条
  • [1] An axiomatic characterization of a value for games in partition function form
    Hu, Cheng-Cheng
    Yang, Yi-You
    SERIES-JOURNAL OF THE SPANISH ECONOMIC ASSOCIATION, 2010, 1 (04): : 475 - 487
  • [2] A coalition formation value for games in partition function form
    Grabisch, Michel
    Funaki, Yukihiko
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 221 (01) : 175 - 185
  • [3] An axiomatic characterization of a value for games in partition function form
    Cheng-Cheng Hu
    Yi-You Yang
    SERIEs, 2010, 1 : 475 - 487
  • [4] Partition decision trees: representation for efficient computation of the Shapley value extended to games with externalities
    Skibski, Oskar
    Michalak, Tomasz P.
    Sakurai, Yuko
    Wooldridge, Michael
    Yokoo, Makoto
    AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS, 2020, 34 (01)
  • [5] A recursive core for partition function form games
    László Á. Kóczy
    Theory and Decision, 2007, 63 : 41 - 51
  • [6] A recursive core for partition function form games
    Koczy, Laszlo A.
    THEORY AND DECISION, 2007, 63 (01) : 41 - 51
  • [7] The recursive nucleolus for partition function form games
    Yang, Guangjing
    Sun, Hao
    JOURNAL OF MATHEMATICAL ECONOMICS, 2023, 104
  • [8] Algorithms for computing the Shapley value of cooperative games on lattices
    Maafa, Khaled
    Nourine, Lhouari
    Radjef, Mohammed Said
    DISCRETE APPLIED MATHEMATICS, 2018, 249 : 91 - 105
  • [9] Convexity and the Shapley value of Bertrand oligopoly TU-games in β-characteristic function form
    Hou, Dongshuang
    Lardon, Aymeric
    Driessen, Theo
    THEORY AND DECISION, 2025,
  • [10] A Graphical Representation for Games in Partition Function Form
    Skibski, Oskar
    Michalak, Tomasz P.
    Sakurai, Yuko
    Wooldridge, Michael
    Yokoo, Makoto
    PROCEEDINGS OF THE TWENTY-NINTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2015, : 1036 - 1042
12345