UPCommons. Portal del coneixement obert de la UPC
Publicación
Contribución de congreso (ConferenceOutput)
On the construction of high dimensional simple games
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 : f0; 1gn ! f0; 1g.
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 n2 ¿1 and provided a construction guaranteeingk ¿ n bn=2c 2 2n¿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 k for a subclass of voting systems. As an application, we give a construction for k 2n¿o(n), i.e., there is no gain from a representation complexity point of view., Peer Reviewed