The least-core and nucleolus of path cooperative games

Qizhi Fang, Bo Li, Xiaohan Shan, Xiaoming Sun

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

4 Citations (Scopus)

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 CS-core, least-core and nucleolus of path cooperative games. Furthermore, we show that the least-core and nucleolus are polynomially solvable for path cooperative games defined on both directed and undirected network.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings
EditorsDachuan Xu, Donglei Du, Dingzhu Du
PublisherSpringer Verlag
Pages70-82
Number of pages13
ISBN (Print)9783319213972
DOIs
Publication statusPublished - 2015
Externally publishedYes
Event21st International Conference on Computing and Combinatorics Conference, COCOON 2015 - Beijing, China
Duration: 4 Aug 20156 Aug 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9198
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on Computing and Combinatorics Conference, COCOON 2015
Country/TerritoryChina
CityBeijing
Period4/08/156/08/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this