Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Game Theory:
TR01-046 | 2nd July 2001
Oded Goldreich, Salil Vadhan, Avi Wigderson

On Interactive Proofs with a Laconic Prover

We continue the investigation of interactive proofs with bounded
communication, as initiated by Goldreich and Hastad (IPL 1998).
Let $L$ be a language that has an interactive proof in which the prover
sends few (say $b$) bits to the verifier.
We prove that the complement $\bar L$ has ... more >>>

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-056 | 25th April 2005
Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis

The Price of Optimum in Stackelberg Games

Consider a system M of parallel machines, each with a strictly increasing and differentiable load dependent latency function. The users of such a system are of infinite number and act selfishly, routing their infinitesimally small portion of the total flow r they control, to machines of currently minimum delay. It ... more >>>

TR05-090 | 17th August 2005
Paul Goldberg, Christos H. Papadimitriou

Reducibility Among Equilibrium Problems

We address the fundamental question of whether the Nash equilibria of
a game can be computed in polynomial time. We describe certain
efficient reductions between this problem for
normal form games with a fixed number of players
and graphical games with fixed degree. Our main result is that ... more >>>

TR05-115 | 27th September 2005
Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou

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-033 | 2nd March 2006
Amit Agarwal, Elad Hazan

Efficient Algorithms for Online Game Playing and Universal Portfolio Management

A natural algorithmic scheme in online game playing is called `follow-the-leader', first proposed by Hannan in the 1950's. Simply stated, this method advocates the use of past history to make future predictions, by using the optimal strategy so far as the strategy for the next game iteration. Randomized variations on ... more >>>

TR06-091 | 29th May 2006
Felix Brandt, Felix Fischer, Markus Holzer

Symmetries and the Complexity of Pure Nash Equilibrium

Strategic games may exhibit symmetries in a variety of ways. A common aspect of symmetry, enabling the compact representation of games even when the number of players is unbounded, is that players cannot (or need not) distinguish between the other players. We define four classes of symmetric games by considering ... 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 >>>

TR07-082 | 27th July 2007
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Kalai, Vahab Mirrokni, Christos H. Papadimitriou

The Myth of the Folk Theorem

The folk theorem suggests that finding Nash Equilibria
in repeated games should be easier than in one-shot games. In
contrast, we show that the problem of finding any (epsilon) Nash
equilibrium for a three-player infinitely-repeated game is
computationally intractable (even when all payoffs are in
{-1,0,-1}), unless all of PPAD ... more >>>

TR07-136 | 28th November 2007
Felix Brandt, Felix Fischer, Markus Holzer

Equilibria of Graphical Games with Symmetries

We study graphical games where the payoff function of each player satisfies one of four types of symmetries in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in graphical games with each of the four types of symmetry. Using a ... more >>>

TR08-021 | 3rd March 2008
Shankar Kalyanaraman, Chris Umans

The Complexity of Rationalizing Matchings

Given a set of observed economic choices, can one infer
preferences and/or utility functions for the players that are
consistent with the data? Questions of this type are called {\em
rationalization} or {\em revealed preference} problems in the
economic literature, and are the subject of a rich body of work.

... more >>>

TR08-089 | 28th September 2008
Noam Berger, Kapur Nevin, Schulman Leonard, Vazirani Vijay


Abstract. We study the decision theory of a maximally risk-averse investor | one whose objec-
tive, in the face of stochastic uncertainties, is to minimize the probability of ever going broke. With
a view to developing the mathematical basics of such a theory, we start with a very simple model
more >>>

TR18-001 | 2nd January 2018
Tim Roughgarden

Complexity Theory, Game Theory, and Economics

This document collects the lecture notes from my mini-course "Complexity Theory, Game Theory, and Economics," taught at the Bellairs Research Institute of McGill University, Holetown, Barbados, February 19-23, 2017, as the 29th McGill Invitational Workshop on Computational Complexity.

The goal of this mini-course is twofold: (i) to explain how complexity ... more >>>

ISSN 1433-8092 | Imprint