Feeds:
Posts

## Taking out the garbage, quasi-strict equilibrium, and PPAD

Suppose Alice, Bob, and Charlie want to decide who has to take out the garbage by playing the following game. Each of the players independently and simultaneously raises his hand or not. Alice loses if exactly one player raises his hand, whereas Bob loses if exactly two players raise their hands, and Charlie loses if either all or no players raise their hand. A normal-form representation of the situation looks as follows (Alice chooses rows, Bob columns, and Charlie matrices).

The game exhibits some peculiar phenomena despite the existence of a unique Nash equilibrium: Alice raises her hand, Bob does not raise his hand, and Charlie randomizes with equal probability. Charlie couldn’t be happier with the equilibrium as he will never have to take out the garbage (and could even decide who has to do the job by playing a pure strategy instead).

The security level of all players is 0.5 and the expected payoff in the Nash equilibrium is (0.5, 0.5, 1). However, the minimax strategies of Alice and Bob are different from their equilibrium strategies, i.e., they can guarantee their equilibrium payoff by not playing their respective equilibrium strategies (a phenomenon that was also observed by Aumann)! The solution in which all players play their minimax strategies obviously suffers from the fact this strategy profile fails to be an equilibrium: Both Alice and Bob would want to deviate. On top of that, the unique equilibrium is particularly weak in the sense that it fails to be quasi-strict, i.e., all players could as well play any other strategy without jeopardizing their payoff.

Quasi-strict equilibrium is an equilibrium refinement proposed in 1973 by Harsanyi and requires that all pure best responses are played with positive probability. Harsanyi showed that in almost all games all equilibria are quasi-strict. Indeed the three-player game above (taken from this paper) is one of the very few exceptions. Quasi-strict equilibrium is rather attractive from an axiomatic perspective. For example, it has been shown that the existence of quasi-strict equilibrium is sufficient to justify the assumption of common knowledge of rationality when players are ‘cautious’ (for more details see here and here).

In 1999, Henk Norde proved that every two-player game contains a quasi-strict equilibrium (via a rather elaborate proof using Brouwer’s fixed-point theorem), strengthening earlier results which showed existence in zero-sum games, bimatrix games with a finite number of equilibria, 2×n games, etc. Norde’s existence result implies that computing a quasi-strict equilibrium is PPAD-hard (while this problem was shown NP-hard for games with at least three players). Curiously, however, membership in PPAD for two-player games remains open due to the intricate existence proof by Norde (see also this review of Norde’s paper by Bernhard von Stengel).

Coming back to the example, it seems as if Charlie has to live with the deficiencies of Nash equilibrium and prepare to take out the garbage with positive probability.