Competitive Packet Routing
With modern communication systems a lot of challenges rise. Consider the Internet, which is a huge network of servers and wires. An amazing amount of data is transported through this network in every second and each packet of data is allowed to freely choose a path through this network. Such a complex scenario leads to a lot of questions:
- What is a good protocol to send informations through the Internet? Which rules could speed up the total performance of the network?
- How long does it take to send a packet from location A to location B?
- What is the benefit of a central authority compared to selfish users in the network? What would it cost to install such an authority? Can we decrease the total travel time without regulating the participants too much?
For dealing with this questions we combine concepts of game theory and network optimization.
Game theory deals with systems in which selfish and rational agents interact with each other. While in network optimization there is the so called packet routing problem which asks for central solution that coordinates all agents in such a network. We represent the internet as a graph, servers become nodes and the wires between them become arcs. Selfish players (representing the packets) want to traverse a network as fast as possible but the capacities of some arcs are too small to handle all players simultaneously. So some of the data has to wait until it can pass this bottleneck.To analyze this kind of conflict we search for equilibria that arise from the selfish decisions of the players. We try to prove the existence of these equilibria. In case of existence, we compare the performance of such states with those that would result if a central authority optimized the paths of all participants. Due to this we can give bounds or guarantees on how bad a lack of coordination can be. Therefore we are able to classify different networks and mechanisms by their performance.
In a primary work we analyzed the impact of a priority list of all players on games, where each player owns a single packet . We derived several new bounds on the price of anarchy and stability for global and local priority policies. We also considered the question of the complexity of computing an optimal priority list. It turns out that even for very restricted cases, i.e. for routing on a tree, the computation of an optimal priority list is APX-hard.
-  Tobias Harks, Britta Peis, Daniel Schmand, and Laura Vargas Koch. Competitive Packet Routing with Priority Lists. 2016
Currently, we are working on Oligopolistic Routing Games, an extended version where each player is allowed to control an arbitrary number of packets.
Further in systems like traffic the priority depends not only on who you are (e.g. a police car) but more often on the road from which you come (e.g. a preference road). To deal with such situations we work on Routing Games with Edge Priorities.