arriving order $\sigma$. For a path $Q_{j^{\prime}}$ that contains two edges
$e_{i},e_{i^{\prime}}$, we notice that buyer $j^{\prime}$ can afford her
demand path. Thus for any order $\sigma$, at least one of
$e_{i},e_{i^{\prime}}$ will be sold at price
$(\frac{1}{2}-\varepsilon^{\prime})\cdot v_{j^{\prime}}$, otherwise buyer
$j^{\prime}$ must have purchased $Q_{j^{\prime}}$. Hence for any order
$\sigma$, the total price of the sold edges is at least
$(\frac{1}{2}-\varepsilon^{\prime})\cdot\mathsf{OPT}$. Since all buyers have
non-negative utility, the worst-case welfare is also at least
$(\frac{1}{2}-\varepsilon^{\prime})\cdot\mathsf{OPT}\geq\frac{\mathsf{OPT}}{2+\varepsilon}$.
∎

######  Theorem 5.4.

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

###### Proof.

Let $\mathcal{Q}$ be the set of paths in the optimal allocation. We define
$\mathcal{Q}_{1}$ to be the set of all paths in $\mathcal{Q}$ that contains
the center of the spider, and we define
$\mathcal{Q}_{2}=\mathcal{Q}\setminus\mathcal{Q}_{1}$. For each path
$Q\in\mathcal{Q}_{1}$, let $j_{Q}$ be the buyer who is allocated her demand
path $Q$ in the optimal allocation. Define $G_{Q}$ to be the graph obtained by
taking the union of all (one or two) legs whose edge sets intersect with
$E(Q)$, and we denote $E_{Q}=E(G_{Q})$. Since paths in $\mathcal{Q}_{1}$ are
edge-disjoint, clearly for any $Q,Q^{\prime}\in\mathcal{Q}_{1}$, $E_{Q}\cap
E_{Q^{\prime}}=\emptyset$. For any edge set $E$, let
$\mathcal{F}|_{E}\subseteq\mathcal{F}$ be the sub-instance that contains all
buyer $j$ where $Q_{j}$ has edges only in $E$. Then
$\mathsf{OPT}(G,\mathcal{F})=\sum_{Q\in\mathcal{Q}_{1}}\mathsf{OPT}(G_{Q},\mathcal{F}|_{E_{Q}})$.

Let $e_{Q,1}$ and $e_{Q,2}$ be the two edges that are in Q and has the spider
center as one endpoint.444$e_{Q,1}=e_{Q,2}$ if the spider center is one
endpoint of path $Q$. Define $G^{\prime}_{Q}$ to be the graph with edge set
$E^{\prime}_{Q}=\\{e|e\in E_{Q}\setminus Q\\}$. In other words,
$G^{\prime}_{Q}$ contains all edges not in $Q$ but in $E_{Q}$. Clearly we have
$\mathsf{OPT}(G_{Q},\mathcal{F}|_{E_{Q}})=\mathsf{OPT}(G^{\prime}_{Q},\mathcal{F}|_{E^{\prime}_{Q}})+v_{j_{Q}}$.
Define $G^{\prime\prime}_{Q}$ to be the graph with edge set
$E^{\prime\prime}_{Q}=Q\setminus\\{e_{Q,1},e_{Q,2}\\}$; in other words,
$G^{\prime\prime}_{Q}$ is the graph formed edges in $Q$, but excluding the
center of the spider. Note that $E_{Q}=E^{\prime}_{Q}\cup
E^{\prime\prime}_{Q}\cup\\{e_{Q,1},e_{Q,2}\\}$. See Figure 11 for an
illustration.

Figure 11: An illustration of edge sets. Edges of $E^{\prime}_{Q}$ are shown
in green, and edges of $E^{\prime\prime}_{Q}$ are shown in red.

Let
$\alpha_{Q}=\frac{\mathsf{OPT}(G^{\prime\prime}_{Q},\mathcal{F}|_{E^{\prime\prime}_{Q}})}{v_{j_{Q}}}$.
Clearly $\alpha_{Q}\leq 1$, since $E^{\prime\prime}_{Q}\subseteq Q$. We will
construct the price vector $p$ as follows. For every $Q\in\mathcal{Q}_{1}$, we
will first construct two price vectors $p_{1}$ and $p_{2}$ on $E_{Q}$. Then
depending on the instance, we will either choose $p(e)=p_{1}(e),\forall e\in
E_{Q}$, or $p(e)=p_{2}(e),\forall e\in E_{Q}$. For every
$e\not\in\cup_{Q\in\mathcal{Q}_{1}}E_{Q}$, we set $p(e)=+\infty$. Now fix any
$Q\in\mathcal{Q}_{1}$ and any $\varepsilon^{\prime}>0$.

#### Construction of $p_{1}$.

For each $e\in E^{\prime}_{Q}$, let $p_{1}(e)=+\infty$. For each $e\in
E^{\prime\prime}_{Q}$, let
$p_{1}(e)=p^{*}(e)+\frac{1}{m}\varepsilon^{\prime}$, where
$p^{*}=\\{p^{*}(e)\\}_{e\in E^{\prime\prime}_{Q}}$ is the set of prices from
Theorem 3.1 on $G^{\prime\prime}_{Q}$, whose worst-case welfare is
$\mathsf{OPT}(G^{\prime\prime}_{Q},\mathcal{F}|_{E^{\prime\prime}_{Q}})$. For
$e=e_{Q,1}$ or $e_{Q,2}$,
$p_{1}(e)=\frac{(1-\alpha_{Q})v_{j_{Q}}}{2}-\varepsilon^{\prime}$. Then no
buyer $j$ where $Q_{j}$ contains an edge in $E^{\prime}_{Q}$ can afford her
path. Also, we notice that since $p^{*}$ is the optimal solution in (LP-Dual)
for instance $(G^{\prime\prime}_{Q},\mathcal{F}|_{E^{\prime\prime}_{Q}})$,
every buyer $j$ where $Q_{j}$ has edges only in $E^{\prime\prime}_{Q}$
satisfies $v_{j}\leq p^{*}(Q_{j})$. Thus none of them can afford her path in
$p_{1}$, as $p_{1}(e)<p^{*}(e)$ for all $e\in E^{\prime\prime}_{Q}$. Moreover,
the total price of edges in $Q$ is $\sum_{e\in
E^{\prime\prime}_{Q}}p_{1}(e)+p_{1}(e_{Q,1})+p_{1}(e_{Q,2})<\mathsf{OPT}(G^{\prime\prime}_{Q},\mathcal{F}|_{E^{\prime\prime}_{Q}})+\varepsilon^{\prime}+(1-\alpha_{Q})v_{j_{Q}}-2\varepsilon^{\prime}<v_{j_{Q}}$.
Consider any item pricing $p$ such that $p(e)=p_{1}(e),\forall e\in E_{Q}$.
From the arguments above, only buyer $j$ whose $Q_{j}$ contains $e_{Q,1}$ or
$e_{Q,2}$ may afford her path. Thus at least one of $e_{Q,1}$ and $e_{Q,2}$
must be sold under $p$ at price
$\frac{(1-\alpha_{Q})v_{j_{Q}}}{2}-\varepsilon^{\prime}$, for any buyers’
arriving order $\sigma$. Otherwise, all edges in $E^{\prime\prime}_{Q}$ must
also be unsold and buyer $j_{Q}$ should have purchased her path $Q$,
contradiction. Thus the contributed welfare from edges in $E_{Q}$ is at least
$\frac{(1-\alpha_{Q})v_{j_{Q}}}{2}-\varepsilon^{\prime}$.

#### Construction of $p_{2}$.

For each $e\in E^{\prime}_{Q}\cup E^{\prime\prime}_{Q}$, let $p_{2}(e)$ be the
price of edge $e$ by applying Theorem 5.2 to $G^{\prime}_{Q}\cup
G^{\prime\prime}_{Q}$, which is a union of at most two path graphs. For
$e=e_{Q,1}$ or $e_{Q,2}$, set $p_{2}(e)=+\infty$. Then by Theorem 5.2, if
$p(e)=p_{2}(e),\forall e\in E_{Q}$, the contributed welfare from edges in
$E_{Q}$ is at least $\frac{2}{3}\mathsf{OPT}(G^{\prime}_{Q}\cup
G^{\prime\prime}_{Q},\mathcal{F}|_{G^{\prime}_{Q}\cup
G^{\prime\prime}_{Q}})=\frac{2}{3}\mathsf{OPT}(G^{\prime}_{Q},\mathcal{F}|_{G^{\prime}_{Q}})+\frac{2}{3}\mathsf{OPT}(G^{\prime\prime}_{Q},\mathcal{F}|_{G^{\prime\prime}_{Q}})=\frac{2}{3}\mathsf{OPT}(G^{\prime}_{Q},\mathcal{F}|_{E^{\prime}_{Q}})+\frac{2}{3}\alpha_{Q}v_{j_{Q}}$,
for any buyers’ arriving order $\sigma$.

Now for any $Q\in\mathcal{Q}_{1}$, we choose the price with a higher
contributed welfare: If
$\frac{(1-\alpha_{Q})v_{j_{Q}}}{2}-\varepsilon^{\prime}>\frac{2}{3}\mathsf{OPT}(G^{\prime}_{Q},\mathcal{F})+\frac{2}{3}\alpha_{Q}v_{j_{Q}}$,
we choose $p(e)=p_{1}(e),\forall e\in E_{Q}$ and choose $p(e)=p_{2}(e)$
otherwise. Thus the worst-case welfare of item pricing $p$ is at least

