Trembling hand (TH) equilibria were introduced by Selten in 1975. Intuitively, these are Nash equi- libria that remain stable when players assume that there is a small probability that other players will choose off-equilibrium strategies. This concept is useful for equilibrium refinement, i.e., selecting the most plausible Nash equilibria when the set of all Nash equilibria can be very large, as is the case, for instance, for Plurality voting with strategic voters. In this paper, we analyze TH equilibria of Plurality voting. We provide an efficient algorithm for com- puting a TH best response and establish many use- ful properties of TH equilibria in Plurality voting games. On the negative side, we provide an exam- ple of a Plurality voting game with no TH equilib- ria, and show that it is NP-hard to check whether a given Plurality voting game admits a TH equilib- rium where a specific candidate is among the elec- tion winners.
|Title of host publication
|25th International Joint Conference on Artificial Intelligence (IJCAI 2016), United States, 2016-07-09 - 2016-07-15
|Published - 1 Jul 2016