# Worst-Case Welfare of Item Pricing in the Tollbooth Problem

Zihan Tan University of Chicago. Email<EMAIL_ADDRESS>Supported in
part by NSF grant CCF-1616584. Yifeng Teng University of Wisconsin-Madison.
Email<EMAIL_ADDRESS>Supported in part by NSF grant CCF-1617505 and
SHF-1704117. Mingfei Zhao Yale University. Email<EMAIL_ADDRESS>Supported by the NSF Award CCF-1942583 (CAREER)

We study the worst-case welfare of item pricing in the _tollbooth problem_.
The problem was first introduced by Guruswami et al [30], 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 [12]) 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.

##  1 Introduction

Welfare maximization in combinatorial auctions is one of the central problems
in market design. The auctioneer is selling $m$ heterogeneous items to $n$
self-interested buyers. She aims to find a welfare-maximizing allocation, and
designs payments to incentivize all buyers to truthfully report their private
preferences. We consider the special case that every buyer is _single-minded_
, which means that the buyer is only interested in buying a certain subset of
items, and has value $0$ if she does not get the whole subset. While the
celebrated VCG mechanism [50, 15, 29] is truthful and maximizes the welfare,
markets in the real world often prefer to implement simpler mechanisms, such
as _item pricing_.

In an item-pricing mechanism, each item is given an individual price. Buyers
come to the auction sequentially and choose the favorite bundle (among the
remaining items) that maximizes their own utilities. For a single-minded
buyer, she will purchase her demand set if and only if all items in the set
are available, and the total price of the items is at most her value. The
performance of an item-pricing mechanism is measured by its _worst-case
welfare_ , that is, the minimum sum of buyers’ value achieved by the mechanism
when the buyers arrive in any adversarial order. In this setting, the
Walrasian equilibrium [1, 17] for gross-substitutes buyers provides a set of
prices as well as a welfare-maximizing allocation, such that every buyer
receives her favorite bundle [36], which allows us to maximize the welfare
using an item-pricing mechanism. However, such an equilibrium (or a set of
prices) may not exist when the buyers are single-minded.

In the paper we focus on a special case of the above problem known as the
_tollbooth problem_ [30], where the set of commodities and demands are
represented by edges and paths in a graph. This setting has found various
real-world applications. For instance, a network service provider wants to
sell bandwidth along with the links of a network by pricing on every single
link, and each customer is only interested in buying a specific path in the
network. In this setting, every item in the auction is an edge in some graph
$G$ representing the network, and every buyer is single-minded and is only
interested in buying all edges of a specific path of $G$. We additionally
impose the restriction that each commodity (edge) may be given to at most one
buyer, which means that if an edge was taken by some previous buyer, then
buyers who come afterward whose demand set contains this edge may no longer
take it. Similar to the general case, Walrasian equilibrium is not guaranteed
to exist for the tollbooth problem. Moreover, Chen and Rudra [11] proved that
the problem of determining the existence of a Walrasian equilibrium and the
problem of computing such an equilibrium (if it exists) are both NP-hard for
the tollbooth problems on general graphs. Therefore, an investigation of the
power and limits of item pricing is a natural next step towards a deeper
understanding of the tollbooth problem. For an item-pricing mechanism, its
_competitive ratio_ is the ratio between the hindsight optimal welfare, i.e.
the optimal welfare achieved by any feasible allocation of items to buyers,
and the worst-case welfare of the item-pricing mechanism. In the paper, we
study the best (smallest) competitive ratio among all item-pricing mechanisms
in a given instance of the tollbooth problem.

The tollbooth problem has been extensively studied in the literature. One line
of work [28, 23, 30, 27, 38] aims to efficiently compute prices of items as
well as a special subset of buyers called _winners_ while maximizing the total
welfare, such that it is feasible to allocate the demand sets to all winners,
and every winner can afford her bundle. There is a major difference between
all works above and our setting. In all works above, it is only required that
the set of buyers who get their demand sets can afford their demand sets. But
there might be other buyers who could afford their demand sets as well but
eventually did not get them (or equivalently, not selected as winners). Since
the arriving order is adversarial in our setting, these buyers might come
before the winners and take their demand sets. The winners may no longer get
their demand sets since some items in their demand sets are already taken.
Therefore, the set of prices computed in the works above may not end up
achieving the worst-case welfare equal to the total value of all winners. It
is not hard to see that our item-pricing mechanisms are stronger than the
settings in the works above: If a set of prices has a competitive ratio
$\alpha$ in our setting, then such a set of prices is automatically an
$\alpha$-approximation in the setting of the works above, but the converse is
not true.

The previous work whose setting is closest to ours is [12] by Cheung and
Swamy. They studied envy-free pricing in the tollbooth problem, which
additionally requires that the losers (buyers who did not get their demand
sets) can not afford their demand sets. Envy-free pricing achieves the same
welfare in any arrival order. They constructed an algorithm in the multi-
supply setting, that takes any LP-based $\alpha$-approximation solution to the
optimal welfare, and returns an envy-free pricing mechanism that achieves
approximation ratio $O(\alpha\cdot\log u)$, where $u$ is the maximum supply of
an item. When the supply of each edge is 1, the algorithm obtains a
$2\alpha$-approximation. Since the best efficient LP-based algorithm [9]
achieves a $4$-approximation algorithm when the underlying graph is a tree,
the algorithm in [12] achieves a competitive ratio $8$ by envy-free pricing on
trees. In our paper, we improve their results by computing an item pricing
that achieves competitive ratio $3$ on trees. Additionally, we analyze the
competitive ratio beyond trees, e.g. cycles and outerplanar graphs. We remark
that in [12], the approximation ratio compares the optimal welfare with the
profit of the pricing, which is the total prices of all sold edges. In fact,
all positive results in our paper also work for profit, as the profit and
welfare of the item-pricing mechanisms in the proofs are the same. In the
paper, we define the competitive ratio using the welfare of the pricing
instead of the profit, in order to have a consistent notation for both lower
and upper bounds.

###  1.1 Our Results

We study the best competitive ratio (the ratio between the optimal welfare and
the worst-case welfare) achieved by any item-pricing mechanism in the
tollbooth problem. Our results can be summarized in the following four
aspects.

#### 1\. Item pricing for special graphs.

We first consider the case where the seller has tie-breaking power. It is
folklore (see e.g. [12, 7]) that when the seller has tie-breaking power and
$G$ is a single path, the competitive ratio of the problem is 1, i.e., there
exists an item-pricing mechanism that achieves the optimal welfare. However,
for graphs beyond paths, even when $G$ is a star, the competitive ratio can be
strictly larger than 1. In the paper, we show that for simple families of
graphs (e.g. trees, cycles, or outerplanar graphs), the competitive ratio is
$O(1)$ or a polylogarithm of $m$. A summary of the results is shown in Table
1. In particular, we prove that the competitive ratio of any tree is at most
3, which improves the 8-approximation obtained in [12].

######  Result 1.

When the seller has tie-breaking power, the competitive ratio is at most 3 for
any tollbooth problem on trees. Moreover, a set of prices that achieves the
desired ratio can be computed in polynomial time.

Graph Class | Lower Bound (with Tie) | Upper Bound (with Tie) | Upper Bound (no Tie)
---|---|---|---
Path |  $1$ ([12, 7]) | 3/2 (tight, Thm 5.1, 5.2)
Star |  $3/2$ (Thm 3.2, 3.3) | 2 (Thm 5.3)
Spider |  $3/2$ (Thm 3.4, 3.3) | 7/2 (Thm 5.4)
Tree |  $3/2$ (Thm 3.3) |  $3$ (Thm 3.5) | 7 (Thm 5.5)
Cycle |  $2$ (Thm 3.6, 3.7) | 2 (Thm 5.6)
Outerplanar |  $\Omega((\frac{\log m}{\log\log m})^{1/2})$ (Thm 4.3) |  $O(\log^{2}m)$ (Thm 3.8) |  $O(\log^{2}m)$ (Theorem 5.7)
Table 1: Summary of results for special families of graphs.

#### 2\. Item pricing for general graphs.

In contrast with our results for special families of graphs, we show that, for
general graphs, the competitive ratio can be polynomial in the number of its
edges, even when the graph is a grid. In [12] and [13], the competitive ratio
was proved to be $O(\sqrt{m})$. This bound also holds for the general single-
minded combinatorial auctions, where the demand of every agent is an arbitrary
set rather than a single path. Here the $O(\sqrt{m})$-competitive ratio was
shown to be tight up to a constant by Feldman et al. [25]. In this paper we
prove an alternative bound $O(m^{0.4}\log^{2}m\log n)$ on the competitive
ratio in any tollbooth problem with a general underlying graph (Theorem 4.4).
When $n$, the number of buyers in the auction, is subexponential on $m$, our
competitive ratio is better than the previous ratio $O(\sqrt{m})$.

######  Result 2.

The competitive ratio for any tollbooth problem is $O(m^{0.4}\log^{2}m\log
n)$. On the other hand, there exists a tollbooth problem instance such that
the competitive ratio is $\Omega(m^{1/8})$. Moreover, there exist a constant
$\alpha\in(0,1)$ and an instance on grid such that the competitive ratio is
$\Omega(m^{\alpha})$. Here $m$ is the number of edges and $n$ is the number of
buyers.

#### 3\. Without tie-breaking power.

In addition to the set of prices, a key factor that can significantly affect
the welfare of an item-pricing mechanism is the _tie-breaking_ rule. For
example, if Walrasian equilibrium exists, item pricing can achieve the optimal
welfare, but requires carefully breaking ties among all the favorite bundles
of every buyer. In most scenarios studied in previous works, it is assumed
that the auctioneer can cleverly convince the buyer to break ties properly so
as to maximize welfare. However, in real markets, buyers often come to the
mechanism themselves and simply purchase an arbitrary favorite bundle that
maximizes their own utility. Therefore it is possible that the absence of tie-
breaking power may influence the welfare achieved by the mechanism. In the
paper, we also compare the welfare guarantee of the best item-pricing
mechanism in both settings of the tollbooth problem: the setting where the
auctioneer has the power of deciding whether or not to allocate the demand
path to the buyer, when the total price of edges in the path equals her value;
and the setting where the buyer decides whether or not to purchase the demand
path in the same scenario.

As discussed above, when $G$ is a single path and the seller has tie-breaking
power, there exists an item pricing that achieves the optimal welfare.
However, when the seller has no tie-breaking power, we present an instance
where $G$ is a single path, that no item pricing can achieve more than
$2/3$-fraction of the hindsight optimal welfare (Theorem 5.1). On the other
hand, we prove that such a $3/2$-approximation is achievable via item pricing
(Theorem 5.2).

######  Result 3.

The competitive ratio for any tollbooth problem on a single path is at most
$3/2$, when the seller has no tie-breaking power. Moreover, the ratio is
tight.

We also provide upper bounds for the competitive ratio in the no tie-breaking
case, when the graph $G$ belongs to some special families of graphs. See also
Table 1 for a summary of the results.

#### 4\. Resource augmentation.

We also study the problem where the seller has more resource to allocate, and
want to compare the welfare achieved in this case to the optimal offline
allocation without such additional resource. To be more specific, comparing to
the optimal offline allocation with supply 1 for each item, the seller has
augmented resources and is allowed to sell $c$ copies of each item to the
buyers. In the literature studying offline path allocation problems on graphs
(e.g. [14]) and previous work using the techniques of resource augmentation
(e.g. [35, 39, 48, 52, 6]), even slightly increased resources usually improves
the competitive ratio significantly. However in our problem, we prove that for
any constant $c>1$, there exists an instance such that the competitive ratio
with augmented resources is $m^{\Omega(1/c)}$, even we allow different item
prices for different copies (Theorem 6.3). In other words, a competitive ratio
that is polynomial in $m$ is unavoidable in the tollbooth problem, even if the
capacity of each edge is augmented by a constant. We also prove an almost-
matching upper bound of $O(m^{1/c})$ in this setting (Theorem 6.1). The
approximation holds for any single-minded welfare maximization problem, where
each buyer may demand any set of items instead of edges in a path.

######  Result 4.

For any constant integer $c>0$, consider the tollbooth problem where each edge
has $c$ copies to sell. There is an instance, such that for any set of prices
$\left\\{p^{k}(i)\mid i\in[m],1\leq k\leq c\right\\}$ where $p^{k}(i)$
represent the price for the $k$-th copies of edge $i$, the item-pricing
mechanism achieves worst-case welfare an $O(m^{-1/(2c+6)})$-fraction of the
optimal welfare when each edge has supply 1. On the other hand, there exists
an item pricing that achieves worst-case welfare an
$\Omega(m^{-1/c})$-fraction of the optimal welfare when each edge has supply
1.

###  1.2 Our Approach and Techniques

#### Techniques for upper bounds.

We use two major tools for computing prices that achieve good worst-case
welfare. First, we consider the natural LP relaxation for computing the
optimal allocation. It is a common technique that the variables of the dual LP
can be interpreted as prices for corresponding items (see e.g. [4, 45, 12, 7,
42]).

$\displaystyle\mbox{(LP-Primal)}~{}~{}~{}~{}\max$
$\displaystyle~{}~{}\sum_{j\in[n]}v_{j}\cdot y_{j}$ (1) subject to
$\displaystyle~{}~{}\sum_{j:i\in Q_{j}}y_{j}\leq 1$
$\displaystyle~{}~{}\forall i\in[m]$ $\displaystyle~{}~{}y_{j}\geq 0$
$\displaystyle~{}~{}\forall j\in[n]$ $\displaystyle\mbox{(LP-
Dual)}~{}~{}~{}~{}~{}~{}\max$ $\displaystyle~{}~{}\sum_{i\in[m]}p_{i}$ (2)
subject to $\displaystyle~{}~{}\sum_{i\in Q_{j}}p_{i}\geq v_{j}$
$\displaystyle~{}~{}\forall j\in[n]$ $\displaystyle~{}~{}p_{i}\geq 0$
$\displaystyle~{}~{}\forall i\in[m]$

We show (in Lemma 3.1) that for any optimal fractional solution $y^{*}$, there
is a price vector $p^{*}$ such that only buyers $j$ with $y^{*}_{j}>0$ can
afford their demand sets. Moreover, such a price vector can be efficiently
computed. This reduces the task of computing prices of items to the task of
finding a subset of buyers, such that (i) their demand paths are “as vertex-
disjoint as possible”; and (ii) their total value of the demand sets is a good
approximation of the optimal objective value of (LP-Primal). We use the above
tools to prove the competitive ratio for stars and spiders.

The above LP-based approach is similar to [12], where they prove an
$8$-approximation when $G$ is a tree. To obtain the improved competitive ratio
$3$ for trees, we use a new approach that makes use of our result for spider
graphs. We start with an optimal allocation (which corresponds to a set
$\mathcal{P}$ of demand paths), and then construct an algorithm (in Lemma 3.6)
that partitions the paths of $\mathcal{P}$ into two subsets
$\mathcal{P}=\mathcal{P}_{1}\cup\mathcal{P}_{2}$, such that the graph obtained
by taking the union of all paths in $\mathcal{P}_{t}$ is a spider, for each
$t\in\left\\{1,2\right\\}$. Then the task of computing the price on the edges
of a tree is reduced to that of a spider, while losing a factor of $2$ in the
competitive ratio.

#### Techniques for lower bounds.

The hard instance for the $\Omega(m^{1/8})$ competitive ratio is constructed
on a simple series-parallel graph (see Figure 1). In the hard instance, every
buyer demands a path connecting the left-most vertex to the right-most vertex,
and the value for each demand path is roughly the same. The demand paths are
constructed carefully, such that (i) each edge of the graph is contained in
approximately the same number of demand paths; and (ii) the demand paths are
intersecting in some delicate way. We can then show that, for any price vector
$p$, if we denote by $\mathcal{P}$ the set of affordable (under $p$) demand
paths, then either the maximum cardinality of an independent subset of
$\mathcal{P}$ is small, or there is a path in $\mathcal{P}$ that intersects
all other paths in $\mathcal{P}$. Either way, we can conclude that the optimal
worst-case welfare achieved by any item-pricing mechanism is small.

Figure 1: A series-parallel graph with large competitive ratio.

###  1.3 Other Related Work

#### Walrasian equilibrium for single-minded buyers.

A closely related problem of our setting is the problem of finding market-
clearing item prices for single-minded buyers. Unlike maximizing the total
value of agents allocated in our setting, a Walrasian equilibrium requires
every buyer with a positive utility to be allocated. The existence of the
Walrasian equilibrium is proven to be NP-hard, while satisfying $\frac{2}{3}$
of the buyers is possible [10, 34, 19, 11]. The hardness of the problem
extends to selling paths on graphs, and is efficiently solvable when the
underlying graph is a tree [11].

#### Profit maximization for single-minded buyers.

For the general profit maximization for single-minded buyers with unlimited
supply, Guruswami et al. [30] proved an $O(\log n+\log m)$-approximation. The
result was improved to an $O(\log B+\log\ell)$-approximation ratio by Briest
and Krysta [5], and then to an $O(\log B)$-approximation by Cheung and Swamy
[12]. Here $B$ is the maximum number of sets containing an item and $\ell$ is
the maximum size of a set. Balcan and Blum [2] gave an
$O(\ell^{2})$-approximation algorithm. Hartline and Koltun [32] gave an FPTAS
with a bounded number of items. On the other hand, the problem was proved to
be NP-hard for both the limited-supply [28] and unlimited-supply [30, 5] case,
and even hard to approximate [18].

#### Profit maximization for the tollbooth problem.

Grigoriev et al. [28] proved that the problem is polynomial-time solvable when
the underlying graph $G$ is a tree, and it is NP-complete to approximate
within factor $O(m^{1-\varepsilon})$ when $G$ is a grid, where $m$ is the
number of buyers. Elbassioni et al. [23] studied the case where $G$ is a tree
and obtained an $O(\log m)$-approximation even when edges have multiple
supplies, improving upon the $O(\log n+\log m)$-approximation obtained in
[30], where $m$ is the number of edges in the graph. When edges have an
unlimited supply, the approximation ratio was further improved to $O(\log
m/\log\log m)$ in [27]. Moreover, Kortsarz et al. [38] studied the case where
$G$ is a rooted tree and every demand path is a subpath of some root-to-leaf
path of $G$. They showed that any such instance can be reduced to the tree
case, by losing a constant factor in the approximation ratio. It worths
mentioning that the tollbooth problem on star graphs analyzed in our paper is
similar to the graph pricing problem (where prices are given to vertices, and
each buyer takes an edge) studied by Balcan and Blum [2], while they
considered the unlimited supply setting. They obtained a 4-approximation,
which was later shown to be tight by Lee [41] unless the Unique Games
Conjecture is false. For the multiple and limited supply case, Friggstad et
al. [26] obtained an $8$-approximation.

#### Pricing for online welfare maximization with tie-breaking power.

The problem of online resource allocation for welfare maximization has been
extensively studied in the prophet inequality literature. In the full-
information setting where all buyers’ values are known, bundle pricing
achieves $2$-approximation to optimal offline welfare [16], even when the
buyers’ values are arbitrary over sets of items. In a Bayesian setting where
the seller knows all buyers’ value distributions, item pricing achieves a
2-approximation in welfare for buyers with fractionally subadditive values
[40, 46, 37, 24], and an $O(\log\log m)$-approximation for subadditive buyers
[21]. For general-valued buyers that demand at most $k$ items, item pricing
can achieve a tight $O(k)$-approximation [20]. [7] studied the problem of
interval allocation on a path graph, and achieves
$(1-\varepsilon)$-approximation via item pricing when each item has supply
$\Omega(k^{6}/\varepsilon^{3})$, and each buyer has a fixed value for getting
allocated any path she demands. [8] further extends the results to general
path allocation on trees and gets a near-optimal competitive ratio via
anonymous bundle pricing.

#### Pricing for online welfare maximization without tie-breaking power.

When the seller does not have tie-breaking power, [16, 42] show that when
there is a unique optimal allocation for online buyers with gross-substitutes
valuation functions, static item pricing can achieve the optimal welfare. When
the optimal allocation is not unique, [16, 3] show that a dynamic pricing
algorithm can obtain the optimal welfare for gross-substitutes buyers, but for
not more general buyers. [33] shows that if the buyers have matroid-based
valuation functions, when the supply of each item is more than the total
demand of all buyers, the minimum Walrasian equilibrium prices achieve near-
optimal welfare. [16, 22] shows that for an online matching market, when the
seller has no tie-breaking power, static item pricing gives at least
$0.51$-fraction of the optimal offline welfare, and no more than
$\frac{2}{3}$.

###  1.4 Organization

In Section 2 we describe the settings of the problems studied in the paper in
detail. In Section 3, we present our results on the competitive ratio for some
special families of graphs, including stars and spiders (Section 3.1), trees
(Section 3.2), cycles (Section 3.3) and outerplanar graphs (Section 3.4). In
Section 4, we prove upper and lower bounds for general graphs and lower bounds
for grids. In Section 5 we present our results in the settings where the
seller does not have tie-breaking power, on path (Section 5.1), stars,
spiders, trees and cycles (Section 5.2). In Section 6, we present our results
in the setting the capacity of edges in the graph is augmented by a constant.
Finally we discuss possible future directions in Section 7.

##  2 Our Model

In this section, we introduce our model in more detail.

A seller wants to sell a set $[m]$ of $m$ heterogeneous items to $n$ buyers.
Each buyer $j$ is single-minded: She demands a set $Q_{j}\subseteq[m]$ with a
positive value $v_{j}$. Her value for a subset $S\subseteq[m]$ of items is
$v_{j}$ if $Q_{j}\subseteq S$, and $0$ otherwise. For every buyer $j$, the set
$Q_{j}$ and the value $v_{j}$ are known to the seller. The seller aims to
maximize the welfare, that is, the sum of all buyers’ value who get their
demand sets. As a special case of the above auction, in the _tollbooth
problem_ , there is an underlying graph $G$. We denote $V(G)$ and $E(G)$ the
vertex and edge set of $G$. Every item in the auction corresponds to an edge
in $E(G)$. Let $E(G)=\\{e_{1},\ldots,e_{m}\\}$. For simplicity, we use the
index $i$ to represent the edge $e_{i}$ as well. For every agent $j$, her
demand set $Q_{j}$ is a single path in graph $G$. For a set of paths
$\mathcal{Q}$, denote $E(\mathcal{Q})=\bigcup_{Q\in\mathcal{Q}}E(Q)$. We say
that paths in $\mathcal{Q}$ are _edge-disjoint_ (_node-disjoint_ , resp.) if
all paths in $\mathcal{Q}$ do not share edges (vertices, resp.).

In the paper we focus on a special class of mechanisms called _item pricing_
mechanisms. In an item pricing mechanism, the seller first computes a posted
price $p(e_{i})$ (or $p_{i}$) for every edge $e_{i}$ in the graph.111In the
paper we allow the posted price $p_{i}$ to be $\infty$. It means that the
price for edge $i$ is sufficiently large, such that no buyer $j$ with $i\in
Q_{j}$ can afford her demand path. The buyers then arrive one-by-one in some
order $\sigma$. When each buyer $j$ arrives, if any edge in her demand set
$Q_{j}$ is unavailable (taken by previous buyers), then she gets anything and
pays 0. Otherwise, she compares her value $v_{j}$ with the total price
$p(Q_{j})=\sum_{i\in Q_{j}}p_{i}$:

  1. 1.

If $p(Q_{j})<v_{j}$, she takes all edges in $Q_{j}$ by paying $p(Q_{j})$;
edges in $Q_{j}$ then become unavailable;

  2. 2.

If $p(Q_{j})>v_{j}$, she takes nothing and pays $0$;

  3. 3.

If $p(Q_{j})=v_{j}$, then whether she takes all edges in $Q_{j}$ at price
$p(Q_{j})$ depends on the specification about tie-breaking.

We consider the following two different settings of tie-breaking. We say that
the seller has the _tie-breaking power_ , if the item pricing mechanism is
also associated with a tie-breaking rule. Specifically, whenever
$p(Q_{j})=v_{j}$ happens for some buyer $j$, the mechanism decides whether the
buyer takes the edges or not, according to the tie-breaking rule. Given any
price vector $p=\\{p_{i}\\}_{i\in[m]}$ and arrival order $\sigma$, we denote
by $\mathsf{Wel}(\mathcal{Q},v;p,\sigma)$ the maximum welfare achieved by the
mechanism among all tie-breaking rules. In the other setting, where the seller
does not have the tie-breaking power, whenever $p(S_{j})=v_{j}$ happens for
some buyer $j$, the buyer herself can decide whether she takes the edges or
not. For every price vector $p$ and arrival order $\sigma$, we denote by
$\mathsf{Wel}_{\mathsf{NT}}(\mathcal{Q},v;p,\sigma)$ the worst-case (minimum)
welfare achieved by the mechanism, over all tie-breaking decisions made by the
buyers.

For any graph $G$, an instance in this problem can be represented as a tuple
$\mathcal{F}=(\mathcal{Q},v)=(\\{Q_{j}\\}_{j\in[n]},\\{v_{j}\\}_{j\in[n]})$
that we refer to as a _buyer profile_. An _allocation_ of the items to the
buyers is a vector $y\in\left\\{0,1\right\\}^{m}$, such that for each item
$i\in[m]$, $\sum_{j\in[n],i\in Q_{j}}y_{j}\leq 1$. Namely, for every $j$,
$y_{j}=1$ if and only if buyer $j$ takes her demand set $Q_{j}$. The welfare
of an allocation $y$ is therefore $\sum_{j\in[n]}v_{j}y_{j}$. We denote by
$\mathsf{OPT}(G,\mathcal{F})$ the optimal welfare over all allocations, and
use $\mathsf{OPT}$ for short when the instance is clear from the context.

Given any item pricing mechanism, we define the _competitive ratio_ as the
ratio of the following two quantities: (i) the hindsight optimal welfare,
which is the total value of the buyers in the optimal offline allocation; and
(ii) the maximum among all choices of prices, of the worst-case welfare when
the buyers’ arrival order $\sigma$ is adversarial. Formally, for any instance
$\mathcal{F}=(\mathcal{Q},v)$,

$\ratio(\mathcal{F})=\frac{\mathsf{OPT}(G,\mathcal{F})}{\max_{p}\min_{\sigma}\mathsf{Wel}(\mathcal{Q},v;p,\sigma)}.$

In the paper, we analyze the competitive ratio when $G$ has different special
structures. For ease of notation, for any graph $G$, denote $\ratio(G)$ the
largest competitive ratio $\ratio(\mathcal{F})$ for any instance $\mathcal{F}$
with underlying graph $G$. And given a graph family $\mathcal{G}$, we denote
$\ratio(\mathcal{G})=\max_{G\in\mathcal{G}}\ratio(G)$. For instance,
$\ratio(\mathsf{Tree})$ represents the worst competitive ratio among all
trees. For the case when the seller has no tie-breaking power, we define
$\textnormal{{gap}}_{\textnormal{{NT}}}(\mathcal{Q},v)$,
$\textnormal{{gap}}_{\textnormal{{NT}}}(G)$ and
$\textnormal{{gap}}_{\textnormal{{NT}}}(\mathcal{G})$ similarly.

##  3 Competitive Ratio for Special Graphs

In this section, we first analyze the competitive ratio when the underlying
graph $G$ has special structures. Throughout this section, we assume that the
seller has tie-breaking power. In Section 5, we consider the case where the
seller does not have tie-breaking power.

Given any instance $\mathcal{F}$, the hindsight optimal welfare is captured by
an integer program. The relaxed linear program (LP-Primal) is shown in
Equation (1) in Section 1.1. Its dual (LP-Dual) is shown in Equation (2). We
denote $\mathsf{OPT}_{\mathsf{LP}}(\mathcal{Q},v)$ (or
$\mathsf{OPT}_{\mathsf{LP}}$ if the instance is clear from context) the
optimum of (LP-Primal). Clearly,
$\mathsf{OPT}_{\mathsf{LP}}(\mathcal{Q},v)\geq\mathsf{OPT}(\mathcal{Q},v)$. We
first present a lemma that is useful throughout this section. The lemma shows
that for any feasible integral solution achieved by rounding from the optimal
fractional solution, we are able to compute prices to guarantee selling to the
exact same set of buyers.

######  Lemma 3.1.

Let $y^{*}$ be any optimal solution of (LP-Primal) and let
$y^{\prime}\in\left\\{0,1\right\\}^{n}$ be any feasible integral solution of
(LP-Primal), such that for each $j\in[n]$, $y^{\prime}_{j}=0$ if
$y_{j}^{*}=0$. Then there exists a price vector
$p=\left\\{p_{i}\right\\}_{i\in[m]}$ that achieves worst-case welfare
$\sum_{j\in[n]}v_{j}\cdot y_{j}^{\prime}$, if the seller has the power of tie-
breaking. Moreover, the price vector $p$ can be computed efficiently.

###### Proof.

Let $p^{*}=\\{p^{*}_{i}\\}_{i\in[m]}$ be any optimal solution for (LP-Dual).
We will show that, for any buyers’ arrival order $\sigma$, with a proper tie-
breaking rule, we can ensure with the prices $p^{*}$ that the outcome of the
selling process is $y^{\prime}$, and therefore it achieves welfare
$\sum_{j\in[n]}v_{j}\cdot y_{j}^{\prime}$.

Consider now a buyer $j$. Assume first that $y_{j}^{\prime}=0$, from the
constraint of (LP-Dual), $\sum_{i\in Q_{j}}p^{*}_{i}\geq v_{j}$. If
$\sum_{i\in Q_{j}}p^{*}_{i}>v_{j}$, then the buyer $j$ cannot afford her
demand set. If $\sum_{i\in Q_{j}}p^{*}_{i}=v_{j}$, since the seller has the
power of tie-breaking, the seller can choose not to give the demand set to
her. Assume now that $y_{j}^{\prime}=1$, so $y_{j}^{*}>0$. From the
complementary slackness, $\sum_{i\in Q_{j}}p^{*}_{i}=v_{j}$. The seller can
sell the demand set $Q_{j}$ to buyer $j$. Since $y^{\prime}$ is a feasible
solution of (LP-Primal), no items will be given to more than one buyer.
Moreover, it is easy to verify that the above tie-breaking rule ensures that
this selling process’s outcome is exactly $y^{\prime}$, for any buyers’
arrival order $\sigma$. Therefore, the worst-case welfare is
$\sum_{j\in[n]}v_{j}\cdot y_{j}^{\prime}$. The set of prices $p^{*}$ can be
computed in polynomial time by solving the (LP-Dual). ∎

An immediate corollary of Lemma 3.1 is for the highway problem, i.e. $G$ is a
single path. In this case, there is always an integral optimal solution for
(LP-Primal) [12, 47]. Thus by Lemma 3.1, there exist prices that achieve
worst-case welfare the same as optimal welfare.

######  Theorem 3.1 ([12, 7]).

$\emph{\ratio}(\mathsf{Path})=1$.

In the rest of this section, we consider different graph classes $\mathcal{G}$
and bound $\ratio(\mathcal{G})$.

###  3.1 Stars and Spiders

We first consider the case where the underlying graph $G$ is a star or a
spider graph. A _spider_ $G$ is a tree with one vertex $u$ of degree at least
3 and all others with degree at most 2. In other words, $E(G)$ can be
decomposed into $k$ paths, where any two paths only intersect at $u$. Star is
a special spider graph, where all vertices other than $u$ has degree 1. See
Figure 2 for an example.

(a) A star.

(b) A spider.

Figure 2: An illustration of stars and spiders.

As a warm-up, we first prove that the competitive ratio of any star graph is
at most $3/2$. For star graphs, let $E(G)=\\{e_{1},\ldots,e_{m}\\}$.

######  Theorem 3.2.

$\emph{\ratio}(\mathsf{Star})\leq 3/2$. Moreover, the set of prices that
achieves the competitive ratio $3/2$ can be computed efficiently.

Here is our plan for the proof: We round the optimal solution of (LP-Primal)
to get a feasible integral solution with a total value of at least
$2/3\cdot\mathsf{OPT}$, and then apply Lemma 3.1. One crucial lemma we use
here is that, if the input graph is a star, then (LP-Primal) contains a half-
integral optimal solution, i.e. an vector in $\\{0,\frac{1}{2},1\\}^{n}$ that
achieves the optimal objective value. This lemma was also proved in [43]. For
completeness, we include a proof of Lemma 3.2 in Appendix A.1.

######  Lemma 3.2.

[43] If $G$ is a star graph, then (LP-Primal) is half-integral, and for each
optimal solution $y^{*}\in\left\\{0,\frac{1}{2},1\right\\}^{n}$, if we denote
$J^{*}=\left\\{j\mid y^{*}_{j}=\frac{1}{2}\right\\}$ and define the graph $H$
as $V(H)=\left\\{u_{i}\mid e_{i}\in\bigcup_{j\in J^{*}}Q_{j}\right\\}$ and
$E(H)=\left\\{(u_{i},u_{i^{\prime}})\mid\exists j\in
J^{*},Q_{j}=\\{e_{i},e_{i^{\prime}}\\}\right\\}$, then $H$ is the union of
vertex-disjoint odd-length cycles.

Proof of Theorem 3.2: Without loss of generality, we assume that for every
$i,i^{\prime}\in[m]$, at most one buyer has demand path
$\\{e_{i},e_{i^{\prime}}\\}$, otherwise we only keep the buyer with the
largest value. Let $y^{*}$ be the optimal solution of (LP-Primal). Let
$\mathcal{B}^{0}$ ($\mathcal{B}^{1},\mathcal{B}^{1/2}$, resp.) be the set of
all buyer $j$ with $y_{j}^{*}=0$ ($1,\frac{1}{2}$, resp.). For buyers in
$\mathcal{B}^{1/2}$, define the graph $H$ as $V(H)=\left\\{u_{i}\mid
e_{i}\in\bigcup_{j\in\mathcal{B}^{1/2}}Q_{j}\right\\}$ and
$E(H)=\left\\{(u_{i},u_{i^{\prime}})\mid\exists
j\in\mathcal{B}^{1/2},Q_{j}=\\{e_{i},e_{i^{\prime}}\\}\right\\}$, then from
Lemma 3.2, $H$ is the union of vertex-disjoint odd-length cycles. It’s easy to
verify that the edge set of every cycle can be partitioned into three subsets,
such that the edges in each subset are vertex-disjoint. Therefore, the edges
of $H$ can be partitioned into three subsets $E(H)=E_{1}\cup E_{2}\cup E_{3}$,
such that the edges in set $E_{w}$ do not share vertices, for each
$w\in\left\\{1,2,3\right\\}$. Note that each edge of $H$ corresponds to the
demand path $Q_{j}$ of a unique buyer $j\in\mathcal{B}^{1/2}$. For simplicity
we denote $\hat{e}_{j}$ the edge of $H$ matched to buyer $j$. Without loss of
generality, assume $\sum_{j:\hat{e}_{j}\in
E_{1}}\geq\frac{1}{3}\cdot\sum_{j\in\mathcal{B}^{1/2}}v_{j}$. We construct a
feasible integral solution $y$ as follows. For every $j\in\mathcal{B}^{1}$,
let $y_{j}=y_{j}^{*}=1$; For every $j\in\mathcal{B}^{1/2}$ such that
$\hat{e}_{j}\in E_{1}$, let $y_{j}=1$; For other $j$, let $y_{j}=0$. Note that
the fact that edges in $E_{1}$ is node-disjoint implies that demand paths
$\\{Q_{j}\mid\hat{e}_{j}\in E_{1}\\}$ are edge-disjoint. Also, since $y^{*}$
is feasible, it’s clear that the demand path for buyer $j\in\mathcal{B}^{1}$
does not intersect with the demand path for $j\in\mathcal{B}^{1/2}$. Thus $y$
is feasible.

To finish the proof, we notice that

$\sum_{j:y_{j}=1}v_{j}\geq\sum_{j\in\mathcal{B}^{1}}v_{j}+\frac{1}{3}\cdot\sum_{j\in\mathcal{B}^{1/2}}v_{j}\geq\frac{2}{3}\cdot\left(\sum_{B_{j}\in\mathcal{B}^{1}}v_{j}+\frac{1}{2}\cdot\sum_{j\in\mathcal{B}^{1/2}}v_{j}\right)=\frac{2}{3}\cdot\mathsf{OPT}_{\mathsf{LP}}\geq\frac{2}{3}\mathsf{OPT}.$

Applying Lemma 3.1 finishes the proof. $\Box$

We prove in the following theorem that the $3/2$ competitive ratio is tight
for star graphs.

######  Theorem 3.3.

For any $\varepsilon>0$, $\emph{\ratio}(\mathsf{Star})>3/2-\varepsilon$.

###### Proof.

Consider a star graph with four edges $e_{1},e_{2},e_{3},e_{4}$. The instance
$\mathcal{F}$ is described as follows:

  * •

Buyer 1 demands the path $Q_{1}$ consisting of edges $e_{1},e_{2}$, with value
$v_{1}=1$;

  * •

Buyer 2 demands the path $Q_{2}$ consisting of edges $e_{1},e_{3}$, with value
$v_{2}=2+\varepsilon$;

  * •

Buyer 3 demands the path $Q_{3}$ consisting of edges $e_{1},e_{4}$, with value
$v_{3}=2+\varepsilon$;

  * •

Buyer 4 demands the path $Q_{4}$ consisting of edges $e_{3},e_{4}$, with value
$v_{4}=2$.

It is clear that the optimal allocation is assigning the edges $e_{1},e_{2}$
to buyer 1, and assigning the edges $e_{3},e_{4}$ to buyer 4. The optimal
welfare is $\mathsf{OPT}(G,\mathcal{F})=3$. However, we will show that any set
of prices on the edges achieve the worst-case welfare at most $2+\varepsilon$.
Then $\ratio(\text{Star})\geq\frac{3}{2+\varepsilon}>\frac{3}{2}-\varepsilon$.

Let $\left\\{p_{i}\right\\}_{1\leq i\leq 4}$ be any set of prices. If
$p(Q_{1})>1$, then buyer 1 cannot afford her demand path $Q_{1}$. Since each
pair of paths in $Q_{2},Q_{3},Q_{4}$ shares an edge, at most one of buyers
$2,3,4$ may get her demand path, so the welfare is at most $2+\varepsilon$. If
$p(Q_{4})>2$, then via similar arguments we can show that the welfare is at
most $2+\varepsilon$. Consider now the case where $p(Q_{1})=p_{1}+p_{2}\leq 1$
and $p(Q_{4})=p_{3}+p_{4}\leq 2$. We have $p_{1}\leq 1$, and one of
$p_{3},p_{4}$ is at most $1$. Assume w.l.o.g. that $p_{3}\leq 1$. We let buyer
3 comes first. Note that $p(Q_{3})=p_{1}+p_{3}\leq 2<2+\varepsilon$.
Therefore, buyer 3 will get her demand path, and later on no other buyer may
get her path. Altogether, the worst-case welfare for any set of prices is at
most $2+\varepsilon$. This completes the proof of Theorem 3.3. ∎

Now we come to spider graphs. We prove that the competitive ratio is at most
$3/2$ for any spider graph. Note that the ratio is tight according to Theorem
3.3.

######  Theorem 3.4.

$\emph{\ratio}(\mathsf{Spider})\leq 3/2$. Moreover, the set of prices that
achieves the competitive ratio $3/2$ can be computed efficiently.

Similar to the proof of Theorem 3.2, we prove in the following lemma that (LP-
Primal) has a half-integral optimal solution. The proof uses Lemma 3.2 and is
postponed to Appendix A.1.

######  Lemma 3.3.

If $G$ is a spider graph, then (LP-Primal) has a half-integral optimal
solution. Moreover, such a solution can be computed efficiently.

Proof of Theorem 3.4: Let $y^{*}$ be a half-integral optimal solution of (LP-
Primal) given by Lemma 3.3. Denote $\mathcal{B}^{1/2}=\left\\{j\mid
y^{*}_{j}=1/2\right\\}$ and $\mathcal{B}^{1}=\left\\{j\mid
y^{*}_{j}=1\right\\}$. Since $y^{*}$ is feasible, paths $\left\\{Q_{j}\mid
j\in\mathcal{B}^{1}\right\\}$ are edge-disjoint, and they do not share the
same edge with paths $\left\\{Q_{j}\mid j\in\mathcal{B}^{1/2}\right\\}$. We
will show that we can efficiently compute a subset
$\mathcal{B}^{\prime}\subseteq\mathcal{B}^{1/2}$, such that (i) the paths
$\left\\{Q_{j}\mid j\in\mathcal{B}^{\prime}\right\\}$ are edge-disjoint; and
(ii) the total value of paths in $\left\\{Q_{j}\mid
j\in\mathcal{B}^{\prime}\right\\}$ is at least
$\frac{1}{3}\cdot\sum_{j\in\mathcal{B}^{1/2}}v_{j}$. If so, we let
$y_{j}=\mathbf{1}[j\in\mathcal{B}^{1}\cup\mathcal{B}^{\prime}]$. Then
$y=\\{y_{j}\\}_{j\in[n]}$ is a feasible integral solution of (LP-Primal).
Moreover,

$\sum_{j:y_{j}=1}v_{j}\geq\sum_{j\in\mathcal{B}^{1}}v_{j}+\frac{1}{3}\cdot\sum_{j\in\mathcal{B}^{1/2}}v_{j}\geq\frac{2}{3}\cdot\left(\sum_{B_{j}\in\mathcal{B}^{1}}v_{j}+\frac{1}{2}\cdot\sum_{j\in\mathcal{B}^{1/2}}v_{j}\right)=\frac{2}{3}\cdot\mathsf{OPT}_{\mathsf{LP}}\geq\frac{2}{3}\mathsf{OPT}.$

Thus applying Lemma 3.1 finishes the proof.

To find a subset $\mathcal{B}^{\prime}$ that satisfies both properties, we
prove the following structural lemma for trees. The proof of the lemma is
postponed to Appendix A.1.

######  Lemma 3.4.

Let $T$ be a tree, let $d\geq 2$ be an integer and let $\mathcal{Q}$ be a set
of paths in $T$, such that every edge of $T$ appears in at most $d$ paths of
$\mathcal{Q}$, then we can efficiently compute a partition of $\mathcal{Q}$
into $d+1$ subsets $\mathcal{Q}_{1},\ldots,\mathcal{Q}_{d+1}$, such that for
every $1\leq i\leq d+1$, paths in $\mathcal{Q}_{i}$ are edge-disjoint.

Now since $y^{*}$ is a feasible solution of (LP-Primal), $y^{*}_{j}=1/2$ for
each $j\in\mathcal{B}^{1/2}$. Thus every edge of $G$ is contained in at most
$2$ paths in $\mathcal{Q}=\\{Q_{j}\mid j\in\mathcal{B}^{1/2}\\}$. By Lemma
3.3, we can efficiently obtain a partition
$(\mathcal{Q}_{1},\mathcal{Q}_{2},\mathcal{Q}_{3})$ of $\mathcal{Q}$, such
that for each $1\leq i\leq 3$, paths in $\mathcal{Q}_{i}$ are edge-disjoint.
Therefore, at least one of sets
$\mathcal{Q}_{1},\mathcal{Q}_{2},\mathcal{Q}_{3}$ contains edge-disjoint paths
of total value at least $\frac{1}{3}\sum_{j\in\mathcal{B}^{1/2}}v_{j}$. This
completes the proof of Theorem 3.4. $\Box$

###  3.2 Trees

Now we consider trees. In this section we prove that the competitive ratio of
any tree graph is at most 3.

######  Theorem 3.5.

$\emph{\ratio}(\mathsf{Tree})\leq 3$. Moreover, the prices that achieve the
competitive ratio 3 can be computed efficiently.

The remainder of this section is dedicated to the proof of Theorem 3.5. In
Section 3.1, we prove that when $G$ is a spider (and star), there exists a
half-integral optimal solution for (LP-Primal). This is necessary to achieve a
feasible allocation through rounding, whose total welfare is at least
$2/3\cdot\mathsf{OPT}$. However, this does not hold for general tree graphs.
In fact, we show in Lemma 3.5 that, for trees, the optimal solution for (LP-
Primal) may contain a positive value with an arbitrarily large denominator.

######  Lemma 3.5.

For any integer $d>0$, there exists a tree $G$ and an instance $\mathcal{F}$,
such that every coordinate of the unique optimal solution of (LP-Primal) is
either $1/d$ or $(d-1)/d$.

###### Proof.

We construct a tree $G$ as follows. The vertex set is
$V(G)=\left\\{u_{i},v_{i}\mid 0\leq i\leq 2d\right\\}$. The edge set is
$E(G)=\left\\{u_{0},v_{0}\right\\}\cup\left\\{(u_{i},u_{0}),(v_{i},v_{0})\mid
1\leq i\leq 2d\right\\}$. Consider the following instance $\mathcal{F}$: It
contains (i) for each $1\leq j\leq 2d$, a buyer $B_{j}$ that demands the path
$Q_{j}=(u_{j},u_{0},v_{0},v_{j})$ with value $3$; (ii) for each $1\leq k\leq
d$, a buyer $B^{u}_{k}$ that demands the path
$Q^{u}_{k}=(u_{2k-1},u_{0},u_{2k})$ with value $2$; and (iii) for each $1\leq
k\leq d$, a buyer $B^{v}_{k}$ that demands the path
$Q^{v}_{k}=(v_{2k},v_{0},v_{2k+1})$ with value $2$. See Figure 3 for an
illustration. It is not hard to see that $G$ is a tree, and in the unique
optimal solution $y$ of (LP-Primal), for each path $Q_{j}$, $y_{j}=1/d$; and
for each path $Q^{u}_{k}$ and each path $Q^{v}_{k^{\prime}}$,
$y_{u,k}=y_{v,k^{\prime}}=(d-1)/d$.

Figure 3: An illustration of graph $G$, where paths of
$\left\\{Q_{1},\ldots,Q_{2d}\right\\}$ are shown in orange, and paths of
$\left\\{Q^{u}_{1},\ldots,Q^{u}_{k}\right\\}\cup\left\\{Q^{v}_{1},\ldots,Q^{v}_{k}\right\\}$
are shown in purple.

∎

To prove Theorem 3.5, we use a different approach from Section 3.1. We prove
the following structural lemma, which partitions a set of edge-disjoint paths
into two sets, such that each set of paths forms a union of vertex-disjoint
spider graphs. And then we apply Theorem 3.4 to get the desired set of prices.

######  Lemma 3.6.

Let $P_{1},\ldots,P_{n}$ be edge-disjoint paths, such that the graph
$G=\bigcup_{j\in[n]}P_{j}$ is a tree, then the set
$\mathcal{P}=\left\\{P_{1},\ldots,P_{n}\right\\}$ can be partitioned into two
sets $\mathcal{P}=\mathcal{P}^{\prime}\cup\mathcal{P}^{\prime\prime}$, such
that both the graph induced by paths in $\mathcal{P}^{\prime}$ and the graph
induced by paths in $\mathcal{P}^{\prime\prime}$ are the union of vertex-
disjoint spiders.

###### Proof.

We choose arbitrarily a vertex $r\in V(G)$ as designate it as the root of the
tree. We iteratively construct a sequence of subsets of $\mathcal{P}$ as
follows. We first let $\mathcal{P}_{1}$ contains all paths of $\mathcal{P}$
that contains the vertex $r$. Then for each $i>1$, as long as
$\mathcal{P}\neq\bigcup_{1\leq t\leq i-1}\mathcal{P}_{t}$, we let
$\mathcal{P}_{i}$ contains all paths in
$\mathcal{P}\setminus\left(\bigcup_{1\leq t\leq i-1}\mathcal{P}_{t}\right)$
that shares a vertex with a path in $\mathcal{P}_{i-1}$. We continue this
process until all paths of $\mathcal{P}$ are included in sets
$\mathcal{P}_{1},\ldots,\mathcal{P}_{k}$ for some $k$. See Figure 4 for an
illustration. We then let $\mathcal{P}^{\prime}=\bigcup_{0\leq
t\leq\lfloor{k/2}\rfloor}\mathcal{P}_{2t+1}$ and
$\mathcal{P}^{\prime\prime}=\bigcup_{1\leq
t\leq\lfloor{k/2}\rfloor}\mathcal{P}_{2t}$. This completes the construction of
the sets $\mathcal{P}^{\prime},\mathcal{P}^{\prime\prime}$. Clearly, sets
$\mathcal{P}^{\prime}$ and $\mathcal{P}^{\prime\prime}$ partition
$\mathcal{P}$.

(a) The graph $G$. Paths are shown in distinct colors.

(b) The paths in $\mathcal{P}_{1}$ are shown in dash lines.

(c) The paths in $\mathcal{P}_{2}$ are shown in dash lines.

(d) The paths in $\mathcal{P}_{3}$ are shown in dash lines.

Figure 4: An illustration of decomposing paths into subsets
$\mathcal{P}_{1},\mathcal{P}_{2},\mathcal{P}_{3}$.

It remains to show that the graph induced by the paths in
$\mathcal{P}^{\prime}$ is the union of vertex-disjoint spiders. The proof for
$\mathcal{P}^{\prime\prime}$ is similar. First, for $0\leq
t<t^{\prime}\leq\lfloor{k/2}\rfloor$, we show that the paths in
$\mathcal{P}_{2t+1}$ are vertex-disjoint from the paths in
$\mathcal{P}_{2t^{\prime}+1}$. Assume for contradiction that this is false,
and let $P\in\mathcal{P}_{2t+1},P^{\prime}\in\mathcal{P}_{2t^{\prime}+1}$ be a
pair of paths that share a common vertex. However, according to the process of
constructing the sets $\mathcal{P}_{1},\ldots,\mathcal{P}_{k}$, if $P$ is
included in $\mathcal{P}_{2t+1}$ while $P^{\prime}$ is not included in any set
of $\mathcal{P}_{1},\ldots,\mathcal{P}_{2t+1}$, since $P^{\prime}$ shares a
vertex with $P^{\prime}$, $P^{\prime}$ should be included in the set
$\mathcal{P}_{2t+2}$ rather than $\mathcal{P}_{2t^{\prime}+1}$, a
contradiction. We then show that, for each $0\leq t\leq\lfloor{k/2}\rfloor$,
the paths in $\mathcal{P}_{2t+1}$ form disjoint spiders. Clearly the paths in
$\mathcal{P}_{1}$ form a spider, since they are edge-disjoint paths that share
only the root $r$ of tree $G$. Consider now some $t\geq 1$. Let $v,v^{\prime}$
be any two distinct vertices of $V(\mathcal{P}_{2t})\cap
V(\mathcal{P}_{2t+1})$. We denote by $\mathcal{P}_{2t+1}(v)$
($\mathcal{P}_{2t+1}(v^{\prime})$, resp.) the subset of paths in
$\mathcal{P}_{2t+1}$ that contains the vertex $v$ ($v^{\prime}$, resp.). We
claim that the paths in $\mathcal{P}_{2t+1}(v)$ are vertex-disjoint from the
paths in $\mathcal{P}_{2t+1}(v^{\prime})$. Note that, if the claim is true,
since the paths in $\mathcal{P}_{2t+1}(v)$ only shares a single node $v$ (as
otherwise there is a cycle caused by some pair of paths in
$\mathcal{P}_{2t+1}(v)$, a contradiction to the fact that graph
$G=\bigcup_{j\in[n]}P_{i}$ is a tree), it follows that the paths in
$\mathcal{P}_{2t+1}(v)$ form a spider, and altogether, the paths in
$\mathcal{P}^{\prime}$ form vertex-disjoint spiders.

It remains to prove the claim. Assume that this is false. Let
$P_{2t+1}\in\mathcal{P}_{2t+1}(v),P^{\prime}_{2t+1}\in\mathcal{P}_{2t+1}(v^{\prime})$
be a pair of paths that shares a common vertex $u$, with $u\neq v,v^{\prime}$.
Note that, from our process of constructing the sets
$\mathcal{P}_{1},\ldots,\mathcal{P}_{k}$, there are two sequences of paths
$P_{1},P_{2},\ldots,P_{2t}$ and
$P^{\prime}_{1},P^{\prime}_{2},\ldots,P^{\prime}_{2t}$, such that (i) for each
$1\leq s\leq 2t$, $P_{s},P^{\prime}_{s}\in\mathcal{P}_{s}$; (ii) for each
$1\leq s\leq 2t$, $P_{s}$ shares a vertex with $P_{s+1}$, and $P^{\prime}_{s}$
shares a vertex with $P^{\prime}_{s+1}$. Since $P_{1}$ and $P^{\prime}_{1}$
shares the root $r$ of tree $G$, it follows that the graph consisting of paths
in $\left\\{P_{s},P^{\prime}_{s}\mid 1\leq s\leq 2t+1\right\\}$ contains a
cycle, a contradiction to the fact that $G$ is a tree. ∎

Proof of Theorem 3.5: Let $\mathcal{Q}^{*}$ be the subset of
$\left\\{Q_{1},\ldots,Q_{n}\right\\}$ that, over all subsets of edge-disjoint
paths in $\left\\{Q_{1},\ldots,Q_{n}\right\\}$, maximizes its total value,
namely $\mathsf{OPT}(G,\mathcal{F})=\sum_{Q_{j}\in\mathcal{Q}^{*}}v_{j}$.
Clearly, graph $G^{*}=\bigcup_{Q\in\mathcal{Q}^{*}}Q$ is the union of a number
of disjoint trees. We further partition $\mathcal{Q}^{*}=\bigcup_{1\leq t\leq
k}\mathcal{Q}^{*}_{t}$, such that the union of paths in each
$\mathcal{Q}^{*}_{t}$ forms a connected component of $G^{*}$, and is therefore
a tree (a subtree of $G$). We then apply Lemma 3.6 to each set
$\mathcal{Q}^{*}_{t}$. Assume the partition for $\mathcal{Q}^{*}_{t}$ is
$\mathcal{Q}^{(1)}_{t}\cup\mathcal{Q}^{(2)}_{t}$ such that
$\sum_{Q_{j}\in\mathcal{Q}^{(1)}_{t}}v_{j}\geq\sum_{Q_{j}\in\mathcal{Q}^{(2)}_{t}}v_{j}$.
Denote $\hat{\mathcal{Q}}^{*}=\bigcup_{1\leq t\leq k}\mathcal{Q}^{(1)}_{t}$.
Then clearly $\hat{G}^{*}=\bigcup_{Q\in\hat{\mathcal{Q}}^{*}}Q$ is the union
of disjoint spiders and
$\sum_{Q_{j}\in\hat{\mathcal{Q}}^{*}}v_{j}\geq\frac{1}{2}\mathsf{OPT}(G,\mathcal{F})$.
Thus by Theorem 3.4, there exists a set of prices $p$ that achieves worst-case
welfare at least $\frac{1}{3}\mathsf{OPT}(G,\mathcal{F})$.

It remains to show that such a price vector $p$ can be computed efficiently.
Firstly, computing the hindsight optimal solution $\mathcal{Q}^{*}$ is
equivalent to computing the maximum weight edge-disjoint paths in a tree, for
which a polynomial-time algorithm exists [49]. According to the proof of Lemma
3.6, partitioning $\mathcal{Q}^{*}$ clearly takes polynomial time. Thus the
price vector can be computed efficiently by Theorem 3.4 that the corresponding
set of prices can be computed efficiently in spider graphs. $\Box$

###  3.3 Cycles

Now we consider the case where $G$ is a cycle. We denote
$V(G)=\left\\{u_{1},\ldots,u_{m}\right\\}$, where the vertices appear on the
cycle in this order. Therefore, $E(G)=\\{(u_{i},u_{i+1})\mid 1\leq i\leq m\\}$
(here $u_{m+1}=u_{1}$). For every pair $a,b$ of distinct integers in
$\left\\{1,\ldots,m\right\\}$, we denote by $P_{a,b}$ the path
$(u_{a},u_{a+1},\ldots,u_{b})$.

######  Theorem 3.6.

$\emph{\ratio}(\mathsf{Cycle})\leq 2$. Moreover, the prices that achieve the
competitive ratio 2 can be computed efficiently.

###### Proof.

Let $\mathcal{Q}^{*}\subseteq\left\\{Q_{1},\ldots,Q_{n}\right\\}$ be the set
of edge-disjoint paths that achieves the optimal welfare, namely
$\mathsf{OPT}(G,\mathcal{F})=\sum_{Q_{j}\in\mathcal{Q}^{*}}v_{j}$. We
distinguish between the following two cases.

Case 1. $|\mathcal{Q}^{*}|=1$. Assume without loss of generality that
$\mathcal{Q}^{*}=\left\\{Q_{1}\right\\}=\left\\{P_{a,b}\right\\}$. We first
set the prices for all edges of $G\setminus P_{a,b}$ to be $+\infty$. Consider
now the instance $(G^{\prime},\mathcal{F}^{\prime})$, where
$G^{\prime}=P_{a,b}$ and
$\mathcal{F}^{\prime}=\left\\{(Q_{i},v_{i})\in\mathcal{F}\mid Q_{i}\subseteq
P_{a,b}\right\\}$. Clearly,
$\mathsf{OPT}(G,\mathcal{F})=\mathsf{OPT}(G^{\prime},\mathcal{F}^{\prime})=v_{1}$.
Since $G^{\prime}$ is a path, from Theorem 3.1, there exist prices
$\left\\{p^{\prime}_{i}\right\\}_{i\in P_{a,b}}$ on edges of $P_{a,b}$ that
achieves the worst-case welfare
$\mathsf{OPT}(G^{\prime},\mathcal{F}^{\prime})$. We now set
$p_{i}=p^{\prime}_{i}$ for each $i\in P_{a,b}$. It is easy to verify that
prices $\left\\{p_{i}\right\\}_{i\in[m]}$ achieve the worst-case welfare
$\mathsf{OPT}(G,\mathcal{F})$.

