Coalition Formation in Weighted Simple-majority Games under Proportional Payoff Allocation Rules

In this paper, we introduce a simple coalition formation game in the environment of bidding, which is a special case of the weighted majority game (WMG), and is named the weighted simple-majority game (WSMG). In WSMG, payoff is allocated to the winners proportional to the players’ powers, which can be measured in various ways. We define a new kind of stability: the counteraction-stability (C-stability), where any potential deviating players will confront counteractions of the other players. We show that C-stable coalition structures in WSMG always contains a minimal winning coalition of minimum total power. For the variant where powers are measured directly by their weights, we show that it is NP-hard to find a C-stable coalition structure and design a pseudo-polynomial time algorithm. Sensitivity analysis for this variant, which shows many interesting properties, is also done. We also prove that it is NP-hard to compute the Holler-Packel indices in WSMGs, and hence in WMGs as well. This work was supported by National Natural Science Foundation of China (No. 70425004). Zhi-Gang Cao received the B. Sc. degree in mathematics, and M. Sc. degree in operations research from Qufu Normal University, PRC in 2003 and 2006, respectively. He is currently a Ph. D. candidate in the Key Laboratory of Management, Decision and Information Systems, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, PRC. His research interests include coalitional games, algorithmic game theory, and combinatorial optimization. Xiao-Guang Yang received the B. Sc. degree in mathematics and the Ph. D. degree in operations research, both from Tsinghua University, PRC in 1986 and 1993, respectively. He is currently a professor as well as the deputy director of the Key Laboratory of Management, Decision and Information Systems, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, PRC. His research interests include risk management, macroeconomic analysis, game theory, and combinatorial optimization.