Conference articles PUBLISHED

1. Freeman, R; Brill, M; Conitzer, V, General tiebreaking schemes for computational social choice, Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, vol. 3 (January, 2015), pp. 1401-1409.
   (last updated on 2024/04/16)

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