Case 2. $|\mathcal{Q}^{*}|\geq 2$. Assume without loss of generality that
$\mathcal{Q}^{*}=\left\\{Q_{1},\ldots,Q_{k}\right\\}$, with
$v_{1}\leq\ldots\leq v_{k}$. If $E(G)\neq\bigcup_{1\leq j\leq k}E(Q_{j})$,
then we set $p_{i}=+\infty$ for all edges of $E(G)\setminus\bigcup_{1\leq
j\leq k}E(Q_{j})$ and consider the instance
$(G^{\prime},\mathcal{F}^{\prime})$, where $G^{\prime}=\bigcup_{1\leq j\leq
k}Q_{j}$ and $\mathcal{F}^{\prime}=\left\\{(Q_{j},v_{j})\in\mathcal{F}\mid
Q_{j}\subseteq G^{\prime}\right\\}$. Clearly,
$\mathsf{OPT}(G,\mathcal{F})=\mathsf{OPT}(G^{\prime},\mathcal{F}^{\prime})=\sum_{1\leq
i\leq k}v_{i}$ and $G^{\prime}$ is the union of a set of vertex-disjoint
paths. Again by Theorem 3.1, there exist $\left\\{p_{i}\right\\}_{i\in E(G)}$
achieves the worst-case welfare $\mathsf{OPT}(G,\mathcal{F})$. Now suppose
$E(G)=\bigcup_{1\leq i\leq k}E(Q_{i})$, i.e. $Q^{*}$ covers the whole cycle.
We set $p_{i}=+\infty$ for all edges of $Q_{1}$ and consider the instance
$(G^{\prime},\mathcal{F}^{\prime})$, where $G^{\prime}=\bigcup_{2\leq j\leq
k}Q_{j}$ and $\mathcal{F}^{\prime}=\left\\{(Q_{j},v_{j})\in\mathcal{F}\mid
Q_{j}\subseteq G^{\prime}\right\\}$. Clearly, since $v_{1}$ is the smallest
among all $v_{j}$s, $\mathsf{OPT}(G^{\prime},\mathcal{F}^{\prime})=\sum_{2\leq
j\leq k}v_{j}\geq\mathsf{OPT}(G,\mathcal{F})/2$ and $G^{\prime}$ is a line
graph. By Theorem 3.1, there exist prices $\left\\{p_{i}\right\\}_{i\in[m]}$
that achieve the worst-case welfare $\mathsf{OPT}(G,\mathcal{F})/2$. ∎

To complement Theorem 3.6, we show in the following theorem that the
competitive ratio $1/2$ for cycles is tight.

######  Theorem 3.7.

For any $\epsilon>0$, $\emph{\ratio}(\mathsf{Cycle})>2-\epsilon$.

###### Proof.

For any $\epsilon>0$, we construct an instance $(G,\mathcal{F})$ such that no
set of prices can achieve worst-case welfare at least
$\frac{1}{2-\epsilon}\cdot\mathsf{OPT}(G,\mathcal{F})$, when the seller has
the tie-breaking power. We set integers $m=10\cdot\lceil 1/\epsilon\rceil$ and
$k=m/2+1$. The instance $(G,\mathcal{F})$ is defined as follows. $G$ is a
cycle with $m$ vertices. $\mathcal{F}=\left\\{(Q_{j},v_{j})\mid 1\leq j\leq
m+2\right\\}$. Specifically, for each $1\leq j\leq m$, we define
$Q_{j}=P_{j,k+j}$, and we define $Q_{m+1}=P_{1,k}$ and $Q_{m+2}=P_{k,1}$. See
Figure 5. For each $1\leq j\leq m$, we define the value $v_{j}=k+1$. For each
$j=m+1,m+2$, we define the value $v_{j}=k-1$.

Figure 5: An illustration of paths $Q_{1},Q_{m+1},Q_{m+2}$.

In the instance there are $m$ paths with length $m/2+1$, and 2 paths with
length $m/2$. It is clear that the optimal solution is
$\left\\{Q_{m+1},Q_{m+2}\right\\}$, so $\mathsf{OPT}(G,\mathcal{F})=m$.

We will prove that there do not exist prices that achieve worst-case welfare
strictly larger than $k+1$. Let $\\{p_{i}\\}_{i\in[m]}$ be any set of prices.
We consider two cases. Assume first that $\sum_{i\in[m]}p_{i}\geq m+1$. Since
$v_{m+1}=v_{m+2}=m/2$, at least one of buyers $m+1$ and $m+2$ cannot afford
its path. Note that any path in $\\{Q_{1},...,Q_{m}\\}$ intersects with all
other paths. Thus for any arrival order, the achieved welfare is at most
$k+1$.

Assume now that $\sum_{i\in[m]}p_{i}<m+1$. We claim that at least one of the
buyers $1,\ldots,m$ can afford her path with a strictly positive utility. It
implies that the worst-case welfare is at most $k+1$, since if such a buyer
comes first and takes her path, all other demand paths are blocked.

To prove the claim, we notice that each edge appears in exactly $k$ paths of
$\left\\{Q_{1},\ldots,Q_{m}\right\\}$, so $\sum_{1\leq j\leq
m}p(Q_{j})=k\cdot\sum_{i\in[m]}p(e)\leq k(m+1)$. On the other hand,
$\sum_{1\leq j\leq m}v_{j}=(k+1)m\geq k(m+1)$. Therefore, there exists some
$1\leq j\leq m$ such that $p(Q_{j})<v_{j}$. Thus the worst-case welfare of any
item pricing is at most $k+1<\frac{m}{2-\epsilon}$, for $m=10\cdot\lceil
1/\epsilon\rceil$. ∎

###  3.4 Outerplanar Graphs

At the end of this section, we consider outerplanar graphs. A graph $G$ is
_outerplanar_ if and only if it admits a planar drawing, in which all vertices
of $G$ lie on the boundary of the outer face. It’s a natural generalization of
trees and cycles. The main result in this subsection is the following theorem.

######  Theorem 3.8.

$\emph{\ratio}({\emph{{Outerplanar}}})=O(\log^{2}m)$.

To prove Theorem 3.8, we use the following lemma. It takes any cut $(S,T)$ of
$G$, and bounds the competitive ratio for graph $G$ by the size of the cut and
the competitive ratio for the subgraphs induced by $S$ and $T$.

######  Lemma 3.7.

Let $G$ be a graph and $(S,T)$ be a cut of $G$, then
$\emph{\ratio}(G)\leq\max\\{\emph{\ratio}(G[S]),\emph{\ratio}(G[T])\\}+|E(S,T)|$,
where $G[S]$ _(_ $G[T]$, resp._)_ is the subgraph of $G$ induced by vertices
of $S$ _(_ $T$, resp._)_.

###### Proof.

Let $\mathcal{F}=\left\\{(Q_{j},v_{j})\mid j\in[n]\right\\}$ be any instance
on graph $G$. Let $\mathcal{Q}^{*}$ be the subset of
$\left\\{Q_{1},\ldots,Q_{n}\right\\}$ that, over all subsets of edge-disjoint
paths in $\left\\{Q_{1},\ldots,Q_{n}\right\\}$, maximizes its total value,
namely $\mathsf{OPT}(G,\mathcal{F})=\sum_{Q_{j}\in\mathcal{Q}^{*}}v_{j}$. We
denote by $\mathcal{Q}^{\prime}$ the set of paths in $\mathcal{Q}^{*}$ that
contains an edge of $E(S,T)$, and we denote
$\mathcal{Q}^{\prime\prime}=\mathcal{Q}^{*}\setminus\mathcal{Q}^{\prime}$.
Since paths in $\mathcal{Q}^{*}$ are edge-disjoint,
$|\mathcal{Q}^{\prime}|\leq|E(S,T)|$.

On one hand, let $Q_{j}$ be the path in $\mathcal{Q}^{\prime}$ with the
largest value $v_{j}$, so $v_{j}\geq v(\mathcal{Q}^{\prime})/|E(S,T)|$. From
Theorem 3.1 and by setting the price for all edges of $G\setminus Q_{j}$ to be
$+\infty$, we can show that there exist prices that achieve worst-case welfare
at least $v_{j}\geq v(\mathcal{Q}^{\prime})/|E(S,T)|$, where
$v(\mathcal{Q}^{\prime})=\sum_{Q_{j}\in\mathcal{Q}^{\prime}}v_{j}$. Put in
another way,

$\frac{v(\mathcal{Q}^{\prime})}{|E(S,T)|}\geq\frac{v(\mathcal{Q}^{*})}{\ratio(G)}.$

On the other hand, note that every path of $\mathcal{Q}^{\prime\prime}$ lies
entirely in either graph $G[S]$ or graph $G[T]$. Denote by
$\mathcal{Q}^{\prime\prime}_{S}$ ($\mathcal{Q}^{\prime\prime}_{T}$, resp.) the
set of paths $\mathcal{Q}^{\prime\prime}$ that lie entirely in graph $G[S]$
($G[T]$, resp.). By setting the price of all edges of $E(S,T)$ to be
$+\infty$, and from the definition of $\ratio(G[S]),\ratio(G[T])$, we get that

$\frac{v(\mathcal{Q}^{\prime\prime}_{S})}{\ratio(G[S])}+\frac{v(\mathcal{Q}^{\prime\prime}_{T})}{\ratio(G[T])}\geq\frac{v(\mathcal{Q}^{*})}{\ratio(G)}.$

Since
$v(\mathcal{Q}^{*})=v(\mathcal{Q}^{\prime})+v(\mathcal{Q}^{\prime\prime})$, it
is easy to derive from the above inequalities that
${\ratio}(G)\leq|E(S,T)|+\max\\{{\ratio}(G[S]),{\ratio}(G[T])\\}$. ∎

The high-level plan for the proof of Theorem 3.8 is to perform a graph
decomposition and then use induction. Intuitively, we would like to compute a
cut $(S,T)$ of $G$, such that $|S|,|T|\leq 0.9m$ and $|E(S,T)|\leq O(\log m)$.
If $G$ contains such a cut, from Lemma 3.7,
$\ratio(G)\leq\max\\{\ratio(G[S]),\ratio(G[T])\\}+O(\log m)$. Since graphs
$G[S],G[T]$ contain at most $0.9m$ vertices each, it is easy to get by
induction that $\ratio(G)=O(\log^{2}m)$. If $G$ does not contain such a cut,
then we will show that graph $G$ must have the a special structure. Formally,
for any edge $e=(u,v)$, consider the two arcs on the circle with $u$ and $v$
as the endpoints. We say that $e$ is _good_ , iff both arcs contain at least
$0.1m$ vertices of $G$. We prove that, if $G$ does not contain a cut mentioned
above, then all good edges must share an common endpoint. See Figure 6(c) for
an illustration of this special structure.

Next we prove directly that $\ratio(G)=O(\log^{2}m)$ when $G$ have the above
structure. In the proof we remove edges properly (by setting the item price to
be $+\infty$) such that the new underlying graph become a spider graph, and
also the new instance still has a high enough optimal welfare. Then by
applying Theorem 3.4, we obtain the desired set of prices. Now we give the
complete proof of the Theorem.

Proof of Theorem 3.8: We will prove by induction that, for every outerplanar
graph $G$ on $m$ vertices, $\ratio(G)\leq 200\log^{2}m$. The base case where
$m=2$ is trivial. Assume that the claim is true for all outerplanar graphs on
less than $m$ vertices. Consider now any outerplanar graph $G$ on $m$
vertices. We say that a cut $(S,T)$ in $G$ is _balanced_ iff $|S|,|T|\leq
0.9m$. Assume first that $G$ contains a balanced cut $(S,T)$ of size at most
$2\log m$. Note that graphs $G[S],G[T]$ contain at most $0.9m$ vertices each.
From the induction hypothesis, $\ratio(G[S]),\ratio(G[T])\leq
200\log^{2}(0.9m)$. Therefore, from Lemma 3.7,

$\ratio(G)\leq\max\\{\ratio(G[S]),\ratio(G[T])\\}+2\log m\leq
200\log^{2}(0.9m)+2\log m<200\log^{2}m.$

We assume from now on that graph $G$ does not contain a balanced cut of size
at most $2\log m$. We fix a planar drawing of $G$, where all vertices lie on
the boundary of a disc $\mathcal{D}$, and all edges lie entirely inside
$\mathcal{D}$. Denote by $\Gamma$ the set of non-outer faces of the planar
drawing. For each face $F\in\Gamma$, the boundary $\partial(F)$ of $F$ is
defined to be the subgraph of $G$ consisting of all vertices and edges of $G$
whose images are incident to $F$. Clearly, for any pair $F_{1},F_{2}$ of faces
in $\Gamma$, $\partial(F_{1})$ and $\partial(F_{2})$ share at most one edge.
Let $e$ be an edge of $G$ and let $F\in\Gamma$ be a face that $e$ is incident
to. Note that the image of $e$, together with the boundary of $\mathcal{D}$,
decomposes $\mathcal{D}$ into two smaller discs
$\mathcal{D}^{1}_{e},\mathcal{D}^{2}_{e}$. Assume that face $F$ lies entirely
in disc $\mathcal{D}^{1}_{e}$. We define the _length of $e$ away from face
$F$_, denoted by $\ell(e,F)$, as the number of vertices in whose image lie in
disc $\mathcal{D}_{2}$ (including the endpoints of $e$) minus one. See Figure
6(a) for an example.

(a) An illustration of the length of $e$ away from $F$: $\ell(e,F)=5$.

(b) The curve connecting the interior of $F$ to the boundary of $\mathcal{D}$.

(c) An illustration of the layout of all good edges.

Figure 6: Illustrations of notions and objects in the proof of Theorem 3.8.

We prove the following lemmas.

######  Lemma 3.8.

Let $F$ be a face in $\Gamma$ and let $e$ be an edge of $\partial(F)$. Let
$\mathcal{D}^{1}_{e},\mathcal{D}^{2}_{e}$ be smaller discs formed by the image
of $e$ and the boundary of $\mathcal{D}$, where face $F$ lies entirely in disc
$\mathcal{D}^{1}_{e}$. Then there is a curve, with one endpoint lying in the
interior of $F$ and the other endpoint lying on the boundary of
$\mathcal{D}^{2}_{e}$, that intersects the image of at most $\log(\ell(e,F))$
edges of $G$. (See the red curve in Figure 6(b) for an example.)

###### Proof.

We prove by induction on the value of $\ell(e,F)$. The base case where
$\ell(e,F)=2$ is trivial. Assume the claim is true for all graphs $G$ and all
such pairs $(e,F)$ satisfying that $\ell(e,F)<k$. Consider now a pair $(e,F)$
in $G$ such that $\ell(e,F)=k$. We incrementally construct the desired curve,
as follows. Let $x_{0}$ be an arbitrary point in the interior of $F$. Note
that edge $e$ is incident to two faces $F,F_{1}$. Let $x_{1}$ be an arbitrary
point in the interior of $F_{1}$, and let $\gamma_{1}$ be a curve connecting
$x_{0}$ to $x_{1}$, while intersecting with only the image of $e$. Let
$e_{1},\ldots,e_{r}$ be all other edges incident to $F_{1}$. Clearly,
$\sum_{1\leq i\leq r}\ell(e,F_{1})\leq\ell(e,F)$. If $r=1$, then $F_{1}$ is
the outer face, and there is a curve $\gamma_{2}$ connecting $x_{1}$ to the
boundary of $\mathcal{D}^{2}_{e}$ that is disjoint from the drawing of $G$. If
$r>1$, then we may assume without loss of generality that
$\ell(e_{1},F_{1})\leq\ell(e,F)/2$. From the induction hypothesis, there is a
curve $\gamma_{2}$ connecting $x_{1}$ to a point on the boundary of
$\mathcal{D}^{2}_{e}$, that intersects the image of at most
$\log(\ell(e_{1},F_{1}))$ edges of $G$. Let $\gamma$ be the concatenation of
curves $\gamma_{1},\gamma_{2}$. It is easy to verify that $\gamma$ connects a
point in the interior of $F$ to a point on the boundary of
$\mathcal{D}^{2}_{e}$, intersecting the image of at most
$\log(\ell(e_{1},F_{1}))+1\leq\log(\ell(e,F))$ edges of $G$. ∎

We use Lemma 3.8 to derive two sufficient conditions for the existence of a
balanced cut.

######  Lemma 3.9.

Let $F$ be a face and let $E(F)=E(\partial(F))$ be its incident edges. Then
graph $G$ contains a balanced cut with size at most $2\log m$ if one of the
following conditions hold: (i) there are two edges $e_{1},e_{2}\in E(F)$ that
do not share any endpoint, and $\ell(e_{1},F),\ell(e_{2},F)\geq 0.1m$; (ii)
there exist three edges $e_{1},e_{2},e_{3}\in E(F)$, such that
$\ell(e_{1},F),\ell(e_{2},F),\ell(e_{3},F)\geq 0.1m$.

###### Proof.

We first prove (i). Denote $e_{1}=(u,u^{\prime})$ and $e_{2}=(v,v^{\prime})$,
such that vertices $u,u^{\prime},v^{\prime},v$ appear on the boundary of
$\mathcal{D}$ in this order. Let $\Lambda$ ($\Lambda^{\prime}$, resp) be the
part of the boundary of disc $\mathcal{D}$ between vertices $u,v$
($u^{\prime},v^{\prime}$, resp.). Since $e_{1},e_{2}$ are both incident to
$F$, consider the edge $e=(u,v)$, and it is easy to see that either $e\in
E(G)$, or we can add $e$ to $G$ so that graph $G\cup\left\\{e\right\\}$ is
still an outerplanar graph, whose corresponding drawing can be obtained from
the drawing of $G$ by adding a curve connecting $u$ to $v$ in face $F$. In
either case, we can apply Lemma 3.8 to compute a curve $\gamma$ connecting a
point $x$ in the interior of $F$ to a point on $\Lambda$, intersecting the
image of at most $\log m$ edges of $G$. Similarly, we can compute a curve
$\gamma^{\prime}$ connecting $x$ to a point on $\Lambda^{\prime}$,
intersecting the image of at most $\log m$ edges of $G$. Let $E^{\prime}$ be
the set of edges whose images are intersected by either $\gamma$ or
$\gamma^{\prime}$, then it is easy to verify that $E^{\prime}$ is a balanced
cut of $G$ with size at most $2\log m$.

We now prove (ii). Denote $e_{1}=(u_{1},v_{1})$, $e_{2}=(u_{2},v_{2})$ and
$e_{3}=(u_{3},v_{3})$. Let $x$ be a point in the interior of $F$, and denote
by $\Gamma_{i}$ the part of the boundary of disc $\mathcal{D}$ between
vertices $u_{i},v_{i}$, for each $i\in\left\\{1,2,3\right\\}$. From Lemma 3.8,
for each $i\in\left\\{1,2,3\right\\}$, we can compute a curve $\gamma_{i}$
connecting $x$ to a point $w_{i}$ on curve $\Gamma_{i}$, and we denote by
$E^{\prime}_{i}$ the set of edges in $G$ whose images are intersected by curve
$\gamma_{i}$. From Lemma 3.8,
$|E^{\prime}_{1}|,|E^{\prime}_{2}|,|E^{\prime}_{3}|\leq\log m$. Since
$\ell(e_{1},F),\ell(e_{2},F),\ell(e_{3},F)\geq 0.1m$, it is easy to see that
at least one of $E^{\prime}_{1}\cup E^{\prime}_{2},E^{\prime}_{2}\cup
E^{\prime}_{3},E^{\prime}_{3}\cup E^{\prime}_{1}$ is a balanced cut of $G$
with size at most $2\log m$. ∎

