Earlier Version

Timed network games with clocks

G. Avni, S. Guha, O. Kupferman, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 37.

Download
OA 369.73 KB

Conference Paper | Published | English
Author
; ;
Department
Series Title
LIPIcs
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 vertex. The cost of traversing an edge depends on the 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 defining 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, the traversal of the network involves an inherent delay, and so sharing and congestion of resources crucially depends on time. We study 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. In addition, each edge has a guard, describing time intervals in which the edge can be traversed, forcing the players to spend time on vertices. Unlike earlier work that add a time component to network games, the time in our model is continuous and cannot be discretized. In particular, players have uncountably many strategies, and a game may have uncountably many pure Nash equilibria. We study properties of timed network games with cost-sharing or congestion cost functions: their stability, equilibrium inefficiency, and complexity. In particular, we show that the answer to the question whether we can restrict attention to boundary strategies, namely ones in which edges are traversed only at the boundaries of guards, is mixed.
Publishing Year
Date Published
2017-06-01
Volume
83
Article Number
37
Conference
MFCS: Mathematical Foundations of Computer Science (SG)
Conference Location
Aalborg, Denmark
Conference Date
2017-08-21 – 2017-08-25
ISSN
IST-REx-ID

Cite this

Avni G, Guha S, Kupferman O. Timed network games with clocks. In: Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017:37. doi:10.4230/LIPIcs.MFCS.2017.37
Avni, G., Guha, S., & Kupferman, O. (2017). Timed network games with clocks (Vol. 83, p. 37). Presented at the MFCS: Mathematical Foundations of Computer Science (SG), Aalborg, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2017.37
Avni, Guy, Shibashis Guha, and Orna Kupferman. “Timed Network Games with Clocks,” 83:37. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.37.
G. Avni, S. Guha, and O. Kupferman, “Timed network games with clocks,” presented at the MFCS: Mathematical Foundations of Computer Science (SG), Aalborg, Denmark, 2017, vol. 83, p. 37.
Avni G, Guha S, Kupferman O. 2017. Timed network games with clocks. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83. 37.
Avni, Guy, et al. Timed Network Games with Clocks. Vol. 83, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 37, doi:10.4230/LIPIcs.MFCS.2017.37.
All files available under the following license(s):
Creative Commons License:
CC-BYCreative Commons Attribution 4.0 International Public License (CC-BY 4.0)
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T10:14:10Z


Material in IST:
Later Version

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar