Uniform generation of anonymous and neutral preference profiles for social choice rules

Abstract

The Impartial Anonymous and Neutral Culture (IANC) model of social choice assumes that the names of the voters as well as the identity of the alternatives are immaterial. This models allows for comparison of structural properties social choice rules (SCRs) for large values of the parameters empirically: whether Condorcet winners exist, whether Borda and Condorcet winners are identical, whether Plurality with run-off winners are among Borda winners, for example.

We derive an exact formula for the number of equivalence classes of preference profiles (called roots) in this model. The number of terms in the formula depends only on the number of alternatives m, and not the much larger number of voters n. In IANC, the equivalence classes defining the roots do not have the same size, making their uniform generation for large values of the parameters nontrivial. We show that the Dixon–Wilf algorithm can be adapted to this problem, and describe a symbolic algebra routine that can be used for Monte-Carlo algorithms for the study of various structural properties of SCRs.