Timed Network Games Conference Paper


Author(s): Avni, Guy; Guha, Shibashis; Kupferman, Orna
Title: Timed Network Games
Title Series: LIPIcs
Affiliation IST Austria
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.
Conference Title: MFCS: Mathematical Foundations of Computer Science (SG)
Conference Dates: August 21- August 25, 2017
Conference Location: Aalborg, Denmark
Publisher: Schloss Dagstuhl- Leibniz-Zentrum für Informatik  
Date Published: 2017-06-01
Start Page: 37:1
End Page: 37:14
Copyright Statement: CC-BY 3.0 DE
Sponsor: The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013, ERC grant no 278410) and the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE/SHi
URL:
DOI: 10.4230/LIPIcs.MFCS.2017.37
Open access: yes (OA journal)
IST Austria Authors
  1. Guy Avni
    6 Avni
Related IST Austria Work