Showing cs.GTShow all
2 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…
cs.GT2025
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…