BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T223444Z
UID:Seminar-EcCo-565@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20171206T130000
DTEND:20171206T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Themistoklis Melissourgos: Approximating Nash Equilibria via an Approximate Version of Caratheodory's Theorem\n\nThis talk is based on the paper "Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem" by Barman that appeared in the proceedings of STOC '15. The following part of the paper's abstract describes the subject of the presentation:\n\nWe present algorithmic applications of an approximate version of Caratheodory's theorem. The theorem states that given a set of vectors X in Rd, for every vector in the convex hull of X there exists an ?-close (under the p-norm distance, for 2 ? p < ?) vector that can be expressed as a convex combination of at most b vectors of X, where the bound b depends on ? and the norm p and is independent of the dimension d. This theorem can be derived by instantiating Maurey's lemma, early references to which can be found in the work of Pisier (1981) and Carl (1985). However, in this paper we present a self-contained proof of this result.\nUsing this theorem we establish that in a bimatrix game with n x n payoff matrices A, B, if the number of non-zero entries in any column of A+B is at most s then an ?-Nash equilibrium of the game can be computed in time nO(log s/?2). This, in particular, gives us a polynomial-time approximation scheme for Nash equilibrium in games with fixed column sparsity s. Moreover, for arbitrary bimatrix games - since s can be at most n - the running time of our algorithm matches the best-known upper bound, which was obtained by Lipton, Markakis, and Mehta (2003).\n\nAppeared in STOC 2015.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=565
LOCATION:
END:VEVENT
END:VCALENDAR