×

Simple games versus weighted voting games: bounding the critical threshold value. (English) Zbl 1436.91060

Summary: A simple game \((N,v)\) is given by a set \(N\) of \(n\) players and a partition of \(2^N\) into a set \(\mathcal{L}\) of losing coalitions \(L\) with value \(v(L)=0\) that is closed under taking subsets and a set \(\mathcal{W}\) of winning coalitions \(W\) with value \(v(W)=1\). We let \(\alpha = \min_{p\geq \mathbf{0},\, p\neq \mathbf{0}} \max_{W\in \mathcal{W}, \,L\in \mathcal{L}}\, \frac{p(L)}{p(W)}\). It is known that the subclass of simple games with \(\alpha <1\) coincides with the class of weighted voting games. Hence, \( \alpha\) can be seen as a measure of the distance between a simple game and the class of weighted voting games. We prove that \(\alpha \leqslant \frac{1}{4}n\) holds for every simple game \((N,v)\), confirming the conjecture of J. Freixas and S. Kurz [Int. J. Game Theory 43, No. 3, 659–692 (2014; Zbl 1304.91021)]. For complete simple games, Freixas and Kurz conjectured that \(\alpha =O(\sqrt{n})\). We also prove this conjecture, up to an \(\ln n\) factor. Moreover, we prove that for graphic simple games, that is, simple games in which every minimal winning coalition has size 2, the problem of computing \(\alpha\) is NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Finally, we show that for every graphic simple game, deciding if \(\alpha <\alpha_0\) is polynomial-time solvable for every fixed \(\alpha_0>0\).

MSC:

91B12 Voting theory
91A12 Cooperative games
91A68 Algorithmic game theory and complexity

Citations:

Zbl 1304.91021

References:

