2 citations · 5 across the 9 of their papers we have counts for
Showing 2025Show all
3 papers · 1 filter
cs.GT2025
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…
math.CO2025
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…
math.PR2025
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…