Project B16: Mechanisms for Network Design Problems

DFG Research Center Matheon Technische Universität Berlin
Duration: Sep. 2005 - May 2010
Project head: Dr. Guido Schäfer
Centrum Wiskunde & Informatica
Algorithms, Combinatorics and Optimization
Science Park 123
1098 XG Amsterdam
The Netherlands
Tel: +31 20 592 4257
email: g dot schaefer at cwi dot nl
Research Assistant: Janina Brenner
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
Germany
Tel: +49 (0)30 - 314 29400 
email: brenner 'at' math.tu-berlin.de
Support: DFG Research Center "Mathematics for Key Technologies" (Matheon)
Quick Links: Publications


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 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 developed cost sharing mechanisms with tight approximation guarantees both with respect to budget balance and social cost for several fundamental network design problems, such as the Steiner forest problem [6], the price-collecting Steiner forest problem [4] and general connectivity problems [7]. Most of these mechanisms were obtained by designing new primal-dual approximation algorithms for the underlying optimization problems that exhibit cross-monotonic cost shares.

Our investigations revealed that group-strategyproof mechanisms for certain scheduling problems inherently suffer from poor budget balance or social cost approximation guarantees. While for makespan scheduling problems we could derive group-strategyproof mechanisms with good budget balance and social cost approximation guarantees, similar results for scheduling problems with completion time objectives are provably impossible [1]. In a very recent work [2], we were able to provide a general framework to design mechanisms that achieve a slightly weaker notion of group-strategyproofness, called weak group-strategyproofness, but significantly better approximation guarantees with respect to budget balance and social cost. This framework allows us to convert greedy-type algorithms into cost sharing mechanisms; using this framework, we were able to derive weakly group-strategyproof mechanisms with attractive budget balance and social cost approximation guarantees for various scheduling problems.

Insights that have been gained in the context of cost sharing turned out to be relevant also for other areas, such as linear programming [6], approximation algorithms and stochastic optimization [5].

Publications.

[1] J. Brenner and G. Schäfer.
Cost Sharing Methods for Makespan and Completion Time Scheduling.
In Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, 2007.
[pdf]
[2] J. Brenner and G. Schäfer.
Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems.
In Proceedings of the 1st International Symposium on Algorithmic Game Theory (SAGT), Lecture Notes in Computer Science, 2008.
[pdf]
[3] J. Brenner and G. Schäfer.
Group-Strategyproof Cost Sharing Mechanisms for Makespan and Other Scheduling Problems.
In Theoretical Computer Science, volume 401(1-3), pages 96-106, 2008.
[4] A. Gupta, J. Könemann, S. Leonardi, R. Ravi, and G. Schäfer.
An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner Forest Problem.
In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM Press, 2007.
[pdf]
[5] L. Fleischer, J. Könemann, S. Leonardi, and G. Schäfer.
Simple Cost Sharing Schemes for Multi-Commodity Rent-or-Buy and Stochastic Steiner Tree.
In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), 2006.
[pdf]
[6] J. Könemann, S. Leonardi, G. Schäfer, and S. van Zwam.
A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game.
SIAM Journal on Computing, volume 37(5), pages 1319-1341, 2008.
[pdf]
[7] J. Könemann, S. Leonardi, G. Schäfer, and D. Wheatley.
Group-Strategyproof Mechanisms for Network Design Games via Primal-Dual Algorithms
Matheon Preprint 467, 2008.

Cooperations.

Within Matheon: B8, B13, and B18.

External:

Diploma Students.