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, 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. On the one hand, we prove an $\Omega(m^{1/8})$ lower bound of the competitive ratio for general graphs. 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 $c$. On the other hand, we study the competitive ratio for special families of graphs. In particular, we improve the ratio when the input graph $G$ is a tree, from 8 (proved by Cheung and Swamy) to 3. We prove that the ratio is $2$ (tight) when $G$ is a cycle and $O(\log^2 m)$ when $G$ is an outerplanar graph. All positive results above require that the seller can choose a proper tie-breaking rule to maximize the welfare. In the paper we also consider the setting where the tie-breaking power is on the buyers' side, i.e. the buyer can choose whether or not to buy her demand path when the total price of edges in the path equals her value. We show that the gap between the two settings is at least a constant even when the underlying graph is a single path (this special case is also known as the highway problem). Meanwhile, in this setting where buyers have the tie-breaking power, we also prove an $O(1)$ upper bound of competitive ratio for special families of graphs.