Kousha Etessami, Andreas Lochbihler

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 >>>

Carme Alvarez, Joaquim Gabarro, Maria Serna

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 >>>

Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye

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 >>>

Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou

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 >>>

Edith Elkind, Leslie Ann Goldberg, Paul Goldberg

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 >>>

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 >>>

Shankar Kalyanaraman, Chris Umans

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 >>>

Paul Spirakis, haralampos tsaknakis

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 >>>

Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum

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 >>>