Flaskhals trängsel spel korrekt modellera egenskaperna hos många verkliga nätverk routing program. De är kända för att ha stark jämvikt - en förstärkning av Nash jämvikt mot motståndskraft mot koalitionsavvikelser. I den här artikeln studerar vi den beräkningsmässiga komplexiteten av ren Nash och stark jämvikt i dessa spel. Vi tillhandahåller en generisk centraliserad algoritm för att beräkna stark jämvikt, som har polynomisk körtid för många intressanta klasser av spel som t.ex. matroid eller singel-commodity flaskhals trängselspel. Dessutom undersöker vi det mer krävande målet att nå jämvikt i polynomet med hjälp av naturlig förbättringsdynamik. Med hjälp av unilateral förbättring dynamik i matroid spel ren Nash equilibria kan uppnås effektivt. I kontrast, datorisering även en enda koalitionell förbättring flytta i matroid och singlecommodity spel är starkt NP-hård. Dessutom etablerar vi en mängd hårdhetsresultat och lägre gränser när det gäller varaktigheten av unilaterala och koalitionella förbättringsdynamik. De fortsätter att hålla även för konvergens till ungefärlig jämvikt.
Komplexiteten i dator PNE och stark jämvikt i dessa spel undersöktes ytterligare i REF.
Computing pure Nash and strong equilibria in bottleneck congestion games
{'venue': 'IN PROC. 18TH EUROPEAN SYMPOSIUM ON ALGORITHMS (ESA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}