Efficient computation of cooperative games for AI and implementation in C++
Short Description
Cooperative game theory and power indices (see e.g. [1]) are techniques traditionally used to analyse voting in committees (see e.g. [2], [3]) or influence in networks (see e.g. [4], [5]). In this project the goal was to apply these techniques in AI along the lines of [6] building upon results from previous international student projects.
About the Project
The new M.Sc. course in Computer Vision and Artificial Intelligence started in the summer semester 2022 and this project – which was jointly supervised by Jochen Staudacher from Kempten and Stefano Moretti from Université Paris-Dauphine – was the first international student project in that program.
Current implementations of concepts from cooperative game theory are prototypical [7] and thus very limited in analysing real-world data. If there are n players (or agents or entities), then the size of the so-called characteristic function of the game grows exponentially with n. Hence the challenge is to find a compact representation [6] for the games to be solved in a concrete application using efficient software. In summer 2020 we ran a very successful international student project overcoming these limitations for the special class of weighted voting games using the technique of dynamic programming for computing power indices efficiently and managed to publish an article in a peer-reviewed journal [8]. In this project we reached beyond power indices and implemented techniques for more general cooperative games. We focussed especially on a very promising approach called marginal contribution nets [9]. Marginal contribution nets allow us represent certain classes of cooperative games compactly and handle large problems.
The project will be continued and extended in another international student project with Stefano Moretti in the same degree program in summer 2023.
Authors
Kempten students taking part in the project: Yannic Bachmann, Marvin Craes, Matthias Schedel.
Supervisors: Jochen Staudacher (Kempten), Stefano Moretti (Université Paris-Dauphine)
Faculty: Computer Science, M.Sc. Program in Computer Vision and Artificial Intelligence
Date of realisation: SS 2022
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] G. Chalkiadakis, E. Elkind, M. Wooldridge, Cooperative game theory: Basic concepts and computational challenges. IEEE Intelligent Systems, 27(3), 86-90, 2012.
[7] 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
[8] 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
[9] S. Ieong, Y. Shoham, Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games, Proc. 6th ACM Conf. Electronic Commerce (ACM-EC 05), ACM, 2005, 193–202.