Forms of representation for simple games: Sizes,conversions and equivalences |
| |
| Institution: | 1. Department of Computer Science, Technical University of Catalonia, Barcelona, Spain;2. Department of Applied Mathematics III. Technical University of Catalonia, Manresa, Spain;1. University of Vienna, Department of Economics, Oskar-Morgenstern-Platz 1, A-1090 Vienna, Austria;2. WU (Vienna University of Economics and Business), Department of Economics, Welthandelsplatz 1, A-1020 Vienna, Austria;3. Vienna University of Technology, Institute of Statistics and Mathematical Methods in Economics, Argentinierstrasse 8/4/105-3, A-1040 Vienna, Austria;4. Wittgenstein Centre (IIASA, VID/ÖAW, WU), Vienna Institute of Demography, Wohllebengasse 12-14, A-1040 Vienna, Austria;5. University of Vienna, Department of Business Administration, Oskar-Morgenstern-Platz 1, A-1090 Vienna, Austria;1. Technische Universität München, Munich, Germany;2. SAP AG, Walldorf, Germany;1. Universitat de València, Spain;2. Universidad de Málaga, Spain;1. Macquarie University, Australia;2. MRC Cognition and Brain Sciences Unit, United Kingdom |
| |
| Abstract: | Simple games are cooperative games in which the benefit that a coalition may have is always binary, i.e., a coalition may either win or loose. This paper surveys different forms of representation of simple games, and those for some of their subfamilies like regular games and weighted games. We analyze the forms of representations that have been proposed in the literature based on different data structures for sets of sets. We provide bounds on the computational resources needed to transform a game from one form of representation to another one. This includes the study of the problem of enumerating the fundamental families of coalitions of a simple game. In particular we prove that several changes of representation that require exponential time can be solved with polynomial-delay and highlight some open problems. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
