Generalized Veto Core and a Practical Voting Rule with Optimal Metric Distortion

We revisit the recent breakthrough result of Gkatzelis et al. on (single-winner) metric voting, which showed that the optimal distortion of 3 can be achieved by a mechanism called PluralityMatching. The rule picks an arbitrary candidate for whom a certain candidate-specific bipartite graph contains a perfect matching. Subsequently, a much simpler rule called PluralityVeto was shown to achieve distortion 3 as well; this rule only constructs such a matching implicitly, but it, too, makes some arbitrary decisions affecting the outcome. Our point of departure is the question whether there is an intuitive interpretation of this matching, with the goal of identifying the underlying source of arbitrariness in these rules. We first observe directly from Hall's condition that a matching for candidate c certifies that there is no coalition of voters that can jointly counterbalance the number of first-place votes c received, along with the first-place votes of all candidates ranked lower than c by any voter in this coalition. This condition closely mirrors the classical definition of the (proportional) veto core in social choice theory, except that coalitions can veto a candidate c whenever their size exceeds the plurality score of c, rather than the average number of voters per candidate. Based on this connection, we define a general notion of the veto core with arbitrary weights for voters and candidates which respectively represent the veto power and the public support they have.