Título:
|
Minimal representations for majority games
|
Autor/a:
|
Freixas Bosch, Josep; Molinero Albareda, Xavier; Roura Ferret, Salvador
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. GRTJ - Grup de Recerca en Teoria de Jocs; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
Abstract:
|
This paper presents some new results about majority games. Isbell (1959) was the first to find a majority game without a minimum normalized representation; he needed 12 voters to construct such a game. Since then, it has been an open problem to find the minimum number of voters of a majority game without a minimum normalized representation. Our main new results are: 1. All majority games with less than 9 voters have a minimum representation. 2. For 9 voters there are 14 majority games without a minimum integer representation, but these games admit a minimal normalized integer representation. 3. For 10 voters exist majority games with neither a minimum integer representation nor a minimal normalized integer representation. |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Simple games -Weighted games -Majority games -Minimum and minimal weighted representations/realizations -Computing games |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Informe |
Compartir:
|
|