Document Open Access Logo

Timed Network Games with Clocks

Authors Guy Avni, Shibashis Guha, Orna Kupferman

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.23.pdf
  • Filesize: 0.51 MB
  • 18 pages

Document Identifiers

Author Details

Guy Avni
  • IST Austria, Klosterneuburg, Austria
Shibashis Guha
  • Université Libre de Bruxelles, Brussels, Belgium
Orna Kupferman
  • Hebrew University, Jerusalem, Israel

Funding

  • Avni, Guy: Supported by the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE/SHiNE), Z211-N23 (Wittgenstein Award), and M2369-N33 (Meitner fellowship).
  • Guha, Shibashis: Supported partially by the ARC project "Non-Zero Sum Game Graphs: Applications to Reactive Synthesis and Beyond" (Fédération Wallonie-Bruxelles).
  • Kupferman, Orna: Supported by the European Research Council (FP7/2007-2013) / ERC grant agreement no 278410.

Cite AsGet BibTex

Guy Avni, Shibashis Guha, and Orna Kupferman. Timed Network Games with Clocks. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.23

Abstract

Network games are widely used as a model for selfish resource-allocation problems. In the classical model, each player selects a path connecting her source and target vertices. The cost of traversing an edge depends on the load; namely, number of players that traverse it. Thus, it abstracts the fact that different users may use a resource at different times and for different durations, which plays an important role in determining the costs of the users in reality. For example, when transmitting packets in a communication network, routing traffic in a road network, or processing a task in a production system, actual sharing and congestion of resources crucially depends on time. In [G. Avni et al., 2017], we introduced timed network games, which add a time component to network games. Each vertex v in the network is associated with a cost function, mapping the load on v to the price that a player pays for staying in v for one time unit with this load. Each edge in the network is guarded by the time intervals in which it can be traversed, which forces the players to spend time in the vertices. In this work we significantly extend the way time can be referred to in timed network games. In the model we study, the network is equipped with clocks, and, as in timed automata, edges are guarded by constraints on the values of the clocks, and their traversal may involve a reset of some clocks. We argue that the stronger model captures many realistic networks. The addition of clocks breaks the techniques we developed in [G. Avni et al., 2017] and we develop new techniques in order to show that positive results on classic network games carry over to the stronger timed setting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
  • Theory of computation → Network formation
  • Theory of computation → Timed and hybrid models
