1 Search Results for "Briest, Patrick"


Document
Stackelberg Network Pricing Games

Authors: Patrick Briest, Martin Hoefer, and Piotr Krysta

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)


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.

Cite as

Patrick Briest, Martin Hoefer, and Piotr Krysta. Stackelberg Network Pricing Games. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 133-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{briest_et_al:LIPIcs.STACS.2008.1340,
  author =	{Briest, Patrick and Hoefer, Martin and Krysta, Piotr},
  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 =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.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.}
}
  • Refine by Author
  • 1 Briest, Patrick
  • 1 Hoefer, Martin
  • 1 Krysta, Piotr

  • Refine by Classification

  • Refine by Keyword
  • 1 Algorithmic Pricing
  • 1 Approximation Algorithms
  • 1 Inapproximability.
  • 1 Stackelberg Games

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2008

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail