Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NASH EQUILIBRIA:
Reports tagged with Nash equilibria:
TR04-055 | 27th May 2004
Kousha Etessami, Andreas Lochbihler

#### The computational complexity of Evolutionarily Stable Strategies

Game theory has been used for a long time to study phenomena in evolutionary biology, beginning systematically with the seminal work of John Maynard Smith. A central concept in this connection has been the notion of an evolutionarily stable strategy (ESS) in a symmetric two-player strategic form game. A regular ... more >>>

TR05-031 | 1st March 2005
Carme Alvarez, Joaquim Gabarro, Maria Serna

#### Pure Nash equilibria in games with a large number of actions

We study the computational complexity of deciding the existence of a
Pure Nash Equilibrium in multi-player strategic games.
We address two fundamental questions: how can we represent a game?, and
how can we represent a game with polynomial pay-off functions?
Our results show that the computational complexity of
deciding ... more >>>

TR05-055 | 19th May 2005
Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye

#### Leontief Economies Encode Nonzero Sum Two-Player Games

We give a reduction from any two-player game to a special case of
the Leontief exchange economy, with the property that the Nash equilibria of the game and the
equilibria of the market are in one-to-one correspondence.

Our reduction exposes a potential hurdle inherent in solving certain
families of market ... more >>>

TR05-115 | 27th September 2005

#### The complexity of computing a Nash equilibrium

We resolve the question of the complexity of Nash equilibrium by
showing that the problem of computing a Nash equilibrium in a game
with 4 or more players is complete for the complexity class PPAD.
Our proof uses ideas from the recently-established equivalence
between polynomial-time solvability of normal-form games and
more >>>

TR06-005 | 13th December 2005
Edith Elkind, Leslie Ann Goldberg, Paul Goldberg

#### Nash Equilibria in Graphical Games on Trees Revisited

Graphical games have been proposed as a game-theoretic model of large-scale
distributed networks of non-cooperative agents. When the number of players is
large, and the underlying graph has low degree, they provide a concise way to
represent the players' payoffs. It has recently been shown that the problem of
finding ... more >>>

TR06-023 | 7th February 2006
Xi Chen, Xiaotie Deng, Shang-Hua Teng

By proving that the problem of computing a $1/n^{\Theta(1)}$-approximate Nash equilibrium remains \textbf{PPAD}-complete, we show that the BIMATRIX game is not likely to have a fully polynomial-time approximation scheme. In other words, no algorithm with time polynomial in $n$ and $1/\epsilon$ can compute an $\epsilon$-approximate Nash equilibrium of an $n\times ... more >>> TR07-059 | 6th July 2007 Shankar Kalyanaraman, Chris Umans #### Algorithms for Playing Games with Limited Randomness We study multiplayer games in which the participants have access to only limited randomness. This constrains both the algorithms used to compute equilibria (they should use little or no randomness) as well as the mixed strategies that the participants are capable of playing (these should be sparse). We frame algorithmic ... more >>> TR07-067 | 22nd May 2007 Paul Spirakis, haralampos tsaknakis #### Computing 1/3-approximate Nash equilibria of bimatrix games in polynomial time. Revisions: 2 In this paper we propose a methodology for determining approximate Nash equilibria of non-cooperative bimatrix games and, based on that, we provide a polynomial time algorithm that computes$\frac{1}{3} + \frac{1}{p(n)} $-approximate equilibria, where$p(n)\$ is a polynomial controlled by our algorithm and proportional to its running time. The ... more >>>

TR19-074 | 22nd May 2019
Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum

#### Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir

The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.

We show that ... more >>>

ISSN 1433-8092 | Imprint