Path cooperative games

Qizhi Fang; Bo Li; Xiaohan Shan; Xiaoming Sun

doi:10.1007/s10878-018-0296-4

Path cooperative games

Qizhi Fang, Bo Li, Xiaohan Shan, Xiaoming Sun

Research output: Journal article publication › Journal article › Academic research › peer-review

Abstract

Cooperative games provide an appropriate framework for fair and stable profit distribution in multiagent systems. In this paper, we study the algorithmic issues on path cooperative games that arise from the situations where some commodity flows through a network. In these games, a coalition of edges or vertices is successful if they establish a path from the source to the sink in the network, and lose otherwise. Based on dual theory of linear programming and the relationship with flow games, we provide the characterizations on the core, CS-core, least-core and nucleolus of path cooperative games, which implies all of these solution concepts are polynomial-time solvable for path cooperative games.

Original language	English
Pages (from-to)	211-229
Number of pages	19
Journal	Journal of Combinatorial Optimization
Volume	36
Issue number	1
DOIs	https://doi.org/10.1007/s10878-018-0296-4
Publication status	Published - 1 Jul 2018
Externally published	Yes

Keywords

Core
CS-core
Least-core
Nucleolus
Path cooperative games

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

More information

10.1007/s10878-018-0296-4

Cite this

@article{be914de1eeb84542a0ecdf6d6a7c1c59,

title = "Path cooperative games",

abstract = "Cooperative games provide an appropriate framework for fair and stable profit distribution in multiagent systems. In this paper, we study the algorithmic issues on path cooperative games that arise from the situations where some commodity flows through a network. In these games, a coalition of edges or vertices is successful if they establish a path from the source to the sink in the network, and lose otherwise. Based on dual theory of linear programming and the relationship with flow games, we provide the characterizations on the core, CS-core, least-core and nucleolus of path cooperative games, which implies all of these solution concepts are polynomial-time solvable for path cooperative games.",

keywords = "Core, CS-core, Least-core, Nucleolus, Path cooperative games",

author = "Qizhi Fang and Bo Li and Xiaohan Shan and Xiaoming Sun",

note = "Funding Information: An extended abstract of this paper appears at the The 21st Annual International Computing and Combinatorics Conference (COCOON?15) Fang et?al. (2015). The first author is supported by the National Natural Science Foundation of China (NSFC) (No. 11271341). The fourth author is supported in part by the National Natural Science Foundation of China Grant 61433014, 61502449, 61602440, the 973 Program of China Grants No. 2016YFB1000201. Finally, we would like to acknowledge our editors and a superb set of anonymous referees for their excellent suggestions. Publisher Copyright: {\textcopyright} 2018, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2018",

month = jul,

day = "1",

doi = "10.1007/s10878-018-0296-4",

language = "English",

volume = "36",

pages = "211--229",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - Path cooperative games

AU - Fang, Qizhi

AU - Li, Bo

AU - Shan, Xiaohan

AU - Sun, Xiaoming

N1 - Funding Information: An extended abstract of this paper appears at the The 21st Annual International Computing and Combinatorics Conference (COCOON?15) Fang et?al. (2015). The first author is supported by the National Natural Science Foundation of China (NSFC) (No. 11271341). The fourth author is supported in part by the National Natural Science Foundation of China Grant 61433014, 61502449, 61602440, the 973 Program of China Grants No. 2016YFB1000201. Finally, we would like to acknowledge our editors and a superb set of anonymous referees for their excellent suggestions. Publisher Copyright: © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2018/7/1

Y1 - 2018/7/1

N2 - Cooperative games provide an appropriate framework for fair and stable profit distribution in multiagent systems. In this paper, we study the algorithmic issues on path cooperative games that arise from the situations where some commodity flows through a network. In these games, a coalition of edges or vertices is successful if they establish a path from the source to the sink in the network, and lose otherwise. Based on dual theory of linear programming and the relationship with flow games, we provide the characterizations on the core, CS-core, least-core and nucleolus of path cooperative games, which implies all of these solution concepts are polynomial-time solvable for path cooperative games.

AB - Cooperative games provide an appropriate framework for fair and stable profit distribution in multiagent systems. In this paper, we study the algorithmic issues on path cooperative games that arise from the situations where some commodity flows through a network. In these games, a coalition of edges or vertices is successful if they establish a path from the source to the sink in the network, and lose otherwise. Based on dual theory of linear programming and the relationship with flow games, we provide the characterizations on the core, CS-core, least-core and nucleolus of path cooperative games, which implies all of these solution concepts are polynomial-time solvable for path cooperative games.

KW - Core

KW - CS-core

KW - Least-core

KW - Nucleolus

KW - Path cooperative games

UR - http://www.scopus.com/inward/record.url?scp=85046436983&partnerID=8YFLogxK

U2 - 10.1007/s10878-018-0296-4

DO - 10.1007/s10878-018-0296-4

M3 - Journal article

AN - SCOPUS:85046436983

SN - 1382-6905

VL - 36

SP - 211

EP - 229

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 1

ER -

Path cooperative games

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this