1997年2月
Complexity of the minimum base game on matroids
MATHEMATICS OF OPERATIONS RESEARCH
- ,
- ,
- ,
- 巻
- 22
- 号
- 1
- 開始ページ
- 146
- 終了ページ
- 164
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1287/moor.22.1.146
- 出版者・発行元
- INFORMS
This paper studies the complexity of computing solution concepts for a cooperative game, called the minimum base game (MEG) (E, c), where its characteristic function c:2(E) --> N is defined as c(S) = (the weight w(B) of a minimum weighted base B subset of or equal to S), for a given matroid M=(E, J) and a weight function w: E --> N. The minimum base game contains, as a special case, the minimum spanning tree game (MSTG) in an edge-weighted graph in which players are located on the edges. By interpreting solution concepts of games (such as core, tau-value and Shapley value) in terms of matroid theory, we obtain: The core of MBG is nonempty if and only if the matroid M has no circuit consisting only of edges with negative weights; checking the concavity and subadditivity of an MBG can be done in oracle-polynomial time; the tau-value of an MBG exists if and only if the core is not empty, the tau-value of MSTG can be computed in polynomial time while there is no oracle-polynomial algorithm for a general MEG; computing the Shapley value of an MSTG is #P-complete, and there is no oracle-polynomial algorithm for computing the Shapley-value bf an MEG.
- リンク情報
-
- DOI
- https://doi.org/10.1287/moor.22.1.146
- DBLP
- https://dblp.uni-trier.de/rec/journals/mor/NagamochiZKI97
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:A1997WQ67400006&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/mor/mor22.html#journals/mor/NagamochiZKI97
- ID情報
-
- DOI : 10.1287/moor.22.1.146
- ISSN : 0364-765X
- eISSN : 1526-5471
- DBLP ID : journals/mor/NagamochiZKI97
- Web of Science ID : WOS:A1997WQ67400006