English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the worst-case welfare of item pricing in the \emph{tollboothproblem}. The problem was first introduced by Guruswami et al, and is a specialcase of the combinatorial auction in which (i) each of the $m$ items in theauction is an edge of some underlying graph; and (ii) each of the $n$ buyers issingle-minded and only interested in buying all edges of a single path. Weconsider the competitive ratio between the hindsight optimal welfare and theoptimal worst-case welfare among all item-pricing mechanisms, when the order ofthe arriving buyers is adversarial. We assume that buyers own the\emph{tie-breaking} power, i.e. they can choose whether or not to buy thedemand path at 0 utility. We prove a tight competitive ratio of $3/2$ when theunderlying graph is a single path (also known as the \emph{highway} problem),whereas item-pricing can achieve the hindsight optimal if the seller is allowedto choose a proper tie-breaking rule to maximize the welfare. Moreover, weprove an $O(1)$ upper bound of competitive ratio when the underlying graph is atree.  For general graphs, we prove an $\Omega(m^{1/8})$ lower bound of thecompetitive ratio. We show that an $m^{\Omega(1)}$ competitive ratio isunavoidable even if the graph is a grid, or if the capacity of every edge isaugmented by a constant factor $c$. The results hold even if the seller hastie-breaking power.

Worst-Case Welfare of Item Pricing in the Tollbooth Problem