Internet har framträtt som det kanske viktigaste nätverket inom modern datorteknik, men ganska mirakulöst skapades det genom en mängd agenters enskilda handlingar snarare än av en central planeringsmyndighet. Detta motiverar spelet-teoretisk studie av nätverksbildning, och vår artikel anser en av de mest välstuderade modeller, ursprungligen föreslagits av Fabrikant et al. I modellen motsvarar var och en av n agenterna en vertex, som kan skapa kanter till andra hörn till en kostnad av α vardera, för någon parameter α. Varje kant kan användas fritt av varje vertex, oavsett vem som betalade skapelsekostnaden. För att återspegla önskan att vara nära andra hörn, varje agent kostnadsfunktion ytterligare ökas av summan av alla (graf-teoretiska) avstånd till alla andra hörn. Tidigare forskning visade att för många regimer av (α, n) parameterutrymme, den totala sociala kostnaden (summan av alla agenters kostnader) för varje Nash jämvikt begränsas av som mest en konstant multipel av den optimala sociala kostnaden. I algoritmisk spelteoretisk nomenklatur kallas detta approximationsförhållande priset för anarki. I vår artikel, vi avsevärt skärpa några av dessa resultat, visar att för alla konstant nonintegral α > 2, priset på anarki är i själva verket 1 + o(1); det vill säga, det är inte bara begränsas av en konstant, men också det tenderar att 1 som n → ∞. För konstant integral α ≥ 2, visar vi att priset på anarki begränsas från 1. Vi tillhandahåller kvantitativa uppskattningar av konvergenstalen för båda resultaten.
För icke-integrerade konstantvärden på α > 2, Graham et al. REF visade att PoA tenderar att 1 som n → ∞.
Anarchy Is Free in Network Creation
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}