Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem
From MaRDI portal
Publication:4571924
DOI10.1137/15M1050574zbMath1416.91016MaRDI QIDQ4571924
Publication date: 4 July 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) 2-person games (91A05) Discrete geometry (52C99) Approximation algorithms (68W25) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04)
Related Items
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games, A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games, Approximate real symmetric tensor rank, \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\), Sampling-based dimension reduction for subspace approximation with outliers, Sparse convex hull coverage, Stable fractional matchings, Escaping Braess's paradox through approximate Caratheodory's theorem
Cites Work
- Moment inequalities for sums of random matrices and their applications in optimization
- Games of fixed rank: a hierarchy of bimatrix games
- A note on approximate Nash equilibria
- Polynomial algorithms for approximating Nash equilibria of bimatrix games
- New algorithms for approximate Nash equilibria in bimatrix games
- Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
- A generalization of Caratheodory's theorem
- Two-person nonzero-sum games and quadratic programming
- Classical Banach spaces
- Detecting high log-densities
- On the Complexity of Approximating a Nash Equilibrium
- The Cover Number of a Matrix and its Algorithmic Applications
- How Hard Is It to Approximate the Best Nash Equilibrium?
- Settling the complexity of computing two-player Nash equilibria
- An Optimization Approach for Approximate Nash Equilibria
- ETH Hardness for Densest-k-Subgraph with Perfect Completeness
- On oblivious PTAS's for nash equilibrium
- The Complexity of Computing a Nash Equilibrium
- Maxima for Graphs and a New Proof of a Theorem of Turán
- A Generalization of Radon's Theorem
- Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis
- Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
- Algorithmic Game Theory
- The approximate rank of a matrix and its algorithmic applications
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
