Zhi-Gang Cao and Xiao-Guang Yang. Coalition Formation in Weighted Simple-majority Games under Proportional Payoff Allocation Rules. International Journal of Automation and Computing, vol. 6, no. 3, pp. 217-222, 2009. DOI: 10.1007/s11633-009-0217-1
Citation: Zhi-Gang Cao and Xiao-Guang Yang. Coalition Formation in Weighted Simple-majority Games under Proportional Payoff Allocation Rules. International Journal of Automation and Computing, vol. 6, no. 3, pp. 217-222, 2009. DOI: 10.1007/s11633-009-0217-1

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.
  • loading

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return