En Nash jämvikt av ett routing nätverk representerar ett stabilt tillstånd av nätverket där ingen användare finner det fördelaktigt att ensidigt avvika från sin routing strategi. I detta arbete undersöker vi strukturen av sådan jämvikt inom ramen för ett visst spel som modellerar självisk routing för en uppsättning n användare varje frakta sin trafik över ett nätverk som består av m parallella länkar. Framför allt är vi intresserade av att identifiera den värsta Nash-jämvikten - den som maximerar de sociala kostnaderna. I värsta fall introducerades Nash equilibria och studerades i Koutsoupiias och Papadimitrious pionjärarbete [9]. Mer specifikt fortsätter vi studien av Conjecture of the Fully Mixed Nash Equilibrium, hädanefter förkortat som FMNE Conjecture, som hävdar att den helt blandade Nash jämvikt, när den existerar, är den värsta-fall Nash jämvikt. (I den helt blandade Nash jämvikt, den blandade strategin för varje användare tilldelar (strikt) positiv sannolikhet till varje länk.) Vi rapporterar om betydande framsteg när det gäller att identifiera giltighet, metoder för att fastställa, och begränsningar av, FMNE Conjecture.
I REF Lücking m.fl. fortsätta att studera helt blandade Nash Equilibrium Conjecture och rapportera betydande framsteg mot att identifiera giltigheten.
Which Is the Worst-Case Nash Equilibrium?
{'venue': 'MFCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}