Trembling Hand Equilibria of Plurality Voting

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

Trembling Hand Equilibria of Plurality Voting

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

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 440-445.

Abstract

Trembling hand (TH) equilibria were introduced by Selten in 1975. Intuitively, these are Nash equilibria 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 computing a TH best response and establish many useful properties of TH equilibria in Plurality voting games. On the negative side, we provide an example of a Plurality voting game with no TH equilibria, and show that it is NP-hard to check whether a given Plurality voting game admits a TH equilibrium where a specific candidate is among the election winners.

Svetlana Obraztsova, Zinovi Rabinovich, Edith Elkind, Maria Polukarov, and Nicholas R. Jennings. 2016. Trembling Hand Equilibria of Plurality Voting. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 440–445. https://ijcai.org/proceedings/2016/69

@inproceedings{ijcai2016p69,
  title     = {Trembling Hand Equilibria of Plurality Voting},
  author    = {Obraztsova, Svetlana and Rabinovich, Zinovi and Elkind, Edith and Polukarov, Maria and Jennings, Nicholas R.},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {440--445},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/69},
}

TY  - CPAPER
TI  - Trembling Hand Equilibria of Plurality Voting
AU  - Obraztsova, Svetlana
AU  - Rabinovich, Zinovi
AU  - Elkind, Edith
AU  - Polukarov, Maria
AU  - Jennings, Nicholas R.
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 440
EP  - 445
UR  - https://ijcai.org/proceedings/2016/69
ER  -