Worst-Case Welfare of Item Pricing in the Tollbooth Problem

Zihan Tan, Yifeng Teng, Mingfei Zhao

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 auc…