Improved hardness of approximation for Stackelberg shortest-path pricing

Patrick Briest*, Parinya Chalermsook, Sanjeev Khanna, Bundit Laekhanukit, Danupon Nanongkai

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

12 Citations (Scopus)

Abstract

We consider the Stackelberg shortest-path pricing problem, which is defined as follows. Given a graph G with fixed-cost and pricable edges and two distinct vertices s and t, we may assign prices to the pricable edges. Based on the predefined fixed costs and our prices, a customer purchases a cheapest s-t-path in G and we receive payment equal to the sum of prices of pricable edges belonging to the path. Our goal is to find prices maximizing the payment received from the customer. While Stackelberg shortest-path pricing was known to be APX-hard before, we provide the first explicit approximation threshold and prove hardness of approximation within 2 - o(1). We also argue that the nicely structured type of instance resulting from our reduction captures most of the challenges we face in dealing with the problem in general and, in particular, we show that the gap between the revenue of an optimal pricing and the only known general upper bound can still be logarithmically large.

Original languageEnglish
Title of host publicationInternet and Network Economics - 6th International Workshop, WINE 2010, Proceedings
Pages444-454
Number of pages11
Volume6484 LNCS
DOIs
Publication statusPublished - 2010
MoE publication typeA4 Article in a conference publication
EventInternational Workshop on Internet and Network Economics - Stanford, United States
Duration: 13 Dec 201017 Dec 2010
Conference number: 6

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6484 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Workshop

WorkshopInternational Workshop on Internet and Network Economics
Abbreviated titleWINE
Country/TerritoryUnited States
CityStanford
Period13/12/201017/12/2010

Fingerprint

Dive into the research topics of 'Improved hardness of approximation for Stackelberg shortest-path pricing'. Together they form a unique fingerprint.

Cite this