in the repository
Title data
Olsen, Martin ; Kurz, Sascha ; Molinero, Xavier:
On the Construction of High Dimensional Simple Games.
Bayreuth
,
2016
. - 13 S.
This is the latest version of this item.
![[thumbnail of high_dimension4_arxiv.pdf]](https://epub.uni-bayreuth.de/style/images/fileicons/application_pdf.png) |
|
||||||||
|
Download (293kB)
|
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 |
|---|---|
| Additional notes (visible to public): | erschienen in:
In: Kaminka, Gal A. ; Fox, Maria ; Bouquet, Paolo ; Hüllermeier, Eyke ; Dignum, Virginia ; Dignum, Frank ; van Harmelen, Frank (Hrsg.): ECAI 2016 : 22nd European Conference on Artificial Intelligence ; proceedings. - New York : IOS Press , 2016 . - S. 880-885 . - (Frontiers in Artificial Intelligence and Applications ; 285 ) ISBN 978-1-61499-671-2 |
| 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 |
| Date Deposited: | 18 Jul 2016 07:30 |
| Last Modified: | 28 May 2021 04:48 |
| URI: | https://epub.uni-bayreuth.de/id/eprint/2935 |
Available Versions of this Item
-
On the Construction of High Dimensional Simple Games. (deposited 04 Feb 2016 11:19)
-
On the Construction of High Dimensional Simple Games. (deposited 19 Apr 2016 06:35)
- On the Construction of High Dimensional Simple Games. (deposited 18 Jul 2016 07:30) [Currently Displayed]
-
On the Construction of High Dimensional Simple Games. (deposited 19 Apr 2016 06:35)
Download Statistics