Fairness in two-player zero-sum games with bandit feedback

Abstract

We study two-player zero-sum games (TPZSGs) with bandit feedback under fairness constraints requiring every action to be played with probability at least $\hat{I}\pm /m$. Existing instance-dependent results target $\text{pure}$ Nash equilibria, while fairness generically produces $\text{mixed}$ equilibria, a harder learning target. Our key technical tool is a reparametrization: every fair strategy decomposes as $p=(\hat{I}\pm /m)1+(1-\hat{I}\pm )\tilde{p}$ with $\tilde{p}\in \hat{I}{”}_m$, and substituting into the payoff form yields $p^{\top }Aq={\tilde{p}}^{\top }\tilde{A}q$ for a fair payoff matrix $\tilde{A}:=(1-\hat{I}\pm )A+\hat{I}\pm 1c^{\top }$, where $c_j=\frac{1}{m}{\sum }_{i}A(i,j)$ is the column-mean vector. The fair game on $A$ is then equivalent to a standard zero-sum game on $\tilde{A}$, so equilibrium existence, KKT structure, and LP basis stability reduce to classical results applied to $\tilde{A}$. We derive the fair minimax value, fair Nash equilibrium, fair regret, and a clean dual representation showing the price of fairness is at most $\hat{I}\pm (1-1/m)$ and vanishes whenever the unconstrained equilibrium already has full support. Our main result is an $\tilde{O}(T^{2/3})$ regret bound for an Explore-Then-Commit algorithm, $\text{Fair-ETC-TPZSG}$, applicable to general mixed fair equilibria, together with a discussion of why naive action elimination does not readily improve it. When the fair equilibrium has a single dominant action, equivalently when ${\tilde{p}}^{\star }$ is a vertex of $\hat{I}{”}_m$, the bound sharpens to instance-dependent $\tilde{O}(1/\tilde{\hat{I}}”(\hat{I}\pm {)}^2)$, where $\tilde{\hat{I}}”(\hat{I}\pm )$ is the LP-margin gap.