Computing the nucleolus of weighted voting games

ABSTRACT

Weighted voting games (WVG) are coalitional games in which an agent's contribution to a coalition is given by his weight, and a coalition wins if its total weight meets or exceeds a given quota. These games model decision-making in political bodies as well as collaboration and surplus division in multiagent domains. The computational complexity of various solution concepts for weighted voting games received a lot of attention in recent years. In particular, Elkind et al.(2007) studied the complexity of stability-related solution concepts in WVGs, namely, of the core, the least core, and the nucleolus. While they have completely characterized the algorithmic complexity of the core and the least core, for the nucleolus they have only provided an NP-hardness result. In this paper, we solve an open problem posed by Elkind et al. by showing that the nucleolus of WVGs, and, more generally, k-vector weighted voting games with fixed k, can be computed in pseudopolynomial time, i.e., there exists an algorithm that correctly computes the nucleolus and runs in time polynomial in the number of players n and the maximum weight W. In doing so, we propose a general framework for computing the nucleolus, which may be applicable to a wider of class of games.

REFERENCES

• 1: J. F. Banzhaf. Weighted voting doesn't work: a mathematical analysis. Rutgers Law Review, 19:317--343, 1965.
• 2: J. M. Bilbao, J. R. Fernández, N. Jiminéz, and J. J. López. Voting power in the European Union enlargement. European Journal of Operational Research, 143:181--196, 2002.
• 3: Xiaotie Deng , Qizhi Fang , Xiaoxun Sun, Finding nucleolus of flow game, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.124-131, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109572]
• 4: Xiaotie Deng , Christos H. Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research, v.19 n.2, p.257-266, May 1994 [doi>10.1287/moor.19.2.257]
• 5: E. Elkind, L. A. Goldberg, P. W. Goldberg, and M. Wooldridge. Computational complexity of weighted threshold games. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, volume 1, pages 718--723, Menlo Park, California, 2007. AAAI Press. ISBN 978-1-57735-323-2.
• 6: M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993.
• 7: H. Hamers, F. Klijn, T. Solymosi, S. Tijs, and D. Vermeulen. On the nucleolus of neighbor games. European J. Oper. Res., 146(1):1--18, 2003.
• 8: Walter Kern , Daniël Paulusma, Matching games: the least core and the nucleolus, Mathematics of Operations Research, v.28 n.2, p.294-308, May 2003 [doi>10.1287/moor.28.2.294.14477]
• 9: A. Kopelowitz. Computation of the kernels of simple games and the nucleolus of n-person games. Preprint RM 37, 1967. Research Program in Game Theory and Mathematical Economics.
• 10: T. Matsui and Y. Matsui. A survey of algorithms for calculating power indices of weighted majority games. J. Oper. Res. Soc. Japan, 43(1):71--86, 2000. New trends in mathematical programming (Kyoto, 1998).
• 11: S. Muroga. Threshold Logic and its Applications. John Wiley & Sons, 1971.
• 12: M. Núñez. A note on the nucleolus and the kernel of the assignment game. Internat. J. Game Theory, 33(1):55--65, 2004.
• 13: K. Prasad , J. S. Kelly, NP-completeness of some problems concerning voting games, International Journal of Game Theory, v.19 n.1, p.1-9, Apr. 1990 [doi>10.1007/BF01753703]
• 14: H. Reijnierse, J. Potters, A. Biswas. The nucleolus of balanced simple flow networks. Games and Economic Behavior, 54 (1), 205--225, 2006.
• 15: D. Schmeidler. The nucleolus of a characteristic function game. SIAM J. Appl. Math., 17:1163--1170, 1969.
• 16: Alexander Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 17: L. S. Shapley and M. Shubik. A method for evaluating the distribution of power in a committee system. In The Shapley value, pages 41--48. Cambridge Univ. Press, Cambridge, 1988.
• 18: T. Solymosi, T. E. S. Raghavan, and S. Tijs. Computing the nucleolus of cyclic permutation games. European J. Oper. Res., 162(1):270--280, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents