Pure Strategy Nash Equilibrium And Query Complexity Dr Ratnik Gandhi

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.