Approximating the least core value and least core of cooperative games with supermodular costs |
| |
Authors: | Andreas S Schulz Nelson A Uhan |
| |
Institution: | 1. Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, 100 Main Street, E62-569, Cambridge, MA 02142, USA;2. Mathematics Department, United States Naval Academy, 572C Holloway Road, Chauvenet Hall, Annapolis, MD 21402, USA |
| |
Abstract: | 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. |
| |
Keywords: | Cooperative games Least core Approximation algorithms Scheduling Matroids |
本文献已被 ScienceDirect 等数据库收录! |
|