Approximating common voting rules by sequential voting in multi-issue domains
When agents need to make decisions on multiple issues, one solution is to vote on the issues sequentially. In this paper, we investigate how well the winner under the sequential voting process approximates the winners under some common voting rules. Some common voting rules, including Borda, k-approval, Copeland, maximin, Bucklin, and Dodgson, admit natural scoring functions that can serve as a basis for approximation results. We focus on multi-issue domains where each issue is binary and the agents' preferences are O-legal, separable, represented by LP-trees, or lexicographic. Our results show significant improvements in the approximation ratios when the preferences are represented by LP-trees, compared to the approximation ratios when the preferences are O-legal. However, assuming that the preferences are separable (respectively, lexicographic) does not significantly improve the approximation ratios compared to the case where the preferences are O-legal (respectively, are represented by LP-trees). Copyright© 2011, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
