The Lipschitz constant of perturbed anonymous games

The Lipschitz constant of a game measures the maximal amount of influence that one player has on the payoff of some other player. The worst-case Lipschitz constant of an n-player k-action $$\delta $$ δ -perturbed game, $$\lambda (n,k,\delta )$$ λ ( n , k , δ ) , is given an explicit probabilistic description. In the case of $$k\ge 3$$ k ≥ 3 , it is identified with the passage probability of a certain symmetric random walk on $${\mathbb {Z}}$$ Z . In the case of $$k=2$$ k = 2 and n even, $$\lambda (n,2,\delta )$$ λ ( n , 2 , δ ) is identified with the probability that two i.i.d. binomial random variables are equal. The remaining case, $$k=2$$ k = 2 and n odd, is bounded through the adjacent (even) values of n. Our characterization implies a sharp closed-form asymptotic estimate of $$\lambda (n,k,\delta )$$ λ ( n , k , δ ) as $$\delta n /k\rightarrow \infty $$ δ n / k → ∞ .