Login
Literature by the same author
plus at Google Scholar
Bibliografische Daten exportieren		  

On the Construction of High Dimensional Simple Games

Title data

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

This is the latest version of this item.

Official URL: Volltext

Abstract in another language

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)
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
Result of work at the UBT: Yes
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
300 Social sciences > 320 Political science
500 Science > 510 Mathematics
Date Deposited: 18 Jul 2016 07:34
Last Modified: 28 May 2021 04:46
URI: https://eref.uni-bayreuth.de/id/eprint/33269

Available Versions of this Item