Keywords
  • Network games
  • Timed automata
  • Nash equilibrium
  • Equilibrium inefficiency

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. S. Aland, D. Dumrauf, M. Gairing, B. Monien, and F. Schoppmann. Exact price of anarchy for polynomial congestion games. SIAM J. Comput., 40(5):1211-1233, 2011. Google Scholar
  2. L. Alfaro, M. Faella, T. A. Henzinger, R. Majumdar, and M. Stoelinga. The element of surprise in timed games. In Proc. 14th Int. Conf. on Concurrency Theory, pages 142-156, 2003. Google Scholar
  3. S. Almagor, G. Avni, and O. Kupferman. Repairing multi-player games. In Proc. 26th Int. Conf. on Concurrency Theory, volume 42 of LIPIcs, pages 325-339, 2015. Google Scholar
  4. R. Alur, M. Bernadsky, and P. Madhusudan. Optimal reachability for weighted timed games. In Proc. 31st Int. Colloq. on Automata, Languages, and Programming, pages 122-133, 2004. Google Scholar
  5. R. Alur, C. Courcoubetis, N. Halbwachs, T. A. Henzinger, P.-H. Ho, X. Nicollin, A. Olivero, J. Sifakis, and S. Yovine. The algorithmic analysis of hybrid systems. Theoretical Computer Science, 138(1):3-34, 1995. Google Scholar
  6. R. Alur and D. Dill. A theory of timed automata. Theoretical Computer Science, 126(2):183-236, 1994. Google Scholar
  7. R. Alur and T. Henzinger. Real-time logics: complexity and expressiveness. In Proc. 5th IEEE Symp. on Logic in Computer Science, pages 390-401, 1990. Google Scholar
  8. R. Alur, T.A. Henzinger, and O. Kupferman. Alternating-time temporal logic. Journal of the ACM, 49(5):672-713, 2002. Google Scholar
  9. R. Alur, S. La Torre, and G. J. Pappas. Optimal paths in weighted timed automata. Theoretical Computer Science, 318(3):297-322, 2004. Google Scholar
  10. E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. SIAM J. Comput., 38(4):1602-1623, 2008. Google Scholar
  11. E. Asarin and O. Maler. As soon as possible: Time optimal control for timed automata. In Proc 2nd International Workshop on Hybrid Systems: Computation and Control, pages 19-30, London, UK, UK, 1999. Springer-Verlag. Google Scholar
  12. G. Avni, S. Guha, and O. Kupferman. An abstraction-refinement methodology for reasoning about network games. In Proc. 33rd Int. Joint Conf. on Artificial Intelligence, pages 70-76, 2017. Google Scholar
  13. G. Avni, S. Guha, and O. Kupferman. Timed network games. In 42nd Int. Symp. on Mathematical Foundations of Computer Science, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2017. Google Scholar
  14. G. Avni, S. Guha, and O. Kupferman. Timed network games with clocks. CoRR, abs/1808.04882, 2018. URL: http://arxiv.org/abs/1808.04882.
  15. G. Avni, T.A. Henzinger, and O. Kupferman. Dynamic resource allocation games. In Proc. 9th International Symposium on Algorithmic Game Theory, volume 9928 of Lecture Notes in Computer Science, pages 153-166, 2016. Google Scholar
  16. G. Avni, O. Kupferman, and T. Tamir. Network-formation games with regular objectives. Information and Computation, 251:165-178, 2016. Google Scholar
  17. G. Behrmann, A. A. Fehnker, T. Hune, K.G. Larsen, P. Pettersson, J. Romijn, and F. W. Vaandrager. Minimum-cost reachability for priced timed automata. In Proc 4th International Workshop on Hybrid Systems: Computation and Control, pages 147-161, London, UK, 2001. Springer-Verlag. Google Scholar
  18. J. Bengtsson and W.Yi. Timed automata: Semantics, algorithms and tools. In Lectures on Concurrency and Petri Nets, Advances in Petri Nets, pages 87-124, 2003. Google Scholar
  19. P. Bouyer, T. Brihaye, V. Bruyère, and J-F. Raskin. On the optimal reachability problem of weighted timed automata. Formal Methods in System Design, 31(2):135-175, oct 2007. Google Scholar
  20. P. Bouyer, F. Cassez, E. Fleury, and K.G. Larsen. Optimal strategies in priced timed game automata. In Proc. 24th Conf. on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, pages 148-160, 2004. Google Scholar
  21. R. Brenguier, F. Cassez, and J-F Raskin. Energy and mean-payoff timed games. In Proc 17th International Workshop on Hybrid Systems: Computation and Control, pages 283-292, 2014. Google Scholar
  22. T. Brihaye, V. Bruyère, J. De Pril, and H. Gimbert. On subgame perfection in quantitative reachability games. Logical Methods in Computer Science, 9(1), 2012. Google Scholar
  23. T. Brihaye, G. Geeraerts, S. N. Krishna, L. Manasa, B. Monmege, and A. Trivedi. Adding negative prices to priced timed games. In Proc. 25th Int. Conf. on Concurrency Theory, pages 560-575, 2014. Google Scholar
  24. K. Chatterjee. Nash equilibrium for upward-closed objectives. In Proc. 15th Annual Conf. of the European Association for Computer Science Logic, volume 4207 of Lecture Notes in Computer Science, pages 271-286. Springer, 2006. Google Scholar
  25. K. Chatterjee, T. A. Henzinger, and M. Jurdzinski. Games with secure equilibria. Theoretical Computer Science, 365(1-2):67-82, 2006. Google Scholar
  26. K. Chatterjee, T. A. Henzinger, and N. Piterman. Strategy logic. In Proc. 18th Int. Conf. on Concurrency Theory, pages 59-73, 2007. Google Scholar
  27. K. Chatterjee, T. A. Henzinger, and V. S. Prabhu. Timed parity games: Complexity and robustness. Logical Methods in Computer Science, 7(4), 2011. Google Scholar
  28. K. Chatterjee, R. Majumdar, and M. Jurdzinski. On Nash equilibria in stochastic games. In Proc. 13th Annual Conf. of the European Association for Computer Science Logic, volume 3210 of Lecture Notes in Computer Science, pages 26-40. Springer, 2004. Google Scholar
  29. G. Christodoulou and E. Koutsoupias. On the price of anarchy and stability of correlated equilibria of linear congestion games. In ESA, pages 59-70, 2005. Google Scholar
  30. G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. In Proc. 37th ACM Symp. on Theory of Computing, pages 67-73, 2005. Google Scholar
  31. A. Fabrikant, C. Papadimitriou, and K. Talwar. The complexity of pure nash equilibria. In Proc. 36th ACM Symp. on Theory of Computing, pages 604-612, 2004. Google Scholar
  32. J. Fearnley and M. Jurdziński. Reachability in two-clock timed automata is pspace-complete. In Proc. 40th Int. Colloq. on Automata, Languages, and Programming, pages 212-223, Berlin, Heidelberg, 2013. Springer-Verlag. Google Scholar
  33. D. Fisman, O. Kupferman, and Y. Lustig. Rational synthesis. In Proc. 16th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems, volume 6015 of Lecture Notes in Computer Science, pages 190-204. Springer, 2010. Google Scholar
  34. S. Guha, M. Jurdzinski, S. N. Krishna, and A. Trivedi. Mean-payoff games on timed automata. In Proc. 36th Conf. on Foundations of Software Technology and Theoretical Computer Science, pages 44:1-44:14, 2016. Google Scholar
  35. T. Dueholm Hansen, R. Ibsen-Jensen, and P. Bro Miltersen. A faster algorithm for solving one-clock priced timed games. In Proc. 24th Int. Conf. on Concurrency Theory, pages 531-545, 2013. Google Scholar
  36. M. Hoefer, V. S. Mirrokni, H. Röglin, and S. Teng. Competitive routing over time. Theor. Comput. Sci., 412(39):5420-5432, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.05.055.
  37. M. Jurdzinski and A. Trivedi. Average-time games. In Proc. 28th Conf. on Foundations of Software Technology and Theoretical Computer Science, pages 340-351, 2008. Google Scholar
  38. E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. Computer Science Review, 3(2):65-69, 2009. Google Scholar
  39. E. Koutsoupias and K. Papakonstantinopoulou. Contention issues in congestion games. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming - Volume Part II, ICALP'12, pages 623-635. Springer-Verlag, 2012. Google Scholar
  40. O. Kupferman and T. Tamir. Hierarchical network formation games. In Proc. 23rd Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems, volume 10205 of Lecture Notes in Computer Science, pages 229-246. Springer, 2017. Google Scholar
  41. F. Laroussinie, N. Markey, and P. Schnoebelen. Model checking timed automata with one or two clocks. In Proc. 15th Int. Conf. on Concurrency Theory, pages 387-401, 2004. Google Scholar
  42. B.C. Moszkowski and Z. Manna. Reasoning in interval temporal logic. In Logics of Programs, volume 164 of Lecture Notes in Computer Science, pages 371-382. Springer, 1983. Google Scholar
  43. J.F. Nash. Equilibrium points in n-person games. In Proceedings of the National Academy of Sciences of the United States of America, 1950. Google Scholar
  44. C. H. Papadimitriou. Algorithms, games, and the internet. In Proc. 33rd ACM Symp. on Theory of Computing, pages 749-753, 2001. Google Scholar
  45. M. Penn, M. Polukarov, and M. Tennenholtz. Random order congestion games. Mathematics of Operations Research, 34(3):706-725, 2009. Google Scholar
  46. A. Pnueli. The temporal semantics of concurrent programs. Theoretical Computer Science, 13:45-60, 1981. Google Scholar
  47. K. Ronald and S. Martin. Nash equilibria and the price of anarchy for flows over time. Theoretical Computer Science, 49(1):71-97, 2011. Google Scholar
  48. R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65-67, 1973. Google Scholar
  49. T. Roughgarden and E. Tardos. How bad is selfish routing? Journal of the ACM, 49(2):236-259, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact