Bruner, M.-L., & Lackner, M. (2014). The Likelihood of Structure in Preference Profiles. 8th Multidisciplinary Workshop on Advances in Preference Handling, Quebec, Kanada, Non-EU. http://hdl.handle.net/20.500.12708/85942
E104-05 - Forschungsbereich Kombinatorik und Algorithmen E192 - Institut für Logic and Computation
8th Multidisciplinary Workshop on Advances in Preference Handling
Quebec, Kanada, Non-EU
In the field of computational social choice, structure in preferences is often described by so-called domain restrictions. Domain restrictions are of major importance since they allow for the circumvention of Arrow's paradox and for faster algorithms. On the other hand, such structure might be disadvantageous if one seeks to protect voting mechanisms against manipulation and control with the help of computational complexity. So far, it is unclear how likely it is that domain restrictions arise. In this paper, we answer this question from a combinatorial point of view. Our results show how unlikely it is that a preference profile belongs to a restricted domain if it is chosen at random under the Impartial Culture assumption.