To stabilize grand coalitions in unbalanced cooperative games

Abstract

In an unbalanced cooperative game whose core is empty, the grand coalition is not sustainable. We consider the case where an outside third party might be interested in stable functioning of the grand coalition since it leads to the optimal social welfare. In this thesis, We investigate several instruments for the outside third party to sustain the stability of the grand coalition for unbalanced cooperative games. Our models and algorithms are generic for a class of cooperative games, and we also show the implementation for specific games arising from logistics applications. We first study the instrument of subsidizing, where the third party will provide an amount of external subsidy if all the players cooperate together such that the grand coalition is then the optimal choice for all the players. The focus in this instrument is to minimize the subsidy provided by the third party. One way to tackle this problem is to solve the so-called optimal cost allocation that satisfies the coalitional stability constraints and maximizes the total cost allocated to all the players. The gap between the grand coalition cost and the maximal total shared cost is the minimum subsidy to provide. 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. In particular, our approach provides a standard framework that is easy to follow, is able to generate a more competitive cost allocation than LP-based algorithms, and is applicable to a broader range of problems. To illustrate the efficiency and performance of the Lagrangian framework, we investigate four types of facility location games. The computational results show that we can find cost allocations better than LP-based algorithms, or provide alternative optimal solutions for situations where the LP-based algorithm is proven to be optimal. The instrument of penalizing is another way to stabilize the grand coalition, where a coalition is required to pay a deviating cost if they leave the grand coalition. Unlike the first instrument, which is at the social opportunity cost of the third party, the instrument of penalizing will cause dissatisfaction of players. In the second part of the thesis, we propose a new scheme, referred to as simultaneously subsidizing and penalizing, that integrates the instruments of subsidizing and penalizing. The key idea of our scheme is to use some external subsidy to reduce the penalty to be imposed to the players who may deviate from the grand coalition. We establish a model that allows a decision maker to quantify the trade off between subsidy and penalty levels, from which we also analytically derive some properties regarding the trade off. Because the problem is computationally difficult, we further provide a generic framework for developing heuristic algorithms for computation, and implement the algorithms on TSP games. Besides the conventional instruments, in the third part of the thesis, we propose a new approach to stabilize the grand coalition for the uncapacitated facility location game. To be specific, the third party can purposely forbid some arcs, e.g., by installing toll stations, such that (1) the resulting uncapacitated facility location game has a non-empty core; (2) the total cost to be shared among all the players stay unchanged; and (3) the total number of toll stations installed is minimized. By investigating the primal-dual relationship, we are able to formulate the problem by a mixed integer linear programming. We further present ways to strengthen the formulation by adding tight constraints. We demonstrate the effectiveness of the formulation by extensive computational experiments.

Date of Award	2015
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology