2016/02/04 by Olsen, Martin, Kurz, Sascha, Molinero, Xavier
#68P30 #91A12 #91B12 #Combinatorics (math.CO) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1602.01581
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 χ\colon\0,1\n→ \0,1\. 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 and provided a construction guaranteeing k≤ n\choose \lfloor n/2\rfloor∈ 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.