Vi anser att det dynamiska beteendet hos flera varianter av nätverket Creation Game, som infördes av Fabrikant et al. Denna förordning träder i kraft dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Equilibrium nätverk i dessa modeller har önskvärda egenskaper som låga sociala kostnader och liten diameter, vilket gör dem attraktiva för decentraliserade skapandet av overlay-nätverk. Tyvärr, på grund av att Nash jämvikt, ingen distribuerad algoritm för att hitta sådana nätverk är känd. Vi behandlar dessa spel som sekventiellt flytta spel och analysera om (okoordinerat) själviskt spel så småningom konvergerar till en jämvikt. Därför kastar vi ljus över en av de mest naturliga algoritmer för detta problem: distribuerad lokal sökning, där i varje steg någon agent utför en myopisk självisk förbättring flytta. Vi visar att snabb konvergens garanteras för alla versioner av Swap Games, som infördes av Alon et al. [SPAA'10], om det ursprungliga nätverket är ett träd. Dessutom visar vi att denna process kan påskyndas till ett nästan optimalt antal åtgärder genom att tillämpa en mycket naturlig flyttpolitik. Tyvärr är dessa positiva resultat inte längre sanna om det ursprungliga nätverket har cykler och vi visar det överraskande resultatet att även en annan kant räcker för att förstöra konvergensgarantin. Detta svarar på ett öppet problem från Ehsani et al. [SPAA'11] i negativ riktning. Dessutom visar vi att när det gäller icke-trädnät kan ingen politik driva på konvergensen. Vi utökar våra negativa resultat till den välstuderade originalversionen, där agenter får köpa och ta bort kanter också. För denna modell visar vi att det inte finns någon konvergensgaranti - även om alla agenter spelar optimalt. Ännu värre, om spelas på en icke-fullständig värd-graf, då finns det tillfällen där ingen sekvens av att förbättra rörelser leder till ett stabilt nätverk. Dessutom analyserar vi om kostnadsdelningen har en positiv inverkan på konvergensbeteendet. För detta överväger vi en version av Corbo och Parkes [PODC'05] där bilateralt samtycke krävs för att skapa en kant och där kantkostnader delas mellan de inblandade agenterna. Vi visar att användningen av en sådan kostnadsdelning regel ger ännu sämre dynamiskt beteende. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. Upphovsrätt till delar av detta verk som ägs av andra än upphovsmannen måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, eller återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Begär tillstånd från authoritys@acm.org. SPAA '13, 23–25 juli 2013, Montréal, Québec, Kanada. Upphovsrätten innehas av ägaren/författarna. Utgivningsrättigheter som är licensierade till ACM. Upphovsrätt 2013 ACM 978-1-4503-1572-2/13/07...$15.00. Slutligen jämför vi våra mestadels negativa teoretiska resultat med en noggrann empirisk studie. Våra simuleringar indikerar två positiva fakta: (1) Det icke-konvergent beteendet verkar vara begränsat till en liten uppsättning patologiska fall och är osannolikt att dyka upp i praktiken. (2) I alla våra simuleringar har vi observerat en anmärkningsvärt snabb konvergens mot ett stabilt nätverk i O(n) steg, där n är antalet agenter.
I sin tur fastställde REF att vissa klasser av nätverksskapande spel är svagt acykliska och dessutom att en särskild schemaläggning av spelare kan säkerställa att den resulterande förbättringsbanan konvergerar till en Nash jämvikt i O(n log n) steg.
On dynamics in selfish network creation
{'venue': "SPAA '13", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}