Worst-Case Welfare of Item Pricing in the Tollbooth Problem
Preprint
Abstract
We study the worst-case welfare of item pricing in the \emph{tollbooth problem}. The problem was first introduced by Guruswami et al, and is a special case of the combinatorial auction in which (i) each of the $m$ items in the auction is an edge of some underlying graph; and (ii) each of the $n$ buyers is single-minded and only interested in buying all edges of a single path. We consider the competitive ratio between the hindsight optimal welfare and the optimal worst-case welfare among all item-pricing mechanisms, when the order of the arriving buyers is adversarial. We assume that buyers own the \emph{tie-breaking} power, i.e. they can choose whether or not to buy the demand path at 0 utility. We prove a tight competitive ratio of $3/2$ when the underlying graph is a single path (also known as the \emph{highway} problem), whereas item-pricing can achieve the hindsight optimal if the seller is allowed to choose a proper tie-breaking rule to maximize the welfare. Moreover, we prove an $O(1)$ upper bound of competitive ratio when the underlying graph is a tree. For general graphs, we prove an $\Omega(m^{1/8})$ lower bound of the competitive ratio. We show that an $m^{\Omega(1)}$ competitive ratio is unavoidable even if the graph is a grid, or if the capacity of every edge is augmented by a constant factor $c$. The results hold even if the seller has tie-breaking power.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Graph Pricing with Limited Supply2021
- An O(log log m) prophet inequality for subadditive combinatorial auctionsACM SIGecom Exchanges, 2020
- Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic InputsSIAM Journal on Computing, 2020
- A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2Journal of the ACM, 2016
- Walrasian Equilibrium: Hardness, Approximations and Tractable InstancesAlgorithmica, 2007
- Multicommodity demand flow in a tree and packing integer programsACM Transactions on Algorithms, 2007
- On Walrasian Price of CPU TimeAlgorithmica, 2007
- Approximation of Walrasian equilibrium in single-minded auctionsTheoretical Computer Science, 2005
- On complexity of single-minded auctionJournal of Computer and System Sciences, 2004
- Thek-server dual and loose competitiveness for pagingAlgorithmica, 1994