Publications [#236192] of Vincent Conitzer

Conference articles PUBLISHED

1. Conitzer, V; Xia, L, Paradoxes of multiple elections: An approximation approach, edited by Brewka, G; Eiter, T; McIlraith, SA, Proceedings of the International Conference on Knowledge Representation and Reasoning (January, 2012), pp. 179-187, AAAI Press, ISBN 9781577355601 [html]
   (last updated on 2024/07/31)

   Abstract:
   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.