Angelo Fanelli

Computing Better Approximate Pure Nash Equilibria in Payoff-maximization Potential Games

It is shown that standard approaches based on unilateral improvement moves can fail to provide any finite approximation guarantee even for simple extensions of Pd--Flip games, so an algorithmic framework based on coordinated moves by small groups of players is proposed, whose approximation guarantee and number of moves...