Paradoxes of multiple elections: An approximation approach

When agents need to make decisions on multiple issues, applying common voting rules becomes computationally hard due to the exponentially large number of alternatives. One computationally efficient 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 that 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. We show some generalized paradoxes of multiple elections: Sequential voting does not approximate many common voting rules well even when the preferences are O-legal or separable. However, these paradoxes are much alleviated or even completely avoided when the preferences are lexicographic or represented by LP-trees. Our results thus draw a border for conditions under which sequential voting rules, which have extremely low computational and communicational cost, are good approximations of some common voting rules w.r.t. their corresponding scoring functions. Copyright © 2012, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Duke Scholars

Author Vincent Conitzer Computer Science