Worst-Case Welfare of Item Pricing in the Tollbooth Problem
Open Access
- 30 April 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 3508-3518
Abstract
We study the worst-case welfare of item pricing in the tollbooth problem. The problem was first introduced by Guruswami et al. [27], 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 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 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 [6, 11]. Moreover, we prove an O(1) upper bound of competitive ratio when the underlying graph is a tree. For general graphs, we prove an Ω(m1/8) lower bound of the competitive ratio. We show that an mΩ(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 29 references indexed in Scilit:
- On Profit-Maximizing Pricing for the Highway and Tollbooth Problems2009
- Combination Can Be Hard: Approximability of the Unique Coverage ProblemSIAM Journal on Computing, 2008
- Multicommodity demand flow in a tree and packing integer programsACM Transactions on Algorithms, 2007
- On Walrasian Price of CPU TimeAlgorithmica, 2007
- How to Sell a Graph: Guidelines for Graph Retailers2006
- Near-Optimal Pricing in Near-Linear Time2005
- On complexity of single-minded auctionJournal of Computer and System Sciences, 2004
- Speed is as powerful as clairvoyanceJournal of the ACM, 2000
- Thek-server dual and loose competitiveness for pagingAlgorithmica, 1994
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985