Trembling hand equilibria of plurality voting
File(s)
Accepted version
Author(s)
Obraztsova, S
Rabinovich, Z
Elkind, E
Polukarov, M
Jennings, N
Type
Conference Paper
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.
Date Issued
2016-07-09
Date Acceptance
2015-12-01
Citation
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016, pp.440-446
ISBN
978-1-57735-770-4
Publisher
AAAI Press / International Joint Conferences on Artificial Intelligence
Start Page
440
End Page
446
Journal / Book Title
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence
Copyright Statement
© 2016 International Joint Conferences on Artificial Intelligence
Source
25th International Joint Conference on AI
Publication Status
Published
Start Date
2016-07-09
Finish Date
2016-07-15
Coverage Spatial
New York City, NY, USA