08/04/2025    15:00 > "Pure Nash equilibria in structured congestion games". 

Carla Michini (University of Winsconsin-Madison) 

will give a presentation on : 

Pure Nash equilibria in structured congestion games. 

Abstract : 

Congestion games are a class of non-cooperative games that can be used to model resource sharing among selfish players. A prominent solution concept for these games is that of pure Nash equilibrium (PNE), a strategy profile where no player has incentive to unilaterally deviate. In this talk I will address two central questions. The first question is: which structures allow us to design a polynomial-time algorithm for the computation of a PNE? The second question is: which structures can limit the inefficiency of pure Nash equilibria? To answer the first question, I will present a polyhedral approach that can be leveraged to design a strongly polynomial-time algorithm to compute a PNE in symmetric totally unimodular (TU) congestion games, where the players’ strategies are binary vectors inside polyhedra defined by TU constraint matrices. In relation to the second question, I will consider different measures of social cost and quantify equilibria inefficiency through the notion of pure Price of Anarchy (PoA). I will present bounds on the PoA for two main structured congestion games: congestion games defined over series-parallel networks and congestion games defined over paving matroids. 

This is a joint work with Bainian Hao. 

   CORE B.-135