Project description.

Background.

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.

Research program.

In this project, we study combinatorial optimization problems from a natural game-theoretic perspective, with a particular focus on network design problems and, recently, also 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.

Expertise.

Our group has a strong theoretical background in algorithmic mechanism design and combinatorial optimization. Furthermore, we have gained expert knowledge by means of industry cooperations on related problems.

Results.

We obtain incentive compatible cost sharing mechanisms for the price collecting Steiner forest problem [2]. More precisely, we present a simple 3-budget-balanced and group-strategyproof mechanism for the above problem. We also show that our mechanism outputs client sets whose social cost is optimal.

While quite some progress has been made in understanding the issues mentioned above with respect to network design problems, they are far from being well-understood in the case of scheduling problems: We show in [1] that for many natural scheduling objectives, most of the known concepts and methodologies seem to be too restrictive to obtain good cost sharing algorithms. We therefore seek alternative, but practically reasonable notions of incentive compatibility and attempt to devise new algorithms that achieve these objectives.

Insights that have been gained in the context of cost sharing have recently turned out to be relevant also for other areas, such as approximation algorithms and stochastic optimization. In [3], we exploit this relationship and present a surprisingly simple 5-approximation algorithm for the well-studied multi-commodity rent-or-buy problem, a fundamental problem in network design. Moreover, we obtain a 6-approximation algorithm for the two-stage stochastic Steiner tree problem. A key ingredient of our approach are cost shares that are 3-strict for the primal-dual Steiner forest algorithm of Agrawal, Klein and Ravi.

Publications.

Cooperations.

Within Matheon: B8, B13, and B15.

Diploma Students.

• Bastian Schilling, diploma thesis jointly supervised with "Deutsches Luft und Raumfahrtzentrum in der Helmholtz-Gemeinschaft" (DLR)