## Title data

Kurz, Sascha ; Molinero, Xavier ; Olsen, Martin:

**On the construction of high dimensional simple games.**

*In:* Kaminka, Gal A. ; Fox, Maria ; Bouquet, Paolo ; Hüllermeier, Eyke ; Dignum, Virginia ; Dignum, Frank ; van Harmelen, Frank
(ed.):
ECAI 2016 : 22nd European Conference on Artificial Intelligence ; proceedings. -
New York
: IOS Press
,
2016
. - pp. 880-885
. - (Frontiers in Artificial Intelligence and Applications
; 285
)

ISBN 978-1-61499-671-2

## 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: | Article in a book |
---|---|

Refereed: | Yes |

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 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 Profile Fields > Emerging Fields Profile Fields > Emerging Fields > Governance and Responsibility Faculties |

Result of work at the UBT: | Yes |

DDC Subjects: | 000 Computer Science, information, general works > 004 Computer science 500 Science > 510 Mathematics |

Date Deposited: | 07 Apr 2017 06:53 |

Last Modified: | 28 May 2021 04:47 |

URI: | https://eref.uni-bayreuth.de/id/eprint/36770 |