Computing Equilibria in Games with Stochastic Action Sets

Abstract

The study of learning in games typically assumes that each player always has access to all of their actions. However, in many practical scenarios, players' available actions might be restricted due to exogenous stochasticity. To model this setting, for a game ${\mathcal{G}}_{\mathrm{orig}}$ with action set $A_i$ for each player $i$, we introduce the corresponding Game with Stochastic Action Sets (GSAS) which is parametrized by a probability distribution over the players' set of possible action subsets ${\mathcal{S}}_i\subseteq 2^{A_i}\setminus \{\varnothing \}$. In a GSAS, players' strategies and Nash equilibria (NE) admit prohibitively large representations, and existing algorithms for NE computation scale poorly. Under the assumption that action availabilities are independent between players, we show that NE in two-player zero-sum (2p0s) GSAS can be approximately represented by a compact vector of size $|A_i|$, overcoming the naïve exponential-sized representation. Computationally, we introduce an algorithm that minimizes ranking regret, converging to NE with high probability in 2p0s-GSAS with rate $O(\sqrt{|A_i|\log |A_i|/T})$. Finally, using the iterates of our algorithm, we develop a stochastic approximation procedure to recover compactly represented NE.

47 pages, 8 figures