Back to the proof of Theorem 3.8. Now we will apply Lemma 3.9 to show that, if
$G$ does not contain a balanced cut of size at most $2\log m$, then $G$ must
have the following special structure. For an edge $e$, let
$F_{e},F^{\prime}_{e}$ be the two faces that $e$ is incident to. We say that
$e$ is _good_ , iff $\ell(e,F_{e})\geq 0.1m$ and $\ell(e,F_{e}^{\prime})\geq
0.1m$. We now show that, if $G$ does not contain a balanced cut of size at
most $2\log m$, then all good edges share an common endpoint. Assume the
contrast that not all good edges share an common endpoint. If we only focus on
the subgraph induced by all good edges (and its natural drawing induced by the
drawing of $G$), then either (i) there exists a face $F$ and two boundary
edges $e_{1},e_{2}$ of $F$, such that $e_{1},e_{2}$ do not share endpoints, or
(ii) there exists two faces $F_{1},F_{2}$ and three edges $e_{1},e_{2},e_{3}$,
such that $e_{1},e_{2}$ are boundary edges of $F_{1}$, $e_{2},e_{3}$ are
boundary edges of $F_{2}$, and $e_{1},e_{3}$ do not share edge. In either
case, it is not hard to see from Lemma 3.9 that we can compute a balanced cut
with size at most $2\log m$.

We denote by $u$ the common vertices of all good edges, denote by
$v_{1},\ldots,v_{r}$ the other endpoints of the good edges, and denote by
$\Lambda_{0},\ldots,\Lambda_{r}$ the parts of the boundary of $\mathcal{D}$,
where $\Lambda_{i}$ is the part between vertices $v_{i}$ and $v_{i+1}$ (here
we view $u=v_{0}=v_{r+1}$), then each curve of
$\Lambda_{0},\ldots,\Lambda_{r}$ contains the image of at most $0.1m$ vertices
(see Figure 6(c)).

Now we prove that the competitive ratio of any graph $G$ with the above
structure is $O(\log^{2}m)$. Let $\mathcal{Q}^{*}$ be the subset of
$\left\\{Q_{1},\ldots,Q_{n}\right\\}$ that, over all subsets of edge-disjoint
paths in $\left\\{Q_{1},\ldots,Q_{n}\right\\}$, maximizes its total value. Let
$\mathcal{Q}_{1}=\\{Q\in\mathcal{Q}^{*}\mid
E(Q)\cap\delta_{G}(u)=\emptyset\\}$ be all demand paths which do not visit
$u$. Here $\delta_{G}(u)$ is the set of edges in $G$ incident to $u$. Let
$\mathcal{Q}_{2}=\mathcal{Q}^{*}\setminus\mathcal{Q}_{1}$. We distinguish
between the following cases.

#### Case 1. $v(\mathcal{Q}_{1})\geq v(\mathcal{Q}^{*})(1-1/(16\log m))$.

In this case we first set the price for all edges of $\delta_{G}(u)$ to be
$+\infty$. Equivalently, we delete edges of $\delta_{G}(u)$ from the graph.
Let $G^{\prime}$ be the remaining graph. It is easy to see that the
$E(G^{\prime})$ can be partitioned into subsets $E_{0},\ldots,E_{r}$, where
set $E_{i}$ contains all edges whose both endpoints lie in curve
$\Lambda_{i}$. From similar arguments in the proof of Lemma 3.8, it is easy to
compute a cut $(S,T)$ of $G^{\prime}$ such that $|E(S,T)|\leq\log(0.1m)$ and
$|S|,|T|\leq 0.6m$. From Lemma 3.7, we get that
$\ratio(G^{\prime})\leq\max\left\\{\ratio(G^{\prime}[S]),\ratio(G^{\prime}[T])\right\\}+\log(0.1m)\leq
200\log^{2}(0.6m)+\log(0.1m)$. Altogether,

$\ratio(G)\leq\bigg{(}1-\frac{1}{16\log
m}\bigg{)}^{-1}\ratio(G^{\prime})\leq\bigg{(}1+\frac{1}{15\log
m}\bigg{)}\bigg{(}\log(0.1m)+200\log^{2}(0.6m)\bigg{)}\leq 200\log^{2}m.$

#### Case 2. $v(\mathcal{Q}_{2})\geq v(\mathcal{Q}^{*})/(16\log m)$.

In this case we first set the price for all edges of $E(G)\setminus
E(\mathcal{Q}_{2})$ to be $+\infty$. Equivalently, we only consider the graph
$G^{\prime\prime}$ obtained by taking the union of all paths in
$\mathcal{Q}_{2}$. For every $Q\in\mathcal{Q}_{2}$, let
$I_{Q}\subseteq\\{v_{1},\ldots,v_{r+1}\\}$ be the set of $v_{j}$s such that
either (i) $Q\cap(E_{j-1}\cup E_{j})\not=\emptyset$; or (ii) One endpoint of
$Q$ is $v_{j}$. Since each path $Q\in\mathcal{Q}_{2}$ contains at least an
edge of $\delta_{G}(u)=\left\\{(v_{t},u)\mid 1\leq t\leq r\right\\}$, $I_{Q}$
must induce either one or two consecutive subsequences of $\\{0,\ldots,r\\}$:
Before and after visiting $u$, the path $Q$ must both visit $v_{j}$s that form
a consecutive sequence.

We notice that for every $0\leq t\leq r$, $E_{t}$ contains at most
$\log(0.1m)$ edge-disjoint paths. Otherwise, there is a curve from the
interior of $\mathcal{D}$ to curve $\Lambda_{t}$, that intersects the image of
at least $\log(0.1m)+1$ edges of $E_{t}$. It contradicts with Lemma 3.8. Note
that the paths in $\mathcal{Q}_{2}$ are edge-disjoint. Then for every
$t\in\\{1,\ldots,r+1\\}$, $v_{t}$ is contained in at most $2\log(0.1m)+1\leq
2\log m$ $I_{Q}$ sets for $Q\in\mathcal{Q}_{2}$: At most $\log(0.1m)$ paths
coming from $v_{t-1}$, at most $\log(0.1m)$ paths coming from $v_{t+1}$, and 1
path that contains the edge $(u,v_{t})$.

######  Lemma 3.10.

(Theorem 1 of [31]) Fix any integer $k\geq 1$. Let graph $G$ be a single line.
For any $j=1,\ldots,n$, let $A_{j}$ be a set of edges that forms a union of
$k$ closed intervals in $G$. Suppose that every edge in $G$ appears in at most
$r$ sets of $A_{j}$, for some $r\geq 2$, then set $\\{A_{j}\\}_{j=1}^{n}$ can
be $2k(r-1)$-colored, such that all sets with any single color are node-
disjoint.

From Lemma 3.10 and the definition of $I_{Q}$, the paths in $\mathcal{Q}_{2}$
can be $(8\log m)$-colored, such that paths with the same color are node-
disjoint, except for their common vertex $u$. Therefore, there exists a set
$\mathcal{Q}^{\prime}_{2}\subseteq\mathcal{Q}_{2}$ of paths that are node-
disjoint except at $u$, and $v(\mathcal{Q}^{\prime}_{2})\geq
v(\mathcal{Q}^{\prime}_{2})/(8\log m)$. Note that the graph formed by the
union of all paths in $\mathcal{Q}^{\prime}_{2}$ is a spider graph. Therefore,
from Theorem 3.4,

$\ratio(G)\leq(16\log m)\cdot\ratio(G^{\prime\prime})\leq(16\log m)\cdot(8\log
m)\cdot(3/2)\leq 200\log^{2}m.$

This completes the proof of Theorem 3.8. $\Box$

##  4 Competitive Ratio for General Graphs

In this section we study the competitive ratio when $G$ is a general graph.
Again in this section we assume that the seller owns the tie-breaking power.
We will start by showing an $\Omega(m^{1/8})$ lower bound by constructing an
instance in the serial-parallel graph (Section 4.1). Then we use a
modification of this instance to prove lower bounds in grids and outerplanar
graphs (Sections 4.2, 4.3). At last, we prove an upper bound for the
competitive ratio in general graphs, that depends on the number of buyers
(Section 4.4).

###  4.1 Lower Bound for General Graphs

######  Theorem 4.1.

$\emph{\ratio}(\emph{{General\text{ }Graphs}})=\Omega(m^{1/8})$, i.e., there
exist a graph $G$ with $|E(G)|=m$ and a buyer profile $\mathcal{F}$ on $G$,
such that no set of prices on edges of $G$ can achieve worst-case welfare
$\Omega(\mathsf{OPT}(G,\mathcal{F})/m^{1/8})$.

The remainder of this subsection is dedicated to the proof of Theorem 4.1. We
will construct the graph $G$ as follows. For convenience, we will construct a
family of graphs $\left\\{H_{a,b}\right\\}_{a,b\in\mathbb{Z}}$, in which each
graph is featured by two parameters $a,b$ that are positive integers. We will
set the exact parameters that will be used for the proof of Theorem 4.1 later.

For a pair $a,b$ of integers, graph $H_{a,b}$ is defined as follows. The
vertex set is $V(H_{a,b})=V_{1}\cup V_{2}$, where
$V_{1}=\left\\{v_{0},\ldots,v_{b}\right\\}$ and $V_{2}=\left\\{u_{i,j}\mid
1\leq i\leq b,1\leq j\leq a\right\\}$. The edges set is
$E(H_{a,b})=\bigcup_{1\leq i\leq b}E_{i}$, where
$E_{i}=\left\\{(v_{i-1},u_{i,j}),(v_{i},u_{i,j})\mid 1\leq j\leq a\right\\}$.
See Figure 7 for an example. Equivalently, if we define the multi-graph
$L_{a,b}$ to be the graph obtained from a length-$b$ path by duplicating each
of its edges $a$ times, then we can view $H_{a,b}$ as obtained from $L_{a,b}$
by subdividing each edge by a new vertex.

Figure 7: An illustration of graph $H_{4,4}$.

Let $a,b$ be such that $b=a+3a^{3}$ and choose $G=H_{a,b}$. Clearly
$m=|E(G)|=2ab$, so $a=\Theta(m^{1/4})$ and $b=\Theta(m^{3/4})$. For
convenience, we can simply work with graph $L_{a,b}$, since every path in
$L_{a,b}$ is also a path in $H_{a,b}$. Note that
$V(L_{a,b})=\left\\{v_{0},\ldots,v_{b}\right\\}$, and we denote by
$e_{i,1},\ldots,e_{i,a}$ the edges in $L_{a,b}$ connecting $v_{i-1}$ and
$v_{i}$. For brevity, we use the index sequence $(j_{1},j_{2},\ldots,j_{b})$
to denote the path consisting of edges
$e_{1,j_{1}},e_{2,j_{2}},\ldots,e_{b,j_{b}}$, where each index $j_{t}\in[a]$,
for each $t\in[b]$. It is clear that a pair of paths
$(j_{1},j_{2},\ldots,j_{b})$ and
$(j^{\prime}_{1},j^{\prime}_{2},\ldots,j^{\prime}_{b})$ are edge-disjoint iff
for each $t\in[b]$, $j_{t}\neq j^{\prime}_{t}$. In the proof we will construct
a buyer profile $\mathcal{F}$ on the multi-graph $L_{a,b}$. Clearly it can be
converted to a buyer profile on graph $H_{a,b}$, with the same lower bound of
competitive ratio. We prove the following lower bound of competitive ratio for
$L_{a,b}$. Theorem 4.1 follows directly from Lemma 4.1 where
$a=\Theta(m^{1/4})$ and $b=\Theta(m^{3/4})$.

######  Lemma 4.1.

$\emph{\ratio}(L_{a,b})\geq\sqrt{a}$.

###### Proof.

We define $\mathcal{F}$ on graph $L_{a,b}$ as follows. We will first define a
set $\mathcal{F}^{*}$ of buyer profile, and then define, for each subset
$S\subseteq[a]$ with $|S|\geq\sqrt{a}$, a buyer profile $\mathcal{F}_{S}$,
where the buyers in different sets are distinct. Then we define
$\mathcal{F}=\mathcal{F}^{*}\cup(\bigcup_{S\subseteq[a],|S|\geq\sqrt{a}}\mathcal{F}_{S})$.

Let the set $\mathcal{F}^{*}$ contain, for each $r\in[a]$, a buyer $r$ with
$Q^{(r)}=(r,r,\ldots,r)$ and $v_{r}=1$. Clearly, demand paths of buyers in
$\mathcal{F}^{*}$ are edge-disjoint. In the construction we will guarantee
that $\mathsf{OPT}(L_{a,b},\mathcal{F})=a$, achieved by giving each buyer in
$\mathcal{F}^{*}$ her demand path.

Before we construct the sets
$\left\\{\mathcal{F}_{S}\right\\}_{S\subseteq[a],|S|\geq\sqrt{a}}$, we will
first state some desired properties of sets
$\left\\{\mathcal{F}_{S}\right\\}$, and use it to finish the proof of Lemma
4.1. Let $\varepsilon>0$ be an arbitrarily small constant.

  1. 1.

For each $S$, set $\mathcal{F}_{S}$ contains $2|S|$ buyers, and every pair
$Q,Q^{\prime}$ of demand paths in $\mathcal{F}_{S}$ share an edge. The value
for every buyer appeared in $\mathcal{F}_{S}$ is $1+\epsilon$.

  2. 2.

For each demand path $Q$ in $\mathcal{F}_{S}$, the index sequence
$(j^{Q}_{1},\ldots,j^{Q}_{b})$ that $Q$ corresponds to satisfies that (i)
$j^{Q}_{i}\in S$ for each $i\in[b]$; and (ii) the set
$\left\\{j^{Q}_{1},\ldots,j^{Q}_{b}\right\\}$ contains all element of $S$.

  3. 3.

The union of all demand paths in $\mathcal{F}_{S}$ covers the graph
$\bigcup_{r\in S}Q^{(r)}$ exactly twice. In other words, for each $i\in[b]$
and every $r\in S$, there are exactly two demand paths $Q$ appeared in
$\mathcal{F}_{S}$ that satisfy $j_{i}^{Q}=r$.

  4. 4.

For any pair $S,S^{\prime}\subseteq[a]$ such that
$|S|,|S^{\prime}|\geq\sqrt{a}$ and $S\cap S^{\prime}\neq\emptyset$, and for
any demand path $Q$ appeared in $\mathcal{F}_{S}$ and $Q^{\prime}$ appeared in
$\mathcal{F}_{S^{\prime}}$, $Q$ and $Q^{\prime}$ share some edge.

Suppose we have successfully constructed the sets
$\left\\{\mathcal{F}_{S}\right\\}_{S\subseteq[a],|S|\geq\sqrt{a}}$ that
satisfy all the above properties. We then define
$\mathcal{F}=\mathcal{F}^{*}\cup(\bigcup_{S\subseteq[a],|S|\geq\sqrt{a}}\mathcal{F}_{S})$.
From the above properties, it is easy to see that
$\mathsf{OPT}(L_{a,b},\mathcal{F})=a$, which is achieved by giving each buyer
in $\mathcal{F}^{*}$ her demand path. We will prove that any prices on edges
of $L_{a,b}$ achieve worst-case welfare $O(\sqrt{a})$.

Consider now any set of prices on edges of $L_{a,b}$. We distinguish between
the following two cases.

#### Case 1: At least $\sqrt{a}$ buyers in $\mathcal{F}^{*}$ can afford their
demand paths.

We let $S$ be the set that contains all indices $r\in[a]$ such that the buyer
$r$ can afford her demand path $Q^{(r)}$, so $|S|\geq\sqrt{a}$. Consider the
set $\mathcal{F}_{S}$ of buyers that we have constructed. We claim that at
least some buyers of $\mathcal{F}_{S}$ can also afford her demand path. To see
why this is true, note that by Property 1, $\mathcal{F}_{S}$ contains $2|S|$
buyers with total value $(2+2\epsilon)|S|$, while the total price of edges in
$\bigcup_{r\in S}Q^{(r)}$ is at most $|S|$. Therefore, by Property 3, there
must exist a buyer in $\mathcal{F}_{S}$ that can afford her demand path. We
then let this buyer come first and get her demand path $Q$. Then from Property
2, all buyers $r\in S$ can not get their demand paths since their demand paths
share an edge with $Q$. All buyers $r\in[a]/S$ can not afford their demand
paths. Moreover, for any buyers’ arriving order, let
$\mathcal{Q}=\\{Q_{1},...,Q_{K}\\}$ ($Q_{1}=Q$) be the set of demand paths
that are allocated eventually. We argue that $K\leq\sqrt{a}$. For every
$k=1,\ldots,K$, $Q_{k}$ must come from the profile
$\bigcup_{S\subseteq[a],|S|\geq\sqrt{a}}\mathcal{F}_{S}$. Let
$S_{k}\subseteq[a]$ be the set that $Q_{k}$ appears in $\mathcal{F}_{S_{k}}$.
Then by Property 1 and 4, we have $S_{k_{1}}\cap S_{k_{2}}=\emptyset$ for any
$k_{1},k_{2}\in[K],k_{1}\not=k_{2}$. Thus we have $K\leq\sqrt{a}$ since
$|S_{k}|\geq\sqrt{a}$ for every $k$. Hence, the achieved welfare is at most
$(1+\varepsilon)\sqrt{a}$, for any buyers’ arriving order.

#### Case 2. Less that $\sqrt{a}$ buyers in $\mathcal{F}^{*}$ can afford their
demand paths.

Similar to Case 1, at most $\sqrt{a}$ buyers from sets
$\bigcup_{S\subseteq[a],|S|\geq\sqrt{a}}\mathcal{F}_{S}$ can get their demand
sets simultaneously. Therefore, the total welfare is at most
$(1+\varepsilon)\sqrt{a}+\sqrt{a}=O(\sqrt{a})$.

It remains to construct the sets
$\left\\{\mathcal{F}_{S}\right\\}_{S\subseteq[a],|S|\geq\sqrt{a}}$ that
satisfy all the above properties. We now fix a set $S\subseteq[a]$ with
$|S|\geq\sqrt{a}$ and construct the set $\mathcal{F}_{S}$. Denote $s=|S|$.
Since each path can be represented by a length-$b$ sequence, we simply need to
construct a $(2s\times b)$ matrix $M_{S}$, in which each row corresponds to a
path in $L_{a,b}$. We first construct the first $s$ columns of the matrix. Let
$N_{S}$ be an $s\times s$ matrix, such that every row and every column
contains each element of $S$ exactly once (it is easy to see that such a
matrix exists). We place two copies of $N_{S}$ vertically, and view the
obtained $(2s\times s)$ matrix as the first $s$ columns of $M_{S}$. We then
construct the remaining $b-s\geq 3a^{3}$ columns of matrix $M_{S}$. Let
$S^{\prime}$ be the multi-set that contains two copies of each element of $S$.
We then let each column be an independent random permutation on elements of
$S^{\prime}$. This completes the construction of the matrix $M_{S}$. We then
add a buyer associated with every path above with value $1+\varepsilon$. This
completes the construction of the set $\mathcal{F}_{S}$.

We prove that the randomized construction satisfies all the desired
properties, with high probability. For Property 1, clearly $\mathcal{F}_{S}$
contains $2|S|$ buyers, and the value associated with each demand path is
$1+\varepsilon$. For every pair of distinct rows in $M_{S}$, the probability
that their entries in $j$-th column for any $j>s$ are identical is $1/2s$, so
the probability that the corresponding two paths are edge-disjoint is at most
$(1-1/2s)^{3a^{3}}$. From the union bound over all pairs of rows, the
probability that there exists a pair of edge-disjoint demand paths in
$\mathcal{F}_{S}$ is at most $\binom{s}{2}\cdot(1-1/2s)^{3a^{3}}\leq
a^{2}\cdot e^{-a^{2}}$. Property 2 is clearly satisfied by the first $s$
column of matrix $M_{S}$. Property 3 is clearly satisfied by the construction
of matrix $M_{S}$. Therefore, from the union bound on all subsets
$S\subseteq[a]$ with $|S|\geq\sqrt{a}$, the probability that Properties 1,2,
and 3 are not satisfied by all sets
$\left\\{\mathcal{F}_{S}\right\\}_{S\subseteq[a],|S|\geq\sqrt{a}}$ is
$a^{2}\cdot e^{-a^{2}}\cdot 2^{a}<e^{-a}$.

