Scaling in Biological and Social Networks - Abstract - Saia
From Santa Fe Institute Events Wiki
| Workshop Navigation |
Virus vs Anti-virus
Jared Saia (UNM)
Abstract:
Consider the following game between a virus and an alert over a population of n agents. Initially, no agents are infected or alerted and each agent in the network is a "detector" independently with small but constant probability . The game starts with a single agent becoming infected. In every time step thereafter, every infected agent sends out a constant number of viruses to other agents in the population, and every alerted agent sends out a constant number of alerts . If a virus is received by an agent that is not a detector, that agent becomes infected. If a virus is received by an agent that is a detector, that agent becomes alerted. If an alert is received by any agent that is not infected, that agent becomes alerted.
Is there a strategy for the alerted nodes that guarantees that 99% of the agents become alerted before they are infected? Surprisingly, the answer is yes. This is true even if 1) the rates at which viruses and alerts can be sent are equal; and 2) the infected agents are intelligent, coordinated and essentially omniscient. The infected agents are essentially omniscient in that they know everything except for which agents are detectors i.e. they know which agents are alerted and which are infected at any time, where alerts are being sent, the overall strategy used by the alerted agents, etc. The alerted nodes are assumed to know nothing about which other agents are infected or alerted, where alerts or viruses are being sent, or the strategy used by the infected agents. Moreover, we can show that the alerted nodes can still win even if the alerts can only be sent through a previously determined network where every node has only constant degree.