Computing near-optimal stable cost allocations for cooperative games by lagrangian relaxation

Lindong Liu, Xiangtong Qi, Zhou Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)687-702
Number of pages16
JournalINFORMS Journal on Computing
Volume28
Issue number4
DOIs
Publication statusPublished - 1 Sep 2016

Keywords

  • Cooperative game
  • Cost allocation
  • Facility location game
  • Game theory
  • Lagrangian relaxation

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Cite this