Paradoxes of multiple elections: An approximation approach

Published

Conference Paper

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 Authors

Cited Authors

  • Conitzer, V; Xia, L

Published Date

  • December 1, 2012

Published In

  • 13th International Conference on the Principles of Knowledge Representation and Reasoning, Kr 2012

Start / End Page

  • 179 - 187

International Standard Book Number 13 (ISBN-13)

  • 9781577355601

Citation Source

  • Scopus