Worst-Case Welfare of Item Pricing in the Tollbooth Problem

We study the worst-case welfare of item pricing in the tollbooth problem. The problem was first introduced by Guruswami et al. [GHK + 05], 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 [CS08, CDH + 17]. Moreover, we prove an O(1) upper bound of competitive ratio when the underlying graph is a tree. For general graphs, we prove an Ω(m 1/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.