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 2ⁿ possible election outcomes. The symmetric group of degree 2ⁿ, S_2ⁿ, acts in a natural way on the set of all such linear orders. A permutation σ∈S_2ⁿ 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 S_2ⁿ 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.