Project Details

Network design problems are fundamental to Application Area B of the DFG Research Center Matheon and have been studied extensively in applied mathematics and theoretical computer science. These studies are primarily about algorithms that efficiently compute "good" solutions to the underlying network design problems; said differently, solution quality and computational efficiency are the major concerns. An assumption that is often made implicitly in this context is that the network participants, also termed agents, are indifferent to the output computed by the algorithm and therefore are willing to accept the proposed solution. However, today's networks, the Internet being the most prominent example, often consist of a multitude of autonomous and selfish agents that may attempt to manipulate the algorithm's decisions if advantageous. We can therefore no longer take this assumption for granted, but instead need to design algorithms that are resilient to these manipulations.

Mechanism design is concerned with the study of algorithms whose inputs are provided by selfish agents that would lie if this helped to achieve their own goals. One of the main objectives in mechanism design is to develop algorithms that are incentive compatible, i.e., that enforce the agents' truth-telling by making it in their own self-interest to do so. Algorithmic mechanism design therefore incorporates all three issues mentioned above, i.e., solution quality, computational efficiency and incentive compatibility of an algorithm.

In this project, we study combinatorial optimization problems from a natural game-theoretic perspective, with a particular focus on network design problems and scheduling problems. We aim at designing cost sharing mechanisms that can be utilized to share a commonly used resource (e.g., the cost of a network infrastructure, the processing time of a compute server) among selfishly acting agents.

The long term goals of this project are to (i) study the effect of selfish behaviour in a cost sharing context for network design and scheduling problems; (ii) identify alternative, practically relevant notions of incentive compatibility; (iii) design new algorithms that achieve the desired game-theoretic objectives; (iv) investigate the impact of the insights obtained in the cost sharing context on other areas, such as approximation algorithms, stochastic optimization, etc.; (v) identify and investigate an online analogon to the cost sharing setting and its objectives.