
Algorithms and Game Theory
with Economic Applications
Research project supported by
DFGgrant ”Algorithmic Tools for Games with Applications to
ECommerce and Networks” within "Aktionsplan Informatik" of
Emmy Noether program and
by
EPSRCgrant 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 noncooperative 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, noncooperative 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 MultiObjective Optimization.
To appear in the
Proceedings of the 21^{st} ACSIAM 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} ACSIAM 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 CollusionResistant Mechanisms with Verification.
In the Proceedings of
the 10th ACM Conference on Electronic Commerce (ACMEC), 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. CollusionResistant
Mechanisms with Verification Yielding Optimal Solutions. In the Proceedings of the 16th European Symposium
on Algorithms (ESA), 2008.
 Patrick Briest. Uniform Budgets and the EnvyFree 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
NonParametric MultiProduct Pricing.
In Proceedings of the 18th ACMSIAM 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. SingleMinded Unlimited Supply Pricing on
Sparse Instances.
In Proceedings of the 17th ACMSIAM 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 ACMSIAM 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.
