Titlebar

Export bibliographic data
Literature by the same author
plus on the publication server
plus at Google Scholar

 

On the Construction of High Dimensional Simple Games

URN to cite this document: urn:nbn:de:bvb:703-epub-2801-1

Title data

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

WarningThere is a more recent version of this item available.

[img]
Format: PDF
Name: high_dimension2_arxiv.pdf
Version: Published Version
Available under License Creative Commons BY 3.0: Attribution
Download (286kB)

Abstract

Voting is a commonly applied method for the aggregation of the preferences of multiple agents into a joint decision. If preferences are binary, i.e., "yes" and "no", every voting system can be described by a (monotone) Boolean function $\chi\colon\{0,1\}^n\rightarrow \{0,1\}$. However, its naive encoding needs $2^n$ bits. The subclass of threshold functions, which is sufficient for homogeneous agents, allows a more succinct representation using $n$ weights and one threshold. For heterogeneous agents one can represent $\chi$ as an intersection of $k$ threshold functions. Taylor and Zwicker have constructed a sequence of examples requiring $k\ge 2^{\frac{n}{2}-1}$ and provided a construction guaranteeing $k\le {n\choose {\lfloor n/2\rfloor}}\in 2^{n-o(n)}$. The magnitude of the worst case situation was thought to be determined by Elkind et al. in 2008, but the analysis unfortunately turned out to be wrong. Here we uncover a relation to coding theory that allows the determination of the minimum number for $k$ for a subclass of voting systems. As an application, we give a construction for $k\ge 2^{n-o(n)}$, i.e., there is no gain from a representation complexity point of view.

Further data

Item Type: Preprint, postprint
Keywords: simple games; weighted games; dimension; coding theory; Hamming distance
Subject classification: Mathematics Subject Classification Code: 91B12 (91A12 68P30)
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
300 Social sciences > 320 Political science
500 Science > 510 Mathematics
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics
Profile Fields > Emerging Fields > Governance and Responsibility
Faculties
Profile Fields
Profile Fields > Emerging Fields
Language: English
Originates at UBT: Yes
URN: urn:nbn:de:bvb:703-epub-2801-1
Date Deposited: 19 Apr 2016 06:35
Last Modified: 19 Apr 2016 06:35
URI: https://epub.uni-bayreuth.de/id/eprint/2801

Available Versions of this Item