Trembling hand equilibria of plurality voting

Svetlana Obraztsova, Zinovi Rabinovich, Edith Elkind, Maria Polukarov, Nicholas R. Jennings

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

8 Citations (Scopus)
34 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publication25th International Joint Conference on Artificial Intelligence (IJCAI 2016), United States, 2016-07-09 - 2016-07-15
Publication statusPublished - 1 Jul 2016

Fingerprint

Dive into the research topics of 'Trembling hand equilibria of plurality voting'. Together they form a unique fingerprint.

Cite this