In this Master Project we set out to investigate such a game-theoretic model both theoretically and experimentally. In our strategic network formation game there are players which can create costly links to other players. The combination of the individual decisions of all players then induces a network. The goal of each player is to obtain a reliable network, which ensures good connectivity to all other players. However, players are greedy and thus weigh their individually obtained network quality against the cost spent for creating links. But if everyone tries to free-ride the network, what happens to the overall network quality?
We are especially interested in networks, which are reliable even under attack from a malicious third party. Even worse, we assume that an attacked node of the network completely fails and the attack spreads virus-like to its neighbors. However, there is hope for our players: they can selfishly decide to buy a firewall and thus protect themselves.
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.