Computer Science – Computer Science and Game Theory
Scientific paper
2011-06-07
EPTCS 54, 2011, pp. 131-145
Computer Science
Computer Science and Game Theory
In Proceedings GandALF 2011, arXiv:1106.0814
Scientific paper
10.4204/EPTCS.54.10
A game-theoretic model for the study of dynamic networks is analyzed. The model is motivated by communication networks that are subject to failure of nodes and where the restoration needs resources. The corresponding two-player game is played between "Destructor" (who can delete nodes) and "Constructor" (who can restore or even create nodes under certain conditions). We also include the feature of information flow by allowing Constructor to change labels of adjacent nodes. As objective for Constructor the network property to be connected is considered, either as a safety condition or as a reachability condition (in the latter case starting from a non-connected network). We show under which conditions the solvability of the corresponding games for Constructor is decidable, and in this case obtain upper and lower complexity bounds, as well as algorithms derived from winning strategies. Due to the asymmetry between the players, safety and reachability objectives are not dual to each other and are treated separately.
Grüner Sten
Radmacher Frank G.
Thomas Wolfgang
No associations
LandOfFree
Connectivity Games over Dynamic Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Connectivity Games over Dynamic Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Connectivity Games over Dynamic Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-25272