5 papers
Finding a Nash equilibrium of a random win-lose game in expected polynomial time
Andrea Collevecchio, Gabor Lugosi, Adrian Vetta +1
A long-standing open problem in algorithmic game theory asks whether or not there is a polynomial time algorithm to compute a Nash equilibrium in a random bimatrix game. We study r…
Extremal independence in discrete random systems
Mikhail Isaev, Igor Rodionov, Rui-Ray Zhang +1
Let be a sequence of random vectors, where and . Under certain weakly dependence conditions, we prove that the distribut…
Correlation between residual entropy and spanning tree entropy of ice-type models on graphs
Mikhail Isaev, Brendan D. McKay, Rui-Ray Zhang
The logarithm of the number of Eulerian orientations, normalised by the number of vertices, is known as the residual entropy in studies of ice-type models on graphs. The spanning t…
Multivariate Poisson approximation of joint subgraph counts in random graphs via size-biased couplings
Eulalia Nualart, Rui-Ray Zhang
Using Chen-Stein method in combination with size-biased couplings, we obtain the multivariate Poisson approximation in terms of the Wasserstein distance. As applications, we study…
Cumulant expansion for counting Eulerian orientations
Mikhail Isaev, Brendan D. McKay, Rui-Ray Zhang
An Eulerian orientation is an orientation of the edges of a graph such that every vertex is balanced: its in-degree equals its out-degree. Counting Eulerian orientations correspond…