Abstract
We study a multiplayer oneround 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
polynomialtime 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 singleminded and unitdemand 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 singleprice 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 singleprice 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 nontrivial
maxflow and LPduality techniques. Our results can be extended to
provide constantfactor 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 = {133142},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897064},
ISSN = {18688969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1340},
URN = {urn:nbn:de:0030drops13406},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1340},
annote = {Keywords: Stackelberg Games, Algorithmic Pricing, Approximation Algorithms, Inapproximability.}
}
Keywords: 

Stackelberg Games, Algorithmic Pricing, Approximation Algorithms, Inapproximability. 
Seminar: 

25th International Symposium on Theoretical Aspects of Computer Science 
Issue Date: 

2008 
Date of publication: 

06.02.2008 