Trembling Hand Equilibria of Plurality Voting

1 Introduction

Plurality voting is a simple and popular method for aggregating preferences of multiple stakeholders over a set of available choices. It involves each stakeholder, or voter, declaring his most preferred alternative; the winner is then selected among the most popular alternatives using a tie-breaking rule. Due to its simplicity, Plurality voting is particularly susceptible to manipulation by dishonest voters: indeed, one can easily figure out if he may benefit from voting for an alternative other than his true top choice [Bartholdi, III et al., 1989]. Thus, when analyzing the outcomes of Plurality voting, it is imperative to take strategic considerations into account. This can be accomplished by viewing voting as a strategic game, and focusing on outcomes that are identified by classic solution concepts (e.g., Nash equilibria) or arise as a result of a natural iterative process (e.g., best response dynamics).

Both approaches have been considered in the literature, going back as far as the pioneering work of Farquharson [1969] (other important contributions include [Moulin, 1979; Dhillon and Lockwood., 2004; Myerson and Weber, 1993]), and have recently received a lot of attention from the

Nicholas R. Jennings

Imperial College United Kingdom

computational social choice community (see [Desmedt and Elkind, 2010; Xia and Conitzer, 2010; Thompson et al., 2013; Obraztsova et al., 2013; Meir et al., 2014; Elkind et al., 2015] for the analysis of Nash equilibria and their refinements and [Meir et al., 2010; Reijngoud and Endriss, 2012; Reyhani and Wilson, 2012; Grandi et al., 2013; Rabinovich et al., 2015] for an investigation of best response dynamics). In particular, it has been observed early on that Plurality voting games have many undesirable Nash equilibria: e.g., in elections with at least 3 voters it is a Nash equilibrium for all voters to vote for the same candidate, even if none of them likes him. For this reason, much of the subsequent work focused on equilibrium refinements, i.e., sets of Nash equilibria that satisfy additional constraints, or, more broadly, outcomes that are stable when we place additional assumptions on voters' utilities. Two examples of the latter approach are Plurality voting games with lazy voters [Borgers, 2004; Desmedt and Elkind, 2010; Elkind et al., 2015], where voters prefer to abstain when they are not pivotal (see e.g. [Kolovos and Harris, 2005] for motivation), or with truth-biased voters, where voters prefer to vote truthfully when they are not pivotal [Dutta and Laslier, 2010; Dutta and Sen, 2012; Thompson et al., 2013; Obraztsova et al., 2013; Elkind et al., 2015]. Both approaches eliminate many of the undesirable Nash equilibria; however, it is not clear if either assumption (or their combination) can be used to capture all real-life Plurality voting scenarios where voters may strategize.

The goal of our paper is to extend this line of work to a classic equilibrium refinement known as Trembling Hand Equilibrium (THE). This concept was introduced by Selten [1975], and has received a considerable amount of attention in the game-theoretic literature (see [Mas-Colell et al., 1995] for basic definitions and [van Damme, 1991] for a comprehensive treatment). It is based on the idea that, when choosing his strategy, a player assumes that other players' hands may tremble, and with a small probability they would choose a strategy at random instead of playing their best response. In the context of voting, this corresponds to voters being confused by the design of the ballot or to errors during the vote counting procedure (such mistakes are well documented in the popular press, see the discussion in [Xia, 2012]). However, to the best of our knowledge, very little is known about trembling hand equilibria of Plurality voting.

Specifically, Messner and Polborn [2002; 2011] were the first to investigate the impact of small errors on voters' equilibrium behavior. However, they combine the trembling hand approach with another tweak of the model, which enables the voters to coordinate their behavior. Thus, their results (which include a characterization of the associated class of equilibria for three candidates, and a proof that a variant of Duverger's law holds in this setting) are not directly applicable if one aims to understand the impact of the trembling hand refinement per se. Other authors who consider THEs in voting focus on dynamic games [Acemoglu et al., 2009], incomplete information scenarios [Jackson and Tan, 2013] or multiwinner elections [Obraztsova et al., 2015], and only the latter paper explicitly addresses the associated algorithmic issues.

Against this background, in this paper we analyze the classic trembling hand equilibria of Plurality voting games. We establish many useful properties of players' trembling hand (TH) best responses and THE. In particular, we characterize games that admit an outcome where some candidate is unanimously supported in a THE. Our analysis enables us to develop a polynomial-time algorithm for computing one's TH best response, and construct THE for a wide range of voters' preferences. On the negative side, we provide an example of a Plurality election that admits no THE, and show that it is NP-hard to check if a given game admits a THE that assigns a positive probability of winning to a given candidate.

2 Model and Preliminaries

We begin by introducing the notation that will be used throughout the paper. We then define Plurality voting games and trembling hand equilibria of these games.

Plurality voting games. There is a set V = ¶v1↪ v2↪ ▷ ▷ ▷ ↪ vn♦ of n voters, who aim to elect a winner from a set C = ¶c1↪ c2↪ ▷ ▷ ▷ ↪ cm♦ of m alternatives, or candidates. Each voter v 2 V has a preference order >v over C, which is a strict total order (a complete, transitive and anti-symmetric binary relation). We write x >v y to express that voter v prefers candidate x to candidate y; we extend this notation to subsets of candidates C0 ✓ C by writing x >v C0 whenever x >v y for all y 2 C0 .

Consider a subset of voters S ✓ V. The plurality score of a candidate c 2 C in a ballot profile bS is given by sc(c; bS) = ♣¶v 2 S ♣ bv = c♦♣. Let sw (bS) = maxc2C sc(c; bS) be the highest score observed in bS. The winning set under bS is the set of alternatives with the highest score:

In Plurality voting, each voter v 2 V submits a vote, or ballot, bv 2 C. A ballot profile of a subset S ✓ V of voters is a vector of ballots bS = (bv)v2S, one for each voter in S. When S = V, we drop the subscript S, and simply write b. For each v 2 V we write b-v to denote the ballot profile obtained from b by removing the ballot of voter v, and we write (b0v ↪ b-v) to denote the ballot profile obtained by adding a ballot b0v of voter v to the profile b-v of the remaining voters.

The unique Plurality winner under b is chosen from W(b) using a tie-breaking rule. In this paper, we consider randomized tie-breaking: the winner is chosen uniformly at random from W(b). It will also be useful to set s⇤ (bS) = maxc2C∩W(bS) sc(c; bS) and consider the set of runners-up Further, we define the following sets of candidates:

Let c⇤ (v; b-v) (respectively, c0 (v; b-v) and c00 (v; b-v)) be voter v's most preferred candidate in C⇤ (b-v) (respectively, in C0 (b-v) and in C00 (b-v)), i.e.,

Since the winner is chosen from W(b) uniformly at random, to discuss voters' strategic behavior, we have to be able to reason about voters' preferences over lotteries. To deal with this issue, we follow the approach used in a number of recent papers [Desmedt and Elkind, 2010; Boutilier et al., 2012; Filos-Ratsikas and Miltersen, 2014; Obraztsova et al., 2011] and assume that each voter is endowed with a utility function δv : C ! N, which assigns a utility to each candidate in C; we require that δv(c) > δv(c0 ) whenever c >v c0 (this means that a voter's preference order is fully described by his utility function). Now, for each voter v 2 V the utility that he derives from a winning set W(bS) is his expected utility when the winner is chosen fromW(bS) uniformly at random, i.e.,

we denote this quantity by uv(bS).

The setting described above induces a normal-form game Γ = hV↪C↪ (uv)v2Vi, where V is the set of players, the set of strategies available to each player is given by C, and the utility function of each player at a strategy profile b is given by uv(b). Games of this form are called Plurality voting games. A strategy profile b is a Nash Equilibrium (NE) of a game Γ if for each player v 2 V and each ballot b0v 2 C it holds that uv(b) ≥ uv(b0v ↪ b-v).

Trembling hand equilibrium (THE) The notion of trembling hand equilibrium goes back to Selten [1975]. Intuitively, it allows for a small probability that, instead of playing his chosen strategy, a player errs and chooses a random one. We consider a popular implementation of this idea, where, for a given small value " > 0, a player with m strategies available to him plays strategically with probability 1 - m", and with probability m" he chooses a strategy uniformly at random.

More formally, fix a trembling hand (TH) probability " > 0. For each voter v, we distinguish between his intended ballot bv and his actual ballot ebv. A voter selects his intended ballot bv. Then, the probability that v's actual ballot is some

This definition can be extended to subsets of voters: for a subset S ✓ V of voters, the joint ballot TH probability given the intended ballot profile bS is given by

Notice that voter v's ballot TH probability defines a fully mixed strategy for v. We will denote this mixed strategy by b"v . Moreover, given a set of voters S ✓ V, we will denote their mixed strategy profile (b"v )v2S by b"S ; we will refer to b"v and b"S as the TH ballot and the joint TH ballot, respectively.

Now, suppose that the intended joint ballot of players in V ∩ ¶v♦ is b-v. When deciding on his intended ballot, a voter realizes that other voters' hands may tremble and assumes that these trembles are independent from each other, but ignores the possibility that his own hand may tremble as well. Thus, v calculates his utility from submitting a ballot bv against b-v as follows:

eb-v2Cn-1 We refer to this quantity as the "-TH utility of voter v. We are now ready to define the notions of "-TH best response, TH best response and TH equilibrium.

Definition 1. Given an " with 0 < " < 1, we say that a ballot b is an "-TH best response ("-TH-BR) of voter v to the intended ballot b-v of the other voters if b 2 argmaxb0 e U " v (b0 ↪ b-v). We say that b is a TH best response (TH-BR) of voter v to b-v if there exists an "0 with 0 < "0 < 1 such that b is an "-TH best response to b-v for all " with 0 < " < "0. A joint ballot b is a TH equilibrium (THE) if for each v 2 V the ballot bv is a TH-BR to b-v.

It will be convenient to rewrite the expression for "-TH utility by grouping the terms according to how many voters' hands have trembled. Formally, for every possible value of the parameter ⌘ we define the set of ⌘-tremblings as follows.

Example 1. Let C = ¶a↪ b♦, V = ¶u↪ v↪w♦ and assume that each voter z 2 V has δz(a) = 1, δz(b) = 0. Then both (a↪ a↪ a) and (b↪ b↪ b) are Nash equilibria of the respective Plurality voting game, simply because no individual player can change the winning set by modifying his vote. However, (b↪ b↪ b) is not a THE of this game. Indeed, consider some " with 0 < " < 1 and a voter v. The joint TH ballot of the remaining voters assigns probability (1 - ")2 to (a↪ a); the ballot profiles (a↪ b) and (b↪ a) occur with probability "(1-") each, and the ballot profile (b↪ b) occurs with probability "2 . Thus, if voter v changes his strategy from b to a, he increases his "-TH utility by 2"(1 - ") > 0: whenever W(b-v) = ¶a↪ b♦ (which happens with probability 2"(1 - ")), switching from b to a increases his utility by 1, and if W(b-v) = ¶a♦ or W(b-v) = ¶b♦, the outcome does not depend on his vote.

Definition 2. Given a set of voters S ✓ V and two ballot profiles b0S , b00S , let d(b0S ↪ b00S ) = ♣¶v 2 S ♣ b0v 6= b00 v ♦♣ denote the Hamming distance between these two ballot profiles. Given an intended ballot profile bS for S and a parameter ⌘ with 0  ⌘  ♣S♣, we say that a ballot ebS is an ⌘-trembling for bS if d(ebS↪ bS) = ⌘. We denote the set of all ⌘-tremblings for bS by B(bS↪ ⌘).

Every ⌘-trembling for V ∩ ¶v♦ occurs with the same probability, namely, ⇣("↪ ⌘) = (1- (m-1)")n-1-⌘ "⌘ . Consequently, we can rewrite the expression for "-TH utility as a sum of n terms, where each term corresponds to a fixed value of ⌘. Specifically, we define

We will now define a class of utility functions that will play an important role in our analysis.

Definition 3. A utility function δv : C ! N of a voter v 2 V is ordinary if the following two conditions hold:

(1) for each triple of distinct candidates a↪ b↪ c 2 C and each k with 0  k  n + m we have

(2) for each pair of distinct candidates a↪ b 2 C, each subset C0 ✓ C ∩ ¶a↪ b♦ and each k with 0  k  n we have

Some of the results in this paper require that all voters have ordinary utilities. This restriction is needed for technical reasons: it ensures that, when comparing two available strategies, a voter can make his decision by considering the smallest number of trembles that change the outcome (see, e.g., the proof of Theorem 1). Note that almost all utility functions are ordinary, in the following sense: if we were to draw voters' utilities for each candidate uniformly at random from a real interval [a↪ b], then all utility functions would be ordinary with probability 1. Moreover, for every utility function δ : C ! N we can find a constant γ 2 N such that the utility function δ0 : C ! N given by δ0 (c) = δ(c) + γ for each c 2 C is ordinary. Thus, we believe that results for voters with ordinary utilities provide useful intuition for the general case; nevertheless, getting rid of this restriction is an important direction for future work.

3 Best Response Calculation

In this section we will explain how voter v can compute his TH best response given the intended ballot profile b-v of other voters. We start by observing that if v can identify a vote that improves the outcome from his perspective (compared to the outcome at b-v), then he should simply ignore the possibility of trembles and submit his best response to the intended ballot profile.

Proposition 1. Consider a voter v 2 V and a ballot profile b-v of the remaining voters. If there exists a ballot b0v 2 C such that uv(b0v ↪ b-v) > uv(b-v) then a ballot b is a TH best response of voter v to b-v if and only if uv(b↪ b-v) ≥ uv(b0 ↪ b-v) for all b0 2 C.

We omit the formal proof of this result due to space constraints; intuitively, Proposition 1 holds because for small " the intended ballot profile is much more likely than all other ballot profiles taken together, so v can ignore the 'secondorder effects' of his vote. Note that we can easily check whether v and b-v satisfy the conditions of Proposition 1, by trying all m = ♣C♣ possible votes. Moreover, these conditions are satisfied whenever ♣W(b-v)♣ > 1, as v can change the outcome in his favor by voting for his most preferred candidate in W(b-v). Thus, from now on we will focus on the case where W(b-v) = ¶w♦ for some w 2 C.

Proposition 2. Suppose that for some voter v and for some ballot profile b-v of the remaining voters we have ♣W(b-v)♣ = 1, and let c be a TH best response of v to b-v. Then s(c) ≥ s⇤ (b-v) - 2.

Proof. Fix a voter v 2 V, a candidate w 2 C and a ballot b-v such that W(b-v) = ¶w♦. Let sw = sw (b-v), s⇤ = s⇤ (b-v), c⇤ = c⇤ (v; b-v), c0 = c0 (v; b-v). Fix a candidate c with s(c) < s⇤ - 2. To show that c is not among v's TH best responses to b-v, we consider two cases.

Case I: c⇤ >v w c⇤ >v w c⇤ >v w In this case, we show that for all sufficiently small " > 0 the quantity ∆ = e U " v (c⇤ ↪ b-v) - e U " v (c↪ b-v) is positive, i.e., the "-TH utility that v derives from voting for c⇤ is higher than his "-TH utility from voting for c. The argument depends on the parity of sw - s⇤ .

First, let us analyze T1. Note that

For every ⌘  ⌘⇤ - 1 and every ballot profile

eb-v 2 B(b-v↪ ⌘) we have sc(w; (c⇤ ↪ eb-v)) > sw - ⌘⇤ , sc(w; (c↪ eb-v)) > sw-⌘⇤ , whereas for every x 2 C∩¶w♦ we have sc(x; (c⇤ ↪ eb-v)) < s⇤ + ⌘⇤ , sc(x; (c↪ eb-v)) < s⇤ + ⌘⇤ . Thus, W(c⇤ ↪ eb-v) = W(c↪ eb-v) = ¶w♦, and hence T1 = 0. Next, consider T3. Since for each x 2 C we have e U " v (x↪ b-v; ⌘) = gx⇣("↪ ⌘), where gx does not depend on ", we can bound the absolute value of T3 as ♣T3♣  ↵"⌘⇤+1 , where ↵ > 0 does not depend on ".

Now, consider T2. There is a ballot eb-v 2 B(b-v↪ ⌘⇤ ) where exactly ⌘⇤ voters err by voting for c⇤ instead of w. We have sc(w; eb-v) = (sw + s⇤ + 1)◁2, sc(c⇤ ; eb-v) = (sw + s⇤ - 1)◁2, so W(c↪ eb-v) = ¶w♦, W(c⇤ ↪ eb-v) = ¶w↪ c⇤ ♦. For every other ballot bb-v 2 B(b-v↪ ⌘⇤ ) it holds that W(c↪ bb-v) = W(c⇤ ↪ bb-v) = ¶w♦. The probability that eb-v occurs under the mixed strategy profile b"-v is ⇣("↪ ⌘⇤ ).

For " < 1◁(2m - 2) we have ⇣("↪ ⌘⇤ ) > "⌘⇤ ◁2n . Thus, T2 ≥ β"⌘⇤ for some β > 0 that does not depend on ". If " is sufficiently small, we have ↵"⌘⇤+1 < β"⌘⇤ , meaning that for such values of " the quantity T1 +T2 +T3 is positive, and hence c cannot be v's "-TH best response to b-v.

sw - s⇤ sw - s⇤ sw - s⇤ is even.

can focus on analyzing e v (c⇤ ↪ b-v; ⌘⇤ ) - e Just as in the previous case, we observe that B(b-v↪ ⌘⇤ ) contains a ballot eb-v where exactly ⌘⇤ voters err by voting for c⇤ instead of w. For this ballot we have W(c↪ eb-v) = ¶w↪ c⇤ ♦, W(c⇤ ↪ eb-v) = ¶c⇤ ♦. For all other ballots bb-v 2 B(b-v↪ ⌘⇤ ) we have W(c↪ bb-v) ✓ ¶w↪ x♦ for some x 2 C⇤ ∩ ¶c⇤ ♦ and either W(c⇤ ↪ bb-v) = W(c↪ bb-v) or W(c⇤ ↪ bb-v) = W(c↪ bb-v) [ ¶c⇤ ♦; as c⇤ >v C ⇤ ∩ ¶c⇤ ♦ and c⇤ >v w, this means that voting for c⇤ is never worse than voting for c. The probability of eb-v under the mixed strategy profile b"-v is at least "⌘⇤ ◁2n for sufficiently small ", so the gain in expected utility that v can obtain by switching his vote from c to c⇤ is at least β"⌘⇤ for some β > 0 that does not depend on ". As in the previous case, this establishes our claim.

The argument for this case is similar. We set ⌘⇤ = (sw - s⇤ )◁2, and represent ∆ as a sum of three terms, corresponding to ⌘ = 0↪ ▷ ▷ ▷ ↪ ⌘⇤ -1, ⌘ = ⌘⇤ , and ⌘ = ⌘⇤ +1↪ ▷ ▷ ▷ ↪ n-1. We show that the first term is 0, since in every ⌘-trembling with ⌘ < ⌘⇤ candidate w is the unique winner no matter how v votes. Also, the absolute value of the third term can be bounded by ↵"⌘⇤+1 for some positive constant ↵. Thus, we U " U " v (c↪ b-v ; ⌘⇤ ).

Case II: w >v c⇤ w >v ⇤ w >v c⇤ The argument for this case is somewhat more complicated. We establish that c is not an "-TH best response to b-v for all sufficiently small " by proving that either w or c0 is a more profitable strategy for small ". If sw - s⇤ is even, we focus on ⌘-tremblings with ⌘ = (sw - s⇤ )◁2 and show that w is more profitable than c, and for odd sw -s⇤ , we look at ⌘-tremblings with ⌘ = (sw - s⇤ + 1)◁2 and show that v's most preferred candidate in ¶w↪ c0 ♦ is more profitable than c. We omit the details due to space constraints.

By inspecting the proof of Proposition 2, one can observe that if x >v y and sc(x; b-v) = sc(y; b-v) then y cannot be v's TH best response to b-v. Combining this observation with Propositions 1 and 2, we discover the following feature of TH best responses.

Corollary 1. A ballot bv can be a TH best response to an intended ballot profile b-v of the other voters only if for some set Z 2 ¶W(b-v)↪C⇤ (b-v)↪C0 (b-v)↪C0 (b-v)♦ we have bv 2 Z and bv >v Z ∩ ¶bv♦.

We will now leverage Corollary 1 to derive a polynomialtime algorithm for computing a TH best response of a given voter v. Importantly, the input to this algorithm is v's utility function and the other voters' ballots; in particular, to compute his best response, v does not need to know the utility functions of other voters.

Theorem 1. Given a voter v 2 V with an ordinary utility function δv and a ballot profile b-v of the remaining voters, we can find in polynomial time a TH-BR of v to b-v.

Proof. Fix a voter v and a ballot profile b-v. By Proposition 1 we can efficiently compute a TH best response if ♣W(b-v)♣ > 1, so from now we will assume that W(b-v) = ¶w♦ for some w 2 C. Let c⇤ = c⇤ (v; b-v), c0 = c0 (v; b-v), c00 = c00 (v; b-v). We know that the set of v's TH best responses to b-v is a subset of ¶w↪ c⇤ ↪ c0 ↪ c00 ♦. Thus, it suffices to compare four values-e U " v (w↪ b-v), e U " v (c⇤ ↪ b-v ), U " U " v (c00 ↪ b-v)-for sufficiently small ".

we will focus on e Suppose first that bv = w. Then for every ballot profile

e v (c0 ↪ b-v) and e Suppose that sw - s⇤ is even and let ⌘⇤ = (sw - s⇤ )◁2 (when sw -s⇤ is odd the analysis is similar, and we omit it due to space constraints). For ⌘ < ⌘⇤ we have W(x↪ eb-v) = ¶w♦ for all eb-v 2 B(b-v↪ ⌘) and all x 2 ¶w↪ c⇤ ↪ c0 ↪ c00 ♦. Further, there is a value ↵ > 0 that does not depend on " such that ♣ e U " v (x↪ b-v; ⌘)♣ < ↵"⌘⇤+1 for each ⌘ ≥ ⌘⇤ + 1 and each x 2 ¶w↪ c⇤ ↪ c0 ↪ c00 ♦. Thus, just as in the proof of Proposition 2, U " v (x↪ b-v; ⌘⇤ ) for x 2 ¶w↪ c⇤ ↪ c0 ↪ c00 ♦.

eb-v 2 B(b-v↪ ⌘⇤ ) we have W(w↪ eb-v) = ¶w♦. Now, suppose that bv = c⇤ . We have W(c⇤ ↪ eb-v) 6= ¶w♦ for a ballot profile eb-v 2 B(b-v↪ ⌘⇤ ) if and only if one of the following four conditions holds:

• w, in which case W(c⇤ ↪ eb-v) = ¶c⇤ ♦; (b) exactly ⌘⇤ voters in eb-v err by voting for some x 2 C⇤ ∩
• (a) exactly ⌘⇤ voters in eb-v err by voting for c⇤ instead of
• ¶c⇤ ♦ instead of w, in which case W(c⇤ ↪ eb-v) = ¶x↪ w♦; (c) exactly ⌘⇤ - 1 voters in eb-v err by voting for c⇤ instead of w, and there is one voter u 2 V ∩ ¶v♦ with bu = w, ebu = y for some y 62 ¶w↪ c⇤ ♦, in which case

W(c⇤ ↪ eb-v) = ¶c⇤ ↪ w♦. Let Pa, Pb, Pc, and Pd be the probability that a ballot profile selected according to b"-v satisfies condition (a), (b), (c), or (d), respectively, and let Pt = Pa + Pb + Pc + Pd. We have

• W(c⇤ ↪ eb-v) = ¶c⇤ ↪ w♦; (d) exactly ⌘⇤ - 1 voters in eb-v err by voting for c⇤ instead of w, and there is one voter u 2 V ∩ ¶v♦ with bu = z, ebu = c⇤ for some z 62 ¶w↪ c⇤ ♦, in which case

with the convention that the second term in the left-hand side is 0 when ♣C⇤ ♣ = 1. We conclude that e U " v (w↪ b-v; ⌘⇤ ) >

e U " v (w↪ b-v; ⌘⇤ ) if X > Ptδv(w) and e U " v (w↪ b-v; ⌘⇤ ) < e U " v (w↪ b-v; ⌘⇤ ) if X < Ptδv(w). Further, since δv is an ordinary utility function, we know that X 6= Ptδv(w), and hence ♣X - Ptδv(w)♣ ≥ β"⌘⇤ for some constant β and all sufficiently small values of ✏. Since the quantities X◁⇣("↪ ⌘⇤ ) and Ptδv(w)◁⇣("↪ ⌘⇤ ) can be computed and compared in polynomial time, this shows that v can decide between w and c⇤ in polynomial time. Note that v may prefer voting for w over voting for c⇤ even if c⇤ >v w; this may happen, for instance, if he finds some candidate in C⇤ ∩¶c⇤ ♦ highly undesirable. In a similar fashion, v can compare all other pairs of candidates from ¶w↪ c⇤ ↪ c0 c00 ♦ and select his best response.

Theorem 1 provides evidence that voters may be able to apply TH-based reasoning when choosing their strategies; indeed, if computing a TH best response was intractable, it would be hard to defend TH equilibria as a reasonable solution concept for Plurality voting games.

4 Properties of Trembling Hand Equilibria

We have shown that a voter can efficiently compute his TH best response to other voters' intended ballot profile. We will now establish several useful properties of trembling hand equilibria of Plurality voting. Throughout this section, we assume that all voters have ordinary utilities, and leave simpler claims without proof due to space constraints.

We first revisit Example 1 and characterize the conditions under which a candidate can be a unanimous winner in a THE. Interestingly, the answer strongly depends on whether the number of voters is even or odd.

Theorem 2. A profile b = (w↪ ▷ ▷ ▷ ↪ w) is a THE if and only if

• ÷ n = ♣V♣ is even and each voter v 2 V prefers w to all other candidates, or

Proof. Suppose that we have ♣V♣ = 2k for some k 2 N. For k = 1 our claim follows from Proposition 1, so assume k > 1. Suppose that a ballot profile b = (w↪ ▷ ▷ ▷ ↪ w) is a THE, and assume for the sake of contradiction that some voter v 2 V has a >v w for some a 2 C. In all ⌘-tremblings with ⌘ < k - 1 candidate w wins irrespective of v's vote, so we focus on (k - 1)-tremblings. If v votes for w, then w is the unique winner in all such tremblings as well. However, there is a (k1)-trembling eb-v where all k-1 erring voters vote for a, and we have W(a↪ eb-v) = ¶a↪w♦, W(a↪ bb-v) = ¶w♦ for any other (k-1)-trembling bb-v. As (δv(a)+δv(w))◁2 > δv(w), voting for w is not a TH best response for v, a contradiction.

• ÷ n is odd and for each voter v 2 V and each candidate a 2 C we have mδv(w)-Pc2C δv(c) ≥ δv(a)-δv(w).

Now, suppose that ♣V♣ = 2k+1 for some k 2 N. Consider a voter v, and let a be his most preferred candidate. From symmetry considerations, it is clear that v's TH best response to b-v is either w or a. To compare the associated TH utilities, it suffices to focus on k-tremblings where all k erring voters vote for the same candidate ci 6= w; if v responds with w, then w remains the unique winner, and if v responds with a, the winning set is ¶w↪ ci♦ when a 6= ci and ¶a♦ otherwise. Since all such tremblings are equally likely and voters' utilities are ordinary, w is a TH best response to b-v if and only if Pc2C∩¶w↪a♦ δv (w)+δv (c) 2 + δv(a)  (m - 1)δv(w). By rearranging the terms, we get the required result.

Theorem 2 says that for an even number of voters a THE outcome can be a consensus only if all voters agree on the best candidate. For an odd number of voters, the situation is more complicated: a candidate w can be a consensus winner if every voter v believes that w provides a 'substantial' advantage (namely, 1m (δv(a) - δv(w)), where a is v's top choice) over a candidate sampled uniformly at random from C.

Example 2. Let C = ¶c1↪ ▷ ▷ ▷ ↪ c5♦, V = ¶u↪ v↪w♦. If we have δz(ci) = i - 1 for each z 2 V and each ci 2 C, then (c5↪ c5↪ c5) and (c4↪ c4↪ c4) are THE (since 5 · 4 - 10 ≥ 4 - 4 and 5·3-10 ≥ 4-3), but (c3↪ c3↪ c3) is not (since 5·2-10 < 4-2). In contrast, if we have δz(ci) = i-1 for i = 1↪ 2↪ 3↪ 4, δz(c5) = 10, for each z 2 V, then (c4↪ c4↪ c4) is not a THE.

Our next result describes THE where the winning set contains at least two candidates. Interestingly, it is reminiscent of existing characterizations of NE with non-singleton winning sets for lazy voters (Theorem 2 in [Desmedt and Elkind, 2010]) and truth-biased voters (Theorem 4 in [Elkind et al., 2015]), under randomized tie-breaking.

Theorem 3. For every trembling hand equilibrium b with ♣W(b)♣ > 1 we have sc(c; b) > 0 if and only if c 2 W(b).

Importantly, Theorem 3 generally implies that contrary to Messner and Polborn [2002; 2011], in our setting the Duverger's law does not hold, i.e., there may exist THE with large winning sets. Even more interestingly, the example below demonstrates that there may exist THE with a single winner and several runners-up.

Example 3. Let C = ¶a↪ b↪ c♦ and let ♣V♣ = 14. There are six voters with preference order abc (where we omit the '>' sign for readability), four voters with preference order bac, and another four voters with preference order cab. Each voter assigns utility 4 to his top choice, 2 to his second choice and 1 to his third choice. In this case, the truthful profile is a trembling hand equilibrium, where candidate a is a unique winner, and both b and c are runners-up.

We now focus on THE where the winning set is a singleton, and not all voters vote for the same candidate, i.e., the set of runners-up is non-empty. In what follows, we consider a THE b with W(b) = ¶w♦ and set sw = sw (b), s⇤ = s⇤ (b).

When the difference between the score of the winner and the score of the runners-up is even, the voters can be partitioned into three groups: the (unique) winner, the runner-up, and the losers (candidates with no votes). Moreover, each voter votes for his most preferred candidate among those with positive scores.

Theorem4. If sw -s⇤ is even then sc(c; b) 2 ¶0↪ s⇤ ♦ for all c 2 C ∩ ¶w♦. Furthermore, bv >v C+(b) ∩ ¶bv♦, 8v 2 V.

Theorem5. If sw -s⇤ is odd then sc(c; b) 2 ¶0↪ s⇤ ↪ s⇤ -1♦ for all c 2 C ∩ ¶w♦.

When sw -s⇤ is odd, there may also exist some candidates whose score is s⇤ - 1.

Note, however, that in the latter case a voter may fail to vote for his most preferred candidate in C+(b): for instance, v may prefer a candidate c with sc(c; b) = s⇤ - 1 to w, yet vote for w, because it is a 'safer' choice.

We will now describe a large class of preference profiles that guarantee the existence of a trembling hand equilibrium.

Theorem 6. Suppose that for a pair of candidates a↪ c 2 C it holds that a strict majority of voters prefer a to c, yet at least three voters prefer c to a. Then there exists a THE b such that W(b) = ¶a♦, C⇤ (b) = ¶c♦, and C +(b) = ¶a↪ c♦.

This result indicates that in large-scale elections we are very likely to have at least one THE; indeed, it is likely that any candidate can be the unique winner in some THE. However, it is possible to construct a small profile with no THE.

Example 4. Let C = ¶a↪ b↪ c↪ d↪ e↪ f♦ and let ♣V♣ = 9. There are six voters with preference order abcdef , one voter with preferences bcdaef , one voter with preferences feadcb, and one voter with preferences cbdefa. Each voter assigns utility 100 to his top choice and utilities in the set ¶1↪ 2↪ 3↪ 4↪ 5♦ to the remaining candidates. Note that no pair of candidates in this election satisfies the conditions of Theorem 6. An extensive case analysis shows that this profile admits no THE.

We conclude this section by showing that, even though we now know quite a bit about the structure of trembling hand equilibria, it may still be difficult to decide whether there is a THE that contains a specific candidate w in its winning set.

Theorem 7. Given a candidate set C, a voter set V, a utility function δv for each voter v 2 V and a distinguished candidate a 2 C, it is NP-hard to decide whether the associated Plurality voting game admits a THE b with a 2 W(b).

5 Discussion and Conclusions

Our results show that trembling hand equilibria of Plurality voting have many good properties. In particular, 'silly' Nash equilibria where all voters vote for an undesirable candidate are eliminated by this equilibrium refinement. Further, THE encourage voters to coordinate on reasonable candidates even when these candidates do not win: all candidates other than the winners are either (almost) runners-up, or receive no votes at all. Also, the problem of computing one's TH best response, while seemingly complicated, turns out to be tractable. On the negative side, Theorem 6 shows that essentially any candidate that is not a Condorcet loser may still become a winner in a THE, i.e., the power of this equilibrium refinement as a tool to eliminate bad equilibria is somewhat limited. Moreover, it can 'overshoot', in that some games have no THE at all (however, such cases are very rare compared to other voting equilibrium refinements studied so far).

There are several open problems suggested by our work. First, it would be desirable to remove or weaken the technical requirement that voters' utilities are ordinary. However, this seems to require looking at ⌘-tremblings for several values of ⌘ simultaneously, which complicates the analysis significantly. Further, it would be interesting to know whether there exists a polynomial-time algorithm for deciding whether a given preference profile admits a THE (note that this is not ruled out by Theorem 7). Another exciting direction, which is enabled by the tractability result of Theorem 1, is exploring the properties of TH best response dynamics, both theoretically and empirically.

Acknowledgments

Svetlana Obraztsova was supported by the I-CORE-ALGO. Edith Elkind was supported by ERC StG 639945. This research has also received financial support from Israel Science Foundation grant #1227/12, UK Research Council for project ORCHID grant EP/I011587/1, COST Action IC1205 on Computational Social Choice, and RFFI grant 14-0100156-a.