Suche nach Personen

plus im Publikationsserver
plus bei Google Scholar

Bibliografische Daten exportieren
 

On the Construction of High Dimensional Simple Games

URN zum Zitieren der Version auf EPub Bayreuth: urn:nbn:de:bvb:703-epub-2801-1

Titelangaben

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

Warnung
There is a more recent version of this item available.

Volltext

[thumbnail of high_dimension2_arxiv.pdf]
Format: PDF
Name: high_dimension2_arxiv.pdf
Version: Veröffentlichte Version
Verfügbar mit der Lizenz Creative Commons BY 3.0: Namensnennung
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.

Weitere Angaben

Publikationsform: Preprint, Postprint
Keywords: simple games; weighted games; dimension; coding theory; Hamming distance
Fachklassifikationen: Mathematics Subject Classification Code: 91B12 (91A12 68P30)
Themengebiete aus DDC: 000 Informatik,Informationswissenschaft, allgemeine Werke > 004 Informatik
300 Sozialwissenschaften > 320 Politikwissenschaft
500 Naturwissenschaften und Mathematik > 510 Mathematik
Institutionen der Universität: Fakultäten > Fakultät für Mathematik, Physik und Informatik
Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut
Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut > Lehrstuhl Wirtschaftsmathematik
Profilfelder > Emerging Fields > Governance and Responsibility
Fakultäten
Profilfelder
Profilfelder > Emerging Fields
Sprache: Englisch
Titel an der UBT entstanden: Ja
URN: urn:nbn:de:bvb:703-epub-2801-1
Eingestellt am: 19 Apr 2016 06:35
Letzte Änderung: 19 Apr 2016 06:35
URI: https://epub.uni-bayreuth.de/id/eprint/2801

Zu diesem Eintrag verfügbare Versionen

Downloads

Downloads pro Monat im letzten Jahr