The Lipschitz constant of perturbed anonymous games

Ron Peretz (), Amnon Schreiber and Ernst Schulte-Geers
Additional contact information
Ron Peretz: Bar-Ilan University
Amnon Schreiber: Bar-Ilan University
Ernst Schulte-Geers: Federal Office for Information Security

International Journal of Game Theory, 2022, vol. 51, issue 2, No 2, 293-306

Abstract: Abstract 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 → ∞ .

Keywords: Anonymous games; Large games; Perturbed games; Approximate Nash equilibrium (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-021-00793-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:51:y:2022:i:2:d:10.1007_s00182-021-00793-x

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-021-00793-x

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().