The Lipschitz Constant of Perturbed Anonymous Games

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 \...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-05
Main Authors: Peretz, Ron, Schreiber, Amnon, Schulte-Geers, Ernst
Format: Article
Language:English
Subjects:
Random variables
Random walk
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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\).
ISSN:2331-8422