[1] Abdi A (2018) Ideal clutters. Ph.D. thesis, University of Waterloo · Zbl 1435.90117
[2] Axenovich, M.; Roy, S., On the structure of minimal winning coalitions in simple voting games, Soc Choice Welf, 34, 429-440 (2010) · Zbl 1201.91046 · doi:10.1007/s00355-009-0408-2
[3] Bachrach, Y.; Elkind, E.; Malizia, E.; Meir, R.; Pasechnik, D.; Rosenschein, J.; Rothe, J.; Zuckerman, M., Bounds on the cost of stabilizing a cooperative game, J Artif Intell Res, 63, 987-1023 (2018) · Zbl 1454.91012 · doi:10.1613/jair.1.11270
[4] Balas, E.; Yu, CS, On graphs with polynomially solvable maximum-weight clique problem, Networks, 19, 247-253 (1989) · Zbl 0661.05036 · doi:10.1002/net.3230190206
[5] Bilbao, JM; García, JRF; Jiménez, N.; López, JJ, Voting power in the European Union enlargement, Eur J Oper Res, 143, 181-196 (2002) · Zbl 1073.91539 · doi:10.1016/S0377-2217(01)00334-4
[6] Biro, P.; Kern, W.; Paulusma, D., Computing solutions for matching games, Int J Game Theory, 41, 75-90 (2012) · Zbl 1232.91026 · doi:10.1007/s00182-011-0273-y
[7] Bock, A.; Chandrasekaran, K.; Könemann, J.; Peis, B.; Sanitá, L., Finding small stabilizers for unstable graphs, Math Program, 154, 173-196 (2015) · Zbl 1337.05085 · doi:10.1007/s10107-014-0854-1
[8] Borwein, J.; Lewis, A., Convex analysis and nonlinear optimization (2000), Berlin: Springer, Berlin · Zbl 0953.90001
[9] Brandstädt, A.; Mosca, R., Maximum weight independent set in \(l\) claw-free graphs in polynomial time, Discret Appl Math, 237, 57-64 (2018) · Zbl 1380.05147 · doi:10.1016/j.dam.2017.11.029
[10] Carreras, F.; Freixas, J., On power distribution in weighted voting, Soc Choice Welf, 24, 269-282 (2005) · Zbl 1100.91015 · doi:10.1007/s00355-003-0302-2
[11] Chalkiadakis, G.; Elkind, E.; Wooldridge, M., Computational aspects of cooperative game theory (2011), San Rafael: Morgan and Claypool Publishers, San Rafael
[12] Deineko, VG; Woeginger, GJ, On the dimension of simple monotonic games, Eur J Oper Res, 170, 315-318 (2006) · Zbl 1134.68369 · doi:10.1016/j.ejor.2004.09.038
[13] Edmonds, J.; Fulkerson, D., Bottleneck extrema, J Comb Theory, 8, 299-306 (1970) · Zbl 0218.05006 · doi:10.1016/S0021-9800(70)80083-7
[14] Elkind E, Chalkiadakis G, Jennings NR (2008) Coalition structures in weighted voting games. In: Proceedings of ECAI 2008, frontiers in artificial intelligence and applications, vol 178, pp 393-397
[15] Elkind, E.; Goldberg, LA; Goldberg, PW; Wooldridge, M., On the computational complexity of weighted voting games, Ann Math Artif Intell, 56, 109-131 (2009) · Zbl 1185.91081 · doi:10.1007/s10472-009-9162-5
[16] Faigle, U.; Kern, W.; Fekete, S.; Hochstaettler, W., The nucleon of cooperative games and an algorithm for matching games, Math Program, 83, 195-211 (1998) · Zbl 0920.90142
[17] Faigle, U.; Kern, W.; Still, G., Algorithmic principles of mathematical programming (2002), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 1036.90001
[18] Fishburn, P.; Brams, S., Minimal winning coalitions in weighted-majority voting games, Soc Choice Welf, 13, 397-417 (1996) · Zbl 0858.90145 · doi:10.1007/BF00182851
[19] Freixas, J.; Kurz, S., On \(\alpha \)-roughly weighted games, Int J Game Theory, 43, 659-692 (2014) · Zbl 1304.91021 · doi:10.1007/s00182-013-0402-x
[20] Freixas, J.; Marciniak, D., On the notion of dimension and codimension of simple games, Contrib Game Theory Manag, 3, 67-81 (2010) · Zbl 1204.91016
[21] Freixas, J.; Puente, MA, Dimension of complete simple games with minimum, Eur J Oper Res, 188, 555-568 (2008) · Zbl 1151.91021 · doi:10.1016/j.ejor.2007.03.050
[22] Freixas, J.; Molinero, X.; Olsen, M.; Serna, M., On the complexity of problems on simple games, RAIRO Oper Res, 45, 295-314 (2011) · Zbl 1235.68082 · doi:10.1051/ro/2011115
[23] Garey, MR; Johnson, DS, Computers and intractability: a guide to the theory of np-completeness (1979), New York: W. H. Freeman & Co., New York · Zbl 0411.68039
[24] Gvozdeva, T.; Hemaspaandra, LA; Slinko, A., Three hierarchies of simple games parameterized by “resource” parameters, Int J Game Theory, 42, 1-17 (2013) · Zbl 1282.91029 · doi:10.1007/s00182-011-0308-4
[25] Hegedüs, T.; Megiddo, N., On the geometric separability of Boolean functions, Discret Appl Math, 66, 205-218 (1996) · Zbl 0854.68034 · doi:10.1016/0166-218X(94)00161-6
[26] Hof F, Kern W, Kurz S, Paulusma D (2018) Simple games versus weighted voting games. In: Proceedings of SAGT 2018, LNCS 11059, pp 69-81 · Zbl 1415.91028
[27] Isbell, JR, A class of majority games, Q J Math, 7, 183-187 (1956) · Zbl 0073.13401 · doi:10.1093/qmath/7.1.183
[28] Kern, W.; Paulusma, D., Matching games: the least core and the nucleolus, Math Oper Res, 28, 294-308 (2003) · Zbl 1082.91016 · doi:10.1287/moor.28.2.294.14477
[29] Könemann J, Pashkovich K, Toth J (2019) Computing the nucleolus of weighted cooperative matching games in polynomial time. In: Proceedings of IPCO 2019, LNCS 11480, pp 413-426 · Zbl 1436.91008
[30] Kurz, S.; Molinero, X.; Olsen, M., On the construction of high dimensional simple games, Proc ECAI, 2016, 880-885 (2016) · Zbl 1396.91013
[31] Nguyen T, Zick Y (2018) Resource based cooperative games: optimization, fairness and stability. In: Proceedings of SAGT 2018, LNCS 11059, pp 239-244 · Zbl 1415.91030
[32] Pashkovich K (2018) Computing the nucleolus of weighted voting games in pseudo-polynomial time. arXiv:181002670 · Zbl 1501.91039
[33] Peled, UN; Simeone, B., Polynomial-time algorithms for regular set-covering and threshold synthesis, Discret Appl Math, 12, 57-69 (1985) · Zbl 0619.05020 · doi:10.1016/0166-218X(85)90040-X
[34] Peters, H., Game theory (2008), Berlin: Springer, Berlin · Zbl 1147.91001
[35] Schrijver, A., Theory of linear and integer programming (1998), New York: Wiley, New York · Zbl 0970.90052
[36] Shapley, LS, Simple games: an outline of the descriptive theory, Behav Sci, 7, 59-66 (1962) · doi:10.1002/bs.3830070104
[37] Solymosi, T.; Raghavan, TE, An algorithm for finding the nucleolus of assignment games, Int J Game Theory, 23, 119-143 (1994) · Zbl 0811.90128 · doi:10.1007/BF01240179
[38] Taylor, AD; Zwicker, WS, Weighted voting, multicameral representation, and power, Games Econ Behav, 5, 170-181 (1993) · Zbl 0765.90030 · doi:10.1006/game.1993.1009
[39] Taylor, AD; Zwicker, WS, Simple games: desirability relations, trading, pseudoweightings (1999), Princeton: Princeton University Press, Princeton · Zbl 0943.91005
[40] Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I., A new algorithm for generating all the maximal independent sets, SIAM J Comput, 6, 505-517 (1977) · Zbl 0364.05027 · doi:10.1137/0206036
[41] von Neumann, J.; Morgenstern, O., Theory of games and economic behavior (1944), Princeton: Princeton University Press, Princeton · Zbl 0063.05930
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.