On the Construction of High Dimensional Simple Games

Titelangaben

Olsen, Martin ; Kurz, Sascha ; Molinero, Xavier:
On the Construction of High Dimensional Simple Games.
Bayreuth , 2016 . - 9 S.

Volltext

	Format: PDF Name: high_dimension_arxiv.pdf Version: Veröffentlichte Version Verfügbar mit der Lizenz Creative Commons BY 3.0: Namensnennung
	Download (218kB)

Abstract

Every simple game can be written as the intersection of a finite number of weighted games. The smallest possible such number is the dimension of a simple game. Taylor and Zwicker have constructed simple games with $n$ players and dimension at least $2^{\frac{n}{2}-1}$. By using theory on error correcting codes, we construct simple games with dimension $2^{n-o(n)}$. Moreover, we show that there are no simple games with dimension $n$ times higher than our games. Our results hold for all $n$.