Speaker: Ratnik Gandhi
Title: Pure Strategy Nash Equilibrium and Query Complexity
Abstract:
Nash equilibrium is one of the central solution concepts in Game theory. A pure strategy Nash equilibrium is a deterministic strategy profile from which no players have any incentive to unilaterally deviate. It has been shown that computing a Nash equilibrium is hard. In this talk, we will consider a query model for computing a pure strategy Nash equilibrium. After discussing the necessary game theoretic background, we will go over a result that gives a lower bound on the query complexity of computing a pure strategy Nash equilibrium. We shall further discuss some recent advances under the same model.