author: niplav, created: 2022-04-05, modified: 2022-04-05, language: english, status: in progress, importance: 2, confidence: likely
Solutions to the textbook “Algorithmic Game Theory”.
$g$ be a two-player game. Now construct a 3-player zero-sum game
$g'$ as following: Add another player
$3$, with one action, and let
the utility of that player be
Then the Nash equilibria of
$G'$ are the same as for
$3$ can't deviate, and the utilities of the other players are not
affected by the actions of
$3$. Therefore, the Nash equilibria in
are the same as for
$g$, and equally hard to find—which means that
Nash equilibria for three-player zero-sum games are at least as hard to
find as for two-player games.