Solutions for Cooperative Games with Restricted Coalition Formation and Almost Core Allocations
Rong Zou is a PhD student in the department Mathematics of Operations Research. Supervisors are prof.dr. M.J. Uetz from the faculty of Electrical Engineering, Mathematics and Computer Science and prof.dr. G. Xu from the Northwestern Polytechnical University, China.
The thesis focuses on cooperative games with transferable utility and incorporates two topics: Solutions for TU-games restricted by cooperation structures and the stability of the grand coalition. While Chapters 3-5 contribute to the former topic with coming up with new solutions and justifying their reasonableness by different approaches, Chapter 6 deals with the latter topic by studying an optimization problem over the set of all stable allocations which we refer to as the almost core.
Chapter 3 is devoted to a new solution for cooperative games with coalition structures, called the α-egalitarian Owen value. This coalitional value extends the α-egalitarian Shapley value (Joosten, 1996) to coalition structure setting. Three approaches are used to characterize this coalitional value. Firstly, we provide two axiomatizations by introducing the α-indemnificatory null player axiom, and the (intra) coalitional quasi-balanced contributions axiom. Secondly, we define an α-guarantee potential function to show that the payoff vector equals the α-egalitarian Owen value. Finally, the coalitional value is implemented by a punishment-reward bidding mechanism. As to future work, it would be interesting to axiomatize the proposed coalitional value based on other axiomatic systems without additivity, such as axioms related to monotonicity (Young, 1985) and associated consistency (Hamiache, 2001).
In Chapter 4, we continue to work with TU-games restricted by coalition structures and propose a coalitional value called the two-step Shapley-solidarity value. In comparison to the two-step Shapley value proposed by Kamijo (Kamijo, 2009), the difference lies in the idea to distribute the worth of a union among its members based on the solidarity value (Nowak & Radzik, 1994}, which implements the solidarity principle for the unions. We provide a procedural interpretation of the two-step Shapley-solidarity value. Moreover, we introduce a new axiom called the coalitional A-null player axiom to axiomatize the value based on additivity. Two other axiomatizations on the basis of quasi-balanced contributions for the grand coalition are also provided to further highlight the precise similarities and differences between our two-step coalitional value and the two-step Shapley value. Except for the given axiomatizations, a non-cooperative implementation of the two-step Shapley-solidarity value based on a bidding mechanism could be considered for future work. In addition, one may study the two coalitional values proposed in the thesis for fuzzy cooperative games with coalition structures.
In Chapter 5, we focus on cooperative games with communication structures and provide efficient extensions of the Myerson value (Myerson, 1977). The idea lies in introducing the Shapley payoffs of the underlying game as players' claims to derive a graph-induced bankruptcy problem. Then, two efficient extensions of the Myerson value are achieved through bankruptcy rules, including the CEA rule and the CEL rule (Aumann & Maschler, 1985).
In line with the spirit of the axioms satisfied by the CEA rule, we introduce two axioms called the sustainability in surplus axiom and the weak fair distribution surplus axiom to axiomatize the efficient constrained equal awards Myerson value. Similarly, we provide an axiomatization for the efficient constrained equal losses Myerson value by defining the so-called residual in surplus axiom and surplus marginality with non-residual players axiom. It remains interesting to consider other bankruptcy rules in a future work, the Talmud rule (Aumann & Maschler, 1985) and the random arrival rule (O’Neill, 1982), for example. Moreover, this approach could also be applied to deal with efficient extensions of the Aumann-Drèze value (AD-value) (Aumann & Drèze, 1974} for cooperative games with coalition structures.
Chapter 6 proceeds with studying the stability of the grand coalition for cost TU-games by addressing an optimization problem to maximize the total shareable cost over what we called the almost core. We analyze the computational complexity of this optimization problem, in relation to the computational complexity of related problems for the core. For games with an empty core, it turns out that it is equivalent to optimization problems for several core relaxations that have been proposed earlier. For games with a non-empty core, we specifically consider the minimum cost spanning tree games as an example of subadditive games with non-empty cores for which it is computationally easy to find a core element. We show that maximizing the total shareable costs over the (non-negative) almost core is NP-hard for mcst games, and we provide a 2-approximation algorithm for this almost core optimization problem under the additional assumption that no subsidy is allowed. It would be interesting to gain more insights into the computational complexity of the almost core problem, possible generalizations, and also for other classes of games.
