Vi föreslår ett enkelt spel för modellering av inneslutning av spridningen av virus i en graf av n noder. Varje nod måste välja att antingen installera antivirusprogram till någon känd kostnad C, eller risk infektion och en förlust L om ett virus som startar vid en slumpmässig inledande punkt i grafen kan nå det utan att stoppas av någon mellanliggande nod. Målet med enskilda noder är att minimera deras individuella förväntade kostnad. Vi bevisar många spel teoretiska egenskaper hos modellen, inklusive en lätt tillämpad karakterisering av Nash equilibria, cuhninating i vårt visar att tillåta själviska användare att välja Nash jämviktsstrategier är mycket oönskade, eftersom priset på anarki är en oacceptabel O(n) i värsta fall. Detta visar särskilt att en centraliserad lösning kan ge en mycket bättre totalkostnad än en jämviktslösning. Även om det är NP-hårdt att beräkna en sådan social optimal, visar vi att problemet kan reduceras till ett tidigare oövervägt kombinatoriskt problem som vi kallar sum-of-square partition problem. Med hjälp av en girig algoritm baserad på glesa skärningar, visar vi att detta problem kan approximeras till inom en faktor av O(log2n), vilket ger samma approximation förhållande för vaccinationsspelet.
Aspnes m.fl. Ref överväga ett diagram-teoretiskt spel som modellerar inneslutning av spridningen av virus på ett nätverk; varje nod individuellt måste välja att antingen installera anti-virus programvara till någon kostnad, eller risk infektion om ett virus når det utan att stoppas av någon mellanliggande nod med installerade antivirusprogram.
Inoculation strategies for victims of viruses and the sum-of-squares partition problem
{'venue': "SODA '05", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}