On oblivious PTAS's for nash equilibrium

DOI10.1145/1536414.1536427zbMath1304.91014OpenAlexW2118559710MaRDI QIDQ5172700

Constantinos Daskalakis, Christos H. Papadimitriou

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536427

zbMATH Keywords

PTASbimatrix gamesanonymous gamesoblivious algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) (n)-person games, (n>2) (91A06) Approximation algorithms (68W25)

Related Items (19)

A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium ⋮ Computation of sparse and dense equilibrium strategies of evolutionary games ⋮ Query Complexity of Approximate Equilibria in Anonymous Games ⋮ Constant Rank Two-Player Games are PPAD-hard ⋮ The Linear Complementarity Problems with a Few Variables per Constraint ⋮ Query complexity of approximate equilibria in anonymous games ⋮ Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem ⋮ Parameterized complexity of sparse linear complementarity problems ⋮ Parameterized two-player Nash equilibrium ⋮ Nash equilibria: complexity, symmetries, and approximation ⋮ Sparse covers for sums of indicators ⋮ Approximate Nash equilibria in anonymous games ⋮ Bargaining dynamics in exchange networks ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Approximating the existential theory of the reals ⋮ A note on approximate Nash equilibria ⋮ Learning Poisson binomial distributions ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

This page was built for publication: On oblivious PTAS's for nash equilibrium