Avni, Guy ;
Guha, Shibashis ;
Kupferman, Orna
Timed Network Games
Abstract
Network games are widely used as a model for selfish resourceallocation 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 costsharing 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.
BibTeX  Entry
@InProceedings{avni_et_al:LIPIcs:2017:8067,
author = {Guy Avni and Shibashis Guha and Orna Kupferman},
title = {{Timed Network Games}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {37:137:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8067},
URN = {urn:nbn:de:0030drops80675},
doi = {10.4230/LIPIcs.MFCS.2017.37},
annote = {Keywords: Network Games, Timed Automata, Nash Equilibrium, Equilibrium Inefficiency}
}
01.12.2017
Keywords: 

Network Games, Timed Automata, Nash Equilibrium, Equilibrium Inefficiency 
Seminar: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Issue date: 

2017 
Date of publication: 

01.12.2017 