Sharing supermodular costs

Sharing supermodular costs

0.00 Avg rating0 Votes
Article ID: iaor20105603
Volume: 58
Issue: 4-Part-2
Start Page Number: 1051
End Page Number: 1056
Publication Date: Jul 2010
Journal: Operations Research
Authors: ,
Keywords: Shapley value
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.

Reviews

Required fields are marked *. Your email address will not be published.