content_image/296239.jpg
For each i , we view the product space A$_{−}$$_{i}$ = ∏ j ̸ = $_{i}$A$_{j}$ as a metric space, with the metric ρ ( a ′ − $_{i}$, a ′′ − $_{i}$) = # { 1 ≤ j ≤ n : j ̸ = i, a ′ j ̸ = a ′′ j } . 

2.1. Definition. The Lipschitz constant of G is given by 

<img src='content_image/296239.jpg'>

where the maximum ranges over all players i , all strategies a$_{i}$ ∈ A$_{i}$ and all pairs a ′ − $_{i}$, a ′′ − i of opponents’ strategy profiles such that ρ ( a ′ − $_{i}$, a ′′ − $_{i}$) = 1. 

Games with Lipschitz constant δ have the property that a player’s payoff does not change by more than δ when one opponent changes his strategy. This implies that for each i and each a$_{i}$ ∈ A$_{i}$ the function f$_{i}$ ( a$_{i}$, · ) is δ –Lipschitz on A$_{−}$$_{i}$ . We denote by L ( n, m, δ ) the set of games with n players, at most m strategies for every player and Lipschitz constant of at most δ . 

2.2. Remark. A notion of ‘influence of a player’ appears also in [1] for a different purpose than in this paper. In our setup, the Lipschitz constant is a property of the game G , while in their setup the influence is a property of the distribution of players’ types and of the mechanism. 

The following Proposition 2.3 establishes a trivial sufficent condition for existence of pure ϵ - equilibrium when the Lipschitz constant is so small that a player’s payoff essentially depends only on her own strategy. 

2.3. Proposition. Let ϵ > 0 and m, n ∈ N . Then every game in L ( n, m, δ ) for δ = ϵ/ 2 n admits a pure ϵ –equilibrium. 

Proof. Let a ∈ A be an arbitrary strategy profile and let a ∗ be a strategy profile such that a ∗ i is a best response to a$_{−}$$_{i}$ for every player i . Then a ∗ is an ϵ –equilibrium. Indeed, for every 4 

