On the core and nucleolus of directed acyclic graph games

• 成果类型: Article
• 署名作者: Sziklai, Balazs; Fleiner, Tamas; Solymosi, Tamas
• 署名单位: HUN-REN; HUN-REN Centre for Economic & Regional Studies; Hungarian Academy of Sciences; Corvinus University Budapest; Budapest University of Technology & Economics; Hungarian Academy of Sciences
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1062-y
• 发表日期: 2017
• 页码: 243-271
• 关键词: spanning tree games; characterization sets; allocation rules; cost allocation; Network games; complexity

摘要

We introduce directed acyclic graph (DAG) games, a generalization of standard tree games, to study cost sharing on networks. This structure has not been previously analyzed from a cooperative game theoretic perspective. Every monotonic and subadditive cost game-including monotonic minimum cost spanning tree games-can be modeled as a DAG-game. We provide an efficiently verifiable condition satisfied by a large class of directed acyclic graphs that is sufficient for the balancedness of the associated DAG-game. We introduce a network canonization process and prove various structural results for the core of canonized DAG-games. In particular, we characterize classes of coalitions that have a constant payoff in the core. In addition, we identify a subset of the coalitions that is sufficient to determine the core. This result also guarantees that the nucleolus can be found in polynomial time for a large class of DAG-games.