License: 
Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1340
URN: urn:nbn:de:0030-drops-13406
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1340/
Briest, Patrick ;
Hoefer, Martin ;
Krysta, Piotr
Stackelberg Network Pricing Games
Abstract
We study a multi-player one-round game termed Stackelberg Network
Pricing Game, in which a leader can set prices for a subset of $m$
priceable edges in a graph. The other edges have a fixed cost.
Based on the leader's decision one or more followers optimize a
polynomial-time solvable combinatorial minimization problem and
choose a minimum cost solution satisfying their requirements based
on the fixed costs and the leader's prices. The leader receives as
revenue the total amount of prices paid by the followers for
priceable edges in their solutions, and the problem is to find
revenue maximizing prices. Our model extends several known pricing
problems, including single-minded and unit-demand pricing, as well
as Stackelberg pricing for certain follower problems like shortest
path or minimum spanning tree. Our first main result is a tight
analysis of a single-price algorithm for the single follower game,
which provides a $(1+varepsilon) log m$-approximation for any
$varepsilon >0$. This can be extended to provide a
$(1+varepsilon )(log k + log m)$-approximation for the general
problem and $k$ followers. The latter result is essentially best
possible, as the problem is shown to be hard to approximate within
$mathcal{O(log^varepsilon k + log^varepsilon m)$. If
followers have demands, the single-price algorithm provides a
$(1+varepsilon )m^2$-approximation, and the problem is hard to
approximate within $mathcal{O(m^varepsilon)$ for some
$varepsilon >0$. Our second main result is a polynomial time
algorithm for revenue maximization in the special case of
Stackelberg bipartite vertex cover, which is based on non-trivial
max-flow and LP-duality techniques. Our results can be extended to
provide constant-factor approximations for any constant number of
followers.
BibTeX - Entry
@InProceedings{briest_et_al:LIPIcs:2008:1340,
author = {Patrick Briest and Martin Hoefer and Piotr Krysta},
title = {{Stackelberg Network Pricing Games}},
booktitle = {25th International Symposium on Theoretical Aspects of Computer Science},
pages = {133--142},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-06-4},
ISSN = {1868-8969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1340},
URN = {urn:nbn:de:0030-drops-13406},
doi = {10.4230/LIPIcs.STACS.2008.1340},
annote = {Keywords: Stackelberg Games, Algorithmic Pricing, Approximation Algorithms, Inapproximability.}
}
|
Keywords: |
|
Stackelberg Games, Algorithmic Pricing, Approximation Algorithms, Inapproximability. |
|
Collection: |
|
25th International Symposium on Theoretical Aspects of Computer Science |
|
Issue Date: |
|
2008 |
|
Date of publication: |
|
06.02.2008 |
