General tiebreaking schemes for computational social choice
Copyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). 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.
Freeman, R; Brill, M; Conitzer, V
Volume / Issue
Start / End Page
Electronic International Standard Serial Number (EISSN)
International Standard Serial Number (ISSN)
International Standard Book Number 13 (ISBN-13)