Sharing Supermodular Costs
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 opti...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
INFORMS
2011
|
| Online Access: | http://hdl.handle.net/1721.1/67659 https://orcid.org/0000-0002-9595-459X |
| _version_ | 1826208969732915200 |
|---|---|
| author | Schulz, Andreas S. Uhan, Nelson A. |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Schulz, Andreas S. Uhan, Nelson A. |
| author_sort | Schulz, Andreas S. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T14:15:18Z |
| format | Article |
| id | mit-1721.1/67659 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:15:18Z |
| publishDate | 2011 |
| publisher | INFORMS |
| record_format | dspace |
| spelling | mit-1721.1/676592022-10-01T20:08:05Z Sharing Supermodular Costs Schulz, Andreas S. Uhan, Nelson A. Sloan School of Management Schulz, Andreas S. Schulz, Andreas S. 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. National Science Foundation (U.S.) (DMI-0426686) 2011-12-14T14:08:03Z 2011-12-14T14:08:03Z 2010-07 2009-11 Article http://purl.org/eprint/type/JournalArticle 0030-364X 1526-5463 http://hdl.handle.net/1721.1/67659 Schulz, A. S., and N. A. Uhan. “Sharing Supermodular Costs.” Operations Research 58.4-Part-2 (2010) : 1051-1056. https://orcid.org/0000-0002-9595-459X en_US http://dx.doi.org/10.1287/opre.1100.0841 Operations Research Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf INFORMS Prof. Andreas Schulz |
| spellingShingle | Schulz, Andreas S. Uhan, Nelson A. Sharing Supermodular Costs |
| title | Sharing Supermodular Costs |
| title_full | Sharing Supermodular Costs |
| title_fullStr | Sharing Supermodular Costs |
| title_full_unstemmed | Sharing Supermodular Costs |
| title_short | Sharing Supermodular Costs |
| title_sort | sharing supermodular costs |
| url | http://hdl.handle.net/1721.1/67659 https://orcid.org/0000-0002-9595-459X |
| work_keys_str_mv | AT schulzandreass sharingsupermodularcosts AT uhannelsona sharingsupermodularcosts |