Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/65467
Title: Computing near-optimal stable cost allocations for cooperative games by lagrangian relaxation
Authors: Liu, L
Qi, X
Xu, Z 
Keywords: Cooperative game
Cost allocation
Facility location game
Game theory
Lagrangian relaxation
Issue Date: 2016
Publisher: INFORMS Inst.for Operations Res.and the Management Sciences
Source: Informs journal on computing, 2016, v. 28, no. 4, p. 687-702 How to cite?
Journal: Informs journal on computing 
Abstract: For a cost-sharing cooperative game with an empty core, we study the problem of calculating a near-optimal cost allocation that satisfies coalitional stability constraints and maximizes the total cost allocated to all players. One application of such a problem is finding the minimum level of subsidy required to stabilize the grand coalition. To obtain solutions, we propose a new generic framework based on Lagrangian relaxation, which has several advantages over existing work that exclusively relies on linear programming (LP) relaxation techniques. Our approach can generate better cost allocations than LP-based algorithms, and is also applicable to a broader range of problems. To illustrate the efficiency and performance of the Lagrangian relaxation framework, we investigate two different facility location games. The results demonstrate that our new approach can find better cost allocations than the LP-based algorithm, or provide alternative optimal cost allocations for cases that the LP-based algorithm can also solve to optimality.
URI: http://hdl.handle.net/10397/65467
ISSN: 1091-9856
DOI: 10.1287/ijoc.2016.0707
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

17
Checked on Aug 21, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.