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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 440-446 |
| Number of pages | 7 |
| Journal | IJCAI International Joint Conference on Artificial Intelligence |
| Volume | 2016-January |
| State | Published - 2016 |
| Event | 25th International Joint Conference on Artificial Intelligence, IJCAI 2016 - New York, United States Duration: Jul 9 2016 → Jul 15 2016 |
Funding
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-01-00156-a
ASJC Scopus subject areas
- Artificial Intelligence