Cooperative Games

The theory of cooperative games with transferable utility offers useful insights into the way parties can share gains from cooperation and secure sustainable agreements. The basic idea of a cooperative game for a finite number of players is to define a characteristic function assigning a value to each coalition of players. The R Package CoopGame [5] was developed at Kempten University and consists of a comprehensive set of tools for cooperative game theory with transferable utility. CoopGame [5] is based on the characteristic function, aims to provide reference implementations and does not strive for efficiency.

We view cooperative game theory as a still underrated tool in data science, especially for the analysis of network data. Real-world networks are large and may involve hundreds of players and thus storing a characteristic function with values of all coalitions is not feasible.

We are very much interested in using the structure of special classes of games and developing efficient algorithms tailored to these problems. For simple games we have only winning coalitions with value 1 and losing coalitions with value 0. Weighted voting games are a special subclass of simple games. Every player is assigned a positive weight and a coalition is winning whenever the weights of its members reach or exceed a certain quota. In the paper [2], we introduce efficient algorithms and a powerful software package for studying weighted voting games.

Weighted voting games enjoy a wide range of applicability beyond classical voting and decision-making situations. An area of our particular interest are financial networks [3,4]. We are looking forward to continuing these studies together with our international partners as well as to studying social networks and biological networks.

Open questions and challenges in this exciting field abound, both in terms of models and algorithms.

Another aspect we are interested in are games in which players have agreed to form a priori unions.

Each union sends a negotiator and afterwards unions need to decide internally how to distribute the gains. Who can formulate the most credible threat to leave her own union? And how can we compute a solution efficiently? For some recent results on the latter question, see [6]. For further algorithms, ideas and applications … please stay tuned.

Publications

[1] Staudacher, J., & Anwander, J. (2019). Conditions for the uniqueness of the Gately point for cooperative games. arXiv preprint, arXiv:1901.01485. https://arxiv.org/abs/1901.01485

[2] Staudacher, J., Kóczy, L. A., Stach, I., Filipp, J., Kramer, M., Noffke, T., Olsson, L., Pichler, J. & 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.

[3] Staudacher, J., Olsson, L., & Stach, I. (2021). Implicit power indices for measuring indirect control in corporate structures. In: Transactions on Computational Collective Intelligence XXXVI. Lecture Notes in Computer Science; Nguyen, N., Kowalczyk, R., Mercik, J., Motylska-Kuzma, A. Eds.; Springer: Berlin/Heidelberg, Volume 13010, pp. 73-93. https://doi.org/10.1007/978-3-662-64563-5_4

[4] Mercik, J., Gladysz, B., Stach, I., & Staudacher, J. (2021). Shapley-Based Estimation of Company Value—Concept, Algorithms and Parameters. 23 pages. Entropy 23(12), 1598. https://doi.org/10.3390/e23121598

[5] Staudacher, J., Anwander, J., et al. (2021): R Package CoopGame. https://cran.r-project.org/package=CoopGame

[6] Staudacher, J., Wagner, F., & Filipp, J. (2022). Dynamic Programming for Computing Power Indices for Weighted Voting Games with Precoalitions. 17 pages. Games 13(1), 6. https://doi.org/10.3390/g13010006