37 citations · 126 across the 31 of their papers we have counts for
34 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…
Once-Reinforced and Self-Interacting Random Walks beyond exchangeability
Andrea Collevecchio, Pierre Tarrès
We present the first rigorous quantitative analysis of once-reinforced random walks (ORRW) on general graphs, based on a novel change of measure formula.~This enables us to prove l…
Basins of Attraction in Two-Player Random Ordinal Potential Games
Andrea Collevecchio, Hlafo Alfie Mimun, Matteo Quattropani +1
We consider the class of two-person ordinal potential games where each player has the same number of actions . Each game in this class admits at least one pure Nash equilibrium…
Finding pure Nash equilibria in large random games
Andrea Collevecchio, Tuan-Minh Nguyen, Ziwen Zhong
Best Response Dynamics (BRD) is a class of strategy updating rules to find Pure Nash Equilibria (PNE) in a game. At each step, a player is randomly picked, and the player switches…
Strongly vertex-reinforced jump process on graphs with bounded degree
Andrea Collevecchio, Tuan-Minh Nguyen
We study asymptotic behaviours of a non-linear vertex-reinforced jump process defined on an arbitrary infinite graph with bounded degree. We prove that if the reinforcement functio…
A class of non-reversible hypercube long-range random walks and Bernoulli autoregression
Andrea Collevecchio, Robert C. Griffiths
We study a large class of long-range random walks which take values on the vertices of an N dimensional hypercube. These processes are connected with multivariate Bernoulli autoreg…