Algorithms and Game Theory

with Economic Applications

Research project supported by

DFG-grant ”Algorithmic Tools for Games with Applications to E-Commerce and Networks” within "Aktionsplan Informatik" of Emmy Noether program and by

EPSRC-grant on ”Algorithmic Mechanism Design and Optimization Problems with Economic Applications”

Description

We consider optimization problems motivated by applications coming from the Internet. These problems introduce the additional difficulties that we do not have the precise input data and the users (agents) behave selfishly. The data is a private property of the agents, and being rational, they usually tend to maximize their own benefit. In such situations the algorithm has to additionally "force" the agents to cooperate. This falls into the classical paradigm of non-cooperative game theory and, in particular, mechanism design.

Game theory and mechanism design have been studied by economists and game theorists for decades, but only very recently by computer scientists. The reason for this arises from modeling situations that naturally occur in the Internet, and many applications there, e.g., networking protocols, electronic commerce, non-cooperative software agents, etc. Hence, efficient algorithmic solutions for problems related to economics, game theory and mechanism design are needed. We plan to work on the design of algorithmic tools for such problems, where we address the fundamental theoretical questions and aim at solutions that would also have practical impact. Our main tools come from approximation algorithms, combinatorial optimization and probabilistic analysis.

Group

Piotr Krysta

Orestis Telelis

Giorgos Christodoulou
Patrick Briest
Carmine Ventre
Jörg Knoche
Martin Hoefer (May 2004 - July 2004)
Katarzyna Paluch (November 2004 - April 2005)

Publications

· F. Grandoni, P. Krysta, S. Leonardi and C. Ventre. Utilitarian Mechanism Design for Multi-Objective Optimization. To appear in the Proceedings of the 21^st AC-SIAM Symposium on Discrete Algorithms (SODA), 2010.

· G. Christodoulou and A. Kovacs. A deterministic truthful PTAS for scheduling related machines. To appear in the Proceedings of the 21^st AC-SIAM Symposium on Discrete Algorithms (SODA), 2010.

· P. Briest, M. Hoefer, L. Guala and C. Ventre. On Stackelberg Pricing with Computationally Bounded Consumers.

To appear in the Proceedings of the Fifth international Workshop on Internet & Network Economics (WINE), 2009.

· P. Penna and C. Ventre. Optimal Collusion-Resistant Mechanisms with Verification.
In the Proceedings of the 10th ACM Conference on Electronic Commerce (ACM-EC), 2009.

· Itai Ashlagi, Piotr Krysta and Moshe Tennenholtz. Social Context Games. In the Proceedings of the 4th International Workshop on Internet and Network Economics (WINE), 2008.

· Paolo Penna and Carmine Ventre. Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions. In the Proceedings of the 16th European Symposium on Algorithms (ESA), 2008.

Patrick Briest. Uniform Budgets and the Envy-Free Pricing Problem.
In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), 2008.
Vincenzo Auletta, Paolo Penna, Giuseppe Persiano, and Carmine Ventre. Alternatives to Truthfulness are Hard to Recognize.
In Proceedings of the 1st International Symposium on Algorithmic Game Theory (SAGT), 2008.
Moshe Babaioff, Patrick Briest, and Piotr Krysta. On the Approximability of Combinatorial Exchange Problems.
In Proceedings of the 1st International Symposium on Algorithmic Game Theory (SAGT), 2008.
Patrick Briest, Martin Hoefer, and Piotr Krysta. Stackelberg Network Pricing Games.
In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS), 2008.
Heiner Ackermann, Patrick Briest, Alexander Fanghänel, and Berthold Vöcking. Who Should Pay for Forwarding Packets?
In Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE), 2007.
Patrick Briest and Piotr Krysta. Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing.
In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007.
Jörg Knoche and Piotr Krysta. An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions.
In Proceedings of the 4th Workshop on Approximation and Online Algorithms (WAOA), 2006.
Patrick Briest and Piotr Krysta. Single-Minded Unlimited Supply Pricing on Sparse Instances.
In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006.
Piotr Krysta. Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing.
In Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2005.
Piotr Krysta. Bicriteria Network Design via Iterative Rounding.
In Proceedings of the 11th International Computing and Combinatorics Conference (COCOON), 2005.
Martin Hoefer and Piotr Krysta. Geometric Network Design with Selfish Agents.
In Proceedings of the 11th International Computing and Combinatorics Conference (COCOON), 2005.
Patrick Briest, Piotr Krysta and Berthold Vöcking. Approximation Techniques for Utilitarian Mechanism Design.
In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), 2005.
Rene Beier, Artur Czumaj, Piotr Krysta and Berthold Vöcking. Computing Equilibria for Congestion Games with (Im)perfect Information.
In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004.

Theses

Jörg Knoche. An Experimental Analysis of Approximation Algorithms for Combinatorial Auctions.
Diploma Thesis, November 2007.
Patrick Briest. Computational Aspects of Combinatorial Pricing Problems.
Ph.D. Thesis, November 2007.
Patrick Briest. Frugality and Truthfulness in Approximate Mechanism Design.
Diploma Thesis, November 2004.
Martin Hoefer. Network Connection Games.
Diploma Thesis, September 2004.