General tiebreaking schemes for computational social choice


Conference Paper

Copyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems ( All rights reserved. In (computational) social choice, how ties are broken can affect the axiomatic and computational properties of a voting rule. In this paper, we first consider settings where we may have multiple winners. We formalize the notion of parallel universes tiebreaking with respect to a particular tree that represents the computation of the winners, and show that the specific tree used does not matter if certain conditions hold. We then move on to settings where a single winner must be returned, generally by randomized tiebreaking, and examine some drawbacks of existing approaches. We propose a new class of tiebreaking schemes based on randomly perturbing the vote profile. Finally, we show that one member of this class uniquely satisfies a number of desirable properties.

Duke Authors

Cited Authors

  • Freeman, R; Brill, M; Conitzer, V

Published Date

  • January 1, 2015

Published In

Volume / Issue

  • 3 /

Start / End Page

  • 1401 - 1409

Electronic International Standard Serial Number (EISSN)

  • 1558-2914

International Standard Serial Number (ISSN)

  • 1548-8403

International Standard Book Number 13 (ISBN-13)

  • 9781450337717

Citation Source

  • Scopus