Tiebreaking is a natural issue in social choice and in computational social choice. However, with the passing of time, it has become more and more clear that tiebreaking is a quite important and subtle issue, and that in some cases one’s choice of tiebreaking scheme can greatly affect the computational complexity and/or social choice properties of whatever election problem is being studied. It is thus important to truly understand what is meant by various classes of tiebreaking approaches, and to seek to understand the behaviors they display. That, with the central focus being on guidance from social choice properties, is the concern of this interesting paper.

Loosely put, in parallel universe tiebreaking, a candidate c is an overall winner if there is some choice of how to break the ties at each intermediate step of the (typically multistage) voting rule so as to make c the winner. This paper provides a formal definition of the notion--up to now used and applied in an ad hoc way one election system at a time--of parallel universe tiebreaking. The paper also argues that respect for certain attractive potential properties of social choice functions supports the attractiveness of parallel universe tiebreaking.

The paper then discusses some existing tiebreaking schemes and introduces a new family of tiebreaking schemes that it calls random perturbation tiebreaking. The paper proves that a particular member of this family is the unique symmetric perturbation tiebreaking scheme that simultaneously satisfies four attractive properties; in addition, the scheme has other attractive properties and potential implementation advantages.