$\displaystyle\sum_{Q\in\mathcal{Q}_{1}}\max\left(\frac{(1-\alpha)v_{j_{Q}}}{2}-\varepsilon^{\prime},\frac{2}{3}\mathsf{OPT}(G^{\prime}_{Q},\mathcal{F}|_{E^{\prime}_{Q}})+\frac{2}{3}\alpha_{Q}v_{j_{Q}}\right)$
$\displaystyle\geq$
$\displaystyle\sum_{Q\in\mathcal{Q}_{1}}\frac{4}{7}\left(\frac{(1-\alpha)v_{j_{Q}}}{2}-\varepsilon^{\prime}\right)+\frac{3}{7}\left(\frac{2}{3}\mathsf{OPT}(G^{\prime}_{Q},\mathcal{F}|_{E^{\prime}_{Q}})+\frac{2}{3}\alpha_{Q}v_{j_{Q}}\right)$
$\displaystyle=$
$\displaystyle\sum_{Q\in\mathcal{Q}_{1}}\left(\frac{2}{7}v_{j_{Q}}+\frac{2}{7}\mathsf{OPT}(G^{\prime}_{Q},\mathcal{F}|_{E^{\prime}_{Q}})-\frac{4}{7}\varepsilon^{\prime}\right)$
$\displaystyle=$
$\displaystyle\sum_{Q\in\mathcal{Q}_{1}}\left(\frac{2}{7}\mathsf{OPT}(G_{Q},\mathcal{F}|_{E_{Q}})-\frac{4}{7}\varepsilon^{\prime}\right)>\frac{2}{7}\mathsf{OPT}(G,\mathcal{F})-\frac{4m}{7}\varepsilon^{\prime}.$

Choosing
$\varepsilon^{\prime}=\frac{\varepsilon\cdot\mathsf{OPT}(G,\mathcal{F})}{10m}$
finishes the proof. By [49], the optimal allocation for any instance on trees
can be computed efficiently. Thus the price vector $p$ can also be computed
efficiently according to the construction above. ∎

For trees, we prove that the competitive ratio is at most 7. Theorem 5.5
follows directly from Lemma 3.6 and Theorem 5.4.

######  Theorem 5.5.

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

For cycles, it is easy to prove that
$\textnormal{{gap}}_{\textnormal{{NT}}}(\mathsf{Cycle})\leq 3$, if we apply
Theorem 5.2 instead of Theorem 3.1 in the proof of Theorem 3.6. In fact, we
show in the following theorem that
$\textnormal{{gap}}_{\textnormal{{NT}}}(\mathsf{Cycle})\leq 2$, with a more
careful analysis. Thus by Theorem 3.7, the competitive ratio 2 is also tight
for the no tie-breaking case.

######  Theorem 5.6.

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

###### Proof.

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\\}$ that maximizes its total value,
maximizes its cardinality. For every $Q\in\mathcal{Q}^{*}$, let $v(Q)$ be the
value of the buyer who receives demand path $Q$ in the optimal allocation
$\mathcal{Q}^{*}$. So
$\mathsf{OPT}(G,\mathcal{F})=\sum_{Q\in\mathcal{Q}^{*}}v(Q)$. We distinguish
between the following cases.

Case 1. $\bigcup_{Q\in\mathcal{Q}^{*}}Q\neq G$. Let $e^{\prime}$ be an edge of
$G$ that does not belong to any path of $\mathcal{Q}^{*}$. We first set the
price of $e^{\prime}$ to be $p(e^{\prime})=+\infty$. Since $G\setminus e$ is a
path, from Theorem 5.2, there exist prices $\left\\{p(e)\right\\}_{e\in
G\setminus e^{\prime}}$ that achieves the worst-case welfare
$\frac{2}{3}\cdot\sum_{Q\in\mathcal{Q}^{*}}v(Q)=\frac{2}{3}\cdot\mathsf{OPT}(G,\mathcal{F})$.

Case 2. $\bigcup_{Q\in\mathcal{Q}^{*}}Q=G$ and $|\mathcal{Q}^{*}|\geq 4$. Let
$Q^{\prime}\in\mathcal{Q}^{*}$ be the path of $\mathcal{Q}^{*}$ with minimum
value. Since $|\mathcal{Q}^{*}|\geq 4$,
$\sum_{Q\in\mathcal{Q}^{*}}v(Q)\geq\frac{3}{4}\cdot\mathsf{OPT}(G,\mathcal{F})$.
We first set the prices for all edges of $Q^{\prime}$ to be $+\infty$. We then
consider the graph $G\setminus Q^{\prime}$. From the similar analysis as in
Case 1, we get that there exist prices $\left\\{p(e)\right\\}_{e\in G\setminus
Q^{\prime}}$ that achieves the worst-case welfare
$\frac{2}{3}\cdot\sum_{Q\in\mathcal{Q}\setminus\left\\{Q^{\prime}\right\\}}v(Q)=\frac{2}{3}\cdot\frac{3}{4}\cdot\mathsf{OPT}(G,\mathcal{F})=\mathsf{OPT}(G,\mathcal{F})/2$.

Case 3. $\bigcup_{Q\in\mathcal{Q}^{*}}Q=G$ and $|\mathcal{Q}^{*}|=2$. Let $Q$
be the path in $\mathcal{Q}^{*}$ with largest value, so
$v(Q)\geq\mathsf{OPT}(G,\mathcal{F})/2$. We first set the prices for all edges
of $G\setminus Q$ to be $+\infty$. From the choice of $\mathcal{Q}^{*}$, there
does not exist a set of edge-disjoint demand paths, whose union is exactly $Q$
and total value equals $v(Q)$. From Lemma 5.2, there exist prices
$\left\\{p(e)\right\\}_{e\in Q}$ that achieves the worst-case welfare
$v(Q)\geq\mathsf{OPT}(G,\mathcal{F})/2$.

Case 4. $\bigcup_{Q\in\mathcal{Q}^{*}}Q=G$ and $|\mathcal{Q}^{*}|=3$. Denote
$\mathcal{Q}^{*}=\left\\{Q_{1},Q_{2},Q_{3}\right\\}$, where the endpoints for
paths $Q_{1}$ ($Q_{2}$ and $Q_{3}$, resp.) are $a,b$ ($b,c$ and $c,a$, resp.).
If some path of $\mathcal{Q}^{*}$ has value less than
$\mathsf{OPT}(G,\mathcal{F})/4$, then we set the prices for all edges of this
path to be $+\infty$, and then from the similar analysis in Case 2, there
exist prices $\left\\{p(e)\right\\}_{e\in G\setminus Q^{\prime}}$ that
achieves the worst-case welfare at least $\mathsf{OPT}(G,\mathcal{F})/2$. Now
assume that $v(Q_{1}),v(Q_{2}),v(Q_{3})\geq\mathsf{OPT}(G,\mathcal{F})/4$. Let
$Q^{\prime}_{1}=Q_{2}\cup Q_{3}$. If there does not exist a set of two edge-
disjoint demand paths, whose union is exactly $Q^{\prime}_{1}$ and total value
equals $v(Q^{\prime}_{1})$, then we set the prices for all edges of $Q_{1}$ to
be $+\infty$, and then from the similar analysis in Case 3, there exist prices
$\left\\{p(e)\right\\}_{e\in G\setminus Q^{\prime}}$ that achieves the worst-
case welfare $v(Q_{2})+v(Q_{3})\geq\mathsf{OPT}(G,\mathcal{F})/2$. Therefore,
there exist demand paths $P_{1},P^{\prime}_{1}$ with $P_{1}\cup
P^{\prime}_{1}=Q_{2}\cup Q_{3}$ and
$v(P_{1})+v(P^{\prime}_{1})=v(Q_{2})+v(Q_{3})$. Similarly, there exist demand
paths $P_{2},P^{\prime}_{2}$ with $P_{2}\cup P^{\prime}_{2}=Q_{3}\cup Q_{1}$
and $v(P_{2})+v(P^{\prime}_{2})=v(Q_{3})+v(Q_{1})$; and there exist demand
paths $P_{3},P^{\prime}_{3}$ with $P_{3}\cup P^{\prime}_{3}=Q_{1}\cup Q_{2}$
and $v(P_{3})+v(P^{\prime}_{3})=v(Q_{1})+v(Q_{2})$. Now consider the path
$P_{1},P^{\prime}_{1},P_{2},P^{\prime}_{2},P_{3},P^{\prime}_{3}$. For similar
reasons, the value of each of these paths is at least
$\mathsf{OPT}(G,\mathcal{F})/4$. From the above discussion, the union of them
contains each edge of $G$ exactly twice. Therefore, either $P_{1}\cup
P^{\prime}_{1}\cup P_{2}$ or $P^{\prime}_{2}\cup P_{3}\cup P^{\prime}_{3}$ is
a path of $G$ with total value at least
$\frac{3}{4}\cdot\mathsf{OPT}(G,\mathcal{F})$. From similar analysis in Case
2, there exist prices $\left\\{p(e)\right\\}_{e\in G\setminus Q^{\prime}}$
that achieves the worst-case welfare
$\frac{2}{3}\cdot\frac{3}{4}\cdot\mathsf{OPT}(G,\mathcal{F})=\mathsf{OPT}(G,\mathcal{F})/2$.
∎

At the last of this section, we consider outerplanar graphs. We show that the
competitive ratio for any instance in the outerplanar graph is also
$O(\log^{2}m)$, in the no tie-breaking case. The proof of Theorem 5.7 is the
same as Theorem 4.3, with the only difference of applying Theorem 5.4 instead
of Theorem 3.4 for spider graphs. The proof is omitted.

######  Theorem 5.7.

$\textnormal{{gap}}_{\textnormal{{NT}}}(\mathsf{Outerplanar})=O(\log^{2}m)$.

##  6 Resource Augmentation

