University of Twente Student Theses


Almost Core Allocations on Minimum Cost Spanning Tree Games

Lin, Boyue (2022) Almost Core Allocations on Minimum Cost Spanning Tree Games.

[img] PDF
Abstract:In cooperative game theory, a core allocation guarantees that no subset of players would prefer to deviate. However, the allocation in the core requires distributing the exact cost of the grand coalition to all individual players. This thesis studies the optimization problem to maximize the total amount that can be distributed over the individual players while maintaining the stability with respect to proper coalitions. The corresponding solution concept is referred to as “almost core”. It shows how much one could maximally tax the total cost of the grand coalition, without any proper coalition wanting to deviate. Some complexity theoretic results of almost core allocations are derived. We study almost core allocations to a class of games with non-empty core: the minimum cost spanning tree games. A tight 2-approximation algorithm to compute an almost core optimum is proposed. The algorithms to compute the almost core optimum on some constrained minimum cost spanning tree structures are also given. In addition, the almost core concept is studied for value games. It turns out that the same algorithmic results can be derived also for value games.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics MSc (60348)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page