Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with PPAD-Completeness:
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 >>>

TR09-041 | 9th April 2009
Shiva Kintali, Laura J Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng

Reducibility Among Fractional Stability Problems

"As has often been the case with NP-completeness proofs, PPAD-completeness proofs will be eventually refined to cover simpler and more realistic looking classes of games. And then researchers will strive to identify even simpler classes." --Papadimitriou (chapter 2 of Algorithmic Game Theory book)

In a landmark paper, Papadimitriou introduced a ... more >>>

TR21-128 | 4th September 2021
Xiaotie Deng, Yuhao Li, David Mguni, Jun Wang, Yaodong Yang

On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games

Similar to the role of Markov decision processes in reinforcement learning, Markov Games (also called Stochastic Games)lay down the foundation for the study of multi-agent reinforcement learning (MARL) and sequential agent interactions. In this paper, we introduce the solution concept, approximate Markov Perfect Equilibrium (MPE), to finite-state Stochastic Games repeated ... more >>>

ISSN 1433-8092 | Imprint