Approximating the Least Core Value and Least Core of Cooperative Games with Supermodular Costs

A. S. Schulz (schulzmit.edu)
N. A. Uhan (uhanusna.edu)

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 + \epsilon)-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:

Category 1: Other Topics (Game Theory )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: Discrete Optimization, available online, March 2013. DOI: 10.1016/j.disopt.2013.02.002

Download:

Entry Submitted: 06/23/2010
Entry Accepted: 07/02/2010
Entry Last Modified: 03/25/2013

Modify/Update this entry