Vi ger flera nya övre och nedre gränser på den värsta svårighetsgraden av Braess Paradox och priset på anarki av självisk routing med avseende på det maximala latensmålet. I enkommoditetsnätverk med obegränsad latensfunktion, bevisar vi att detta värsta pris för anarki är exakt n − 1, där n är antalet nätverksvertikaler. För Braess Paradox i sådana nätverk, visar vi att avlägsnande på de flesta c kanter från ett nätverk minskar den gemensamma latens som uppstår av trafiken vid jämvikt med som mest en faktor av c + 1. I synnerhet är den värsta-fall svårighetsgraden av Braess Paradox med en enda kant avlägsnande maximeras i Braess ursprungliga fyra-vertex nätverk. I multicommodity nätverk uppvisar vi en oändlig familj av två-commodity nätverk, relaterade till Fibonacci nummer, där både den värsta-fall svårighetsgraden av Braess Paradox och priset på anarki för maximal latency mål växer exponentiellt med nätverksstorleken. Denna konstruktion visar att ett stort antal kända själviska routingresultat för enskilda kombinät inte har några analoger i nätverk med två eller flera varor. Vi visar också en övre gräns för båda dessa mängder som är exponentiellt i nätverksstorleken och oberoende av nätverkslatensfunktionerna, vilket visar att vår konstruktion är nära optimal. Slutligen använder vi vår familj av två-varor nätverk för att uppvisa en naturlig nätverksdesign problem med i sig exponentiellt (i) approximabilitet.
Lin m.fl. REF visar för två kommoditetsnätverk relaterade till Fibonacci-nummer att både den värsta graden av Braess paradox och priset på anarki för det maximala latensmålet växer exponentiellt med nätstorleken.
Stronger Bounds on Braess ’ s Paradox and the Maximum Latency of Selfish Routing ∗
{'venue': 'ICALP', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}