In algorithmic game theory  we are concerned with modelling and understanding situations in which multiple agents with a selfish agenda interact. A classical example is traffic, where people aim to reach their destination as early as possible while influencing each other’s arrival times. In algorithmic game theory we aim to find models that depict real world situations as good as possible but are still analyzable. The first question is mostly: How do equilibrium states look like? An equilibrium state is a state where given the strategies of all other agents, every agent realizes the best possible objective function value for him or herself. Every day traffic can be seen as an equilibrium since given the routes of everyone else, an agents aims to arrive as early as possible.

One of my main research topics in algorithmic game theory are Nash flows over time. 

In a classical routing game, we are given a graph, where every arc is equipped with a cost function. Such a function assigns a cost to an arc dependent on the amount of players using it. Additionally, we are given a set of players that aim to find a connection from a start node to a destination node. These models are static in the sense that for every arc we have one number that describes the rate with which players use this arc. Since real-world traffic situations can be highly time dependent the field of dynamic routing games evolved. In such games agents move over time through the network and experience delay dependent on which players use the same arc at the same time. More concrete, in most models each arc is equipped with a free flow transit time and a throughput capacity. When at some point in time more players aim to enter an arc than the capacity allows a queue forms and thus, additional to the free flow transit time, the players experience some waiting time when traversing the arc.

In our research we aim to understand and analyze equilibria, so called Nash flows over time, in such dynamic routing games. Moreover, we study the connection to the traffic simulation software MATSim, which is  widely used traffic prediction tool. 

In combinatorial optimization we consider problems with a finite but usually large set of solutions. A classical problem is to calculate a shortest path from A to B. But instead of trying and comparing all possible solutions we aim to find the best one in a clever way. More concrete, we aim to describe algorithms that can find an optimal solution by only using polynomial in the input size many operations. There exists a class of problems where it is widely assumed that such algorithms do not exist. In this case we need to lower our expectations. Instead of wanting an optimal solution fast, we can aim to get a fairly good solution fast. More formally, instead of finding an optimal solution in polynomial time, we find an α-approximate solution in polynomial time. This means the value of the computed solution is within α range of the optimal function value.

One topic I like to work on is clustering, especially k-center problems. 

The k-center problem is a well-known optimization problem in computer science and operations research. The goal is to identify the optimal location for k centers in a given set of data points, such that the maximum distance between any data point and its nearest center is minimized. This problem has many practical applications, such as facility location and clustering.

In recent years, there has been growing interest in incorporating fairness considerations into k-center. Fairness can be defined in many ways, but typically refers to the idea that the benefits and costs of a decision should be distributed fairly among different groups.

Papers I was involved in, in this area are: Techniques for Generalized k-Center Problem (arXiv) and A Simple Combinatorial Algorithm for Robust Matroid Center (arXiv) both with Georg Anegg and Rico Zenklusen.

Currently, I am engaged in a project at ETH where we assist in exam planning. This endeavor is both enjoyable and provides an excellent opportunity to experiment with algorithms on complex problems and apply them to optimize the exam timetable for the benefit of both students and examiners at ETH.