-

 

 

 




Optimization Online





 

Sharing Supermodular Costs

Andreas S. Schulz (schulz***at***mit.edu)
Nelson A. Uhan (nuhan***at***purdue.edu)

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:

Category 1: Other Topics (Game Theory )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: Operations Research. http://dx.doi.org/10.1287/opre.1100.0841

Download:

Entry Submitted: 08/28/2007
Entry Accepted: 08/28/2007
Entry Last Modified: 08/04/2010

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society