黑料不打烊

Title: Finding Nash equilibria in random win-lose games

Abstract: Finding a Nash equilibrium in large two-person games is known to be computationally hard in the worst case. In this talk we discuss whether in "typical" games this is still the case. In particular, we consider random win-lose games, where the entries of the payoff matrices are independent Bernoulli random variables with parameter p. We show that for a wide range of values of the parameter p, there is an expected polynomial time algorithm that computes a Nash equilibrium. The talk is based on joint work with Andrea Collevecchio, Adrian Vetta, and Rui-Ray Zhang.

Zoom Link: