The Symposium on Algorithmic Game Theory (SAGT) is one of the premier conferences on Algorithmic Game Theory and its purpose is to bring together researchers from Computer Science, Economics, Mathematics, Psychology, Physics, and Biology to present and discuss original research at the intersection of Algorithms and Game Theory.
The Algorithm Engineering group contributes the paper presented below.
Anna Melnichenko, a PhD students of the group, will receive student support from the ACM allowing her to present her research in Liverpool.
Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Münn, MartinOn Selfish Creation of Robust Networks. Symposium on Algorithmic Game Theory (SAGT) 2016: 141-152
Robustness is one of the key properties of nowadays networks. However, robustness cannot be simply enforced by design or regulation since many important networks, most prominently the Internet, are not created and controlled by a central authority. Instead, Internet-like networks emerge from strategic decisions of many selfish agents. Interestingly, although lacking a coordinating authority, such naturally grown networks are surprisingly robust while at the same time having desirable properties like a small diameter. To investigate this phenomenon we present the first simple model for selfish network creation which explicitly incorporates agents striving for a central position in the network while at the same time protecting themselves against random edge-failure. We show that networks in our model are diverse and we prove the versatility of our model by adapting various properties and techniques from the non-robust versions which we then use for establishing bounds on the Price of Anarchy. Moreover, we analyze the computational hardness of finding best possible strategies and investigate the game dynamics of our model.
Our research focus is on theoretical computer science and algorithm engineering. We are equally interested in the mathematical foundations of algorithms and developing efficient algorithms in practice. A special focus is on random structures and methods.