The Lipschitz constant of perturbed anonymous games
| Autor: | Ernst Schulte-Geers, Ron Peretz, Amnon Schreiber |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Statistics and Probability Computer Science::Computer Science and Game Theory Economics and Econometrics Probability (math.PR) Stochastic game Characterization (mathematics) Lambda Lipschitz continuity Random walk Combinatorics Mathematics (miscellaneous) Computer Science - Computer Science and Game Theory Bounded function FOS: Mathematics Statistics Probability and Uncertainty Constant (mathematics) Random variable Mathematics - Probability Social Sciences (miscellaneous) Computer Science and Game Theory (cs.GT) Mathematics |
| Zdroj: | International Journal of Game Theory. 51:293-306 |
| ISSN: | 1432-1270 0020-7276 |
| DOI: | 10.1007/s00182-021-00793-x |
| Popis: | The worst-case Lipschitz constant of an $n$-player $k$-action $\delta$-perturbed game, $\lambda(n,k,\delta)$, is given an explicit probabilistic description. In the case of $k\geq 3$, $\lambda(n,k,\delta)$ is identified with the passage probability of a certain symmetric random walk on $\mathbb Z$. In the case of $k=2$ and $n$ even, $\lambda(n,2,\delta)$ is identified with the probability that two two i.i.d.\ Binomial random variables are equal. The remaining case, $k=2$ and $n$ odd, is bounded through the adjacent (even) values of $n$. Our characterisation implies a sharp closed form asymptotic estimate of $\lambda(n,k,\delta)$ as $\delta n /k\to\infty$. Comment: earlier version was submitted to EC20 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink