Skip to main content
Kent Academic Repository

Finding the nucleoli of large cooperative games

Nguyen, Tri-Dung, Thomas, Lyn (2016) Finding the nucleoli of large cooperative games. European Journal of Operational Research, 248 (3). pp. 1078-1092. ISSN 0377-2217. (doi:10.1016/j.ejor.2015.08.017) (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:93644)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided.
Official URL:
http://dx.doi.org/10.1016/j.ejor.2015.08.017

Abstract

The nucleolus is one of the most important solution concepts in cooperative game theory as a result of its attractive properties - it always exists (if the imputation is non-empty), is unique, and is always in the core (if the core is non-empty). However, computing the nucleolus is very challenging because it involves the lexicographical minimization of an exponentially large number of excess values. We present a method for computing the nucleoli of large games, including some structured games with more than 50 players, using nested linear programs (LP). Although different variations of the nested LP formulation have been documented in the literature, they have not been used for large games because of the large size and number of LPs involved. In addition, subtle issues such as how to deal with multiple optimal solutions and with tight constraint sets need to be resolved in each LP in order to formulate and solve the subsequent ones. Unfortunately, this technical issue has been largely overlooked in the literature. We treat these issues rigorously and provide a new nested LP formulation that is smaller in terms of the number of large LPs and their sizes. We provide numerical tests for several games, including the general flow games, the coalitional skill games and the weighted voting games, with up to 100 players. © 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.

Item Type: Article
DOI/Identification number: 10.1016/j.ejor.2015.08.017
Uncontrolled keywords: Computation theory; Computer games; Linear programming, Constraint generation; Cooperative game; Multilevel programming; Nucleolus; Payoff distribution, Game theory
Subjects: H Social Sciences
Divisions: Divisions > Kent Business School - Division > Department of Analytics, Operations and Systems
Depositing User: Tri-Dung Nguyen
Date Deposited: 17 Mar 2022 15:23 UTC
Last Modified: 17 Aug 2022 12:22 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/93644 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.