Bi-Weekly Talk: Competitive Packet Routing: How Mistrusting Harms Performance

Wednesday, 04.04.2018, 10:15am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10

 

Speaker: Laura Vargas Koch and Björn Tauer

 

We will start our talk with a basic introduction to algorithmic game theory and then talk about our current research in competitive packet routing. Here we consider a game-theoretic variant of packet routing. In contrast to classical packet routing, we are  lacking a central authority. Instead, selfish acting players route from a source to a sink and try to r each the sink as fast as possible. The network is represented by a directed graph, each edge of which being endowed with a transit time, as well as a capacity bounding the number of traffic units entering an edge simultaneously. This means if more player want to enter an edge than it is possible, there is a conflict between the players. To solve these conflicts we consider several rules. One of them is a total ordering of the players, we will only give an overview about the results for this rule. Another possibility to solve these conflicts comes from traffic. Here it makes sense to define priorities on the edges - main roads are preferred over smaller roads. This means if more players want to enter an edge than it is possible, the players coming from the main road are preferred. We present an algorithm computing a certain class of equilibria in these games, mistrustful equilibria and we analyze their properties. Further we examine the connection to earliest arrival flows.