2 citations · 5 across the 9 of their papers we have counts for
10 papers
Cycle structure of best-response dynamics in random bimatrix games
Georgios Nikolaos Karelas, Gábor Lugosi, Rui-Ray Zhang
We study the best-response dynamics in games with random payoffs. We consider two-player bimatrix games, with strategies each. We assume that payoffs come from a continuous dis…
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…
On Pauling's residual entropy estimate for regular graphs with growing degree
M. Hasheminezhad, M. Isaev, B. D. McKay +1
In 1935, Pauling proposed an estimate for the number of Eulerian orientations of a graph in the context of the theoretical behaviour of water ice. The logarithm of the number of Eu…
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…
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…
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…
Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence
Rui-Ray Zhang
Let integer and integer . Define the binomial random -uniform hypergraph to be the -uniform graph on the vertex set such that each…
Generalization bounds for learning under graph-dependence: A survey
Rui-Ray Zhang, Massih-Reza Amini
Traditional statistical learning theory relies on the assumption that data are identically and independently distributed (i.i.d.). However, this assumption often does not hold in m…
When Janson meets McDiarmid: Bounded difference inequalities under graph-dependence
Rui-Ray Zhang
We establish concentration inequalities for Lipschitz functions of dependent random variables, whose dependencies are specified by forests. We also give concentration results for d…
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…