# Corelab Seminar

*2014-2015*

### Kyriakos Axiotis (NTUA)

* Approximating Nash Equilibria and Dense Subgraphs via an
Approximate Version of Caratheodory’s Theorem
*

**Abstract.**

We present a recent paper of Siddharth Barman, introducing algorithmic applications of an approximate version of Caratheodory's theorem about convex hulls in R^d. Using this theorem Barman establishes an algorithm for computing ε-Nash equilibria for bimatrix games, parameterized by the sparsity of the payoff matrices. This yields a polynomial time approximation scheme for games with fixed column sparsity. The same theorem leads to an additive approximation algorithm for the normalized densest k-subgraph problem (parameterized by the maximum degree d) and also for the densest

k x k-bipartite subgraph problem.