The Behavior of Systems with Selfish UsersCopyright: Martin Braun
Due to my position at two chairs and my additional work on the Ford Alliance Project my current research is divided into several main topics, that all are related to the "Behavior of systems with selfish users" and "Social Choice" Theory. I will sketch the different topics here.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 information 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 analyse 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.
Moreover, we are interested in the behaviour of different network-mechanism as well as different performance measures. So we compare utilitarian as well as egalitarian cost functions and compare the results. 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.
Links to related publications:
Autonomous Shuttle-Fleets for Cities
The Ford Alliance Project Autonomous Shuttle-Fleets for Cities is a cooperation between Ford Motor Company and RWTH Aachen University. Here, additionally to our chair, the Chair of Operation Research as well as the Chair and Institute of Urban and Transportation Planning are involved. This bright expertise of all participants results in a lot of synergy effects and thus several questions according to autonomous shuttles ca be answered.
Such a shuttle fleet has the potential to decease traffic congestion in a city center by substituting individual traffic but simultaneously increasing the mobility of all inhabitants. Operating such a fleet causes several optimization problems in design and management. In this project, we focus on operational tasks as well as strategic tasks.
One aim of this project is to develop a transport model for the region of Aachen that integrates this prospective service as an addition to public transport.
A first step is to simulate the demand of this new traffic mode in each iteration of the simulation (Click for more details). Afterwards the simulation will perform the tasks of the shuttle fleet according to our algorithms. Afterwards the customer can evaluate the service of the fleet such that we can validate our performance and prices. So this simulation is a great tool to observe the performance of an autonomous shuttle fleet based on real data of Aachen.
The conception and analysis of our heuristic approaches is still not finished yet. Moreover, I supervise different Master and Bachelor theses related to this simulation. For example we try to develop advanced dispatching algorithms, do path-calculations with energy constraints or investigate optimal reallocation strategies. On the other side we are interested in the development of pricing mechanism and auctions. For example we will analyse the impact of price reductions on ride sharing to the behaviour of the customer. Which price policy will give incentives to usage of such kind of services?