We consider the case where each item has augmented resources. In this section
we prove results in the general combinatorial auction with single-minded
buyers. To distinguish from the tollbooth problem setting, let
$U=\left\\{1,\ldots,m\right\\}$ be the item set. Given a buyer profile
$\mathcal{F}=\left\\{(Q_{j},v_{j})\right\\}_{j\in[n]}$, we denote by
$\mathsf{OPT}(U,\mathcal{F})$ the maximum welfare by allocating items in $U$
to the buyers, such that each item is assigned to at most one buyer. The
seller, however, has more resources to allocate during the selling process.
For each item $i\in U$, the seller has $c$ copies of the item, and each copy
is sold to at most one buyer. In an item-pricing mechanism, the seller is
allowed to set different prices for different copies. Formally, for each item
$i\in U$, the seller sets $c$ prices $p^{1}(i)\leq\ldots\leq p^{c}(i)$, such
that for each $1\leq k\leq c$, the $k$-th copy of item $i$ is sold at price
$p^{k}(i)$. When a buyer comes, if $k-1$ copies of item $i$ has already been
sold, the buyer can purchase item $i$ with price $p^{k}(i)$. Again we define
the worst-case welfare of an item pricing as the minimum welfare among all the
buyers’ arriving order.

With the augmented resources, the seller can certainly achieve more welfare
than in the case with a single unit per item. We show that item pricing can
achieve worst-case welfare $\Omega(m^{-1/c})\cdot\mathsf{OPT}(U,\mathcal{F})$.

######  Theorem 6.1.

For any buyer profile $\mathcal{F}=\left\\{(Q_{j},v_{j})\right\\}_{j\in[n]}$
and any integer $c>0$, there exists a set
$\left\\{p^{k}(i)\mid i\in U,1\leq k\leq c\right\\}$ of prices on items of
$U$, that achieves worst-case welfare
$\Omega(m^{-1/c})\cdot\mathsf{OPT}(U,\mathcal{F})$, even when the seller has
no tie-breaking power.

###### Proof.

Let $\mathcal{Q}=\left\\{Q_{j_{1}},\ldots,Q_{j_{t}}\right\\}$ be an
independent set with maximum total value. Denote
$J=\left\\{j_{1},\ldots,j_{t}\right\\}$, so
$\mathsf{OPT}(U,\mathcal{F})=\sum_{j\in J}v_{j}$. Denote
$v=\mathsf{OPT}(U,\mathcal{F})$.

$U^{\prime}=\bigcup_{Q\in\mathcal{Q}}Q$, so $U^{\prime}\subseteq U$ and
$|U^{\prime}|\leq m$. Note that $v=\sum_{j:Q_{j}\in\mathcal{Q}}v_{j}$. We now
define the prices on items of $U$ as follows. For each element $i\notin
U^{\prime}$, we define $p^{1}(i)=\ldots=p^{c}(i)=+\infty$. For each element
$i\in U^{\prime}$ and for each $1\leq k\leq c$, we define
$p^{k}(i)=\frac{1}{2m}\cdot m^{(k-1)/c}$.

We now show that these prices achieve worst-case welfare $\Omega(v/m^{1/c})$.
Consider the remaining items of $U$ at the end of the selling process.
Clearly, all copies of items in $U\setminus U^{\prime}$ must be unsold. Fix
any buyers’ order. We distinguish between the following cases.

Case 1. Some element of $U^{\prime}$ is sold out. From the definition of
prices in $\left\\{p^{k}(i)\mid i\in U,1\leq k\leq c\right\\}$, for each $i\in
U^{\prime}$, $p^{c}(i)=\frac{v}{2}\cdot m^{-1/c}$. Therefore, if all $c$
copies of the item $i$ are sold, then the $c$-th copy is sold at price
$p^{c}(i)=\frac{v}{2}\cdot m^{-1/c}$. It follows that the welfare is
$\frac{v}{2}\cdot m^{-1/c}=\Omega(v\cdot m^{-1/c})$.

Case 2. No elements of $U^{\prime}$ are sold out. For each $i\in U^{\prime}$,
we define $\tilde{p}(i)=p^{k+1}(i)$ iff $k$ copies of $i$ are sold. Since no
elements of $U^{\prime}$ are sold out, $\tilde{p}(i)$ is well-defined for all
$i\in U^{\prime}$. If $k\geq 1$ copies of item $i$ are sold, the total prices
of the sold copies of $i$ is at least $p^{k}(i)=\tilde{p}(i)\cdot
m^{-1/c}>(\tilde{p}(i)-\frac{v}{2m})m^{-1/c}$; If $k=0$ copies of item $i$ are
sold, it also holds that $(\tilde{p}(i)-\frac{v}{2m})m^{-1/c}=0$. Since each
buyer has a non-negative utility, the total welfare is at least $\sum_{i\in
U^{\prime}}(\tilde{p}(i)-\frac{v}{2m})m^{-1/c}\geq m^{-1/c}\sum_{i\in
U^{\prime}}\tilde{p}(i)-\frac{v}{2}m^{-1/c}$.

Let $\tilde{\mathcal{Q}}\subseteq\mathcal{Q}$ be the demand sets of
$\mathcal{Q}$ that are sold. If
$\sum_{j:Q_{j}\in\tilde{\mathcal{Q}}}v_{j}\geq\frac{v}{4}$, then the welfare
of the pricing is already $\Omega(v\cdot m^{-1/c})$. Otherwise,
$\sum_{j:Q_{j}\in\tilde{\mathcal{Q}}}v_{j}<\frac{v}{4}$, then
$\sum_{j:Q_{j}\in\mathcal{Q}\setminus\tilde{\mathcal{Q}}}v_{j}>\frac{3v}{4}$.
Since none of the buyers in $\mathcal{Q}\setminus\tilde{\mathcal{Q}}$ are
sold, it means that the total prices of all items at the end of the selling
process is at least $\frac{3v}{4}$, since $\sum_{i\in
U^{\prime}}\tilde{p}(i)\geq\sum_{Q\in\mathcal{Q}\setminus\tilde{\mathcal{Q}}}\tilde{p}(Q)\geq\sum_{j:Q_{j}\in\mathcal{Q}\setminus\tilde{\mathcal{Q}}}\tilde{v}_{j}>\frac{3v}{4}$.
The theorem follows since the total welfare is at least $m^{-1/c}\sum_{i\in
U^{\prime}}\tilde{p}(i)-\frac{v}{2}\cdot m^{-1/c}=\Omega(v\cdot m^{-1/c})$. ∎

On the other hand, in Theorem 6.2 we show that a polynomial dependency on $m$
in the competitive ratio is in fact unavoidable.

######  Theorem 6.2.

For any integer $c>0$, there exists a ground set $U$ with $|U|=m$ and a buyer
profile $\mathcal{F}=\left\\{(Q_{j},v_{j})\right\\}_{j\in[n]}$, such that any
set $\left\\{p^{k}(i)\mid i\in U,1\leq k\leq c\right\\}$ of prices achieves
worst-case welfare $O(c\cdot m^{-1/(c+1)})\cdot\mathsf{OPT}(U,\mathcal{F})$,
even the seller has tie-breaking power.

###### Proof.

Let $r$ be the number such that $m=\binom{r}{c+1}$, so $r=O(c\cdot
m^{1/(c+1)})$. Denote $I=\left\\{1,\ldots,r\right\\}$ and let
$U=\left\\{u_{J}\mid J\subseteq I,|J|=c+1\right\\}$, namely $U$ contains
$\binom{r}{c+1}=m$ elements, where each element is indexed by a size-$(c+1)$
subset $J$ of $I$. We define the buyer profile as follows. There are
$(c+1)r+1$ buyers: buyer $B_{0}$, and, for each $1\leq k\leq c+1,1\leq j\leq
r$, a buyer named $B^{k}_{j}$. The demand set for buyer $B_{0}$ is $S_{0}=U$,
and her value is $|U|=\binom{r}{c+1}$. For each $1\leq j\leq r$ and for each
$1\leq k\leq c+1$, the demand set of buyer $B^{k}_{j}$ is
$Q^{k}_{j}=\left\\{u_{J}\mid j\in J\right\\}$, and her value is
$v(S^{k}_{j})=|S^{k}_{j}|=\binom{r-1}{c}$. Clearly optimal allocation when
each item has supply 1 is to assign all elements of $U$ to $B_{0}$, and the
optimal welfare is $\mathsf{OPT}(U,\mathcal{F})=|U|=\binom{r}{c+1}$. Moreover,
it is easy to verify that any $c+1$ demand sets of
$\left\\{Q^{k}_{j}\right\\}_{1\leq k\leq c+1,1\leq j\leq r}$ shares at least
one element of $U$.

We claim that any set of prices can achieve worst-case welfare at most
$c\cdot\binom{r-1}{c}$. Note that this finishes the proof of Theorem 6.2,
since

$\frac{c\cdot\binom{r-1}{c}}{\mathsf{OPT}(U,\mathcal{F})}=\frac{c\cdot\binom{r-1}{c}}{\binom{r}{c+1}}=\frac{c\cdot\binom{r-1}{c}}{\frac{r}{c+1}\cdot\binom{r-1}{c}}=\frac{c(c+1)}{r}=O\left(\frac{c+1}{m^{1/(c+1)}}\right).$

It remains to prove the claim.

Let $\left\\{p^{k}(u)\mid u\in U,1\leq k\leq c\right\\}$ be any set of prices.
We will iteratively construct an order $\sigma$ on buyers, such that if the
buyers come to the auction according to this order, the achieved welfare is at
most $c\cdot\binom{r-1}{c}$. Initially. $\sigma$ is an empty sequence.
Throughout, we maintain a set $\left\\{\tilde{p}(u)\right\\}_{u\in U}$ of
prices, such that at any time, $\tilde{p}(u)$ is the price of the cheapest
available copy of item $u$. Initially, $\tilde{p}(u)=p^{1}(u)$ for all $u\in
U$.