For Property 4, consider any pair $S,S^{\prime}$ of such sets and any row in
the matrix $M_{S}$ and any row in the matrix $M_{S^{\prime}}$. Since $S\cap
S^{\prime}\neq\emptyset$, the probability that they have the same element in
any fixed column is at least $(1/|S|)\cdot(1/|S^{\prime}|)\geq 1/a^{2}$, so
the probability that the corresponding two paths are edge-disjoint is at most
$(1-a^{-2})^{3a^{3}}<e^{-3a}$. From the union bound, the probability that
Property 4 is not satisfied is at most $e^{-3a}\cdot(2^{a}\cdot
2a)^{2}<e^{-a}$. Altogether, our randomized construction satisfies all the
desired properties with high probability. Thus there must exist a
deterministic construction of $\mathcal{F}_{S}$ that satisfies all the
properties. This completes the proof of Lemma 4.1. ∎

###  4.2 Lower Bound for Grids

We notice that in the graph $L_{a,b}$ and $H_{a,b}$ that we constructed in
Theorem 4.1, the maximum degree among all vertices is $2a$, which is a
polynomial of $m$. Therefore, it is reasonable to ask the large competitive
ratio is due to the existence of high-degree vertices that are shared by many
demand paths. In this section, we show a negative answer to this question. We
prove that a $poly(m)$ lower bound of the competitive ratio when $G$ is
restricted to be a grid.

######  Theorem 4.2.

Let $G$ be the $(\sqrt{m}\times\sqrt{m})$-grid (so that $G$ has $\Theta(m)$
edges). Then $\emph{\ratio}(G)=\Omega(m^{1/20})$.

The proof is enabled by replacing each high-degree vertex in the graph
$H_{a,b}$ with a gadget, so that every vertex in the modified graph $G$ has
degree at most 4. Formally, the graph $G=R_{a,b}$ is constructed as follows.
Consider a high-degree vertex $v_{i}\in V(H_{a,b})$. Recall that it has $2a$
incident edges $\left\\{(v_{i},u_{i,j}),(v_{i},u_{i+1,j})\mid
j\in[a]\right\\}$ in graph $H_{a,b}$ (see Figure 8(a)). The gadget for vertex
$v_{i}$ is constructed as follows. We first place the vertices
$u_{i,1},\ldots,u_{i,a},u_{i+1,1}\ldots,u_{i+1,a}$ on a circle in this order,
and then for each $j\in[a]$, we draw a line segment connecting $u_{i,j}$ with
$u_{i+1,j}$, such that every pair of these segments intersects, and no three
segments intersect at the same point. We then replace each intersection with a
new vertex. See Figure 8(b) for an illustration.

(a) The vertex $v_{i}$ and its incident edges in $H_{a,b}$.

(b) The gadget graph $K_{i}$.

Figure 8: An illustration of the gadget construction.

Now the modified graph can be embedded in the grid since each vertex has
degree at most 4. Denote by $K_{i}$ the resulting graph after constructing the
gadget, as shown in Figure 8(b). We use the following lemma.

######  Lemma 4.2.

Let $\sigma$ be any permutation on $[a]$, then graph $K_{i}$ contains a set
$\mathcal{P}_{i}=\left\\{P_{i,j}\mid j\in[a]\right\\}$ of edge-disjoint paths,
such that path $P_{i,j}$ connects vertex $u_{i,j}$ to vertex
$u_{i+1,\sigma(j)}$.

Before proving Lemma 4.2, we first give the proof of Theorem 4.2 using Lemma
4.2.

Proof of Theorem 4.2: First, the graph $R_{a,b}$ is obtained by taking the
union of all graphs $\left\\{K_{i}\right\\}_{0\leq i\leq b}$, while
identifying, for each $i\in[b]$ and $j\in[a]$, the vertex $u_{i,j}$ in
$K_{i-1}$ with the vertex $u_{i,j}$ in $K_{i}$. Clearly, the maximum vertex
degree in graph $R_{a,b}$ is $4$.

We now show that we can easily convert the buyer-profile $\mathcal{F}$ on
graph $H_{a,b}$ into a buyer-profile $\hat{\mathcal{F}}$ on graph $R_{a,b}$,
while preserving all desired properties. Consider first the buyers
$1,\ldots,a$ in $\mathcal{F}^{*}$. Let $\sigma_{i}$ be the identity
permutation on $[a]$, for each $i\in[b]$. From Lemma 4.2, there exist sets
$\left\\{\mathcal{P}^{*}_{i}\right\\}_{i\in[b]}$ of edge-disjoint paths, where
$\mathcal{P}^{*}_{i}=\left\\{P^{*}_{i,j}\mid j\in[a]\right\\}$ for each
$i\in[b]$. We then let $\hat{\mathcal{F}^{*}}$ contains, for each $j\in[a]$, a
buyer $\hat{B}^{*}_{j}$ demanding the path $\hat{Q}_{j}$ with value $1$, where
$\hat{Q}_{j}$ is the sequential concatenation of paths
$P^{*}_{1,j},\ldots,P^{*}_{b,j}$. Clearly, paths
$\left\\{\hat{Q}_{j}\right\\}_{j\in[a]}$ are edge-disjoint. Consider now a set
$S\subseteq[a]$ with $|S|\geq\sqrt{a}$. Recall that in $\mathcal{F}_{S}$ we
have $2|S|$ buyers, whose demand paths cover the paths $\left\\{Q^{(j)}\mid
j\in S\right\\}$ exactly twice. Therefore, for each $i\in[b]$, the way that
these paths connect vertices of $U_{i-1}=\left\\{u_{i-1,j}\mid
j\in[a]\right\\}$ to vertices of $U_{i}=\left\\{u_{i,j}\mid j\in[a]\right\\}$
form two perfect matchings between vertices of $U_{i-1}$ and vertices of
$U_{i}$. From Lemma 4.2, there are two sets
$\mathcal{P}_{i},\mathcal{P}^{\prime}_{i}$ of edge-disjoint paths connecting
vertices of $U_{i-1}$ and vertices of $U_{i}$. We then define, for each demand
path $Q=(j_{0},j_{1},\ldots,j_{b})$222We can arbitrarily assign additionally
the path $Q$ with some index $j_{0}\in S$, such that each index of $S$ is
assigned to exactly two demand paths in $\mathcal{D}_{S}$. in
$\mathcal{F}_{S}$, its corresponding path $\hat{Q}$ to be the sequential
concatenation of, the corresponding path in
$\mathcal{P}_{1}\cup\mathcal{P}^{\prime}_{1}$ that connects $u_{0,j_{0}}$ to
$u_{1,j_{1}}$, the corresponding path in
$\mathcal{P}_{2}\cup\mathcal{P}^{\prime}_{2}$ that connects $u_{1,j_{1}}$ to
$u_{2,j_{2}}$, all the way to the corresponding path in
$\mathcal{P}_{b}\cup\mathcal{P}^{\prime}_{b}$ that connects $u_{b-1,j_{b}-1}$
to $u_{b,j_{b}}$. It is easy to verify that all desired properties are still
satisfied. Lastly, to ensure that the graph $R_{a,b}$ can be embedded into the
$(\sqrt{m}\times\sqrt{m})$-grid, we need $\sqrt{n}=a^{2}b$, where
$b=a+3a^{3}$. Thus $a=\Theta(m^{1/10})$. Theorem 4.2 now follows from Lemma
4.1. $\Box$

It remains to prove Lemma 4.2.

###### Proof of Lemma 4.2.

We prove by induction on $a$. The base case where $a=1$ is trivial. Assume
that the lemma is true for all integers $a\leq r-1$. Consider the case where
$a=r$. For brevity of notations, we rename $K_{i}$ by $K$, $\mathcal{P}_{i}$
by $\mathcal{P}$, $u_{i,j}$ by $u_{j}$ and $u_{i+1,j}$ by $u^{\prime}_{j}$.
Recall that the graph $K$ is the union of $r$ paths $W_{1},\ldots,W_{r}$,
where path $W_{j}$ connects vertex $u_{j}$ to vertex $u^{\prime}_{r+1-j}$,
such that every pair of these paths intersect at a distinct vertex. Recall
that we are also given a permutation $\sigma$ on $[r]$, and we are required to
find a set $\mathcal{P}=\left\\{P_{j}\mid j\in[r]\right\\}$ of edge-disjoint
paths in $K$, such that the path $P_{j}$ connects $u_{j}$ to
$u^{\prime}_{\sigma(j)}$.

We first define the graph $K^{\prime}=K\setminus W_{r}$, and we define an one-
to-one mapping $f:[r\\!-\\!1]\to\left\\{2,\ldots,r\right\\}$ as follows. For
each $j\in[r\\!-\\!1]$ such that $\sigma(j)\in\left\\{2,\ldots,r\right\\}$, we
set $f(j)=\sigma(j)$; for $j\in[r\\!-\\!1]$ such that $\sigma(j)=1$, we set
$f(j)=\sigma(r)$. Note that $K^{\prime}$ is a graph consisting of
$(r\\!-\\!1)$ pairwise intersecting paths, and $f$ is a one-to-one mapping
from the left set of vertices of $K^{\prime}$ to the right set of vertices of
$K^{\prime}$. From the induction hypothesis, there is a set
$\mathcal{P}^{\prime}=\left\\{P^{\prime}_{j}\mid j\in[r\\!-\\!1]\right\\}$ of
edge-disjoint paths, such that path $P^{\prime}_{j}$ connects $u_{j}$ to
$u^{\prime}_{f(j)}$. If $\sigma(r)=1$, then we simply let
$\mathcal{P}=\mathcal{P}^{\prime}\cup\left\\{W_{r}\right\\}$, and it is easy
to check that the set $\mathcal{P}$ of paths satisfy the desired properties.
Assume now that $\sigma(r)\neq 1$, then the path $P^{\prime}_{\sigma^{-1}(a)}$
is currently connecting $u_{\sigma^{-1}(a)}$ to $u^{\prime}_{k}$, which is a
wrong destination. Observe that $W_{r}$ connects $u_{k}$ to $u^{\prime}_{1}$
and is edge-disjoint with $P^{\prime}_{\sigma^{-1}(a)}$. Moreover, it is easy
to see that $P^{\prime}_{\sigma^{-1}(a)}$ must intersect with $W_{r}$ at at
least one vertex. Let $x$ be the intersection that are closest to $u_{k}$ on
$W_{r}$. We then define the path $P_{k}$ as the concatenation of (i) the
subpath of $W_{k}$ between $u_{k}$ and $x$, and (ii) the subpath of
$P^{\prime}_{\sigma^{-1}(a)}$ between $x$ and $u^{\prime}_{\sigma(k)}$.
Similarly. we define the path $P_{\sigma^{-1}(a)}$ as the concatenation of (i)
the subpath of $P^{\prime}_{\sigma^{-1}(a)}$ between $u_{\sigma^{-1}(a)}$ and
$x$, and (ii) the subpath of $W_{r}$ between $x$ and $u^{\prime}_{1}$. We then
let
$\mathcal{P}=(\mathcal{P}^{\prime}\setminus\left\\{P^{\prime}_{\sigma^{-1}(a)}\right\\})\cup\left\\{P_{k},P_{\sigma^{-1}(a)}\right\\}$,
and it is easy to check that the set $\mathcal{P}$ of paths satisfy the
desired properties. ∎

###  4.3 Lower Bound for Outerplanar Graphs

By embedding the serial-parallel graph constructed in the proof of Theorem
4.1, we also prove that a polylogarithmic competitive ratio is unavoidable for
outerplanar graphs.

######  Theorem 4.3.

$\emph{\ratio}(\mathsf{Outerplanar})=\Omega((\frac{\log m}{\log\log
m})^{1/2})$.

###### Proof.

We will show that there is an outerplanar graph $G$ with $m$ edges, such that
we can embed the graph $L_{a,b}$ (constructed in Section 4) into $G$, and then
Theorem 4.3 follows immediately from Lemma 4.1. In fact, it is easy to embed
$a$ parallel paths into an outerplanar graph with $2^{a-1}$ edges (as Figure
9). Therefore, we can embed the graph $L_{a,b}$ into an outerplanar graph with
$2^{a-1}\cdot b$ edges. Setting $b=a+3a^{3}$ and $2^{a-1}\cdot b=m$, we have
$a=\Omega(\log m/\log\log m)$. From Lemma 4.1, we conclude that
$\ratio(\textsf{Outerplanar})=\Omega((\frac{\log m}{\log\log m})^{1/2})$.

Figure 9: An illustration of embedding parallel paths between two vertices in
an outerplanar graph. Edges of the same color represent such a path.

∎

###  4.4 Upper Bound for General Graphs

At last, we prove the following upper bound for the competitive ratio in any
tollbooth problem (on general graphs). The competitive ratio depends on the
number of buyers in the auction. Note that when $n$ is sub-exponential on $m$,
the competitive ratio proved in Theorem 4.4 is better than the competitive
ratio $O(\sqrt{m})$ proved in [12, 13].

######  Theorem 4.4.

For any given instance $(G,\mathcal{F})$ with $|E(G)|=m$ and
$|\mathcal{F}|=n$, there exists a set of prices on edges of $G$ that achieves
worst-case welfare
$\Omega(\mathsf{OPT}(G,\mathcal{F})/(m^{0.4}\cdot\log^{2}m\cdot\log n))$.

The remainder of the section is dedicated to the proof of Theorem 4.4. Choose
parameter $\alpha=1/10$. Denote
$\mathcal{F}=\left\\{(Q_{j},v_{j})\right\\}_{j\in[n]}$. Let
$\mathcal{Q}=\left\\{Q_{j_{1}},\ldots,Q_{j_{t}}\right\\}$ be the independent
set of paths that, among all independent subsets of
$\left\\{Q_{1},\ldots,Q_{n}\right\\}$, maximizes its total value, namely
$\mathcal{Q}=\arg_{\tilde{\mathcal{Q}}:\tilde{\mathcal{Q}}\text{ is
independent}}\max\left\\{\sum_{j:Q_{j}\in\tilde{\mathcal{Q}}}v_{j}\right\\}$.
For every $Q\in\mathcal{Q}$, we denote $v(Q)$ the value of the buyer who is
allocated her demand path $Q$ in the optimal allocation $\mathcal{Q}$. We
denote $J=\left\\{j_{1},\ldots,j_{t}\right\\}$, so
$\mathsf{OPT}(G,\mathcal{F})=\sum_{j\in J}v_{j}$. We first pre-process the set
$\mathcal{Q}$ as follows.

For each integer $1\leq k\leq\log m$, we denote by $\mathcal{Q}_{k}$ the
subset of paths in $\mathcal{Q}$ that whose length lies in the interval
$[2^{k-1},2^{k})$. Clearly, there exists some integer $k^{*}$ with
$v(\mathcal{Q}_{k^{*}})=\sum_{Q\in\mathcal{Q}_{k^{*}}}v(Q)\geq\Omega(\mathsf{OPT}/\log
m)$. We denote $\mathcal{Q}^{*}=\mathcal{Q}_{k^{*}}$ and denote
$L=2^{k^{*}-1}$, so the length of each path in $\mathcal{Q}^{*}$ lies in
$[L,2L)$.

Let $v^{*}$ be the maximum value of a path in $\mathcal{Q}^{*}$, namely
$v^{*}=\max\left\\{v_{j}\mid Q_{j}\in\mathcal{Q}^{*}\right\\}$. We let
$\mathcal{Q}^{*}_{0}$ contains all paths in $\mathcal{Q}^{*}$ with value at
most $v^{*}/m^{2}$. Then, for each integer $1\leq t\leq 2\log n$, we denote by
$\mathcal{Q}^{*}_{t}$ the subset of paths in $\mathcal{Q}^{*}$ whose length
lie in the interval $(v^{*}/2^{t},v^{*}/2^{t-1}]$. Clearly, the total value of
the paths in $\mathcal{Q}^{*}_{0}$ is at most $m\cdot(v^{*}/m^{2})=v^{*}/m$
(since $|\mathcal{Q}^{*}_{0}|\leq|\mathcal{Q}^{*}|\leq m$). Therefore, there
exists some integer $t^{*}$ with
$v(\mathcal{Q}^{*}_{t^{*}})=\sum_{Q\in\mathcal{Q}^{*}_{t^{*}}}v(Q)\geq\Omega(v(\mathcal{Q}^{*})/\log
m)$. We denote $\mathcal{Q}^{\prime}=\mathcal{Q}^{*}_{t^{*}}$ and denote
$\hat{v}=v^{*}/2^{t^{*}}$, so the value of each path of $\mathcal{Q}^{\prime}$
lies in $(\hat{v},2\hat{v}]$.

So far we obtain a set $\mathcal{Q}^{\prime}$ of paths, and two parameters
$L,\hat{v}$, such that

  1. 1.

all paths in $\mathcal{Q}^{\prime}$ have length in $[L,2L)$;

  2. 2.

all paths in $\mathcal{Q}^{\prime}$ have value in $(\hat{v},2\hat{v}]$;

  3. 3.

the total value of all paths in $\mathcal{Q}^{\prime}$ is
$\Omega(\mathsf{OPT}/\log^{2}m)$.

We use the following observations.

######  Observation 4.1.

If $|\mathcal{Q}^{\prime}|<m^{1/2-\alpha}$, then there exist prices on edges
of $G$ achieving worst-case welfare
$\Omega(\mathsf{OPT}/(m^{1/2-\alpha}\cdot\log^{2}m))$.

###### Proof.

Let $Q$ be a path in $\mathcal{Q}^{\prime}$ with largest value, so $v(Q)\geq
v(\mathcal{Q}^{\prime})/m^{1/2-\alpha}$. We first set the price of each edge
of $E(G\setminus Q)$ to be $+\infty$. From Theorem 3.1, we know that there is
a set of prices on edges of $Q$, that achieves the worst-case welfare
$\Omega(v(Q))$. Therefore, we obtain a set of prices for all edges in the
graph, that achieves worst-case welfare
$v(Q)=\Omega(v(\mathcal{Q}^{\prime})/m^{1/2-\alpha})=\Omega(\mathsf{OPT}/(m^{1/2-\alpha}\cdot\log^{2}m))$.
∎

######  Observation 4.2.

If $L<m^{1/2-\alpha}$, then there exist prices on edges of $G$ achieving
worst-case welfare $\Omega(\mathsf{OPT}/(m^{1/2-\alpha}\cdot\log^{2}m))$.

###### Proof.

We define the edge prices as the following. For each path
$Q\in\mathcal{Q}^{\prime}$ and for each edge $e\in Q$, we set its price
$\tilde{p}(e)$ to be $v(Q)/2L$, and we set the price for all other edges to be
$+\infty$. Note that, for each $Q\in\mathcal{Q}^{\prime}$,
$\tilde{p}(Q)=\sum_{e\in Q}\tilde{p}(e)=|E(Q)|\cdot(v(Q)/2L)<v(Q)$. Therefore,
no matter what order in which the buyers come, at the end of the selling
process, for each $Q\in\mathcal{Q}^{\prime}$, at least one edge is taken at
the price of $v(Q)/2L$. It follows that the welfare is at least
$\sum_{Q\in\mathcal{Q}^{\prime}}v(Q)/(2L)=\Omega(v(\mathcal{Q}^{\prime})/m^{1/2-\alpha})=\Omega(\mathsf{OPT}/(m^{1/2-\alpha}\cdot\log^{2}m))$.
∎

