nach oben

Social Choice and Welfare

Erschienen in:

18.01.2016 | Original Paper

The inverse problem for power distributions in committees

verfasst von: Sascha Kurz

Erschienen in: Social Choice and Welfare | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Several power indices have been introduced in the literature in order to measure the influence of individual committee members on an aggregated decision. Here we ask the inverse question and aim to design voting rules for a committee such that a given desired power distribution is met as closely as possible. We generalize the approach of Alon and Edelman who studied power distributions for the Banzhaf index, where most of the power is concentrated on few coordinates. It turned out that each Banzhaf vector of an n-member committee that is near to such a desired power distribution, also has to be near to the Banzhaf vector of a k-member committee. We show that such Alon-Edelman type results exist for other power indices like e.g. the Public Good index or the Coleman index to prevent actions, while such results are principally impossible to derive for e.g. the Johnston index.

Vorheriger Artikel Erratum to: The role of subjective beliefs in preferences for redistribution

Nächster Artikel On surplus-sharing in partnerships

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Arguably, some power indices, like the Banzhaf and the Shapley-Shubik index, are generally more accepted and applied than others. On the other hand, the pros and cons of several power indices are frequently discussed in the older and latest literature.

As an example, we mention Brams et al. (1989) arguing that the Johnston index is best suited for measuring presidential power.

There exists a stream of literature discussing the question of a fair power distribution within a committee, see e.g. Le Breton et al. (2012), Penrose (1946), Laruelle and Widgrén (1998), Shapley and Shubik (1954).

There are several more recent papers using this denomination and trying to algorithmically attack this issue. Considerations about the problem itself date back further, see. e.g. Imrie (1973), Nurmi (1982), Papayanopoulos (1983).

For completeness, we remark that there is also a stream of literature that characterizes the sets of general transferable utility games. These are more general objects than the voting procedures that we will study here. Given a certain solution concept, i.e. a more general object than a power index, their solution exactly coincides with a given vector, see e.g. Dragan (2005), Dragan (2012), Dragan (2013).

Also the website http://powerslave.val.utu.fi/indices.html has served as a source.

Several authors have tried to formalize such a common structure, see e.g. Bertini et al. (2013), Malawski (2004). Our approach is not claimed to be superior and has of course many similarities, but it seems to be more convenient in our situation.

This constructive reformulation was already implicitly contained in the proof of Alon and Edelman (2010).

See also (Taylor and Zwicker 1999, Definition 1.4.4, 1.4.7).

We remark that the set of winning coalitions \(\mathcal {W}\) can be partitioned into the sets \(\mathcal {W}_A\) for all \(A\subseteq [k]\), so that we can implicitly define a game via the definition of the set of reduced games.

The k-rounding operation is indeed a shortening function \(\mathcal {V}_n\times [n]\rightarrow \mathcal {V}_n\) for many of the most meaningful of classes \(\mathcal {V}_n\subseteq \overline{\mathcal {S}_n}\) mildly modified to satisfy a technical condition, see Lemma 4 and Corollary 1.

with respect to the \(\Vert \cdot \Vert _1\)-norm.

see Definition 7.(4).

See also (Dubey and Shapley 1979, Corollary 1).

