Arrangement
YOU ARE HERE: News & Events » Events archive » Event

Vincenzo Bonifaci seminar

2007.04.09 | Peter Bro Miltersen

Date Fri Apr 20
Time 10:15 11:15
Location Turing-024

Title: The complexity of uniform Nash equilibria

Abstract

We investigate the complexity of finding Nash equilibria in which the
strategy of each player is uniform on its support set. We show that,
even for a restricted class of win-lose bimatrix games, deciding the
existence of such uniform equilibria is an NP-complete problem.Our
proof exploits a connection between uniform equilibria and some
appropriately defined graph structures associated to the game.

CS Calendar
Comments on content: 
Revised 2012.05.22