Strategy-Proof Voting Rules over Multi-issue Domains with Restricted Preferences

In this paper, we characterize strategy-proof voting rules when the set of alternatives has a multi-issue structure, and the voters’ preferences are represented by acyclic CP-nets that follow a common order over issues. Our main result is a simple full characterization of strategy-proof voting rules satisfying non-imposition for a very natural restriction on preferences in multi-issue domains: we show that if the preference domain is lexicographic, then a voting rule satisfying non-imposition is strategy-proof if and only if it can be decomposed into multiple strategy-proof local rules, one for each issue and each setting of the issues preceding it. We also obtain the following variant of Gibbard-Satterthwaite: when there are at least two issues and each of the issues can take at least two values, then there is no non-dictatorial strategy-proof voting rule that satisfies non-imposition, even when the domain of voters’ preferences is restricted to linear orders that are consistent with acyclic CP-nets following a common order over issues. This impossibility result follows from either one of two more general new impossibility results we obtained, which are not included in this paper due to the space constraint.