THESIS
2015
x, 116 pages : illustrations ; 30 cm
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 f...[
Read more ]
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.
Post a Comment