We perform a total of $c$ iterations, and now we fix some $1\leq k\leq c$ and
describe the $k$-th iteration. We first check whether or not there is a set
$Q_{j}^{k}$ with $\tilde{p}(Q_{j}^{k})\leq v(Q_{j}^{k})$. If so, assume
$\tilde{p}(Q_{j_{k}}^{k})\leq v(Q^{k}_{j_{k}})$, then we add the buyer
$B^{k}_{j_{k}}$ to the end of the current sequence $\sigma$, update the price
$\tilde{p}(u)$ for all items $u\in Q^{k}_{j_{k}}$ to their next price in
$\left\\{p^{k}(u)\mid 1\leq k\leq c\right\\}$. And then continue to the next
iteration. Otherwise, since every element of $U$ appears in exactly $c+1$ sets
of $Q^{k}_{1},\ldots,Q^{k}_{r}$, and $\sum_{1\leq j\leq
r}v(Q^{k}_{j})=r\binom{r-1}{c}=(c+1)\binom{r}{c+1}=(c+1)\cdot|U|$, we get that
$\tilde{p}(U)>|U|$. Therefore, no buyer can afford her demand set, and the
welfare will be $0$. In this case, we add all buyers to the end of $\sigma$
and terminate the algorithm.

We now analyze the algorithm. If the algorithm is terminated before it
completes $c$ iterations, then from the construction above, the buyer $B_{0}$
will not get her demand set. Also, since any $c+1$ other demand sets share an
element of $U$, at most $c$ other buyers may get their demand sets. Therefore,
the welfare is at most $c\cdot\binom{r-1}{c}$. Assume that the algorithm
successfully completes $c$ iterations. From the description of the algorithm,
in each iteration, some buyer from $\left\\{B^{k}_{j}\mid 1\leq k\leq
c+1,1\leq j\leq r\right\\}$ will be added to the sequence, and moreover, this
buyer will get her demand set under order $\sigma$. Therefore, after $c$
iterations, we added $c$ distinct buyers to the sequence that will get their
demand sets. Since any $c+1$ demand sets shares an element of $U$, we know
that no other buyer may get her demand set anymore, so the welfare is at most
$c\cdot\binom{r-1}{c}$. ∎

In Theorem 6.3, we prove that a polynomial welfare gap also exists in the
tollbooth problem. We adapt the series-parallel graph $H_{a,b}$ used in
Theorem 4.1 and show that a polynomial competitive ratio is unavoidable in the
tollbooth problem, even each edge has a constant $c$ number of copies. Note
that the benchmark we are comparing to is $\mathsf{OPT}(G,\mathcal{F})$, the
optimal welfare when each edge has supply 1.

######  Theorem 6.3.

In the tollbooth problem, for any constant integer $c>0$, there exists a graph
$G$ with $m$ edges and a buyer profile
$\mathcal{F}=\left\\{(Q_{j},v_{j})\right\\}_{j\in[n]}$, such that any set
$\left\\{p^{k}(e)\mid e\in E(G),k\in[c]\right\\}$ of prices achieves worst-
case welfare $O(m^{-1/(2c+6)})\cdot\mathsf{OPT}(G,\mathcal{F})$.

###### Proof.

We will use the graph $H_{a,b}$ constructed in Theorem 4.1. For convenience,
we will work with the multi-graph $L_{a,b}$. The parameters $a,b$ are set such
that $b=a+2(c+1)^{c+2}a^{c+2}$ and $m=ab$, so $a=\Theta(m^{1/(c+3)})$.

We now define the buyer profile. Recall that in Theorem 4.1 the buyer profile
$\mathcal{F}=\mathcal{F}^{*}\cup(\bigcup_{S\subseteq[a],|S|\geq\sqrt{a}}\mathcal{F}_{S})$,
where $\mathcal{F}^{*}$ contains, for each $r\in[a]$, a buyer $B^{*}_{r}$
demanding the path $Q^{(r)}=(r,r,\ldots,r)$ with value $1$. The buyer profile
$\hat{\mathcal{F}}$ that we will use in this subsection is similar to
$\mathcal{F}$. Specifically, we will keep the buyers in $\mathcal{F}^{*}$, but
will also additionally construct, for each set $S\subseteq[a]$ such that
$|S|\geq\sqrt{ca}$ (instead of $|S|\geq\sqrt{a}$), a set
$\hat{\mathcal{F}}_{S}$ of buyers, whose demand paths and values satisfy the
following properties.

  1. 1.

For each $S$, set $\hat{\mathcal{F}}_{S}$ contains $(c+1)|S|$ buyers, and
every pair $Q,Q^{\prime}$ of demand paths in $\hat{\mathcal{F}}_{S}$ share
some edge, and the value for each demand path is $1+\epsilon$.

  2. 2.

