%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Network Games BibTeX-file % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % last modified: 14.05.2010 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %--- some strings --- @string{sp = {Springer}} @string{lncs = {Lecture Notes in Computer Science}} @string{jacm = {Journal of the ACM}} @string{jcss = {Journal of Computer and System Sciences}} @string{tcs = {Theoretical Computer Science}} @string{jalgorithms = {Journal of Algorithms}} @string{monet = {Mobile Networks and Applications}} %--- Request-Response Games --- @inproceedings{WalHueTho03, author = {Nico Wallmeier and Patrick H\"{u}tten and Wolfgang Thomas}, title = {Symbolic Synthesis of Finite-State Controllers for Request-Response Specifications}, booktitle = {Proceedings of CIAA}, year = 2003, pages = {11--22}, ee = {http://link.springer.de/link/service/series/0558/bibs/2759/27590011.htm}, crossref = {DBLP:conf/wia/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/wia/2003, title = {Implementation and Application of Automata, 8th International Conference, CIAA 2003, Santa Barbara, California, USA, July 16-18, 2003, Proceedings}, booktitle = {Proceedings of CIAA}, publisher = sp, series = lncs, volume = 2759, year = 2003, isbn = {3-540-40561-5}, bibsource = {DBLP, http://dblp.uni-trier.de}, % editor = {Oscar H. Ibarra and Zhe Dang}, } @inproceedings{HorThoWal08, author = {Florian Horn and Wolfgang Thomas and Nico Wallmeier}, title = {Optimal Strategy Synthesis in Request-Response Games}, booktitle = {Proceedings of ATVA}, year = 2008, pages = {361--373}, ee = {http://dx.doi.org/10.1007/978-3-540-88387-6_31}, crossref = {DBLP:conf/atva/2008}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/atva/2008, title = {Automated Technology for Verification and Analysis, 6th International Symposium, ATVA 2008, Seoul, Korea, October 20-23, 2008. Proceedings}, booktitle = {Proceedings of ATVA}, publisher = sp, series = lncs, volume = 5311, year = 2008, isbn = {978-3-540-88386-9}, bibsource = {DBLP, http://dblp.uni-trier.de}, % editor = {Sung Deok Cha and Jin-Young Choi and Moonzoo Kim and Insup Lee and Mahesh Viswanathan}, } %--- Dynamic Networks by F.Radmacher and W.Thomas --- @InProceedings{RadTho07, author = {Frank G. Radmacher and Wolfgang Thomas}, title = {A Game Theoretic Approach to the Analysis of Dynamic Networks}, booktitle = {Proceedings of VerAS}, year = 2008, series = {Electronic Notes in Theoretical Computer Science}, volume = {200\,(2)}, pages = {21--37}, publisher = {Elsevier}, abstract = {A model of dynamic networks is introduced which incorporates three kinds of network changes: deletion of nodes (by faults or sabotage), restoration of nodes (by actions of ``repair''), and creation of nodes (by actions that extend the network). The antagonism between the operations of deletion and restoration resp.\ creation is modelled by a game between the two agents ``Destructor'' and ``Constructor''. In this framework of dynamic model-checking, we consider as specifications (``winning conditions'' for Constructor) elementary requirements on connectivity of those networks which are reachable from some initial given network. We show some basic results on the (un-)\,decidability and hardness of dynamic model-checking problems.} } %--- Randomized Sabotage Games by D.Klein, F.Radmacher, and W.Thomas --- @inproceedings{KleRadTho09, author = {Dominik Klein and Frank G. Radmacher and Wolfgang Thomas}, title = {The Complexity of Reachability in Randomized Sabotage Games}, booktitle = {Proceedings of FSEN}, year = 2009, pages = {162--177}, ee = {http://dx.doi.org/10.1007/978-3-642-11623-0_9}, crossref = {DBLP:conf/fsen/2009}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/fsen/2009, title = {Fundamentals of Software Engineering, Third IPM International Conference, FSEN 2009, Kish Island, Iran, April 15-17, 2009, Revised Selected Papers}, booktitle = {FSEN}, publisher = sp, series = lncs, volume = 5961, year = 2010, isbn = {978-3-642-11622-3}, ee = {http://dx.doi.org/10.1007/978-3-642-11623-0}, bibsource = {DBLP, http://dblp.uni-trier.de}, % editor = {Farhad Arbab and Marjan Sirjani}, } %--- Games Against Nature --- @article{Pap85-nature, author = {Christos H. Papadimitriou}, title = {Games Against Nature}, journal = jcss, volume = {31}, number = {2}, year = 1985, pages = {288--301}, bibsource = {DBLP, http://dblp.uni-trier.de} } %--- Original Sabotage Game --- @inproceedings{Ben05, author = {Johan van Benthem}, title = {An Essay on Sabotage and Obstruction}, booktitle = {Mechanizing Mathematical Reasoning, Essays in Honor of J\"{o}rg H.\ Siekmann on the Occasion of His 60th Birthday}, year = {2005}, pages = {268--276}, ee = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}id=53W0FPYAJTBD9BNG}, crossref = {DBLP:conf/birthday/2005siekmann}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/birthday/2005siekmann, title = {Mechanizing Mathematical Reasoning, Essays in Honor of J\"{o}rg H.\ Siekmann on the Occasion of His 60th Birthday}, booktitle = {Mechanizing Mathematical Reasoning}, publisher = {Springer}, series = lncs, volume = {2605}, year = {2005}, isbn = {3-540-25051-4}, editor = {Dieter Hutter and Werner Stephan}, bibsource = {DBLP, http://dblp.uni-trier.de} } %--- Rohde --- @TECHREPORT{LR03a, author = {Christof L\"{o}ding and Philipp Rohde}, title = {Solving the Sabotage Game is {PSPACE}-hard}, institution = {RWTH Aachen}, year = 2003, number = {AIB-05-2003}, pdf = {/download/papers/rohde/aib-2003-05.pdf}, abstract = { We consider the sabotage game presented by van Benthem in an essay on the occasion of J\"{o}rg Siekmann's 60th birthday. In this game one player moves along the edges of a finite, directed or undirected multi-graph and the other player takes out a link after each step. There are several algorithmic tasks over graphs which can be considered as winning conditions for this game, for example reachability, Hamilton path or complete search. As the game definitely ends after at most the number of edges (counted with multiplicity) steps, it is easy to see that solving the sabotage game for the mentioned tasks takes at most PSPACE in the size of the graph. We will show that on the other hand solving this game in general is PSPACE-hard for all conditions. We extend this result to some variants of the game (removing more than one edge per round and removing vertices instead of edges). Finally we introduce a modal logic over changing models to express tasks corresponding to the sabotage games. We will show that model checking this logic is PSPACE-complete.}, } @INPROCEEDINGS{LR03b, author = {Christof L\"{o}ding and Philipp Rohde}, title = {Solving the Sabotage Game is {PSPACE}-hard}, booktitle = {Proceedings of MFCS}, series = lncs, publisher = sp, volume = 2747, pages = {531--540}, year = 2003, ps = {/download/papers/rohde/mfcs03.ps.gz}, pdf = {/download/papers/rohde/mfcs03.pdf}, copyright = {\copyright \url{http://www.springer.de/comp/lncs/}{Springer}}, abstract = { We consider the sabotage game as presented by van Benthem. In this game one player moves along the edges of a finite multi-graph and the other player takes out a link after each step. One can consider usual algorithmic tasks like reachability, Hamilton path, or complete search as winning conditions for this game. As the game definitely ends after at most the number of edges steps, it is easy to see that solving the sabotage game for the mentioned tasks takes at most PSPACE in the size of the graph. In this paper we establish the PSPACE-hardness of this problem. Furthermore, we introduce a modal logic over changing models to express tasks corresponding to the sabotage games and we show that model checking this logic is PSPACE-complete.}, % booktitle = {Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science, MFCS 2003}, } @INPROCEEDINGS{LR03c, author = {Christof L\"{o}ding and Philipp Rohde}, title = {Model Checking and Satisfiability for Sabotage Modal Logic}, booktitle = {Proceedings of FSTTCS}, series = lncs, publisher = sp, volume = 2914, pages = {302--313}, year = 2003, ps = {/download/papers/rohde/fsttcs03.ps.gz}, pdf = {/download/papers/rohde/fsttcs03.pdf}, copyright = {\copyright \url{http://www.springer.de/comp/lncs/}{Springer}}, abstract = { We consider the sabotage modal logic SML which was suggested by van Benthem. SML is the modal logic equipped with a `transition-deleting' modality and hence a modal logic over changing models. It was shown that the problem of uniform model checking for this logic is PSPACE-complete. In this paper we show that, on the other hand, the formula complexity and the program complexity are linear, resp., polynomial time. Further we show that SML lacks nice model-theoretic properties such as bisimulation invariance, the tree model property, and the finite model property. Finally we show that the satisfiability problem for SML is undecidable. Therefore SML seems to be more related to FO than to usual modal logic.}, % booktitle = {Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2003}, } @INPROCEEDINGS{Roh04, author = {Philipp Rohde}, title = {Moving in a Crumbling Network: The Balanced Case}, booktitle = {Proceedings of CSL}, series = lncs, publisher = sp, volume = 3210, pages = {310--324}, year = 2004, ps = {/download/papers/rohde/csl04.ps.gz}, pdf = {/download/papers/rohde/csl04.pdf}, copyright = {\copyright \url{http://www.springer.de/comp/lncs/}{Springer}}, abstract = { In this paper we continue the study of 'sabotage modal logic' SML which was suggested by van Benthem. In this logic one describes the progression along edges of a transition graph in alternation with moves of a saboteur who can delete edges. A drawback of the known results on SML is the asymmetry of the two modalities of 'moving' and 'deleting': Movements are local, whereas there is a global choice for edge deletion. To balance the situation and to obtain a more realistic model for traffic and network problems, we require that also the sabotage moves (edge deletions) are subject to a locality condition. We show that the new logic, called path sabotage logic PSL, already has the same complexities as SML (model checking, satisfiability) and that it lacks the finite model property. The main effort is finding a pruned form of SML-models that can be enforced within PSL and giving appropriate reductions from SML to PSL.}, % booktitle = {Proceedings of the 18th International Workshop on Computer Science Logic, CSL 2004}, } @PhdThesis{Roh05, author = {Philipp Rohde}, title = {On Games and Logics over Dynamically Changing Structures}, school = {RWTH Aachen}, year = {2005}, pdf = {http://www.metaego.de/publications/dissertation.pdf}, abstract = { In the classical framework of graph algorithms, program logics, and corresponding model checking games, one considers changes of system states and movements of agents within a system, but the underlying graph or structure is assumed to be static. This limitation motivates a more general approach where dynamic changes of structures are relevant. In this thesis, we take up a proposal of van Benthem from 2002 and consider games and modal logics over dynamically changing structures, where we focus on the deletion of edges of a graph, resp., transitions of a Kripke structure. We investigate two-player games where one player tries to reach a designated vertex of a graph while the opponent sabotages this by deleting edges. It is shown that adding the `saboteur' makes these games algorithmically much harder to solve. Further, we analyze corresponding modal logics which are augmented with cross-model modalities referring to submodels from which a transition has been removed. On the one hand, it turns out that these `sabotage modalities' already strengthen standard modal logic in such a way that many nice algorithmic and model-theoretic properties get lost. On the other hand, the model checking problem remains decidable. The main limitation of modal logic is the lack of a mechanism for unbounded iteration or recursion. To overcome this, we augment the `sabotage modal logics' of the first part of the thesis with constructors for forming least and greatest monadic fixed-points. The resulting logic extends the well-known μ-calculus and is capable of expressing iterative properties like reachability or recurrence as well as basic changes of the underlying Kripke structure, namely, the deletion of transitions. Finally, we introduce extended parity games where in addition, both players are able to delete edges of the arena and to store, resp., restore the current appearance of the arena by use of a fixed number of registers. We show that these games serve as model checking games for the aforementioned `sabotage μ-calculus'.}, } %--- Learning and Teaching as a Game: A Sabotage Approach --- @inproceedings{GieKurVel09, author = {Nina Gierasimczuk and Lena Kurzen and Fernando R. Vel\'{a}zquez-Quesada}, title = {Learning and Teaching as a Game: A Sabotage Approach}, booktitle = {Proceedings of LORI}, year = 2009, pages = {119--132}, ee = {http://dx.doi.org/10.1007/978-3-642-04893-7_10}, crossref = {DBLP:conf/lori/2009}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/lori/2009, title = {Logic, Rationality, and Interaction, Second International Workshop, LORI 2009, Chongqing, China, October 8-11, 2009. Proceedings}, booktitle = {Proceedings of LORI}, publisher = sp, series = lncs, volume = 5834, year = 2009, isbn = {978-3-642-04892-0}, ee = {http://dx.doi.org/10.1007/978-3-642-04893-7}, bibsource = {DBLP, http://dblp.uni-trier.de}, % editor = {Xiangdong He and John F. Horty and Eric Pacuit}, } %--- Games for Learning: A Sabotage Approach @InProceedings{GieKurVel09-old, author = {Nina Gierasimczuk and Lena Kurzen and Fernando R. Vel\'{a}zquez-Quesada}, title = {Games for Learning: A Sabotage Approach}, booktitle = {Proceedings of MALLOW 2009}, year = 2009, series = {CEUR Workshop Proceedings (CEUR-WS.org)}, volume = {494}, pages = {165--172}, issn = {1613-0073} % publisher = {M. Jeusfeld c/o Redaktion Sun SITE, Informatik V, RWTH Aachen}, % title = {Central EURope workshop proceedings}, } %-- Attractor Strategy Paper @inproceedings{thomas95, author = {Wolfgang Thomas}, title = {On the Synthesis of Strategies in Infinite Games}, booktitle = {Proceedings of STACS}, pages = {1--13}, year = 1995, series = lncs, volume = 900, publisher = sp, ee = {http://dx.doi.org/10.1007/3-540-59042-0_57}, bibsource = {DBLP, http://dblp.uni-trier.de}, % editor = {Ernst W.\ Mayr and Claude Puech}, } %--- Automata, Logics, and Infinite Games Buch --- @Book{GTW02-book, author = {Erich Gr\"{a}del and Wolfgang Thomas and Thomas Wilke}, title = {Automata, Logics, and Infinite Games}, publisher = sp, year = {2002}, volume = {2500}, series = lncs, } %--- Determinacy of Borel Games--- @article{Martin75, author = {Martin, Donald A.}, title = {Borel Determinacy}, journal = {Annals of Mathematics}, volume = 102, year = 1975, number = 2, pages = {363--371}, issn = {0003-486X} } %--- Stockmeyers PhD thesis showing PSPACE-hardness of QBF and associated games @phdthesis{stockmeyer, author = {Larry J. Stockmeyer}, title = {The Complexity of Decision Problems in Automata Theory and Logic}, school = {MIT}, year = {1974}, } %--- Complexity book Papadimitriou @book{Pap94-book, author = {Christos H. Papadimitriou}, title = {Computational Complexity}, publisher = {Addison Wesley}, year = {1994}, } %--- Model-Checking Buch --- @book{CGP99, author = {Edmund M. {Clarke,~Jr.} and Orna Grumberg and Doron A. Peled}, title = {Model Checking}, year = {1999}, isbn = {0-262-03270-8}, publisher = {MIT Press}, address = {Cambridge, MA, USA} } %--- Sonstiges 1 --- @inproceedings{GaoWan08, author = {Lin Gao and Xinbing Wang}, title = {A game approach for multi-channel allocation in multi-hop wireless networks}, booktitle = {Proceedings of MobiHoc}, year = {2008}, pages = {303--312}, ee = {http://doi.acm.org/10.1145/1374618.1374659}, crossref = {DBLP:conf/mobihoc/2008}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/mobihoc/2008, title = {Proceedings of the 9th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2008, Hong Kong, China, May 26-30, 2008}, booktitle = {Proceedings of MobiHoc}, publisher = {ACM}, year = {2008}, isbn = {978-1-60558-073-9}, bibsource = {DBLP, http://dblp.uni-trier.de}, % editor = {Xiaohua Jia and Ness B. Shroff and Peng-Jun Wan}, } @article{XMS08, author = {Chunsheng Xin and Liangping Ma and Chien-Chung Shen}, title = {A Path-Centric Channel Assignment Framework for Cognitive Radio Wireless Networks}, journal = monet, volume = {13}, number = {5}, year = {2008}, pages = {463--476}, ee = {http://dx.doi.org/10.1007/s11036-008-0084-y}, bibsource = {DBLP, http://dblp.uni-trier.de} } @ARTICLE{SvS09, title = {Distributed Resource Management in Multihop Cognitive Radio Networks for Delay-Sensitive Transmission}, author = {Hsien-Po Shiang and Mihaela van der Schaar}, journal = {IEEE Transactions on Vehicular Technology}, year = {2009}, volume = {58}, number = {2}, pages = {941--953}, doi = {10.1109/TVT.2008.925308}, ISSN = {0018-9545} } %--- Sonstiges 2 --- @inproceedings{AMS89, author = {Baruch Awerbuch and Yishay Mansour and Nir Shavit}, title = {Polynomial End-To-End Communication (Extended Abstract)}, booktitle = {Proceedings of FOCS}, year = {1989}, pages = {358--363}, crossref = {DBLP:conf/focs/FOCS30}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/focs/FOCS30, title = {30th Annual Symposium on Foundations of Computer Science, 30 October-1 November 1989, Research Triangle Park, North Carolina, USA}, booktitle = {Proceedings of FOCS}, publisher = {IEEE}, year = {1989}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{ABS03, author = {Baruch Awerbuch and Andr\'{e} Brinkmann and Christian Scheideler}, title = {Anycasting in Adversarial Systems: Routing and Admission Control}, booktitle = {Proceedings of ICALP}, year = {2003}, pages = {1153--1168}, ee = {http://link.springer.de/link/service/series/0558/bibs/2719/27191153.htm}, crossref = {DBLP:conf/icalp/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/icalp/2003, title = {Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings}, booktitle = {Proceedings of ICALP}, publisher = {Springer}, series = lncs, volume = {2719}, year = {2003}, isbn = {3-540-40493-7}, bibsource = {DBLP, http://dblp.uni-trier.de} % editor = {Jos C. M. Baeten and Jan Karel Lenstra and Joachim Parrow and Gerhard J. Woeginger}, } @article{AAGMRS97, author = {Yehuda Afek and Baruch Awerbuch and Eli Gafni and Yishay Mansour and Adi Ros\'{e}n and Nir Shavit}, title = {Slide -- The Key to Polynomial End-to-End Communication}, journal = jalgorithms, volume = {22}, number = {1}, year = {1997}, pages = {158--186}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{AOKR03, author = {William Aiello and Rafail Ostrovsky and Eyal Kushilevitz and Adi Ros\'{e}n}, title = {Dynamic routing on networks with fixed-size buffers}, booktitle = {Proceedings of SODA}, year = {2003}, pages = {771--780}, ee = {http://doi.acm.org/10.1145/644108.644236}, bibsource = {DBLP, http://dblp.uni-trier.de} }