Permutations of separable preference orders

The notion of separability is important in economics, operations research, and political science, where it has recently been studied within the context of referendum elections. In a referendum election on n   questions, a voter's preferences may be represented by a linear order on the 2n2n possible election outcomes. The symmetric group of degree 2n2n, S2nS2n, acts in a natural way on the set of all such linear orders. A permutation σ∈S2nσ∈S2n is said to preserve separability   if for each separable order ≻≻, σ(≻)σ(≻) is also separable. Here, we show that the set of separability-preserving permutations is a subgroup of S2nS2n and, for 4 or more questions, is isomorphic to the Klein 4-group. Our results indicate that separable preferences are rare and highly sensitive to small changes. The techniques we use have applications to the problem of enumerating separable preference orders and to other broader combinatorial questions.