License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.23
URN: urn:nbn:de:0030-drops-96053
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9605/
Avni, Guy ;
Guha, Shibashis ;
Kupferman, Orna
Timed Network Games with Clocks
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.
BibTeX - Entry
@InProceedings{avni_et_al:LIPIcs:2018:9605,
author = {Guy Avni and Shibashis Guha and Orna Kupferman},
title = {{Timed Network Games with Clocks}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {23:1--23:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-086-6},
ISSN = {1868-8969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9605},
URN = {urn:nbn:de:0030-drops-96053},
doi = {10.4230/LIPIcs.MFCS.2018.23},
annote = {Keywords: Network games, Timed automata, Nash equilibrium, Equilibrium inefficiency}
}
|
Keywords: |
|
Network games, Timed automata, Nash equilibrium, Equilibrium inefficiency |
|
Collection: |
|
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
27.08.2018 |
