Vi anser att ett riktat nätverk där varje kant har en latensfunktion som anger den tid som krävs för att passera kanten med tanke på dess överbelastning. Själviska, icke-kooperativa agenter utgör nätverkstrafiken och vill resa från en källa vertex s till en destination t så snabbt som möjligt. Eftersom den rutt som väljs av en nätanvändare påverkar den överbelastning som andra upplever, modellerar vi problemet som ett icke-kooperativt spel. Om man antar att varje agent endast kontrollerar en försumbar del av den totala trafiken, Nash equilibria i detta icke-kooperativa spel motsvarar s-t flöden där alla flödesvägar har lika latens. Ett naturligt mått på prestandan hos ett nätverk som används av själviska medel är den vanliga latency som användare upplever i en Nash jämvikt. Braess Paradox är det kontraintuitiva men välkända faktum att ta bort kanter från ett nätverk kan förbättra dess prestanda. Braess Paradox motiverar följande nätverksdesign problem: med tanke på ett nätverk, vilka kanter bör tas bort för att få det bästa flödet vid Nash jämvikt? På motsvarande sätt, med tanke på ett nät av kanter som kan byggas, vilket subnätverk kommer att uppvisa den bästa prestandan när den används själviskt? Vi ger optimala omätbarhetsresultat och approximationsalgoritmer för detta nätverksdesignproblem. Till exempel, vi bevisar att det inte finns någon approximation algoritm för detta problem med approximation förhållande mindre än n/2, där n är antalet nät hörn, om inte P = NP. Vi visar vidare att denna hårdhet resultat är det bästa möjliga, genom att uppvisa en (n/2)-tillnärmning algoritm. Vi visar också snäva omätbarhetsresultat när ytterligare struktur, t.ex. linearitet, införs på nätverkets latensfunktioner. Dessutom bevisar vi att en optimal approximationsalgoritm för dessa problem är den triviala algoritmen: med tanke på ett nätverk av kandidatkanter, bygga hela nätverket. Som en följd av detta visar vi att Braess Paradox-även i sina värsta möjliga manifestationer-är omöjligt att upptäcka effektivt. På vägen till dessa resultat ger vi en grundläggande generalisering av Braess Paradox: förbättringen av prestandan som kan åstadkommas genom att ta bort kanter kan vara godtyckligt stor i stora nätverk. Även om Braess Paradox har haft 35 år som ett lärobok exempel, vårt resultat är den första att förlänga dess svårighetsgrad utöver det i Braess ursprungliga fyrnode nätverk.
Motiverad av Braess paradox, där avlägsnandet av en kant förbättrar effektiviteten i jämvikten routing, Roughgarden REF studerar problemet med att ta bort kanter från ett nätverk för att minimera fördröjningen vid jämvikt i det resulterande nätverket.
On the severity of Braess's paradox: designing networks for selfish users is hard
{'venue': 'J. Comput. Syst. Sci.', 'journal': 'J. Comput. Syst. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}