ORIE Colloquium: Sriram Sankaranarayanan (IIM Ahmedabad)

Best-response Algorithms for Lattice Convex-Quadratic Simultaneous Games

We evaluate the best-response (BR) algorithm for lattice convex-quadratic simultaneous games, where the players have nonlinear objectives and unbounded feasible sets. We provide a sufficient condition that if certain interaction matrices (the product of the inverse of the positive definite matrix defining the convex- quadratic terms and the matrix that connects one player’s problem to another’s) have all their singular values less than 1, then the iterates do not diverge regardless of the initial point. We prove that if the iterates are trapped among finitely many strategies (called a trap), a relaxed version of the Nash equilibrium can be calculated by identifying a mixed-strategy Nash equilibrium of the finite game where the players’ strategies are restricted to those in the trap. To establish the tightness of our sufficient condition, we also show examples where even if one singular value of one interaction matrix exceeds 1, there are infinitely many initial points from which the iterates diverge. Finally, we prove that if all the singular values of all the interaction matrices exceed 1, then the iterates diverge from every initial point except possibly a finite set of initializations. (This is a single-author work)

Bio: Sriram Sankaranarayanan is an assistant professor in the Operations and Decision Sciences area at the Indian Institute of Management Ahmedabad. He also serves as the co-chairperson of the Brij Disa Centre for Data Science and Artificial Intelligence. His research focuses on two key areas: 1) algorithm development for multi-firm interactions where he develops algorithms to address challenges arising from interactions among multiple firms; and 2) game-theoretic modeling in operations and supply chains where he constructs game-theoretic models to analyze firm interactions in operational and supply chain contexts. His work has been published in various journals including Management Science, Mathematical Programming, Production and Operations Management.