We remark that the differences in the upper bounds are due to the tighter estimate of \(\left| \widehat{{\text {Bz}}}_i(v,2^{[n]})-\widehat{{\text {Bz}}}_i(v',2^{[n]})\right| \) in the second part of the proof of Theorem 2 compared to the estimation in Alon and Edelman (2010). The generalized bound would have been \(\Vert \widehat{P}(v')-\widehat{P}(v)\Vert _1\le \frac{(2kf_1(k)+1)\varepsilon '}{1-(kf_1(k)+1)\varepsilon '}+\varepsilon '\) using the original proof.

Exceptions are power indices based on somewhat global properties like, e.g., the nucleolus, see Schmeidler (1969), and the minimum sum representation index, see Freixas and Kaniovski (2014).

See Freixas and Kurz (2014) and Gvozdeva et al. (2013), where three hierarchies of simple games have been introduced.

Alon N, Edelman P (2010) The inverse Banzhaf problem. Soc Choice Welf 34(3):371–377CrossRef

Alonso-Meijide J, Freixas J (2010) A new power index based on minimal winning coalitions without any surplus. Decis Support Syst 49(1):70–76CrossRef

Alonso-Meijide J, Freixas J, Molinero X (2012) Computation of several power indices by generating functions. Appl Math Comput 219(8):3395–3402

Banzhaf J (1965) Weighted voting doesn’t work: a mathematical analysis. Rutgers Law Rev 19:317–343

Bertini C, Freixas J, Gambarelli G, Stach I (2013) Comparing power indices. Int. Game Theory Rev 15(2)

Bertini C, Gambarelli G, Stach I (2008) A public help index. In: Braham M, Steffen F (eds) Power, freedom, and voting. Springer, Berlin, pp 83–98

Bolger E (1986) Power indices for multicandidate voting games. Internat J Game Theory 15(3):175–186CrossRef

Braham Me, Steffen Fe (2008) Power, freedom, and voting. In: Essays in honour of Manfred J. Holler. Papers presented at the Festschrift conference, Hamburg, August 17–20, 2006. Springer, Berlin, p 438 (xiv)

Brams S, Kilgour D, Affuso P (1989) Presidential power: a game-theoretic analysis. In: Brace P, Harrington C, King G (eds) The presidency in american politics. New York University Press, pp 55–74

Chang P-L, Chua V, Machover M (2006) LS Penrose’s limit theorem: tests by simulation. Math Soc Sci 51(1):90–106CrossRef

Coleman J (1971) Control of collectivities and the power of a collectivity to act. In: Lieberman B (ed) Social Choice. Gordon and Breach, pp 269–300

De A, Diakonikolas I, Feldman V, Servedio R (2012a) Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces. In: Proceedings of the 44th symposium on theory of computing, STOC ’12, pp 729–746. ACM, New York

De A, Diakonikolas I, Servedio R (2012b) The inverse Shapley value problem. In: Automata, Languages, and Programming, pp 266–277. Springer

de Keijzer B, Klos T, Zhang Y (2010) Enumeration and exact design of weighted voting games. In: Proceedings of the 9th international conference on autonomous agents and multiagent systems, vol 1, pp 391–398. International Foundation for Autonomous Agents and Multiagent Systems

de Keijzer B, Klos T, Zhang Y (2014) Finding optimal solutions for voting game design problems. J Artif Intell Res 50:105–140

Deegan J Jr, Packel E (1978) A new index of power for simple \(n\)-person games. Internat J Game Theory 7(2):113–123CrossRef

Dragan I (2005) On the inverse problem for semivalues of cooperative TU games. Int J Pure Appl Math 22(4):545–561

Dragan I (2012) On the inverse problem for multiweighted Shapley values of cooperative TU games. Int J Pure Appl Math 75(3):279–287

Dragan I (2013) The inverse problem for binomial semivalues of cooperative TU games. In: Petrosyan LA, Zenkevich NA (eds) Game theory and management. Proceedings of the seventh international conference game theory and management. SPb.: Graduate School of Management SPbU, 2013, p 274, vol 26, p 72

Dubey P, Neyman A, Weber R (1981) Value theory without efficiency. Math Oper Res 6(1):122–128CrossRef

Dubey P, Shapley L (1979) Mathematical properties of the Banzhaf power index. Math Oper Res 4(2):99–131CrossRef

Felsenthal D, Machover M (1998) The measurement of voting power: Theory and practice, problems and paradoxes, vol xviii, p 322. Edward Elgar, Cheltenham

Felsenthal D, Machover M (2005) Voting power measurement: a story of misreinvention. Soc Choice Welf 25(2–3):485–506CrossRef

Freixas J, Kaniovski S (2014) The minimum sum representation as an index of voting power. Eur J Oper Res 233(3):739–748CrossRef

Freixas J, Kurz S (2014) On \(\alpha \)-roughly weighted games. Internat J Game Theory 43(3):659–692CrossRef

Freixas J, Zwicker W (2003) Weighted voting, abstention, and multiple levels of approval. Soc Choice Welf 21(3):399–431CrossRef

Freixas J, Zwicker W (2009) Anonymous yes-no voting with abstention and multiple levels of approval. Games Econ Behav 67(2):428–444CrossRef

Gvozdeva T, Hemaspaandra L, Slinko A (2013) Three hierarchies of simple games parameterized by “resource” parameters. Internat J Game Theory 42(1):1–17CrossRef

Holler M (1982) Forming coalitions and measuring voting power. Polit Stud 30(2):262–271CrossRef

Imrie R (1973) The impact of the weighted vote on representation in municipal governing bodies of New York State. Ann New York Acad Sci 219(1):192–199CrossRef

Isbell J (1958) A class of simple games. Duke Math J 25:423–439CrossRef

Johnston R (1978) On the measurement of power: some reactions to Laver. Environ Plann A 10(8):907–914CrossRef

König T, Bräuninger T (2001) Decisiveness and inclusiveness: Intergovernmental choice of European decision rules. In: Holler MJ, Owen G (eds) Power indices and coalition formation. Kluwer, pp 273–290

Kurz S (2012a) On minimum sum representations for weighted voting games. Ann Oper Res 196(1):361–369CrossRef

Kurz S (2012b) On the inverse power index problem. Optimization 61(8):989–1011CrossRef

Kurz S (2014) Measuring voting power in convex policy spaces. Economies 2(1):45–77CrossRef

Kurz S, Napel S (2014) Heuristic and exact solutions to the inverse power index problem for small voting bodies. Ann Oper Res 215(1):137–163CrossRef

Kurz S, Napel S, Nohn A (2014) The nucleolus of large majority games. Econ Lett 123(3):139–143CrossRef

Laruelle A, Valenciano F (2011) Voting and collective decision-making. Bargaining and power. Reprint of the 2008 hardback ed., vol xvii, p 184. Cambridge University Press, Cambridge

Laruelle A, Valenciano F (2013) Voting and power. In: Power, Voting, and voting power: 30 years after, pp 137–149. Springer

Laruelle A, Widgrén M (1998) Is the allocation of voting power among EU states fair? Public Choice 94(3–4):317–339CrossRef

Le Breton M, Montero M, Zaporozhets V (2012) Voting power in the EU Council of Ministers and fair decision making in distributive politics. Math Soc Sci 63(2):159–173CrossRef

Lindner I, Machover M (2004) LS Penrose’s limit theorem: proof of some special cases. Math Soc Sci 47(1):37–49CrossRef

Lindner I, Owen G (2007) Cases where the Penrose limit theorem does not hold. Math Soc Sci 53(3):232–238CrossRef

Malawski M (2004) “Counting” power indices for games with a priori unions. Theory Decis 56(1–2):125–140CrossRef

Milnor J, Shapley L (1978) Values of large games II: oceanic games. Math Oper Res 3(4):290–307CrossRef

Neyman A (1982) Renewal theory for sampling without replacement. Ann Prob, pp 464–481

Nurmi H (1980) Game theory and power indices. Zeitschrift für Nationalökonomie 40(1–2):35–58CrossRef

Nurmi H (1982) The problem of the right distribution of voting power. In: Power, voting, and voting power, pp 203–212. Springer

O’Donnell R, Servedio R (2011) The chow parameters problem. SIAM J Comput 40(1):165–199CrossRef

Papayanopoulos L (1983) On the partial construction of the semi-infinite Banzhaf polyhedron. In: Fiacco A, Kortanek K (eds) Semi-infinite programming and applications, lecture notes in economics and mathematical systems, vol 215, pp 208–218. Springer, Berlin, Heidelberg

Penrose L (1946) The elementary statistics of majority voting. J R Stat Soc 109:53–57CrossRef

Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM J Appl Math 17:1163–1170CrossRef

Shapiro N, Shapley L (1978) Values of large games, I: a limit theorem. Math Oper Res 3(1):1–9CrossRef

Shapley L (1953) A value for \(n\)-person games. Contrib. Theory of Games. Ann Math Stud

Shapley L, Shubik M (1954) A method for evaluating the distribution of power in a committee system. Am Polit Sci Rev 48(03):787–792CrossRef

Straffin P (1977) Homogeneity, independence, and power indices. Public Choice 30(1):107–118CrossRef

Taylor A, Zwicker W (1999) Simple games, desirability relations, trading, pseudoweightings. Princeton University Press, Princeton

Titel: The inverse problem for power distributions in committees
verfasst von: Sascha Kurz
Publikationsdatum: 18.01.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: Social Choice and Welfare / Ausgabe 1/2016
Print ISSN: 0176-1714
Elektronische ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-015-0946-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2016

A conjecture on the construction of orderings by Borda’s rule

Infinite-horizon social evaluation with variable population size

Pairwise partition graphs and strategy-proof social choice in the exogenous indifference class model

Erratum to: The role of subjective beliefs in preferences for redistribution

Multidimensional political competition with non-common beliefs

The greatest unhappiness of the least number