Abstrakt. Vi studerar den kombinatoriska strukturen och beräknings komplexitet extrem Nash equilibria, som maximerar eller minimerar en viss objektiv funktion, i samband med en självisk routing spel. Specifikt antar vi en samling n användare, var och en med en blandad strategi, som är en sannolikhetsfördelning över m parallella länkar, för att kontrollera routing av sin egen tilldelade trafik. I en Nash jämvikt, varje användare rutt sin trafik på länkar som minimerar dess förväntade latency kostnad. Våra strukturella resultat ger betydande bevis för Fully Mixed Nash Equilibrium Conjecture, som säger att den värsta Nash jämvikt är den helt blandade Nash jämvikt, där varje användare väljer varje länk med positiv sannolikhet. Specifikt, Vi bevisar att Fully Mixed Nash Equilibrium Conjecture gäller för ren Nash Equilibria och att under ett visst villkor, den sociala kostnaden för någon Nash jämvikt ligger inom en faktor på 6 + ε, av den helt blandade Nash jämvikt, förutsatt att länkkapaciteten är identisk. Våra komplexa resultat inkluderar hårdhet, approximabilitet och omätbarhet. Här visar vi, att för identiska länkkapaciteter och under ett visst tillstånd, finns det en randomiserad, polynom-tidsalgoritm för att approximera den värsta sociala kostnaden inom en faktor godtyckligt nära 6 + ε. Dessutom bevisar vi att för alla godtyckliga heltal k > 0, är det N P-hård att avgöra om någon given tilldelning av användare till länkar kan omvandlas till en ren Nash jämvikt med hjälp av de flesta k själviska steg. Om vi antar identiska länkkapaciteter, ger vi ett polynom-tids approximationssystem (PTAS) för att approximera den bästa sociala kostnaden över alla rena Nash equilibria. Slutligen bevisar vi att det är N P-hårdt att uppskatta den värsta sociala kostnaden inom en multiplikativ faktor 2 − 2 m + 1 − ε. Mängden 2–2 m + 1 är den snäva övre gränsen för förhållandet mellan de värsta sociala kostnaderna och den optimala kostnaden i modellen med identiska kapaciteter.
I REF Gairing m.fl. studera den kombinatoriska strukturen och beräkningskomplexiteten hos extrem Nash equilibria, dvs. Equilibria som maximerar eller minimerar den objektiva funktionen.
Extreme nash equilibria
{'venue': 'In Proc. of the 8th Italian Conference on Theoretical Computer Science, LNCS 2841', 'journal': None, 'mag_field_of_study': ['Computer Science']}