From the above observations, we only need to consider the case where
$|\mathcal{Q}^{\prime}|\geq m^{1/2-\alpha}$ and $L\geq m^{1/2-\alpha}$. Since
$|\mathcal{Q}^{\prime}|\cdot L\leq\sum_{Q\in\mathcal{Q}^{\prime}}|E(Q)|\leq
m$, we get that $|\mathcal{Q}^{\prime}|,L\leq m^{1/2+\alpha}$. We can also
assume without loss of generality that $\hat{v}=1$, namely each path of
$\mathcal{Q}^{\prime}$ has value in $(1,2]$. We now perform the following
steps.

#### Step 1. Construct a random subset $\mathcal{Q}^{\prime\prime}$ of
$\mathcal{Q}^{\prime}$.

Let $\mathcal{Q}^{\prime\prime}$ be a subset of $\mathcal{Q}^{\prime}$
obtained by including each path $Q\in\mathcal{Q}^{\prime}$ independently with
probability $1/2$. Then we set the price for each edge that is not contained
in any path of $\mathcal{Q}^{\prime\prime}$ to be $+\infty$. From Chernoff’s
bound, with high probability $v(\mathcal{Q}^{\prime\prime})\geq
v(\mathcal{Q}^{\prime})/3$, so
$v(\mathcal{Q}^{\prime\prime})\geq\Omega(\mathsf{OPT}/\log^{2}m)$. Let
$\tilde{\mathcal{Q}}$ be the set of all paths in
$\left\\{Q_{1},\ldots,Q_{n}\right\\}$ that do not contain an edge whose price
is $+\infty$, namely the set $\tilde{\mathcal{Q}}$ contains all paths that
survive the current price. Here we say a path $Q$ survives a price $p$, if
$\sum_{e\in E(Q)}p(e)<v(Q)$, i.e. the buyer’s value is higher than the price
of her demand path. Note that the set $\tilde{\mathcal{Q}}$ may contain paths
of any length. We use the following observation.

######  Observation 4.3.

With high probability, all paths in $\tilde{\mathcal{Q}}$ intersect at most
$2\log n$ paths in $\mathcal{Q}^{\prime\prime}$.

###### Proof.

For each path $Q$, if it intersects with at least $2\log n$ paths in
$\mathcal{Q}^{\prime}$, then the probability that it belongs to
$\tilde{\mathcal{Q}}$ is at most $(1/2)^{2\log n}=1/n^{2}$. From the union
bound, the probability that there exists a path of
$\left\\{Q_{1},\ldots,Q_{n}\right\\}$ that intersects at least $2\log n$ paths
in $\mathcal{Q}^{\prime}$ and is still contained in $\tilde{\mathcal{Q}}$ is
at most $n\cdot(1/n^{2})=1/n$. Observation 4.3 then follows. ∎

#### Step 2. Analyze a special set of short surviving paths.

We set $L^{\prime}=m^{1/4-\alpha/2}$, and let $\tilde{\mathcal{Q}}^{\prime}$
contains all paths in $\tilde{\mathcal{Q}}$ with length less than
$L^{\prime}$. Clearly,
$\tilde{\mathcal{Q}}^{\prime}\cap\mathcal{Q}^{\prime\prime}=\emptyset$. Let
$\hat{\mathcal{Q}}$ be a max-total-value independent subset of
$\tilde{\mathcal{Q}}^{\prime}$. We distinguish between the following two cases
on the value of $v(\hat{\mathcal{Q}})$.

Case 1. $v(\hat{\mathcal{Q}})\geq
v(\mathcal{Q}^{\prime\prime})/100L^{\prime}$. We will show that in this case,
there exist prices on edges of $G$ that achieve worst-case welfare
$\Omega(\mathsf{OPT}/(m^{1/2-\alpha}\cdot\log^{2}m))$. We define the edge
prices as follows. For each path $Q\in\hat{\mathcal{Q}}$ and for each edge of
$Q$, we set its price to be $v(Q)/L^{\prime}$, and we set the price for all
other edges to be $+\infty$. Similar to Observation 4.2, the worst-case
welfare is at least
$\sum_{Q\in\hat{\mathcal{Q}}}v(Q)/L^{\prime}=\Omega(v(\hat{\mathcal{Q}})/L^{\prime})=\Omega(v(\mathcal{Q}^{\prime\prime})/L^{\prime
2})=\Omega(\mathsf{OPT}/(m^{1/2-\alpha}\cdot\log^{2}m))$.

Case 2. $v(\hat{\mathcal{Q}})\leq
v(\mathcal{Q}^{\prime\prime})/100L^{\prime}$. We set the prices of the edges
in two stages. In the first stage, for each path $Q\in\hat{\mathcal{Q}}$ and
for each edge in $Q$, we set its price $p(e)$ to be $v(Q)$, and for all other
edges that belong to some path of $\mathcal{Q}^{\prime\prime}$, we set its
price to be $0$. Recall that we have already set the price for all edges that
do not belong to a path of $\mathcal{Q}^{\prime\prime}$ to be $+\infty$. We
prove the following observations.

######  Observation 4.4.

No path in $\tilde{\mathcal{Q}}^{\prime}$ survives price $p$.

###### Proof.

Assume by contradiction that there is a path $Q$ with length
$|E(Q)|<L^{\prime}$ that survives the price $p$. Let
$\hat{\mathcal{Q}}^{\prime}$ be the set of paths in $\hat{\mathcal{Q}}$ that
intersect $Q$. From the definition, $v(Q)>\sum_{e\in E(Q)}p(e)\geq
v(\hat{\mathcal{Q}}^{\prime})$. Consider the set
$(\hat{\mathcal{Q}}\setminus\hat{\mathcal{Q}}^{\prime})\cup\left\\{Q\right\\}$.
From the above discussion, this set is an independent set of paths with length
less than $L^{\prime}$, with total value at least the total value of
$\hat{\mathcal{Q}}$, while containing strictly less paths than
$\hat{\mathcal{Q}}$. This leads to a contradiction to the optimality of
$\hat{\mathcal{Q}}$. ∎

######  Observation 4.5.

The total value of all paths in $\mathcal{Q}^{\prime\prime}$ that survives $p$
is at least $0.99\cdot v(\mathcal{Q}^{\prime\prime})$.

###### Proof.

For each path $Q\in\mathcal{Q}^{\prime\prime}$ that does not survive the price
$p$, its value is below $\sum_{e\in E(Q)}p(e)$. Since paths in
$\mathcal{Q}^{\prime\prime}$ are edge-disjoint, the total value of paths in
$\mathcal{Q}^{\prime\prime}$ that do not survive the price $p$ is at most
$\sum_{e\in
E(\mathcal{Q}^{\prime\prime})}p(e)\leq\sum_{Q\in\hat{\mathcal{Q}}}L^{\prime}\cdot
v(Q)\leq L^{\prime}\cdot v(\hat{\mathcal{Q}})\leq
v(\mathcal{Q}^{\prime\prime})/100$. Observation 4.5 then follows. ∎

We now modify the price $p$ in the first stage as the following. For each path
$Q\in\mathcal{Q}^{\prime\prime}$ and for each edge $e\in Q$, we increase its
price by $v(Q)/4L$. Note that the prices of all other edges are already set to
be $+\infty$ before the first stage. This completes the definition of the
prices on edges. We now show that these prices will achieve worst-case welfare
$\Omega(\mathsf{OPT}/(m^{1/2-\alpha}\cdot\log^{2}m\cdot\log n))$, thus
completing the proof of Theorem 4.4.

First, since the total price on all edges of $\mathcal{Q}^{\prime\prime}$ is
at most
$v(\mathcal{Q}^{\prime\prime})/100+\sum_{Q\in\mathcal{Q}^{\prime\prime}}2L\cdot(v(Q)/4L)\leq
0.51\cdot v(\mathcal{Q}^{\prime\prime})$, the set of paths in
$\mathcal{Q}^{\prime\prime}$ that survives the ultimate price has total value
at least $0.49\cdot v(\mathcal{Q}^{\prime\prime})$. We denote this set by
$\hat{\mathcal{Q}^{\prime\prime}}$. Since all path in
$\mathcal{Q}^{\prime\prime}$ has length $[L,2L)$ and value
$(\hat{v},2\hat{v}]$, $|\hat{\mathcal{Q}}^{\prime\prime}|\geq
0.49|\mathcal{Q}^{\prime\prime}|/4\geq 0.1|\mathcal{Q}^{\prime\prime}|$.
Denote by $\bar{\mathcal{Q}}$ the resulting set of paths that is being taken
in the selling process. It is clear that

  * •

each path $Q^{\prime}\in\bar{\mathcal{Q}}$ has length at least $L^{\prime}$;

  * •

for each path $Q\in\hat{\mathcal{Q}}^{\prime\prime}$, there is a path
$Q^{\prime}\in\bar{\mathcal{Q}}$ that intersects $Q$; and

  * •

each path $Q^{\prime}\in\bar{\mathcal{Q}}$ intersects at most $2\log n$ paths
in $\hat{\mathcal{Q}}^{\prime\prime}$.

Altogether, we get that
$|\bar{\mathcal{Q}}|\geq|\hat{\mathcal{Q}}^{\prime\prime}|/(2\log n)$, the
length of each path in $\bar{\mathcal{Q}}$ is at least $L^{\prime}$, and each
edge of $E(\bar{\mathcal{Q}})$ has price at least $\min_{e\in
E(\hat{\mathcal{Q}}^{\prime\prime})}\left\\{p(e)\right\\}$. Therefore, the
total value of paths in $\bar{\mathcal{Q}}$ is at least

$\frac{|\hat{\mathcal{Q}}^{\prime\prime}|}{2\log n}\cdot
L^{\prime}\cdot\min_{e\in
E(\hat{\mathcal{Q}}^{\prime\prime})}\left\\{p(e)\right\\}\geq\frac{|\hat{\mathcal{Q}}^{\prime\prime}|}{2\log
n}\cdot
L^{\prime}\cdot\Omega\left(\frac{v(\mathcal{Q}^{\prime\prime})}{|\mathcal{Q}^{\prime\prime}|\cdot
L}\right)=\Omega\left(\frac{v(\mathcal{Q}^{\prime\prime})\cdot
L^{\prime}}{L\cdot\log
n}\right)\geq\Omega\left(\frac{\mathsf{OPT}}{m^{1/2-\alpha}\cdot\log^{2}m\log
n}\right),$

where the last inequality is obtained by combining $L\leq m^{1/2+\alpha}$,
$L^{\prime}=m^{1/4-\alpha/2}$ and $\alpha=1/10$.

##  5 Competitive Ratios without the Tie-Breaking Power

In this section, we consider the scenario where the seller does not have the
tie-breaking power.

###  5.1 Path

We first focus on the case when $G$ is a single path. Unlike the scenario with
tie-breaking power, where the optimal welfare can be obtained with some set of
prices (Theorem 3.1), the competitive ratio may be strictly larger than 1 when
the seller has no tie-breaking power.

######  Theorem 5.1.

$\textnormal{{gap}}_{\textnormal{{NT}}}(\mathsf{Path})\geq 3/2$, i.e. there
exists a path graph $G$ and an instance $\mathcal{F}$, such that any set of
prices achieves worst-case welfare at most
$2/3\cdot\mathsf{OPT}(G,\mathcal{F})$, when the seller has no tie-breaking
power.

###### Proof.

Let $G$ be a path consisting of three edges $e_{1},e_{2},e_{3}$, that appears
on the path in this order. The instance is described below.

  * •

Buyer 1 demands the path consisting of a single edge $e_{1}$, with value $1$;

  * •

Buyer 2 demands the path consisting of a single edge $e_{3}$, with value $1$;

  * •

Buyer 3 demands the path consisting of edges $e_{1},e_{2}$, with value $2$;
and

  * •

Buyer 4 demands the path consisting of edges $e_{2},e_{3}$, with value $2$.

It is clear that the optimal allocation is assigning $e_{1}$ to buyer 1 and
$e_{2},e_{3}$ to buyer 4 (or assigning $e_{3}$ to buyer 2 and $e_{1},e_{2}$ to
buyer 3). The optimal welfare $\mathsf{OPT}(G,\mathcal{F})=3$. We now show
that, for any prices $p_{1},p_{2},p_{3}$, there is an order $\sigma$ of the
four buyers such that the obtained welfare is at most $2$, when the seller has
no tie-breaking power. We distinguish between two cases.

Case 1. $p_{1}\leq 1$ and $p_{3}\leq 1$. We let buyers 1 and 3 come first and
take edges $e_{1}$ and $e_{3}$ respectively. Note that the seller does not
have the tie-breaking power. The buyer can decide whether or not to take the
path when the price equals the value. Now buyers 3 and 4 cannot get their
paths. So the obtained welfare is $2$.

Case 2. $p_{1}>1$ or $p_{3}>1$. Assume without loss of generality that
$p_{1}>1$. If $p_{2}+p_{3}\leq 2$, then we let buyer 4 come first and take
edges $e_{2}$ and $e_{3}$. It is clear that no other buyer can get her path.
So the total welfare is 2. If $p_{2}+p_{3}>2$, then $p_{1}+p_{2}+p_{3}>3$.
Note that it is impossible in this case all edges are sold, since the
hindsight optimal welfare is 3. Therefore, the obtained welfare is at most
$2$. ∎

In Theorem 5.2 we prove that the competitive ratio $3/2$ is tight for path
graphs, when the seller has no tie-breaking power.

######  Theorem 5.2.

$\textnormal{{gap}}_{\textnormal{{NT}}}(\mathsf{Path})\leq 3/2$. Moreover, the
prices that achieve the competitive ratio 3/2 can be computed efficiently.

###### Proof.

From Theorem 3.1, (LP-Primal) has an integral optimal solution. We denote by
$y^{*}$ the integral optimal solution of (LP-Primal) that maximizes
$\sum_{j\in[n]}y^{*}_{j}$. Note that $y^{*}$ can be computed by solving a
slightly different LP that is obtained from (LP-Primal) by changing its
objective to $\sum_{j\in[n]}(v_{j}+\varepsilon^{\prime})\cdot y_{j}$, for some
small enough $\varepsilon^{\prime}>0$. Define $Y=\left\\{j\mid
y^{*}_{j}=1\right\\}$ and $\mathcal{Q}_{Y}=\left\\{Q_{j}\mid
y^{*}_{j}=1\right\\}$.

######  Lemma 5.1.

There is an $\varepsilon>0$ and an optimal solution
$\left\\{p^{*}(e)\right\\}_{e\in E(G)}$ for (LP-Dual), such that (i) for each
edge $e\in E(\mathcal{Q}_{Y})$, $p^{*}(e)\geq\varepsilon$; and (ii) for each
$j\in[m]$, either $p^{*}(Q_{j})=v_{j}$, or $p^{*}(Q_{j})>v_{j}+m\varepsilon$.

Proof of Lemma 5.1: Let
$\varepsilon^{\prime}=\frac{1}{m^{2}}\cdot\min_{j}v_{j}$. We construct another
instance $\mathcal{F}^{\prime}$ from $\mathcal{F}$ as follows. We add, for
each $e\in E(G)$ a new buyer demanding the path consisting of a single edge
$e$ with value $\varepsilon^{\prime}$. On one hand, it is easy to see that
$y^{*}$ is still an optimal solution of this new instance. Let $p^{*}$ be any
optimal solution for the corresponding dual LP for the new instance
$\mathcal{F}$. Define
$\varepsilon^{\prime\prime}=\frac{1}{2m}\min_{j:p*(Q_{j})>v_{j}}(p^{*}(Q_{j})-v_{j})$
and $\varepsilon=\min\\{\varepsilon^{\prime},\varepsilon^{\prime\prime}\\}$.
Clearly $p^{*}$ is also an optimal dual solution for the instance
$\mathcal{F}$ and satisfies both properties. $\Box$

Now choose $\varepsilon>0$ and the prices $p^{*}$ from Lemma 5.1. We define
$A=\left\\{j\mid v_{j}=p^{*}(Q_{j})\right\\}$ and
$\mathcal{Q}_{A}=\left\\{Q_{j}\mid j\in A\right\\}$.

######  Definition 5.1.

We say that a set $\mathcal{Q}\subseteq\mathcal{Q}_{A}$ of edge-disjoint paths
is _good_ , iff set $\mathcal{Q}_{A}\setminus\mathcal{Q}$ does not contain
another subset $\mathcal{Q}^{\prime}$ of $|\mathcal{Q}^{\prime}|\geq 2$ edge-
disjoint paths, such that
$\bigcup_{j:Q_{j}\in\mathcal{Q}^{\prime}}Q_{j}=\bigcup_{j:Q_{j}\in\mathcal{Q}}Q_{j}$.

We prove the following lemma about good edge-disjoint paths.

######  Lemma 5.2.

There is an efficient algorithm that, given a good set $\mathcal{Q}$ of edge-
disjoint paths, computes a set of positive prices $p=\\{p(e)\\}_{e\in
E(\mathcal{Q})}$ that achieves worst-case welfare at least
$\sum_{Q_{j}\in\mathcal{Q}}v_{j}$.

###### Proof.

We denote $I=\bigcup_{Q_{j}\in\mathcal{Q}}Q_{j}$ and
$\mathcal{Q}_{I}=\\{Q_{j}\in\mathcal{Q}_{A}\mid Q_{j}\subseteq I\\}$. First,
for each edge $e\notin E(I)$, we set its price $p(e)=+\infty$. Therefore, all
buyers $j$ with $Q_{j}\notin\mathcal{Q}_{I}$ cannot get her demand path. We
will show that we can efficiently compute prices $\left\\{p(e)\right\\}_{e\in
E(I)}$ for edges of $I$, such that (i) for each path $Q_{j}\in\mathcal{Q}$,
$v_{j}>p(Q_{j})$; and (ii) for each path
$Q_{j}\in\mathcal{Q}_{I}\setminus\mathcal{Q}$, $v_{j}<p(Q_{j})$. It is clear
that the set $\left\\{p(e)\right\\}_{e\in E(G)}$ of prices achieves worst-case
welfare $\sum_{Q_{j}\in\mathcal{Q}}v_{j}$.

The existence of prices $\left\\{p(e)\right\\}_{e\in E(I)}$ is equivalent to
the feasibility of the following system.