For each demand path $Q$ in $\hat{\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 $\hat{\mathcal{F}}_{S}$ covers the graph
$\bigcup_{r\in S}Q^{(r)}$ exactly $c+1$ times. In other words, for each
$i\in[b]$, the multi-set $\left\\{j^{Q}_{i}\mid
Q\in\hat{\mathcal{F}}_{S}\right\\}$ contains each element of $S$ exactly
twice.

  4. 4.

For any $c+1$ subsets $S_{1},\ldots,S_{c+1}$ of $[a]$, such that
$|S_{t}|\geq\sqrt{ca}$ for each $t\in[c\\!+\\!1]$ and
$\bigcap_{t}S_{t}\neq\emptyset$, for any $c+1$ demand paths
$Q_{1},\ldots,Q_{c+1}$ such that $Q_{t}\in\hat{\mathcal{F}}_{S_{t}}$ for each
$t\in[c\\!+\\!1]$, $\bigcap_{t}E(Q_{t})\neq\emptyset$.

Suppose that we have successfully constructed the sets
$\left\\{\hat{\mathcal{F}}_{S}\right\\}_{S\subseteq[a],|S|\geq\sqrt{ca}}$ that
satisfy the above properties. We then let $\mathcal{F}$ be the union of
$\mathcal{F}^{*}$ and, for each set $S\subseteq[a],|S|\geq\sqrt{ca}$, $c$
distinct copies of set $\hat{\mathcal{F}}_{S}$. In other words, for each buyer
in $\left\\{\hat{\mathcal{F}}_{S}\right\\}_{S\subseteq[a],|S|\geq\sqrt{ca}}$,
we duplicate $c$ buyers and add all of them into our buyer profile. This
completes the description of $\hat{\mathcal{F}}$. From the above properties,
it is easy to see that $\mathsf{OPT}(L_{a,b},\hat{\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}$ may achieve worst-case welfare
$O(\sqrt{ca})$. Since $a=\Theta(m^{1/(c+3)})$,
$\sqrt{a}=\Theta(m^{1/(2c+6)})$, which completes the proof of Theorem 6.3.

Consider now any set $\left\\{p^{k}(e)\mid e\in E(L_{a,b}),k\in[c]\right\\}$
of prices on edges of $L_{a,b}$. From Properties 2 and 4, it is easy to see
that at most $\sqrt{ca}$ buyers from
$\hat{\mathcal{F}}\setminus\mathcal{F}^{*}$ can get their demand paths
simultaneously. We consider the following arrival order of the buyers in
$\hat{\mathcal{F}}$. The buyers in $\hat{\mathcal{F}}$ are divided into
$(c+1)$ groups, where each of the first $c$ groups contains a copy of each
buyer from $(\bigcup_{S\subseteq[a],|S|\geq\sqrt{a}}\mathcal{F}_{S})$, and the
last group contains all buyers of $\mathcal{F}^{*}$. The buyers come to the
auction according to their group index: All buyers from the first group come
first (buyers within the same group come at an arbitrary order), and then all
buyers from the second group come, etc.

Assume that we pause the selling process right after all buyers from the first
$ca$ groups have come. Currently for each edge $e\in E(L_{a,b})$, some copies
of it were taken and there is a price $p^{*}(e)$ on its next copy. We
distinguish between the following two cases.

#### Case 1. At least $\sqrt{ca}$ buyers in $\mathcal{F}^{*}$ can afford their
demand paths at prices $\left\\{p^{*}(e)\right\\}_{e\in E(L_{a,b})}$.

We let $S$ be the set that contains all indices $r\in[a]$ such that the buyer
$B^{*}_{r}$ can afford her demand path $Q^{(r)}$ at prices
$\left\\{p^{*}(e)\right\\}_{e\in E(L_{a,b})}$, so $|S|\geq\sqrt{ca}$. Similar
to Lemma 4.1, it is easy to show that at least one buyer in
$\hat{\mathcal{F}}_{S}$ can afford her demand path, and therefore all $c$
copies of this buyer in $\hat{\mathcal{F}}$ will get their demand paths. This
implies that $p^{*}(Q^{(r)})=+\infty$ for all $r\in S$, contradicting with the
assumption in this case.

#### Case 2. At most $\sqrt{ca}$ buyers in $\mathcal{F}^{*}$ can afford their
demand paths at prices $\left\\{p^{*}(e)\right\\}_{e\in E(L_{a,b})}$.

Similar to Lemma 4.1, the optimal welfare is at most $(2+\epsilon)\sqrt{ca}$.

It remains to construct the sets
$\left\\{\hat{\mathcal{F}}_{S}\right\\}_{S\subseteq[a],|S|\geq\sqrt{ca}}$ that
satisfy the required properties. The construction is almost identical to that
of Theorem 4.1. The only difference is that we need to construct a
$(c+1)s\times b$ matrix $M^{\prime}_{S}$, instead of a $2s\times b$ matrix.
Accordingly, we first place $(c+1)$ copies of matrix $N_{S}$ vertically as the
first $s$ columns of $M^{\prime}_{S}$, and then for the next $b-s$ columns, we
let each column to be each column be an independent random permutation on
elements of the multiset that contains, for each element of $S$, $(c+1)$
copies of it. It is easy to verify that, with $b=a+2(c+1)^{c+2}a^{c+2}$, all
the desired properties are satisfied with high probability.

∎

##  7 Future Work

We study the worst-case welfare of item pricing in the tollbooth problem.
There are several future directions following out results. Firstly, in the
paper we assume that all buyers’ value are all public. A possible future
direction is to study the Bayesian setting where the seller does not have
direct access to each buyer’s value, but only know the buyers’ value
distributions. Secondly, we focus on the tollbooth problem where each buyer
demands a fixed path on a graph. An alternative setting is that each buyer has
a starting vertex and a terminal vertex on the graph, and she has a fixed
value for getting routed through any path on the graph. Such a setting is
equivalent to the tollbooth problem when the underlying graph is a tree, where
a constant competitive ratio is proved in our paper. However, there may exist
more than one path between two vertices in a graph beyond tree, and thus the
buyer is not single-minded in this setting. In the paper we have shown that
item pricing may not approximate the optimal welfare well in the tollbooth
problem. It remains open whether the item pricing performs well in the
alternative setting. Thirdly, the power of tie-breaking hasn’t been studied
much in the literature on mechanism design. It would be interesting to see
other scenarios where the tie-breaking power also makes much difference.

## References

  * [1] K. J. Arrow et al.  An extension of the basic theorems of classical welfare economics.  In Proceedings of the second Berkeley symposium on mathematical statistics and probability. The Regents of the University of California, 1951\.
  * [2] M.-F. Balcan and A. Blum.  Approximation algorithms and online mechanisms for item pricing.  In Proceedings of the 7th ACM Conference on Electronic Commerce, pages 29–35, 2006.
  * [3] B. Berger, A. Eden, and M. Feldman.  On the power and limits of dynamic pricing in combinatorial markets.  In International Conference on Web and Internet Economics, pages 206–219. Springer, 2020.
  * [4] S. Bikhchandani and J. W. Mamer.  Competitive equilibrium in an exchange economy with indivisibilities.  Journal of economic theory, 74(2):385–413, 1997.
  * [5] P. Briest and P. Krysta.  Single-minded unlimited supply pricing on sparse instances.  In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 1093–1102, 2006.
  * [6] I. Caragiannis, A. Filos-Ratsikas, S. K. S. Frederiksen, K. A. Hansen, and Z. Tan.  Truthful facility assignment with resource augmentation: An exact analysis of serial dictatorship.  In International Conference on Web and Internet Economics, pages 236–250. Springer, 2016.
  * [7] S. Chawla, N. R. Devanur, A. E. Holroyd, A. R. Karlin, J. B. Martin, and B. Sivan.  Stability of service under time-of-use pricing.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 184–197, 2017.
  * [8] S. Chawla, J. B. Miller, and Y. Teng.  Pricing for online resource allocation: Intervals and paths.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1962–1981. SIAM, 2019.
  * [9] C. Chekuri, M. Mydlarz, and F. B. Shepherd.  Multicommodity demand flow in a tree and packing integer programs.  ACM Transactions on Algorithms (TALG), 3(3):27–es, 2007.
  * [10] N. Chen, X. Deng, and X. Sun.  On complexity of single-minded auction.  Journal of Computer and System Sciences, 69(4):675–687, 2004.
  * [11] N. Chen and A. Rudra.  Walrasian equilibrium: Hardness, approximations and tractable instances.  Algorithmica, 52(1):44–64, 2008.
  * [12] M. Cheung and C. Swamy.  Approximation algorithms for single-minded envy-free profit-maximization problems with limited supply.  In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 35–44. IEEE, 2008.
  * [13] F. Y. Chin, S.-H. Poon, H.-F. Ting, D. Xu, D. Yu, and Y. Zhang.  Approximation and competitive algorithms for single-minded selling problem.  In International Conference on Algorithmic Applications in Management, pages 98–110. Springer, 2018.
  * [14] J. Chuzhoy and S. Li.  A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2.  Journal of the ACM (JACM), 63(5):1–51, 2016.
  * [15] E. H. Clarke.  Multipart pricing of public goods.  Public choice, pages 17–33, 1971.
  * [16] V. Cohen-Addad, A. Eden, M. Feldman, and A. Fiat.  The invisible hand of dynamic market pricing.  In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 383–400, 2016.
  * [17] G. Debreu.  The coefficient of resource utilization.  Econometrica: Journal of the Econometric Society, pages 273–292, 1951.
  * [18] E. D. Demaine, U. Feige, M. Hajiaghayi, and M. R. Salavatipour.  Combination can be hard: Approximability of the unique coverage problem.  SIAM Journal on Computing, 38(4):1464–1483, 2008.
  * [19] X. Deng, L.-S. Huang, and M. Li.  On walrasian price of cpu time.  Algorithmica, 48(2):159–172, 2007.
  * [20] P. Dutting, M. Feldman, T. Kesselheim, and B. Lucier.  Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs.  SIAM Journal on Computing, 49(3):540–582, 2020.
  * [21] P. Dütting, T. Kesselheim, and B. Lucier.  An o (log log m) prophet inequality for subadditive combinatorial auctions.  ACM SIGecom Exchanges, 18(2):32–37, 2020.
  * [22] A. Eden, U. Feige, and M. Feldman.  Max-min greedy matching.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * [23] K. Elbassioni, R. Raman, S. Ray, and R. Sitters.  On profit-maximizing pricing for the highway and tollbooth problems.  In International Symposium on Algorithmic Game Theory, pages 275–286. Springer, 2009.
  * [24] M. Feldman, N. Gravin, and B. Lucier.  Combinatorial auctions via posted prices.  In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 123–135. SIAM, 2014.
  * [25] M. Feldman, N. Gravin, and B. Lucier.  On welfare approximation and stable pricing.  arXiv preprint arXiv:1511.02399, 2015.
  * [26] Z. Friggstad and M. Mahboub.  Graph pricing with limited supply.  arXiv preprint arXiv:1912.05010, 2019.
  * [27] I. Gamzu and D. Segev.  A sublogarithmic approximation for highway and tollbooth pricing.  In International Colloquium on Automata, Languages, and Programming, pages 582–593. Springer, 2010.
  * [28] A. Grigoriev, J. Van Loon, R. Sitters, and M. Uetz.  How to sell a graph: Guidelines for graph retailers.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 125–136. Springer, 2006.
  * [29] T. Groves.  Incentives in teams.  Econometrica: Journal of the Econometric Society, pages 617–631, 1973.
  * [30] V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSherry.  On profit-maximizing envy-free pricing.  In SODA, volume 5, pages 1164–1173. Citeseer, 2005.
  * [31] A. Gyárfás.  On the chromatic number of multiple interval graphs and overlap graphs.  Discrete mathematics, 55(2):161–166, 1985.
  * [32] J. D. Hartline and V. Koltun.  Near-optimal pricing in near-linear time.  In Workshop on Algorithms and Data Structures, pages 422–431. Springer, 2005.
  * [33] J. Hsu, J. Morgenstern, R. Rogers, A. Roth, and R. Vohra.  Do prices coordinate markets?  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 440–453, 2016.
  * [34] L.-S. Huang, M. Li, and B. Zhang.  Approximation of walrasian equilibrium in single-minded auctions.  Theoretical computer science, 337(1-3):390–398, 2005.
  * [35] B. Kalyanasundaram and K. Pruhs.  Speed is as powerful as clairvoyance.  Journal of the ACM (JACM), 47(4):617–643, 2000.
  * [36] A. S. Kelso Jr and V. P. Crawford.  Job matching, coalition formation, and gross substitutes.  Econometrica: Journal of the Econometric Society, pages 1483–1504, 1982.
  * [37] R. Kleinberg and S. M. Weinberg.  Matroid prophet inequalities.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 123–136, 2012.
  * [38] G. Kortsarz, H. Räcke, and R. Raman.  Profit-maximizing pricing for tollbooths.
  * [39] E. Koutsoupias.  Weak adversaries for the k-server problem.  In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 444–449. IEEE, 1999.
  * [40] U. Krengel and L. Sucheston.  On semiamarts, amarts, and processes with finite value.  Probability on Banach spaces, 4:197–266, 1978.
  * [41] E. Lee.  Hardness of graph pricing through generalized max-dicut.  In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 391–399, 2015.
  * [42] R. P. Leme and S. C.-w. Wong.  Computing walrasian equilibria: Fast algorithms and structural properties.  Mathematical Programming, 179(1):343–384, 2020.
  * [43] M. Mahajan.  Lecture note.  2010\.  https://www.imsc.res.in/~meena/matching/lecture5.pdf.
  * [44] J. Misra and D. Gries.  A constructive proof of vizing’s theorem.  In Information Processing Letters. Citeseer, 1992.
  * [45] N. Nisan and I. Segal.  The communication requirements of efficient allocations and supporting prices.  Journal of Economic Theory, 129(1):192–224, 2006.
  * [46] E. Samuel-Cahn et al.  Comparison of threshold stop rules and maximum for independent nonnegative random variables.  the Annals of Probability, 12(4):1213–1216, 1984.
  * [47] A. Schrijver.  Theory of linear and integer programming.  John Wiley & Sons, 1998.
  * [48] D. D. Sleator and R. E. Tarjan.  Amortized efficiency of list update and paging rules.  Communications of the ACM, 28(2):202–208, 1985.
  * [49] R. E. Tarjan.  Decomposition by clique separators.  Discrete mathematics, 55(2):221–232, 1985.
  * [50] W. Vickrey.  Counterspeculation, auctions, and competitive sealed tenders.  The Journal of finance, 16(1):8–37, 1961.
  * [51] V. G. Vizing.  On an estimate of the chromatic class of a p-graph.  Discret Analiz, 3:25–30, 1964.
  * [52] N. Young.  The k-server dual and loose competitiveness for paging.  Algorithmica, 11(6):525–541, 1994.

##  Appendix A Missing Details from Section 3

###  A.1 Missing Details from Section 3.1

Proof of Lemma 3.2: Let $y$ be any optimal solution of (LP-Primal) that is an
extreme point of the polytope defined by (LP-Primal). Denote $J=\left\\{j\mid
0<y_{j}<1\right\\}$. We define a graph $\hat{H}$ according to $J$ as follows.
The vertex set of $\hat{H}$ contains (i) a vertex $u_{i}$ for each edge
$e_{i}\in E(G)$; and (ii) a vertex $\hat{u}_{i}$, for all $1\leq i\leq m$ such
that there exists a buyer $B_{j}$ with $j\in J$ whose demand path $Q_{j}$
contains a single edge $e_{i}$. In other words,
$V(\hat{H})=\left\\{u_{1},\ldots,u_{m}\right\\}\cup\left\\{\hat{u}_{i}\mid\exists
j\in J,Q_{j}=(e_{i})\right\\}$. The edge set of $\hat{H}$ contains (i) an edge
$(u_{i},u_{i^{\prime}})$ for each demand path $Q_{j}=(e_{i},e_{i^{\prime}})$
with $j\in J$; and (ii) an edge $(u_{i},\hat{u}_{i})$ for each demand path
$Q_{j}=(e_{i})$ with $j\in J$. In other words,
$E(\hat{H})=\left\\{(u_{i},u_{i^{\prime}})\mid\exists j\in
J,Q_{j}=(e_{i},e_{i^{\prime}})\right\\}\cup\left\\{(u_{i},\hat{u}_{i})\mid\exists
j\in J,Q_{j}=(e_{i})\right\\}$.

We say that a graph is _Eulerian_ iff the degree for each vertex is even. It
is folklore that every Eulerian graph contains a trail that visits each edge
once. We use the following claim and its simple corollary.

######  Claim A.1.

$\hat{H}$ does not contain an Eulerian subgraph with even number of edges.

###### Proof.

Assume the contrast that graph $\hat{H}$ does contain an Eulerian subgraph,
and let $(u_{r_{1}},\ldots,u_{r_{t}},u_{r_{1}})$ be the trail that visits each
edge of this Eulerian subgraph exactly once (note that such a trail may not
contain vertices of $\left\\{\hat{u}_{i}\mid\exists j\in
J,Q_{j}=(e_{i})\right\\}$). Define

$\hat{J}_{0}=\left\\{j\mid Q_{j}=(e_{i},e_{i^{\prime}}),\text{ s.t.
}\left\\{r_{k},r_{k+1}\right\\}=\left\\{i,i^{\prime}\right\\}\text{ for some
even }1\leq k\leq t\right\\};$

and

$\hat{J}_{1}=\left\\{j\mid Q_{j}=(e_{i},e_{i^{\prime}}),\text{ s.t.
}\exists\text{ odd
}k,\left\\{r_{k},r_{k+1}\right\\}=\left\\{i,i^{\prime}\right\\}\right\\}.$

Clearly, sets $\hat{J}_{0}$ and $\hat{J}_{1}$ are disjoint. We define
$z\in\left\\{-1,0,1\right\\}^{n}$ to be the $n$-dimensional vector, such that,
for each $1\leq j\leq n$, $z_{j}=1$ iff $j\in\hat{J}_{0}$, $z_{j}=-1$ iff
$j\in\hat{J}_{1}$, and $z_{j}=0$ otherwise. Let $\varepsilon$ be any constant
such that $0<\varepsilon<\min\left\\{y_{j},1-y_{j}\mid j\in J\right\\}$.
Clearly, vectors $y+\epsilon z$ and $y-\epsilon z$ are both feasible solutions
of (LP-Primal). This contradicts the fact that $y$ is an extreme point of the
polytope defined by (LP-Primal). ∎

As a corollary, all cycles of $\hat{H}$ contains odd number of edges, and all
odd-cycles in $\hat{H}$ are vertex-disjoint. We further prove the following
claim.

######  Claim A.2.

Every odd cycle of $\hat{H}$ belongs to a distinct connected component of
$\hat{H}$.

###### Proof.

If $\hat{H}$ does not contain any odd cycle or only contains one odd cycle,
then there is nothing to prove. Assume the contrast that $\hat{H}$ contains
two odd-cycles $C,C^{\prime}$ lying in the same connected component of
$\hat{H}$. Let $P$ be a path connecting a vertex $u$ of $C$ to a vertex
$u^{\prime}$ of $C^{\prime}$. Let
$V(C)=\left\\{u,u_{i_{1}},\ldots,u_{i_{r}}\right\\}$,
$V(C^{\prime})=\left\\{u^{\prime},u_{i^{\prime}_{1}},\ldots,u_{i^{\prime}_{s}}\right\\}$,
and
$V(P)=\left\\{u,u_{i^{\prime\prime}_{1}},\ldots,u_{i^{\prime\prime}_{t}},u^{\prime}\right\\}$,
where $r,s$ are even and the vertices are indexed according to the order in
which they appear on $C$, $C^{\prime}$ or $P$. Define

$J_{0}=\left\\{j\mid Q_{j}=(e_{i},e_{i^{\prime}}),\text{ s.t.
}\left\\{i_{k},i_{k+1}\right\\}=\left\\{i,i^{\prime}\right\\}\text{ for some
even }0\leq k\leq r\right\\};$ $J_{1}=\left\\{j\mid
Q_{j}=(e_{i},e_{i^{\prime}}),\text{ s.t.
}\left\\{i_{k},i_{k+1}\right\\}=\left\\{i,i^{\prime}\right\\}\text{ for some
odd }0\leq k\leq r\right\\};$ $J_{0}^{\prime}=\left\\{j\mid
Q_{j}=(e_{i},e_{i^{\prime}}),\text{ s.t.
}\left\\{i_{k},i_{k+1}\right\\}=\left\\{i,i^{\prime}\right\\}\text{ for some
even }0\leq k\leq s\right\\};$ $J_{1}^{\prime}=\left\\{j\mid
Q_{j}=(e_{i},e_{i^{\prime}}),\text{ s.t.
}\left\\{i_{k},i_{k+1}\right\\}=\left\\{i,i^{\prime}\right\\}\text{ for some
odd }0\leq k\leq s\right\\};$ $\quad\quad J_{0}^{\prime\prime}=\left\\{j\mid
Q_{j}=(e_{i},e_{i^{\prime}}),\text{ s.t.
}\left\\{i_{k},i_{k+1}\right\\}=\left\\{i,i^{\prime}\right\\}\text{ for some
even }0\leq k\leq t\right\\};\text{ and}$ $J_{1}^{\prime\prime}=\left\\{j\mid
Q_{j}=(e_{i},e_{i^{\prime}}),\text{ s.t.
}\left\\{i_{k},i_{k+1}\right\\}=\left\\{i,i^{\prime}\right\\}\text{ for some
odd }0\leq k\leq t\right\\};$

Let $z\in\left\\{0,1\right\\}^{n}$ be the vector such that for each $1\leq
j\leq n$, $z_{j}=1$ iff $j\in J_{0}$, $z_{j}=-1$ iff $j\in J_{1}$, and
$z_{j}=0$ otherwise. We define vectors $z^{\prime},z^{\prime\prime}$ according
to sets $J^{\prime}_{0},J^{\prime}_{1}$ and sets
$J^{\prime\prime}_{0},J^{\prime\prime}_{1}$ similarly. Let $\varepsilon$ be
any constant such that $0<\varepsilon<\min\left\\{y_{j},1-y_{j}\mid j\in
J\right\\}$. If $t$ is odd, then we let $\tilde{z}=\epsilon z+\epsilon
z^{\prime}-2\epsilon z^{\prime\prime}$; if $t$ is even, then we let
$\tilde{z}=\epsilon z-\epsilon z^{\prime}-2\epsilon z^{\prime\prime}$.
Clearly, vectors $y+\tilde{z}$ and $y-\tilde{z}$ are both feasible solutions
of (LP-Primal). This contradicts the fact that $y$ is an extreme point of the
polytope defined by (LP-Primal). ∎

As a corollary, each connected component of $\hat{H}$ is either a tree itself,
or the union of an odd cycle with some disjoint trees, each sharing a distinct
vertex with the cycle. We further prove the following claim.

######  Claim A.3.

No connected component of $\hat{H}$ is a tree.

###### Proof.

Assume the contrast that $\hat{H}$ has a connected component that is a tree.
Let $T$ be such a tree and we root $T$ at an arbitrary vertex of $T$. We say
that an edge $(u^{\prime},u^{\prime\prime})$ (where $u^{\prime}$ is the parent
vertex of $u^{\prime\prime}$ in $T$) of $T$ is a _type- $0$_ edge iff the
tree-distance between $u$ and $u^{\prime}$ in $T$ is even; otherwise we say
that it is a _type- $1$_ edge. We define $J_{0}=\left\\{j\mid
Q_{j}=(e_{i},e_{i^{\prime}}),\text{ s.t. }(u_{i},u_{i^{\prime}})\text{ is a
type-0 edge}\right\\}$, and $J_{1}=\left\\{j\mid
Q_{j}=(e_{i},e_{i^{\prime}}),\text{ s.t. }(u_{i},u_{i^{\prime}})\text{ is a
type-1 edge}\right\\}$. Claim A.3 follows from similar arguments in the proof
of Claim A.1. ∎

Via similar arguments in the proof of Claim A.2, we can prove the following
claim.

######  Claim A.4.

No connected component of $\hat{H}$ contains an odd-cycle and at least one
non-cycle edge.

Combining Claim A.1, Claim A.2, Claim A.3 and Claim A.4, every connected
component of $\hat{H}$ is a single odd-cycle. It remains to show that all
coordinates of $\left\\{y_{j}\right\\}_{j\in J}$ are $1/2$. Consider an odd
cycle $C$ with $V(C)=\left\\{u_{i_{1}},\ldots,u_{i_{r}}\right\\}$ (where $r$
is odd), where the vertices are indexed in the same order in which they appear
on $C$. For each $1\leq t\leq r$, let $Q_{j_{t}}$ be the path that contains
edges $e_{i_{t}},e_{i_{t+1}}$. Via similar arguments in the proof of Claim
A.2, we can show that $y_{j_{t}}+y_{j_{t+1}}=1$ for all $1\leq t\leq r$. Since
$r$ is odd, we conclude that $y_{j_{t}}=1/2$ for all $1\leq t\leq r$. This
completes the proof of Lemma 3.2. $\Box$

Proof of Lemma 3.3: We provide the proof of Lemma 3.3, using Lemma 3.2.

We first modify the buyer profile as follows. For each edge $e$ of $G$, we add
a buyer $B_{e}$ who demands the path that contains a single edge $e$ and has
value $0$ upon the path. Equivalently, we consider the following linear
program.

(LP-1) $\displaystyle\text{maximize }\sum_{j\in[n]}v_{j}\cdot y_{j}$ s.t.
$\displaystyle\hat{y}_{i}+\sum_{j:e_{i}\in Q_{j}}y_{j}=1$
$\displaystyle\forall\text{ }1\leq i\leq m$ $\displaystyle y_{j}\geq 0$
$\displaystyle\forall\text{ }j\in[n]$ $\displaystyle\hat{y}_{i}\geq 0$
$\displaystyle\forall\text{ }1\leq i\leq m$

It is easy to see that (LP-1) is equivalent to (LP-Primal), in the sense that
(i) their optimal values are the same; and (ii) any optimal solution to (LP-1)
naturally induces an optimal solution to (LP-Primal), and vice versa. Consider
now an optimal solution $y^{*}=(y^{*}_{j})_{j\in[n]}$ of (LP-Primal). We
define $\hat{y}^{*}\in[0,1]^{m}$ as: for each $1\leq i\leq m$,
$\hat{y}^{*}_{i}=1-\sum_{j:e_{i}\in Q_{j}}y^{*}_{j}$. It is easy to see that
$(y^{*},\hat{y}^{*})$ is an optimal solution of (LP-1).

We will now construct a star graph $H$ and a buyer profile
$\mathcal{F}^{\prime}$ on $H$ as follows. Assume that the spider graph $G$
contains $\ell$ legs, and the $k$-th leg is denoted by $L_{k}$ (so
$E(G)=\bigcup_{1\leq k\leq\ell}E(L_{k})$). Then $H$ is a star graph with
$\ell$ edges, that are denoted by
$\tilde{e}_{1},\tilde{e}_{2},\ldots,\tilde{e}_{\ell}$, respectively. We now
construct the buyer profile $\mathcal{F}^{\prime}$ iteratively. Denote
$\mathcal{Q}=\left\\{Q_{1},\ldots,Q_{n}\right\\}\cup\left\\{(e_{i})\mid
e_{i}\in E(G)\right\\}$. Throughout, we maintain: (i) for each path
$Q\in\mathcal{Q}$, a real number $x_{Q}$, that is initialized as follows: if
$Q=Q_{j}$ for some $j\in[n]$, then $x_{Q}=y^{*}_{j}$; if $Q=(e_{i})$ for some
$e_{i}\in E(G)$, then $x_{Q}=\hat{y}^{*}_{i}$; and (ii) a buyer profile
$\mathcal{F}^{\prime}$, that initially contains no buyers. In each iteration,
we will add one buyer into $\mathcal{F}^{\prime}$ and modify the values
$\left\\{x_{Q}\right\\}_{q\in\mathcal{Q}}$. We will maintain the invariant
that for each $1\leq k\leq\ell$, the sum $Z_{e}=\sum_{Q:e\in Q}x_{Q}$ are the
same for all edges $e\in E_{k}$ of the $k$-th leg are the same (but the sums
$Z_{e},Z_{e^{\prime}}$ may be distinct for edges $e,e^{\prime}$ that belong to
distinct legs). Clearly, initially this invariant holds. We now describe an
iteration. Let $\hat{Q}=\arg_{Q\in\mathcal{Q}:x_{Q}\neq
0}\min\left\\{x_{Q}\right\\}$. We consider the following two cases.

Case 1. Path $\hat{Q}$ contains edges from two distinct legs. Assume path
$\hat{Q}$ contains some edges from $L_{k_{1}},L_{k_{2}}$. Let $P_{1}$ be the
subpath of $L_{k_{1}}$ formed by edges of $L_{k_{1}}\setminus\hat{Q}$, and we
define $P_{2}$ similarly. We denote by $v_{1},v^{\prime}_{1}$ the endpoints of
$P_{1}$, where $v^{\prime}_{1}$ is the leaf of the leg $L_{k_{1}}$. We use the
following claim.

######  Claim A.5.

If $P_{1}\neq\emptyset$, then there exists an path $Q\in\mathcal{Q}$, such
that (i) $x_{Q}\geq x_{\hat{Q}}$; and (ii) $Q$ is a subpath of $P_{1}$ and
contains $v_{1}$ as one of its endpoints.

###### Proof.

Denote by $\hat{e},\hat{e}^{\prime}$ the edges incident to $v_{1}$, where
$\hat{e}$ belongs to $\hat{Q}$ and $\hat{e}^{\prime}$ belongs to $P_{1}$.
Assume for contradiction that there is no such $Q$, then any path
$Q\in\mathcal{Q}$ with $x_{Q}>0$ that contains edge $\hat{e}^{\prime}$ must
also contain edge $\hat{e}$. However, since edges $\hat{e},\hat{e}^{\prime}$
belong to the same leg, and the path $\hat{Q}$ contains $\hat{e}$ but not
$\hat{e}^{\prime}$, the invariant that $Z_{\hat{e}}=Z_{\hat{e}^{\prime}}$
cannot hold, a contradiction. ∎

As an easy corollary of Claim A.5, we can find a set
$\mathcal{Q}^{\prime}_{1}\subseteq\mathcal{Q}$ of paths, such that (i) the
paths of $\mathcal{Q}^{\prime}_{1}$ are edge-disjoint; (ii) the union of paths
of $\mathcal{Q}^{\prime}_{1}$ is $P_{1}$; and (iii) for each
$Q\in\mathcal{Q}^{\prime}_{1}$, the value $x_{Q}\geq x_{\hat{Q}}>0$.
Similarly, we can find a set $\mathcal{Q}^{\prime}_{2}\subseteq\mathcal{Q}$ of
paths, such that (i) the paths of $\mathcal{Q}^{\prime}_{2}$ are edge-
disjoint; (ii) the union of paths of $\mathcal{Q}^{\prime}_{2}$ is $P_{2}$;
and (iii) for each $Q\in\mathcal{Q}^{\prime}_{2}$, the value $x_{Q}\geq
x_{\hat{Q}}>0$. Therefore, if we set
$\mathcal{Q}^{\prime}=\left\\{\hat{Q}\right\\}\cup\mathcal{Q}^{\prime}_{1}\cup\mathcal{Q}^{\prime}_{2}$,
then the paths of $\mathcal{Q}^{\prime}$ are edge-disjoint, their union is
$L_{k_{1}}\cup L_{k_{2}}$, and for each path $Q\in\mathcal{Q}^{\prime}$,
$x_{Q}\geq x_{\hat{Q}}$. We then add a buyer to $\mathcal{F}^{\prime}$ as
follows. Its demand path $P$ contains two edges
$\tilde{e}_{k_{1}},\tilde{e}_{k_{1}}$, and its value is defined as
$v(P)=\sum_{Q\in\mathcal{Q}^{\prime}}v(Q)$. We also define
$w^{*}_{P}=x_{\hat{Q}}$, and then we decrease the value $x_{Q}$ for all
$Q\in\mathcal{Q}^{\prime}$ by $x_{\hat{Q}}$.

Case 2. Path $\hat{Q}$ contains edges from one leg. Assume path $\hat{Q}$
contains only edges of $L_{k_{1}}$. We define path $P_{1}$ similarly as in
Case 1. Via similar arguments, we can compute a set $\mathcal{Q}^{\prime}_{1}$
of edge-disjoint paths whose union is $P_{1}$, and $x_{Q}\geq x_{\hat{Q}}>0$
for each path $Q\in\mathcal{Q}^{\prime}_{1}$. We denote by $v_{2}$ the
endpoint of $\hat{Q}$ that is closer to the center of the spider. If $v_{2}$
is the center then we set $\mathcal{Q}^{\prime}_{2}=\emptyset$. Otherwise, by
repeatedly applying Claim A.5 to the subpath of $L_{k_{1}}$ between $v_{2}$
and the center (that we denote by $P_{2}$), we can compute a set
$\mathcal{Q}^{\prime}_{2}$ of edge-disjoint paths with $x_{Q}\geq
x_{\hat{Q}}>0$ for each path $Q\in\mathcal{Q}^{\prime}_{2}$, such that the
union of paths of $\mathcal{Q}^{\prime}_{2}$ is either $P_{2}$ or the union of
$P_{2}$ with some other entire leg $L_{k_{2}}$. Assume the former, then we add
a buyer to $\mathcal{F}^{\prime}$ as follows. Its demand path $P$ contains one
edge $\tilde{e}_{k_{1}}$, and its value is defined as
$v(P)=\sum_{Q\in\mathcal{Q}^{\prime}}v(Q)$, where
$\mathcal{Q}^{\prime}=\left\\{\hat{Q}\right\\}\cup\mathcal{Q}^{\prime}_{1}\cup\mathcal{Q}^{\prime}_{2}$.
Assume the latter, then we add a buyer to $\mathcal{F}^{\prime}$ as follows.
Its demand path $P$ contains two edges $\tilde{e}_{k_{1}},e_{k_{2}}$, and its
value is defined as $v(P)=\sum_{Q\in\mathcal{Q}^{\prime}}v(Q)$. In both cases,
we also define $w^{*}_{P}=x_{\hat{Q}}$, and then we decrease the value $x_{Q}$
for all $Q\in\mathcal{Q}^{\prime}$ by $x_{\hat{Q}}$. We say that paths in
$\mathcal{Q}^{\prime}$ _contributes_ to path $P$.

This finishes the description of an iteration. Clearly, after each iteration,
the invariant that for each $1\leq k\leq\ell$, the sum $Z_{e}$ are the same
for all edges $e\in E_{k}$ of the $k$-th leg still holds. Moreover, the number
of paths $Q$ in $\mathcal{Q}$ with $x_{Q}>0$ is decreased by at least one
after each iteration. Therefore, the algorithm terminates in $m+n$ iterations.
At the end, $x_{Q}=0$ for all paths $Q\in\mathcal{Q}$. Let
$\mathcal{F}^{\prime}=\left\\{(P,v_{P})\right\\}_{P\in\mathcal{P}}$ be the
buyer profile that we get at the end of the algorithm. It is easy to see that
(i) for each $j\in[n]$, $y^{*}_{j}=\sum_{P:Q_{j}\text{ contributes to
}P}w^{*}_{P}$, and for each $1\leq i\leq n$,
$\hat{y}^{*}_{j}=\sum_{P:(e_{i})\text{ contributes to }P}w^{*}_{P}$; and (ii)
$\sum_{P\in\mathcal{P}}v_{P}\cdot w^{*}_{P}=\sum_{j\in[n]}v_{j}\cdot
y^{*}_{j}$. We consider the following linear program.

(LP-2) $\displaystyle\text{maximize }\sum_{P\in\mathcal{P}}v_{P}\cdot w_{P}$
s.t. $\displaystyle\sum_{P:\tilde{e}_{i}\in P}w_{P}=1$
$\displaystyle\forall\text{ }1\leq i\leq\ell$ $\displaystyle w_{P}\geq 0$
$\displaystyle\forall\text{ }P\leq\mathcal{P}$

We now show that $w^{*}=(w^{*}_{P})_{P\in\mathcal{P}}$ is an optimal solution
of (LP-2). Assume the contrast that there exists another feasible solution
$w^{\prime}=(w^{\prime}_{P})_{P\in\mathcal{P}}$ of (LP-2), such that
$\sum_{P\in\mathcal{P}}v_{P}\cdot w^{*}_{P}<\sum_{P\in\mathcal{P}}v_{P}\cdot
w^{\prime}_{P}$. We define vector $y^{\prime}\in[0,1]^{n}$ as: for each
$j\in[n]$, $y^{\prime}_{j}=\sum_{P:Q_{j}\text{ contributes to
}P}w^{\prime}_{P}$, and define vector $\hat{y}^{\prime}\in[0,1]^{n}$ as: for
each $1\leq i\leq n$, $\hat{y}^{\prime}_{j}=\sum_{P:(e_{i})\text{ contributes
to }P}w^{\prime}_{P}$. It is easy to see that $(y^{\prime},\hat{y}^{\prime})$
is a feasible solution to (LP-1), and moreover, $\sum_{j\in[n]}v_{j}\cdot
y^{\prime}_{j}=\sum_{P\in\mathcal{P}}v_{P}\cdot
w^{\prime}_{P}>\sum_{P\in\mathcal{P}}v_{P}\cdot
w^{*}_{P}=\sum_{j\in[n]}v_{j}\cdot y^{*}_{j}$. This causes a contradiction to
the optimality of $(y^{*},\hat{y}^{*})$. Therefore, from Lemma 3.2, $w^{*}$ is
half-integral. Since for each $j\in[n]$, $y^{*}_{j}=\sum_{P:Q_{j}\text{
contributes to }P}w^{*}_{P}$, and for each $1\leq i\leq n$,
$\hat{y}^{*}_{j}=\sum_{P:(e_{i})\text{ contributes to }P}w^{*}_{P}$,
$(y^{*},\hat{y}^{*})$ is also half-integral. It follows that $y^{*}$ is half-
integral. $\Box$

Proof of Lemma 3.4: We construct an algorithm that partitions the set
$\mathcal{Q}$ of paths into $d+1$ subsets
$\mathcal{Q}_{1},\ldots,\mathcal{Q}_{d+1}$. We root $T$ at an arbitrarily
chosen vertex $r\in V(T)$, and we say that a vertex $v\in V(T)$ is _at the
$i$-th level_ iff the tree-distance between $v$ and $r$ in $T$ is $i$. The
algorithm will compute the sets $\mathcal{Q}_{1},\ldots,\mathcal{Q}_{d+1}$
iteratively. Initially, all sets are set to be $\emptyset$. The algorithm
proceeds sequentially in phases. In the $i$-th phase, the algorithm process
all vertices at the $i$-th level one-by-one. Upon processing a vertex $v$, we
will assign all paths containing at least one edge of $E_{v}$ to some set of
$\left\\{\mathcal{Q}_{1},\ldots,\mathcal{Q}_{d+1}\right\\}$, where $E_{v}$ is
the set of edges connecting $v$ to some of its children.

Fix an integer $i$ and a vertex $v$ at the $i$-th level, and we now describe
the iteration of processing the vertex $v$. Let $\mathcal{Q}(v)$ contain all
paths of $\mathcal{Q}$ that contains at least one edge connecting $v$ to some
of its children. The $\mathcal{Q}(v)$ can be partitioned into three subsets:
set $\mathcal{Q}^{0}(v)$ contains all paths of $\mathcal{Q}(v)$ that are
already assigned to some set of
$\left\\{\mathcal{Q}_{1},\ldots,\mathcal{Q}_{d+1}\right\\}$; set
$\mathcal{Q}^{1}(v)$ contains all paths of $\mathcal{Q}(v)$ that are not yet
already assigned and contains exactly $1$ edge of $E_{v}$; and set
$\mathcal{Q}^{2}(v)$ contains all paths of $\mathcal{Q}(v)$ that are not yet
already assigned and contains exactly $2$ edges of $E_{v}$. Note that each
path of $\mathcal{Q}^{0}(v)$ must contain the edge $\hat{e}$ connecting $v$ to
its parent vertex and exactly one edge of $E_{v}$, so they must belong to
distinct sets of $\left\\{\mathcal{Q}_{1},\ldots,\mathcal{Q}_{d+1}\right\\}$.
We construct an auxiliary graph $H$ as follows. The vertex set is
$V(H)=\left\\{u_{\hat{e}}\right\\}\cup\left\\{u_{e}\mid e\in
E_{v}\right\\}\cup\left\\{\hat{u}_{Q}\mid Q\in\mathcal{Q}^{1}(v)\right\\}$.
The edge set is partitioned into three subsets $E(H)=E_{0}\cup E_{1}\cup
E_{2}$, where $E_{0}=\left\\{(u_{e},v)\mid Q\in\mathcal{Q}^{0}(v),e=Q\cap
E_{v}\right\\}$, $E_{1}=\left\\{(u_{e},\hat{u}_{Q})\mid
Q\in\mathcal{Q}^{1}(v),e=Q\cap E_{v}\right\\}$, and
$E_{2}=\left\\{(u_{e},u_{e^{\prime}})\mid
Q\in\mathcal{Q}^{2}(v),\left\\{e,e^{\prime}\right\\}=Q\cap E_{v}\right\\}$.
Clearly, every path of $\mathcal{Q}(v)$ correspond to an edge in $E(H)$, that
we denote by $f_{Q}$. It is clear from the definition of $H$ that, for every
pair $Q,Q^{\prime}$ of paths in $\mathcal{Q}(v)$, $Q$ and $Q^{\prime}$ are
edge-disjoint iff edges $f_{Q}$ and $f_{Q^{\prime}}$ of $E(H)$ do not share a
vertex.

Since every edge $e\in E_{v}$ is contained in at most $d$ paths of
$\mathcal{Q}(v)$, from the definition of graph $H$, every vertex in $H$ has
degree at most $d$. From Vizing’s Theorem [51, 44], we can efficiently find a
coloring of all edges of $E(H)$ with $d+1$ colors, such that edges with same
color do not share vertices. Note that, since all edges in
$\left\\{f_{Q}\mid\mathcal{Q}^{0}(v)\right\\}$ share the vertex $u_{\hat{e}}$,
these edges will have different colors in any valid edge-coloring. We now
assign, for each $Q\in\mathcal{Q}^{0}(v)$, all paths $Q^{\prime}$ of
$\mathcal{Q}(v)$ whose corresponding edge $f_{Q^{\prime}}\in\mathcal{Q}(v)$
has the same color as edge $f_{Q}$, to the same set of
$\left\\{\mathcal{Q}_{1},\ldots,\mathcal{Q}_{d+1}\right\\}$. And then we
assign, for any color that is not used by edges in $\left\\{f_{Q}\mid
Q\in\mathcal{Q}^{0}(v)\right\\}$, all paths whose corresponding edge
$f_{Q^{\prime}}\in\mathcal{Q}(v)$ has this color to a distinct set of
$\left\\{\mathcal{Q}_{1},\ldots,\mathcal{Q}_{d+1}\right\\}$ that does not
contain paths of $\mathcal{Q}^{0}(v)$. This completes the iteration of
processing the vertex $v$. Since edges of have different colors, it is clear
that, after this iteration, each set of
$\left\\{\mathcal{Q}_{1},\ldots,\mathcal{Q}_{d+1}\right\\}$ contains edge-
disjoint paths. Therefore, if we keep processing all vertices in this way,
then we obtain a valid partition of the original set $\mathcal{Q}$ of paths
into at most $d+1$ subsets $\mathcal{Q}_{1},\ldots,\mathcal{Q}_{d+1}$, such
that the paths in each subset are edge-disjoint. $\Box$