Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > PAUL GOLDBERG:
All reports by Author Paul Goldberg:

TR18-120 | 21st June 2018
Alexandros Hollender, Paul Goldberg

The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard

The complexity class PPAD is usually defined in terms of the END-OF-LINE problem, in which we are given a concise representation of a large directed graph having indegree and outdegree at most 1, and a known source, and we seek some other degree-1 vertex. We show that variants where we ... more >>>


TR17-056 | 7th April 2017
Paul Goldberg, Christos Papadimitriou

Towards a Unified Complexity Theory of Total Functions

Revisions: 1

The complexity class TFNP is the set of {\em total function} problems that belong to NP: every input has at least one output and outputs are easy to check for validity, but it may be hard to find an output. TFNP is not believed to have complete problems, but it ... more >>>


TR13-136 | 27th September 2013
Paul Goldberg, Aaron Roth

Bounds for the Query Complexity of Approximate Equilibria

We analyze the number of payoff queries needed to compute approximate correlated equilibria. For multi-player, binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For well-supported approximate correlated equilibrium (a restriction where a player's behavior must always be approximately optimal, in the ... 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 >>>


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


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




ISSN 1433-8092 | Imprint