Approximating the least core value and least core of cooperative games with supermodular costs

被引:31
作者
Schulz, Andreas S. [1 ,2 ]
Uhan, Nelson A. [3 ]
机构
[1] MIT, Alfred P Sloan Sch Management, Cambridge, MA 02142 USA
[2] MIT, Ctr Operat Res, Cambridge, MA 02142 USA
[3] USN Acad, Dept Math, Annapolis, MD 21402 USA
基金
美国国家科学基金会;
关键词
Cooperative games; Least core; Approximation algorithms; Scheduling; Matroids; SCHEDULING INDEPENDENT TASKS; TOTALLY BALANCED GAMES; SPANNING TREE GAMES; LOT-SIZING GAMES; BARGAINING SET; ALGORITHMS; COMPLEXITY; NUCLEOLUS; ALLOCATION;
D O I
10.1016/j.disopt.2013.02.002
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on oracles that approximately determine maximally violated constraints. This framework yields a 3-approximation algorithm for computing the least core value of supermodular cost cooperative games, and a polynomial-time algorithm for computing a cost allocation in the 2-approximate least core of these games. This approximation framework extends naturally to submodular profit cooperative games. For scheduling games, a special class of supermodular cost cooperative games, we give a fully polynomial-time approximation scheme for computing the least core value. For matroid profit games, a special class of submodular profit cooperative games, we give exact polynomial-time algorithms for computing the least core value as well as a least core cost allocation. Published by Elsevier B.V.
引用
收藏
页码:163 / 180
页数:18
相关论文
共 55 条
[1]  
[Anonymous], 1972, DECISION ORG
[2]  
[Anonymous], 1971, Internat. J. Game Theory
[3]  
[Anonymous], 1988, THE SHAPLEY VALUE
[4]  
[Anonymous], MATH METHOD OPER RES
[5]  
Aumann RJ, 1964, Advances in Game Theory, V52, P443, DOI 10.1515/9781400882014-022
[6]   COST ALLOCATION FOR A SPANNING TREE - GAME THEORETIC APPROACH [J].
BIRD, CG .
NETWORKS, 1976, 6 (04) :335-350
[7]   SCHEDULING INDEPENDENT TASKS TO REDUCE MEAN FINISHING TIME [J].
BRUNO, J ;
COFFMAN, EG ;
SETHI, R .
COMMUNICATIONS OF THE ACM, 1974, 17 (07) :382-387
[8]   A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization [J].
Buchbinder, Niv ;
Feldman, Moran ;
Naor, Joseph ;
Schwartz, Roy .
2012 IEEE 53RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2012, :649-658
[9]   Randomized metarounding [J].
Carr, R ;
Vempala, S .
RANDOM STRUCTURES & ALGORITHMS, 2002, 20 (03) :343-352
[10]  
Chen X., 2006, OM200601 IOMS NEW YO