TY - GEN
T1 - On the Construction of High-Dimensional Simple Games
AU - Olsen, Martin
AU - Kurz, Sascha
AU - Molinero, Xavier
PY - 2016
Y1 - 2016
N2 - 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 ?: {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 ≥ 2n/2-1 and provided a construction guaranteeing k ≤ ([nn/2]) ∈ 2
n-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 > 2
n-o(n), i.e., there is no gain from a representation complexity point of view.
AB - 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 ?: {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 ≥ 2n/2-1 and provided a construction guaranteeing k ≤ ([nn/2]) ∈ 2
n-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 > 2
n-o(n), i.e., there is no gain from a representation complexity point of view.
UR - http://www.scopus.com/inward/record.url?scp=85013115114&partnerID=8YFLogxK
U2 - 10.3233/978-1-61499-672-9-880
DO - 10.3233/978-1-61499-672-9-880
M3 - Konferencebidrag i proceedings
SN - 978-1-61499-671-2
VL - 285
T3 - Frontiers in Artificial Intelligence and Applications
SP - 880
EP - 885
BT - Frontiers in Artificial Intelligence and Applications
PB - IOS Press
ER -