Sharing Supermodular Costs

Andreas S. Schulz () and Nelson A. Uhan ()
Additional contact information
Andreas S. Schulz: Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Nelson A. Uhan: School of Industrial Engineering, Purdue University, West Lafayette, Indiana 47907

Operations Research, 2010, vol. 58, issue 4-part-2, 1051-1056

Abstract: We study cooperative games with supermodular costs. We show that supermodular costs arise in a variety of situations; in particular, we show that the problem of minimizing a linear function over a supermodular polyhedron---a problem that often arises in combinatorial optimization---has supermodular optimal costs. In addition, we examine the computational complexity of the least core and least core value of supermodular cost cooperative games. We show that the problem of computing the least core value of these games is strongly NP-hard and, in fact, is inapproximable within a factor strictly less than 17/16 unless P = NP. For a particular class of supermodular cost cooperative games that arises from a scheduling problem, we show that the Shapley value---which, in this case, is computable in polynomial time---is in the least core, while computing the least core value is NP-hard.

Keywords: games/group decisions; cooperative; analysis of algorithms; computational complexity; mathematics; combinatorics (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1100.0841 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:58:y:2010:i:4-part-2:p:1051-1056

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().