Search for: All records

We study the query complexity of finding the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \)in two-player zero-sum matrix games. Fearnley and Savani [18] showed that for any randomized algorithm, there exists ann×ninput matrix where it needs to queryΩ(n²) entries in expectation to compute asingleNash equilibrium. On the other hand, Bienstock et al. [5] showed that there is a special class of matrices for which one can queryO(n) entries and compute its set of all Nash equilibria. However, these results do not fully characterize the query complexity of finding the set of all Nash equilibria in two-player zero-sum matrix games. In this work, we characterize the query complexity of finding the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \)in terms of the number of rowsnof the input matrix\(A \in \mathbb {R}^{n \times n} \), row support size\(k_1 := |\bigcup \limits _{x \in \mathcal {X}_\ast } \text{supp}(x)| \), and column support size\(k_2 := |\bigcup \limits _{y \in \mathcal {Y}_\ast } \text{supp}(y)| \). We design a simple yet non-trivial randomized algorithm that returns the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \)by querying at mostO(nk⁵· polylog(n)) entries of the input matrix\(A \in \mathbb {R}^{n \times n} \)in expectation, wherek≔ max{k₁,k₂}. This upper bound is tight up to a factor of poly(k), as we show that for any randomized algorithm, there exists ann×ninput matrix with min {k₁,k₂} = 1, for which it needs to queryΩ(nk) entries in expectation in order to find the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \). 

Leading approaches to algorithmic fairness and policy-induced distribution shift are often misaligned with long-term objectives in sequential settings. We aim to correct these shortcomings by ensuring that both the objective and fairness constraints account for policy-induced distribution shift. First, we motivate this problem using an example in which individuals subject to algorithmic predictions modulate their willingness to participate with the policy maker. Fairness in this example is measured by the variance of group participation rates. Next, we develop a method for solving the resulting constrained, non-linear optimization problem and prove that this method converges to a fair, locally optimal policy given first-order information. Finally, we experimentally validate our claims in a semi-synthetic setting. 

Leading approaches to algorithmic fairness and policy-induced distribution shift are often misaligned with long-term objectives in sequential settings. We aim to correct these shortcomings by ensuring that both the objective and fairness constraints account for policy-induced distribution shift. First, we motivate this problem using an example in which individuals subject to algorithmic predictions modulate their willingness to participate with the policy maker. Fairness in this example is measured by the variance of group participation rates. Next, we develop a method for solving the resulting constrained, non-linear optimization problem and prove that this method converges to a fair, locally optimal policy given first-order information. Finally, we experimentally validate our claims in a semi-synthetic setting.