Bibliografische Daten exportieren
Literatur vom gleichen Autor
plus auf ERef Bayreuth
plus bei Google Scholar


On the construction of high dimensional simple games


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 (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


Link zum Volltext (externe URL): Volltext


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.

Weitere Angaben

Publikationsform: Aufsatz in einem Buch
Begutachteter Beitrag: Ja
Keywords: simple games; dimension; error-correcting codes
Fachklassifikationen: Mathematics Subject Classification Code: 91B12 91A12 68P30
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
Profilfelder > Emerging Fields > Governance and Responsibility
Titel an der UBT entstanden: Ja
Themengebiete aus DDC: 000 Informatik,Informationswissenschaft, allgemeine Werke > 004 Informatik
500 Naturwissenschaften und Mathematik > 510 Mathematik
Eingestellt am: 07 Apr 2017 06:53
Letzte Änderung: 07 Apr 2017 06:53
URI: https://eref.uni-bayreuth.de/id/eprint/36770