Session: Games and Variational Inequalities
Chair: Chuangyin Dang
Cluster: nan
Talk 1: A Characterization of Nash Equilibrium in Behavioral Strategies through $(\gamma,\varepsilon)$-Nash Equilibrium with Local Sequential Rationality under Kreps and Wilson's Consistency and Its Computation
Speaker: Chuangyin Dang
Abstract: This paper develops a characterization of Nash equilibrium in behavioral strategies (NashEBS) through the introduction of $(\gamma,\varepsilon)$-Nash equilibrium with local sequential rationality under Kreps and Wilson's consistency, capitalizing on an extra behavioral strategy profile. For any given $\gamma>0$, we generate a perfect $\gamma$-Nash equilibrium as a limit point of a sequence of $(\gamma,\varepsilon_k)$-Nash equilibrium with $\varepsilon_k\to 0$. We acquire a NashEBS from a limit point of a sequence of perfect $\gamma_q$-Nash equilibrium with $\gamma_q\to 0$. This characterization allows one to analytically find all NashEBSs for small extensive-form games. An application of the characterization yields a polynomial system as a necessary and sufficient condition for determining whether a totally mixed assessment is a $(\gamma,\varepsilon)$-Nash equilibrium. Exploiting the system, we devise differentiable path-following methods to compute a NashEBS by establishing the existence of smooth paths, which are secured from the equilibrium systems of logarithmic-barrier, entropy-barrier, square-root-barrier, and convex-quadratic-penalty extensive-form games. Comprehensive numerical results further confirm the efficiency of the methods.
Talk 2: A Bandit Learning Approach to Continuous Multi-Agent Games
Speaker: Jianghai Hu
Abstract: A variety of practical problems can be modeled by multi-player games where a group of self-interested players aim at optimizing their own local objectives, where the objectives depend on the (continuous) actions taken by other players. In many cases, the local gradient information of each player's objective, critical for many existing algorithms, is not available. In this talk, we will focus on designing solution algorithms for multi-player games using bandit feedback, i.e., the only available feedback for each player is the realized objective values. Our proposed solution algorithms are based on the residual feedback scheme and the extra-gradient methods, and require only one query of objective function per iteration for each player. We show that the actual sequence of play generated by the algorithms converges to the game's critical points and characterize the convergence rates for certain classes of games. We also discuss extensions when there are delays in receiving feedback and when a multi-point estimation scheme is used. Numerical examples will be given to illustrate the effectiveness of the proposed algorithms.
Talk 3: PEPit-Assisted Primal-Dual Coordinate Descent Method for Weak-MVI Problems
Speaker: Iyad WALWIL
Abstract: We introduce two novel primal-dual algorithms for tackling non-convex, non-concave, and non-smooth saddle point problems characterized by the weak Minty variational inequality (MVI). The first algorithm generalizes the well-known Primal-Dual Hybrid Gradient (PDHG) method to address this challenging problem class. The second algorithm introduces a randomly extrapolated primal-dual coordinate descent approach, extending the Stochastic Primal-Dual Hybrid Gradient (SPDHG) algorithm. Designing a coordinated algorithm to solve non-convex, non-concave saddle point problems is unprecedented, and proving its convergence posed significant difficulties. This challenge motivated us to utilize PEPit, a Python-based tool for computer-assisted worst-case analysis of first-order optimization methods. By integrating PEPit with automated Lyapunov function techniques, we successfully derived our second novel algorithm. Both methods are effective under a mild condition on the weak-MVI parameter, achieving linear convergence with constant step sizes that adapt to the problem’s structure. Numerical experiments on sigmoid and perceptron-regression problems validate our theoretical findings.
