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