Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem (Q4571924): Difference between revisions

Latest revision as of 01:27, 16 July 2024

scientific article; zbMATH DE number 6898315

Language	Label	Description	Also known as
English	Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem	scientific article; zbMATH DE number 6898315

Statements

instance of

scholarly article

0 references

title

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

0 references

author

Siddharth Barman

0 references

published in

SIAM Journal on Computing

0 references

publication date

4 July 2018

0 references

zbMATH Keywords

Carathéodory's theorem

0 references

Nash equilibria

0 references

bilinear and quadratic programs

0 references

Khintchine inequality

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

The Cover Number of a Matrix and its Algorithmic Applications

0 references

The approximate rank of a matrix and its algorithmic applications

0 references

A generalization of Caratheodory's theorem

0 references

Q4790110

0 references

Detecting high log-densities

0 references

New algorithms for approximate Nash equilibria in bimatrix games

0 references

Q3834561

0 references

ETH Hardness for Densest-k-Subgraph with Perfect Completeness

0 references

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis

0 references

Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces

0 references

Settling the complexity of computing two-player Nash equilibria

0 references

On the Complexity of Approximating a Nash Equilibrium

0 references

The Complexity of Computing a Nash Equilibrium

0 references

A note on approximate Nash equilibria

0 references

On oblivious PTAS's for nash equilibrium

0 references

Q3594446

0 references

How Hard Is It to Approximate the Best Nash Equilibrium?

0 references

Games of fixed rank: a hierarchy of bimatrix games

0 references

Polynomial algorithms for approximating Nash equilibria of bimatrix games

0 references

Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games

0 references

Classical Banach spaces

0 references

Two-person nonzero-sum games and quadratic programming

0 references

Q4530626

0 references

Maxima for Graphs and a New Proof of a Theorem of Turán

0 references

Algorithmic Game Theory

0 references

Q5726007

0 references

Q3952642

0 references

Moment inequalities for sums of random matrices and their applications in optimization

0 references

Q4768187

0 references

An Optimization Approach for Approximate Nash Equilibria

0 references

A Generalization of Radon's Theorem

0 references

Identifiers

zbMATH Open document ID

1416.91016

0 references

DOI

10.1137/15M1050574

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4571924

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+The Cover Number of a Matrix and its Algorithmic Applications
+Normal rank
@@ Property / cites work @@
+The approximate rank of a matrix and its algorithmic applications
+Normal rank
@@ Property / cites work @@
+A generalization of Caratheodory's theorem
@@ Property / cites work: A generalization of Caratheodory's theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Q4790110
@@ Property / cites work: Q4790110 / rank @@
+Normal rank
@@ Property / cites work @@
+Detecting high log-densities
@@ Property / cites work: Detecting high log-densities / rank @@
+Normal rank
@@ Property / cites work @@
+New algorithms for approximate Nash equilibria in bimatrix games
+Normal rank
@@ Property / cites work @@
+Q3834561
@@ Property / cites work: Q3834561 / rank @@
+Normal rank
@@ Property / cites work @@
+ETH Hardness for Densest-<i>k</i>-Subgraph with Perfect Completeness
+Normal rank
@@ Property / cites work @@
+Approximating the best Nash Equilibrium in <i>n<sup>o</sup></i><sup>(log <i>n</i>)</sup>-time breaks the Exponential Time Hypothesis
+Normal rank
@@ Property / cites work @@
+Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
+Normal rank
@@ Property / cites work @@
+Settling the complexity of computing two-player Nash equilibria
+Normal rank
@@ Property / cites work @@
+On the Complexity of Approximating a Nash Equilibrium
+Normal rank
@@ Property / cites work @@
+The Complexity of Computing a Nash Equilibrium
@@ Property / cites work: The Complexity of Computing a Nash Equilibrium / rank @@
+Normal rank
@@ Property / cites work @@
+A note on approximate Nash equilibria
@@ Property / cites work: A note on approximate Nash equilibria / rank @@
+Normal rank
@@ Property / cites work @@
+On oblivious PTAS's for nash equilibrium
@@ Property / cites work: On oblivious PTAS's for nash equilibrium / rank @@
+Normal rank
@@ Property / cites work @@
+Q3594446
@@ Property / cites work: Q3594446 / rank @@
+Normal rank
@@ Property / cites work @@
+How Hard Is It to Approximate the Best Nash Equilibrium?
+Normal rank
@@ Property / cites work @@
+Games of fixed rank: a hierarchy of bimatrix games
+Normal rank
@@ Property / cites work @@
+Polynomial algorithms for approximating Nash equilibria of bimatrix games
+Normal rank
@@ Property / cites work @@
+Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
+Normal rank
@@ Property / cites work @@
+Classical Banach spaces
@@ Property / cites work: Classical Banach spaces / rank @@
+Normal rank
@@ Property / cites work @@
+Two-person nonzero-sum games and quadratic programming
+Normal rank
@@ Property / cites work @@
+Q4530626
@@ Property / cites work: Q4530626 / rank @@
+Normal rank
@@ Property / cites work @@
+Maxima for Graphs and a New Proof of a Theorem of Turán
+Normal rank
@@ Property / cites work @@
+Algorithmic Game Theory
@@ Property / cites work: Algorithmic Game Theory / rank @@
+Normal rank
@@ Property / cites work @@
+Q5726007
@@ Property / cites work: Q5726007 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3952642
@@ Property / cites work: Q3952642 / rank @@
+Normal rank
@@ Property / cites work @@
+Moment inequalities for sums of random matrices and their applications in optimization
+Normal rank
@@ Property / cites work @@
+Q4768187
@@ Property / cites work: Q4768187 / rank @@
+Normal rank
@@ Property / cites work @@
+An Optimization Approach for Approximate Nash Equilibria
+Normal rank
@@ Property / cites work @@
+A Generalization of Radon's Theorem
@@ Property / cites work: A Generalization of Radon's Theorem / rank @@
+Normal rank