Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem

DOI10.1137/15M1050574zbMath1416.91016MaRDI QIDQ4571924

Siddharth Barman

Publication date: 4 July 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

Khintchine inequalityNash equilibriaCarathéodory's theorembilinear and quadratic programs

Mathematics Subject Classification ID

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 (8)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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 n^{o(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

This page was built for publication: Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem