2.9. Remark. One can define the Lipschitz constant of a game in a slightly different way, to get a stronger result: For every game G let η ( G ) = max {| ( f$_{i}$ ( a ′ $_{i}$, a ′ − $_{i}$) − f$_{i}$ ( a ′′ $_{i}$, a ′ − $_{i}$) ) − ( f$_{i}$ ( a ′ $_{i}$, a ′′ − $_{i}$) − f$_{i}$ ( a ′′ $_{i}$, a ′′ − $_{i}$) ) |} where the maximum ranges over all players i , all strategies a ′ $_{i}$, a ′′ i ∈ A$_{i}$ and all pairs a ′ − $_{i}$, a ′′ − i of opponents’ strategy profiles such that ρ ( a ′ − $_{i}$, a ′′ − $_{i}$) = 1. Then η ( G ) ≤ 2 δ ( G ) so that if δ ( G ) is small then so is η ( G ), but η ( G ) may be small even for games with large Lipschitz constant. Still, Theorem 2.5 has the following simple corollary: 2.10. Corollary. Let ϵ > 0 and m, n ∈ N . Then every game G with n players, at most m strategies per player and with η ( G ) ≤ ϵ/ √ 8 n log(2 mn ) admits a pure ϵ –equilibrium. Proof. Let G be a game with η ( G ) ≤ ϵ/ √ 8 n log(2 mn ). For every player i let ¯ a$_{i}$ ∈ A$_{i}$ and let g$_{i}$ : A → R be the payoff functions given by g$_{i}$ ( a ) = f$_{i}$ ( a ) − f$_{i}$ (¯ a$_{i}$, a$_{−}$$_{i}$ ). Let G ′ be the game with action sets A$_{i}$ and payoff functions g$_{i}$ . Then δ ( G $^{′}$) ≤ η ( G ) so that G ′ has a pure ϵ -equilibrium by Theorem 2.5, but every such an equilibrium is also an ϵ -equilibrium in G . □ 3. Proof of Theorem 2.5 The proof follows Kalai’s [12] proof for anonymous games. The gist of the proof is the observation that a random realized strategy profile of a mixed Nash equilibrium is, with high probability, an ϵ -equilibrium. Kalai dubs this phenomena self–purification . In Kalai’s anonymous setup, the argument relies on the law of large numbers. Here we use the related fact that the value of a Lipschitz function under a random input is concentrated around its expectation. A similar argument appears in Deb and Kalai [9] and Carmona and Pod- czeck [6]. 3.1. Proposition. [13, Corollary 1.17] Let A$_{1}$, . . . , A$_{n}$ be finite sets and let µ = µ$_{1}$ × · · · × µ$_{n}$ be a product probability measure over A = ∏ $_{i}$A$_{i}$ . Let F : A → R be a real valued function 6