Information and Representation in Computational Social Choice
Ilan Frank

Abstract:
Voting rules are functions aggregating the preferences of voters
regarding a set of alternatives, and the theoretical properties of
these objects are investigated in voting theory, as well as in
computational social choice, where we study their computational
aspects.  The question of how much information such rules actually
need in order to compute their result has been studied from various
angles in recent years, via concepts such as the communication
complexity (Conitzer and Sandholm), compilation complexity (Chevaleyre
et al.), and informational size (Sato). We review these concepts and
analyze the relations between them. That will lead us to a discussion
about representation of information: We describe different
representations for different voting rules and construct a hierarchy of
those representations. We then discuss generalized scoring rules
(introduced by Xia and Conitzer), and show how they relate to our
previous discussion.  Finally, we build a correspondence between one
representation for voting rules and subgroups of the symmetric group,
thus showing a connection between group theory and informational
representations in voting theory. We use that correspondence to prove
a theorem posed by Sato in his paper on informational size.