Suppose that an @math -simplex is partitioned into @math convex regions having disjoint interiors and distinct labels, and we may learn the label of any point by querying it. The learning objective is to know, for any point in the simplex, a label that occurs within some distance @math from that point. We present two algorithms for this task: Constant-Dimension Generalised Binary Search (CD-GBS), which for constant @math uses @math queries, and Constant-Region Generalised Binary Search (CR-GBS), which uses CD-GBS as a subroutine and for constant @math uses @math queries. We show via Kakutani's fixed-point theorem that these algorithms provide bounds on the best-response query complexity of computing approximate well-supported equilibria of bimatrix games in which one of the players has a constant number of pure strategies. We also partially extend our results to games with multiple players, establishing further query complexity bounds for computing approximate well-supported equilibria in this setting.
For a bimatrix game, simple @math -close labellings can be constructed by querying best responses at mixed strategies arising as uniform distributions over sufficiently large multisets of pure strategies. As a consequence of our main theorem, best responses to these multiset distributions contain enough information to compute approximate WSNE. This result is in the spirit of @cite_0 and @cite_1 , who aim to quantify specific @math such that some approximate equilibrium arises as a uniform mixture over multisets of size @math . We note in our scenario that there is also a guaranteed existence of an approximate equilibrium using sufficiently large multisets, however verifying that a specific pair of mixed strategies is an approximate WSNE is not straightforward using only best response queries. This is in contrast to the verification of approximate equilibria via utility queries as studied in @cite_0 .
@cite_0 @cite_1
1941744740 2131967794
We show that in any n -player, m -action normal-form game, we can obtain an approximate equilibrium by sampling any mixed-action equilibrium a small number of times. We study three types of equilibria: Nash, correlated, and coarse-correlated. For each one we obtain upper and lower bounds on the number of samples required for the empirical distribution over the sampled action profiles to form an approximate equilibrium with probability close to 1. These bounds imply that using a small number of samples we can test whether or not players are playing according to an approximate equilibrium, even in games where n and m are large. In addition, our results substantially improve previously known upper bounds on the support size of approximate equilibria in games with many players. In particular, for the three types of equilibria we show the existence of approximate equilibrium with support-size polylogarithmic in n and m , whereas the previously best-known upper bounds were polynomial in n ( [Hemon S, de Rougemont M, Santha M (2008) Approximate nash equilibria for multi-player games. Algorithmic Game Theory (Springer), 267–278], Germano and Lugosi [Germano F, Lugosi G (2007) Existence of sparsely supported correlated equilibria. Econom. Theory 32(3):575–578], [Hart S, Mas-Colell A, Babichenko Y (2013) Simple Adaptive Strategies: From Regret-Matching to Uncoupled Dynamics , Vol. 4 (World Scientific Publishing Company)]). We prove the existence of e-Nash equilibrium strategies with support logarithmic in the number of pure strategies. We also show that the payoffs to all players in any (exact) Nash equilibrium can be e-approximated by the payoffs to the players in some such logarithmic support e-Nash equilibrium. These strategies are also uniform on a multiset of logarithmic size and therefore this leads to a quasi-polynomial algorithm for computing an e-Nash equilibrium. To our knowledge this is the first subexponential algorithm for finding an e-Nash equilibrium. Our results hold for any multiple-player game as long as the number of players is a constant (i.e., it is independent of the number of pure strategies). A similar argument also proves that for a fixed number of players m, the payoffs to all players in any m-tuple of mixed strategies can be e-approximated by the payoffs in some m-tuple of constant support strategies.We also prove that if the payoff matrices of a two person game have low rank then the game has an exact Nash equilibrium with small support. This implies that if the payoff matrices can be well approximated by low rank matrices, the game has an e-equilibrium with small support. It also implies that if the payoff matrices have constant rank we can compute an exact Nash equilibrium in polynomial time.