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

__
TR17-056
| 7th April 2017
__

Paul Goldberg, Christos Papadimitriou#### Towards a Unified Complexity Theory of Total Functions

Revisions: 1

__
TR13-136
| 27th September 2013
__

Paul Goldberg, Aaron Roth#### Bounds for the Query Complexity of Approximate Equilibria

__
TR06-005
| 13th December 2005
__

Edith Elkind, Leslie Ann Goldberg, Paul Goldberg#### Nash Equilibria in Graphical Games on Trees Revisited

__
TR05-115
| 27th September 2005
__

Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou#### The complexity of computing a Nash equilibrium

__
TR05-090
| 17th August 2005
__

Paul Goldberg, Christos H. Papadimitriou#### Reducibility Among Equilibrium Problems

Alexandros Hollender, Paul Goldberg

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

Paul Goldberg, Christos Papadimitriou

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

Paul Goldberg, Aaron Roth

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

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

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

Paul Goldberg, Christos H. Papadimitriou

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