4 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…
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…