On Selfish Creation of Robust Networks

摘要: Robustness is one of the key properties nowadays networks. However, robustness cannot be simply enforced by design or regulation since many important networks, most prominently Internet, are not created and controlled a central authority. Instead, Internet-like networks emerge from strategic decisions selfish agents. Interestingly, although lacking coordinating authority, such naturally grown surprisingly robust while at same time having desirable like small diameter. To investigate this phenomenon we present first simple model for network creation which explicitly incorporates agents striving position in protecting themselves against random edge-failure. We show that our diverse prove versatility adapting various techniques non-robust versions then use establishing bounds on Price Anarchy. Moreover, analyze computational hardness finding best possible strategies game dynamics model.