  We study an envy-free pricing problem, in which each buyer wishes to buy a
shortest path connecting her individual pair of vertices in a network owned by
a single vendor. The vendor sets the prices of individual edges with the aim of
maximizing the total revenue generated by all buyers. Each customer buys a path
as long as its cost does not exceed her individual budget. In this case, the
revenue generated by her equals the sum of prices of edges along this path. We
consider the unlimited supply setting, where each edge can be sold to
arbitrarily many customers. The problem is to find a price assignment which
maximizes vendor's revenue. A special case in which the network is a tree is
known under the name of the tollbooth problem. Gamzu and Segev proposed a
$\mathcal{O} \left( \frac{\log m}{\log \log m} \right)$-approximation algorithm
for revenue maximization in that setting. Note that paths in a tree network are
unique, and hence the tollbooth problem falls under the category of
single-minded bidders, i.e., each buyer is interested in a single fixed set of
goods.
  In this work we step out of the single-minded setting and consider more
general networks that may contain cycles. We obtain an algorithm for pricing
cactus shaped networks, namely networks in which each edge can belong to at
most one simple cycle. Our result is a polynomial time $\mathcal{0} \left(
\frac{\log m}{\log \log m}\right)$-approximation algorithm for revenue
maximization in tollbooth pricing on a cactus graph. It builds upon the
framework of Gamzu and Segev, but requires substantially extending its main
ideas: the recursive decomposition of the graph, the dynamic programming for
rooted instances and rounding the prices.
