Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Strategic Network Formation under Attack

Master Project - Summer 2016

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?

Network before attack      Network after attack

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.

Results

The results of the project have resulted in the following publications:

  • Efficient Best Response C... - Download
    Friedrich, Tobias; Ihde, Sven; Keßler, Christoph; Lenzner, Pascal; Neubert, Stefan; Schumann, David Efficient Best Response Computation for Strategic Network Formation under AttackSymposium on Algorithmic Game Theory (SAGT) 2017: 199–211
     
  • Brief Announcement: Effic... - Download
    Friedrich, Tobias; Ihde, Sven; Keßler, Christoph; Lenzner, Pascal; Neubert, Stefan; Schumann, David Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under AttackSymposium on Parallelism in Algorithms and Architectures (SPAA) 2017: 321–323
     

Project Team

The Master Project is organized by the Algorithm Engineering Group. The following group members and students are participating:

Project Supervisor

Hasso Plattner Institute

Office: A-1.10
Tel.: +49 331 5509-410
E-Mail: friedrich(at)hpi.de

Project Supervisor

Hasso Plattner Institute

Office: A-1.5
Tel.: +49 331 5509-419
E-Mail: pascal.lenzner(at)hpi.de

Sven Ihde

Project Participant

Hasso Plattner Institute

E-Mail: sven.ihde(at)student.hpi.de

Christoph Keßler

Project Participant

Hasso Plattner Institute

E-Mail: christoph.kessler(at)student.hpi.de

Stefan Neubert

Project Participant

Hasso Plattner Institute

E-Mail: stefan.neubert(at)student.hpi.de

David Schumann

Project Participant

Chair for Algorithm Engineering
Hasso Plattner Institute

E-Mail: david.schumann@student.hpi.de