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.

The metric distortion framework posits that n voters and m candidates are jointly embedded in a metric space such that voters rank candidates that are closer to them higher. A voting rule's purpose is to pick a candidate with minimum total distance to the voters, given only the rankings, but not the actual distances. As a result, in the worst case, each deterministic rule picks a candidate whose total distance is at least three times larger than that of an optimal one, i.e., has distortion at least 3. A recent breakthrough result showed that achieving this bound of 3 is possible; however, the proof is non-constructive, and the voting rule itself is a complicated exhaustive search. Our main result is an extremely simple voting rule, called Plurality Veto, which achieves the same optimal distortion of 3. Each candidate starts with a score equal to his number of first-place votes. These scores are then gradually decreased via an n-round veto process in which a candidate drops out when his score reaches zero. One after the other, voters decrement the score of their bottom choice among the standing candidates, and the last standing candidate wins. We give a one-paragraph proof that this voting rule achieves distortion 3. This rule is also immensely practical, and it only makes two queries to each voter, so it has low communication overhead. We also show that a straightforward extension can be used to give a constructive proof of the more general Ranking-Matching Lemma of Gkatzelis et al. We also generalize Plurality Veto into a class of randomized voting rules in the following way: Plurality veto is run only for k < n rounds; then, a candidate is chosen with probability proportional to his residual score. This general rule interpolates between Random Dictatorship (for k=0) and Plurality Veto (for k=n-1), and k controls the variance of the output. We show that for all k, this rule has expected distortion at most 3.

Abstract In a strategic-form game, a strategy profile is an equilibrium if no viable coalition of agents (or players) benefits (in the Pareto sense) from jointly changing their strategies. Weaker or stronger equilibrium notions can be defined by considering various restrictions on coalition formation. For instance, in a Nash equilibrium, it is assumed that viable coalitions are singletons, and in a super strong equilibrium, it is assumed that every coalition is viable. Restrictions on coalition formation can be justified by communication limitations, coordination problems, or institutional constraints. In this paper, inspired by social structures in various real-life scenarios, we introduce certain restrictions on coalition formation, and on their basis, we introduce a number of equilibrium notions. As an application, we study our equilibrium notions in resource selection games (RSGs), and we present a complete set of existence and nonexistence results for general RSGs and their important special cases.