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

Title data

Kurz, Sascha ; Molinero, Xavier ; Olsen, Martin:
On the Construction of High Dimensional Simple Games.
2016
Event: 22. European Conference on Artificial Intelligence (ECAI) 2016 , 29.08-02.09.2016 , The Hague, Holland.
(Conference item: Conference , Speech )

Related URLs

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. However, its naive encoding needs 2n 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 χ as an intersection of k threshold functions. Taylor and Zwicker have constructed a sequence of examples requiring k>=2^(n/2-1). 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 k for a subclass of voting systems. As an application, we give a new construction closing the gap from a representation complexity point of view.

Further data

Item Type: Conference item (Speech)
Refereed: Yes
Additional notes: speaker: Martin Olsen
Keywords: simple games; dimension; error-correcting codes
Subject classification: Mathematics Subject Classification Code: 91B12 91A12 68P30
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics in Economy
Profile Fields > Emerging Fields
Profile Fields > Emerging Fields > Governance and Responsibility
Faculties
Faculties > Faculty of Mathematics, Physics und Computer Science
Profile Fields
Result of work at the UBT: Yes
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
500 Science > 510 Mathematics
Date Deposited: 22 Nov 2016 09:36
Last Modified: 23 Nov 2016 06:57
URI: https://eref.uni-bayreuth.de/id/eprint/35166