Efficient computation of power indices for the analysis of network data
Short Description
Power indices (see e.g. [1]) are algorithms that can be used in order to analyse voting in committees (see e.g. [2,3]) or influence in networks (see e.g. [4,5]). Currently, the applicability of these algorithms for analysing network data is limited as available implementations, like e.g. [6], are constrained due to storage requirements.
About the Project
At the beginning of this international student project in March 2020 we were immediately faced with the challenges of the Covid pandemic. We had originally planned for Jochen Staudacher to advise the Kempten student team in person and to “meet” Izabella Stach from Kraków and László Kóczy from Budapest virtually every week via DFNConf. By the end of March, we had successfully and happily switched to videoconferencing using Zoom and it was clear to everybody that this trinational student project was happening entirely in the virtual sphere until its successful completion in July 2020.
In simple games there are only two types of coalitions. There are winning coalitions with value 1 and losing coalitions with value 0. In this project, we focussed on the computation of so-called power indices for weighted voting games, a very important subclass of simple games. In a weighted voting game each player assigned a positive weight which in some situations can be understood as the number of votes of a voting block. A law or motion gets passed in the committee if a certain quota, normally more than 50% of the sum of all weights, is reached or exceeded. Power indices provide measures for evaluating the power or influence of individual players.
The goal of this project was to compute power indices for weighted voting games efficiently using the technique of dynamic programming building upon the existing papers by Uno [7] and Kurz [8].
In brief, we are happy to say that this trinational student project was truly successful as it lead to new efficient algorithms and an article in a peer-reviewed journal [9]. The C++ software is publicly available via https://github.com/jhstaudacher/EPIC and we also provide an R interface to our software via https://github.com/jhstaudacher/EPIC-R
The software EPIC (Efficient Power Index Computation) forms a solid foundation for many of Jochen Staudacher’s international research cooperations and the supervision of subsequent student projects as well as bachelor and master theses. In particular, there was a follow-up project on simple games and binary decisions diagrams with another six keen Kempten students in summer 2021, jointly supervised by Izabella Stach from AGH UST in Kraków and Jochen Staudacher.
Authors
Kempten students taking part in the project: Jan Filipp, Marcus Kramer, Till Noffke, Linus Olsson, Jonas Pichler, Tobias Singer
Supervisors: Lázsló Á. Kóczy (BME Budapest), Izabella Stach (AGH University of Science and Technology, Kraków), Jochen Staudacher (Kempten),
Faculty: Computer Science, B.Sc. Programs in Computer Science and Game Engineering
Date of realisation: SS 2020
References
[1] S.R. Chakravarty, M. Mitra, P. Sarkar, A Course on Cooperative Game Theory. Cambridge University Press, 2015.
[2] E. Algaba, J.M. Bilbao, J.R. Fernandéz, The distribution of power in the European Constitution, European Journal of Operational Research, 2007, 176 (3), 1752-66.
[3] L.Á. Kóczy, Beyond Lisbon: Demographic trends and voting power in the European Union Council of Ministers, Mathematical Social Sciences, 2012, 63 (2), 152-8.
[4] C. Bertini, J. Mercik, I. Stach, Indirect Control and Power, Operations Research and Decisions, 26 (2), pp. 7-30, 2016.
[5] M.J. Holler, F. Rupp, Power in networks: A PGI Analysis of Krackhardt’s Kite Network, Springer Lecture Notes in Computer Science 11890, 2019, 21-34.
6] J. Staudacher, J. Anwander, Using the R package CoopGame for the analysis, solution and visualization of cooperative games with transferable utility. R Vignette for package version 0.2.2, 2022, https://cran.r-project.org/package=CoopGame
[7] T. Uno, Efficient computation of power indices for weighted majority games. In: International Symposium on Algorithms and Computation. Springer, Berlin, Heidelberg, 2012, 679-689.
[8] S. Kurz, Computing the Power Distribution in the IMF, 19 pages, arXiv preprint, arXiv: 1603.01443, 2016.
[9] J. Staudacher, L.A. Kóczy, I. Stach, J. Filipp, M. Kramer, T. Noffke, L. Olsson, J. Pichler and T. Singer, T. (2021), Computing power indices for weighted voting games via dynamic programming. Operations Research and Decisions, 31(2), 123-145. https://doi.org/10.37190/ord210206