Seminars

View all Seminars  |  Download ICal for this event

Query-Efficient Algorithms to Find the Unique Nash Equilibrium in a Two-Player Zero-Sum Matrix Game

Series: Bangalore Theory Seminars

Speaker: Arnab Maiti, University of Washington

Date/Time: Feb 23 11:00:00

Location: Online Talk (See Teams link below)

Abstract:
We study the query complexity of identifying Nash equilibria in two-player zero-sum matrix games. Grigoriadis and Khachiyan (1995) showed that any deterministic algorithm needs to query Ω(n2) entries in worst case from an n �? n input matrix in order to compute an ε-approximate Nash equilibrium, where ε < 1/2 . Moreover, they designed a randomized algorithm that queries O(nlog(n)/ε2) entries from the input matrix in expectation and returns an ε-approximate Nash equilibrium when the entries of the matrix are bounded between �??1 and 1. However, these two results do not completely characterize the query complexity of finding an exact Nash equilibrium in two-player zero-sum matrix games. In this work, we characterize the query complexity of finding an exact Nash equilibrium for two-player zero-sum matrix games that have a unique Nash equilibrium (x*,y*). We first show that any randomized algorithm needs to query Ω(nk) entries of the input matrix A �?? Rn�?n in expectation in order to find the unique Nash equilibrium where k = |supp(x*)|. We complement this lower bound by presenting a simple randomized algorithm that, with probability 1�??δ, returns the unique Nash equilibrium by querying at most O(nk4 · polylog(n/δ)) entries of the input matrix A �?? Rn�?n. In the special case when the unique Nash Equilibrium is a pure-strategy Nash equilibrium (PSNE), we design a simple deterministic algorithm that finds the PSNE by querying at most O(n) entries of the input matrix.


Microsoft teams link:

Link


We are grateful to the Kirani family for generously supporting the theory seminar series

Hosts: KVN Sreenivas, Rameesh Paul, Rahul Madhavan, Manisha Padala