$\left\\{\begin{array}[]{cccc}\displaystyle\sum_{e\in
Q_{j}}p(e)&<&v_{j},&\forall Q_{j}\in\mathcal{Q};\\\ \displaystyle\sum_{e\in
Q_{j}}p(e)&>&v_{j},&\forall
Q_{j}\in\mathcal{Q}_{I}\setminus\mathcal{Q}.\end{array}\right.$ (3)

From the definition of $A$, and since
$\mathcal{Q}_{I}\subseteq\mathcal{Q}_{A}$, for each path
$Q_{j}\in\mathcal{Q}_{I}$, $\sum_{e\in Q_{j}}p^{*}(e)=v_{j}$. We denote
$\alpha(e)=p(e)-p^{*}(e)$ for all $e\in E(I)$, then system (3) is feasible if
the following system is feasible, for some small enough
$\varepsilon^{\prime}>0$.

$\left\\{\begin{array}[]{cccc}\displaystyle\sum_{e\in
Q_{j}}\alpha(e)&\leq&-\varepsilon^{\prime},&\forall Q_{j}\in\mathcal{Q};\\\
\displaystyle\sum_{e\in Q_{j}}\alpha(e)&\geq&\varepsilon^{\prime},&\forall
Q_{j}\in\mathcal{Q}_{I}\setminus\mathcal{Q}.\end{array}\right.$ (4)

From Farkas’ Lemma, system (4) is feasible if and only if the following system
is infeasible.

$\left\\{\begin{array}[]{rccc}\displaystyle\sum_{Q_{j}\in\mathcal{Q}}\beta_{j}\cdot\mathbbm{1}[e\in
Q_{j}]-\sum_{Q_{j}\in\mathcal{Q}_{I}\setminus\mathcal{Q}}\beta_{j}\cdot\mathbbm{1}[e\in
Q_{j}]&=&0,&\forall e\in E(I);\\\
\displaystyle\sum_{Q_{j}\in\mathcal{Q}_{I}}\beta_{j}&>&0;\\\
\beta_{j}&\in&[0,1],&\forall Q_{j}\in\mathcal{Q}_{I}.\end{array}\right.$ (5)

where the additional constraints $\beta_{j}\leq 1,\forall
Q_{j}\in\mathcal{Q}_{I}$ will not influence the feasibility of the system due
to scaling. Next we will prove that system (5) is feasible iff it admits an
integral solution.

######  Definition 5.2.

We say that a matrix $A$ is _totally unimodular_ iff the determinant of every
square submatrix of $A$ belongs to $\\{0,-1,+1\\}$.

######  Lemma 5.3 (Folklore).

If a matrix $A\in\mathbb{R}^{n\times m}$ is totally unimodular and a vector
$b\in\mathbb{R}^{n}$ is integral, then every extreme point of the polytope
$\\{x\in\mathbb{R}^{m}\mid Ax\leq b,x\geq 0\\}$ is integral.

######  Lemma 5.4 ([47]).

A matrix $A\in\mathbb{R}^{n\times m}$ is totally unimodular iff for any subset
$R\subseteq[n]$, there exists a partition $R=R_{1}\cup R_{2}$, $R_{1}\cap
R_{2}=\emptyset$, such that for any $j\in[m]$,

$\sum_{i\in R_{1}}a_{ij}-\sum_{i\in R_{2}}a_{ij}\in\\{0,-1,+1\\}.$

######  Lemma 5.5.

System (5) is feasible if and only if it admits an integral solution.

###### Proof.

We prove that the coefficient matrix $C$ in system (5) is totally
unimodular.333The second inequality in system (5) is strict inequality. We can
modify it to an equivalent inequality
$\sum_{j:Q_{j}\in\mathcal{Q}}\beta_{j}\geq\varepsilon_{0}$ for some
sufficiently small $\varepsilon_{0}>0$ and then apply Lemma 5.3. For any set
of rows $R=\\{i_{1},i_{2},\cdots,i_{k}\\}$ such that
$i_{1}<i_{2}<\cdots<i_{k}$, We define the partition
$R_{1}=\\{i_{1},i_{3},i_{5},...\\}$ be the set with odd index and
$R_{2}=\\{i_{2},i_{4},i_{6},...\\}$ be the set with even index. For every
column $j$, $Q_{j}$ is an subpath and thus the ones (or -1s for
$Q_{j}\in\mathcal{Q}_{I}\setminus\mathcal{Q}$) in the vector
$(C_{ij})_{i=1}^{m}$ are consecutive. Hence the difference between $\sum_{i\in
R_{1}}C_{ij}$ and $\sum_{i\in R_{2}}C_{ij}$ is at most 1. By Lemma 5.4, $C$ is
totally unimodular. ∎

Assume for contradiction that (5) is feasible, let
$\beta^{*}\in\left\\{0,1\right\\}^{\mathcal{Q}_{I}}$ be an integral solution
of (5). Note that the constraints
$\sum_{j:Q_{j}\in\mathcal{Q}}\beta^{*}_{j}\cdot\mathbbm{1}[e\in
Q_{j}]-\sum_{j:Q_{j}\in\mathcal{Q}_{I}\setminus\mathcal{Q}}\beta^{*}_{j}\cdot\mathbbm{1}[e\in
Q_{j}]=0,\forall e\in E(I)$ and the fact that paths of $\mathcal{Q}$ are edge-
disjoint imply that the paths in set
$\mathcal{Q}^{\prime}=\\{Q_{j}\mid\beta_{j}=1\\}$ are edge-disjoint. Note that
$\mathcal{Q}^{\prime}\cap\mathcal{Q}=\emptyset$ and
$\bigcup_{Q_{j}\in\mathcal{Q}^{\prime}}Q_{j}=\bigcup_{Q_{j}\in\mathcal{Q}}Q_{j}$,
and this is a contradiction to the assumption that the set $\mathcal{Q}$ is
good. Therefore, system (5) is infeasible, and thus system (4) is feasible.
Let $(\alpha(e))_{e\in E(I)}$ be a solution of system (4), such that
$\sum_{e\in E(I)}|\alpha(e)|\leq\varepsilon$. It is clear that such a solution
exists due to scaling. We set $p(e)=p^{*}(e)+\alpha(e)$ for all $e\in E(I)$,
and it is clear that the prices $\left\\{p(e)\right\\}_{e\in E(G)}$ satisfy
all the properties of Lemma 5.2. Moreover, prices $\left\\{p(e)\right\\}_{e\in
E(G)}$ are positive. ∎

We now complete the proof of Theorem 5.2 using Lemma 5.2.

We denote $\mathcal{Q}_{Y}=\left\\{Q_{1},Q_{2},\ldots,Q_{k}\right\\}$, where
the paths are indexed according to the order in which they appear on $G$.
First, for each edge $e\notin E(\mathcal{Q}_{Y})$, we set its price
$\tilde{p}(e)=+\infty$. Therefore, any buyer $j$ with $e\in Q_{j}$ cannot take
her demand path. In fact, we may assume without loss of generality that
$\bigcup_{1\leq j\leq k}Q_{j}=G$, since otherwise we can view each connected
component (which is also a path) of graph $\bigcup_{1\leq j\leq k}Q_{j}$ as
the whole graph, and compute prices for its edges separately.

We will compute three sets
$\hat{\mathcal{Q}}_{1},\hat{\mathcal{Q}}_{2},\hat{\mathcal{Q}}_{3}\subseteq\mathcal{Q}_{A}$
of edge-disjoint paths, such that

  1. 1.

every edge of $E(G)$ is contained in exactly two paths of
$\hat{\mathcal{Q}}_{1},\hat{\mathcal{Q}}_{2},\hat{\mathcal{Q}}_{3}$; and

  2. 2.

for each $t\in\left\\{1,2,3\right\\}$, if we further partition the set
$\hat{\mathcal{Q}}_{t}$ into subsets
$\hat{\mathcal{Q}}^{1}_{t},\ldots,\hat{\mathcal{Q}}^{r_{t}}_{t}$, such the
union of the paths in each set $\hat{\mathcal{Q}}^{1}_{t}$ forms a connected
component (which is also a path) of graph
$\bigcup_{Q_{j}\in\hat{\mathcal{Q}}_{t}}Q_{j}$, then each of the sets
$\hat{\mathcal{Q}}^{1}_{t},\ldots,\hat{\mathcal{Q}}^{r_{t}}_{t}$ is a good set
of edge-disjoint paths.

By definition,
$\sum_{Q_{j}\in\hat{\mathcal{Q}}_{1}}v_{j}+\sum_{Q_{j}\in\hat{\mathcal{Q}}_{2}}v_{j}+\sum_{Q_{j}\in\hat{\mathcal{Q}}_{3}}v_{j}=2\cdot\mathsf{OPT}(G,\mathcal{F})$.
Assume without loss of generality that
$\sum_{Q_{j}\in\hat{\mathcal{Q}}_{1}}v_{j}\geq(2/3)\cdot\mathsf{OPT}(G,\mathcal{F})$.
Then from Lemma 5.2, there exist prices $\left\\{\tilde{p}(e)\right\\}_{e\in
E(\mathcal{Q}_{Y})}$ that achieves worst-case welfare at least
$\sum_{Q_{j}\in\hat{\mathcal{Q}}_{1}}v_{j}\geq(2/3)\cdot\mathsf{OPT}(G,\mathcal{F})$.

#### Compute the sets
$\hat{\mathcal{Q}}_{1},\hat{\mathcal{Q}}_{2},\hat{\mathcal{Q}}_{3}$.

We now compute the desired sets
$\hat{\mathcal{Q}}_{1},\hat{\mathcal{Q}}_{2},\hat{\mathcal{Q}}_{3}$ of edge-
disjoint paths, which, from the above discussion, completes the proof of
Theorem 5.2.

We start by defining $\hat{\mathcal{Q}}$ to be the multi-set that contains,
for each path $Q_{j}\in\mathcal{Q}_{Y}$, two copies
$Q^{\prime}_{j},Q^{\prime\prime}_{j}$ of $Q_{j}$. We initially set

  * •

$\hat{\mathcal{Q}}_{1}=\left\\{Q^{\prime}_{6r+3},Q^{\prime}_{6r+4}\mid 1\leq
r\leq
k/6\right\\}\cup\left\\{Q^{\prime\prime}_{6r},Q^{\prime\prime}_{6r+1}\mid
1\leq r\leq k/6\right\\}$;

  * •

$\hat{\mathcal{Q}}_{2}=\left\\{Q^{\prime}_{6r+1},Q^{\prime}_{6r+2}\mid 1\leq
r\leq
k/6\right\\}\cup\left\\{Q^{\prime\prime}_{6r+4},Q^{\prime\prime}_{6r+5}\mid
1\leq r\leq k/6\right\\}$; and

  * •

$\hat{\mathcal{Q}}_{3}=\left\\{Q^{\prime}_{6r+2},Q^{\prime}_{6r+3}\mid 1\leq
r\leq
k/6\right\\}\cup\left\\{Q^{\prime\prime}_{6r+2},Q^{\prime\prime}_{6r+3}\mid
1\leq r\leq k/6\right\\}$.

See Figure 10(a) for an illustration. Clearly, sets
$\hat{\mathcal{Q}}_{1},\hat{\mathcal{Q}}_{2},\hat{\mathcal{Q}}_{3}$ partition
$\hat{\mathcal{Q}}$, each contains edge-disjoint paths, and every edge appears
twice in paths of
$\hat{\mathcal{Q}}_{1},\hat{\mathcal{Q}}_{2},\hat{\mathcal{Q}}_{3}$. However,
sets $\hat{\mathcal{Q}}_{1},\hat{\mathcal{Q}}_{2},\hat{\mathcal{Q}}_{3}$ may
not satisfy Property 2. We will then iteratively modify sets
$\hat{\mathcal{Q}}_{1},\hat{\mathcal{Q}}_{2},\hat{\mathcal{Q}}_{3}$, such that
at the end Property 2 is satisfied.

Throughout, we also maintain graphs
$G_{t}=\bigcup_{Q\in\hat{\mathcal{Q}}_{t}}Q$, for each
$t\in\left\\{1,2,3\right\\}$. As sets
$\hat{\mathcal{Q}}_{1},\hat{\mathcal{Q}}_{2},\hat{\mathcal{Q}}_{3}$ change,
graphs $G_{1},G_{2},G_{3}$ evolve. We start by scanning the path $G$ from left
to right, and process, for each each connected component of graphs
$G_{1},G_{2},G_{3}$, as follows.

We first process the connected component in $G_{1}$ formed by the single path
$Q_{1}^{\prime\prime}$. Clearly, set $\left\\{Q_{1}^{\prime\prime}\right\\}$
is good, since if there are other paths
$\hat{Q},\hat{Q}^{\prime}\in\mathcal{Q}_{A}$ such that
$\hat{Q},\hat{Q}^{\prime}$ are edge-disjoint and
$\hat{Q}\cup\hat{Q}^{\prime}=Q_{1}$, then the set
$\left\\{\hat{Q},\hat{Q}^{\prime},Q_{2},\ldots,Q_{k}\right\\}$ corresponds to
another integral optimal solution $\hat{y}^{*}$ of (LP-Primal) with
$\sum_{j\in[n]}\hat{y}^{*}_{j}=k+1>k=\sum_{j\in[n]}\hat{y}^{*}_{j}$, a
contradiction to the definition of $y^{*}$. We do not modify path
$Q^{\prime\prime}_{1}$ in $\hat{\mathcal{Q}}_{1}$ and continue to the next
iteration.

We then process the connected component in $G_{2}$ formed by the paths
$Q_{1}^{\prime},Q_{2}^{\prime}$. If the set
$\left\\{Q_{1}^{\prime},Q_{2}^{\prime}\right\\}$ is good, then we do not
modify this component and continue to the next iteration. Assume now that the
set $\left\\{Q_{1}^{\prime},Q_{2}^{\prime}\right\\}$ is not good. From similar
arguments, there exist two other paths
$Q^{*}_{1},Q^{*}_{2}\in\mathcal{Q}_{A}$, such that $Q^{*}_{1},Q^{*}_{2}$ are
edge-disjoint and $Q^{*}_{1}\cup Q^{*}_{2}=Q_{1}\cup Q_{2}$. We then replace
the paths $Q^{\prime}_{1},Q^{\prime}_{2}$ in $\hat{\mathcal{Q}}_{2}$ by paths
$Q^{*}_{1},Q^{*}_{2}$. Let $v^{*}_{1}$ be the vertex shared by paths
$Q^{*}_{1},Q^{*}_{2}$, so $v^{*}_{1}\neq v_{1}$. We distinguish between the
following cases.

Case 1. $v^{*}_{1}$ is to the left of $v_{1}$ on path $G$. As shown in Figure
10(b), we keep the path $Q^{*}_{2}$ in $\hat{\mathcal{Q}}_{2}$, and move path
$Q^{*}_{1}$ to $\hat{\mathcal{Q}}_{3}$. Clearly, we create two new connected
components: one in $G_{3}$ formed by a single path $Q^{*}_{1}$, and the other
in $G_{2}$ formed by a single path $Q^{*}_{2}$. From similar arguments, the
corresponding singleton sets
$\left\\{Q^{*}_{1}\right\\},\left\\{Q^{*}_{2}\right\\}$ are good.

Case 2. $v^{*}_{1}$ is to the right of $v_{1}$ on path $G$. As shown in Figure
10(c), we keep the path $Q^{*}_{2}$ in $\hat{\mathcal{Q}}_{2}$, move path
$Q^{*}_{1}$ to $\hat{\mathcal{Q}}_{1}$ and additionally move the path
$Q^{\prime}_{1}$ processed in previous iteration to $\hat{\mathcal{Q}}_{2}$.
Clearly, we create two new connected components: one in $G_{1}$ formed by a
single path $Q^{*}_{1}$, and the other in $G_{2}$ formed by a single path
$Q^{*}_{2}$. From similar arguments, the corresponding singleton sets
$\left\\{Q^{*}_{1}\right\\},\left\\{Q^{*}_{2}\right\\}$ are good. Note that we
have additionally moved $Q^{\prime}_{1}$ to $\hat{\mathcal{Q}}_{2}$, but since
we did not change the corresponding component, the singleton set
$\left\\{Q^{\prime}_{1}\right\\}$ is still good.

(a) An illustration of paths in set
$\hat{\mathcal{Q}}_{1}\cup\hat{\mathcal{Q}}_{2}\cup\hat{\mathcal{Q}}_{3}$ at
the beginning.

(b) An illustration of path modification in Case 1.

(c) An illustration of path modification in Case 2.

(d) How old and new paths/components may possibly interact.

Figure 10: Illustrations of the algorithm for computing path sets
$\hat{\mathcal{Q}}_{1},\hat{\mathcal{Q}}_{2},\hat{\mathcal{Q}}_{3}$.

We continue processing the remaining connected components in the same way
until all components are good. We will show that, every time a connected
component is not good and the corresponding two paths are replaced with two
new paths, the connected components in $G_{1},G_{2},G_{3}$ that we have
processed in previous iterations will stay good. Therefore, the algorithm will
end up producing good components in $G_{1},G_{2},G_{3}$ consisting of a good
set of one or two edge-disjoint paths.

To see why this is true, consider an iteration where we are processing a
component consisting of paths $Q^{\prime\prime}_{i},Q^{\prime\prime}_{i+1}$,
and there exists edge-disjoint paths $Q^{*}_{i},Q^{*}_{i+1}$ such that
$Q^{*}_{i}\cup Q^{*}_{i+1}=Q^{\prime\prime}_{i}\cup Q^{\prime\prime}_{i+1}$,
while the endpoint $v^{*}_{i}$ shared by $Q^{*}_{i}$ and $Q^{*}_{i+1}$ is an
endpoint of a processed component, as shown in Figure 10(d). Note that this is
the only possibility that the new components may influence the previous
components, However, we will show that this is impossible. Note that
$Q^{\prime\prime}_{i}\in\mathcal{Q}_{Y}$. We denote by $Q^{r}$ the path with
endpoints $v^{*}_{i}$ and $v_{i}$, then clearly paths $Q^{*}_{i},Q^{r}$ are
not in $\mathcal{Q}_{Y}$, edge-disjoint and satisfy that $Q_{i}=Q^{*}_{i}\cup
Q^{r}$. Consider now the set
$(\mathcal{Q}_{Y}\setminus\left\\{Q_{i}\right\\})\cup\left\\{Q^{*}_{i},Q^{r}\right\\}$.
It is clear that this set corresponds to another integral optimal solution
$\hat{y}^{*}$ of (LP-Primal) with
$\sum_{j\in[n]}\hat{y}^{*}_{j}=k+1>k=\sum_{j\in[n]}\hat{y}^{*}_{j}$, a
contradiction to the definition of $y^{*}$. ∎

###  5.2 Other Special Families of Graphs

We bound the competitive ratio for the no tie-breaking case, when $G$ is in
special families of graphs discussed in Section 3. For star and spider graphs,
we prove that the competitive ratios are at most $2$ and $7/2$ respectively.

######  Theorem 5.3.

For any $\varepsilon>0$,
$\textnormal{{gap}}_{\textnormal{{NT}}}(\mathsf{Star})\leq 2+\varepsilon$.
Moreover, the prices that achieve the competitive ratio $2+\varepsilon$ can be
computed efficiently.

###### Proof.

The optimal allocation can be computed efficiently by [49]. Let $\mathcal{Q}$
be the set of paths in the optimal allocation, so
$\mathsf{OPT}=\sum_{j:Q_{j}\in\mathcal{Q}}v_{j}$. We set the prices on the
edges of $G$ as follows. Let $\varepsilon^{\prime}=\varepsilon/5$. For each
path $Q_{j}\in\mathcal{Q}$, if it contains a single edge $e_{i}$, then we set
the price of $e_{i}$ to be $(1-\varepsilon^{\prime})\cdot v_{j}$; if it
contains two edges $e_{i},e_{i^{\prime}}$, then we set the price of both
$e_{i}$ and $e_{i^{\prime}}$ to be $(\frac{1}{2}-\varepsilon^{\prime})\cdot
v_{j}$. For each edges that does not belong to any path of $\mathcal{Q}$, we
set its price to be $+\infty$.

We now show that the above prices will achieve worst-case welfare at least
$(\frac{1}{2}-\varepsilon^{\prime})\cdot\mathsf{OPT}$. For a path $Q_{j}$ that
contains a single edges $e_{i}$, clearly $e_{i}$ will be taken by some buyer
(not necessarily $j$) at price $(1-\varepsilon^{\prime})\cdot v_{j}$, for any