Proof of 2. We first solve 1 and get the optimal solution \(x^*\). Next, we apply 10 to obtain three solutions \(\tilde{x}^{(1)}, \tilde{x}^{(2)}, \tilde{x}^{(3)}\). We now do the following:

• w.p.\(\frac{1}{11}\), we run the algorithm provided by 10 to obtain a profit of \(\frac{1}{2} \cdot {\mathsf{LP}}(\tilde{x}^{(1)})\), else

• we run the algorithm provided by 9 on one of \(\tilde{x}^{(2)}\) or \(\tilde{x}^{(3)}\), each w.p. \(\frac{5}{11}\).

Since \(\tilde{x}^{(2)}\) and \(\tilde{x}^{(3)}\) both admit a \(2.5\)-trades decomposition, our final expected profit is \[\begin{align} \frac{1}{11} \cdot \frac{{\mathsf{LP}}(\tilde{x}^{(1)})}{2} + \frac{5}{11} \cdot \frac{1}{10} \cdot ({\mathsf{LP}}(\tilde{x}^{(2)}) + {\mathsf{LP}}(\tilde{x}^{(3)})) ~=~ \frac{{\mathsf{LP}}(\tilde{x}^{(1)}) + {\mathsf{LP}}(\tilde{x}^{(2)}) + {\mathsf{LP}}(\tilde{x}^{(3)})}{22} ~=~ \frac{{\mathsf{LP}}(x^*)}{22}. \end{align}\] Since 6 guarantees that \({\mathsf{LP}}(x^*)\) is at least the expected profit of the optimal offline algorithm, the algorithm achieves a \(\frac{1}{22}\)-approximation. ◻

Proof. It suffices to show that after performing one step of uncrossing in 1, the feasibility of \(\tilde{x}\) holds, and the objective remains unchanged. For the objective, note that the objective of 1 only depends on the value of every \(q^b_i(\tilde{x})\) and \(q^s_i(\tilde{x})\). Since the values of \(q^b_i(\tilde{x})\) and \(q^s_i(\tilde{x})\) remain unchanged after performing one uncrossing step, the objective remains unchanged. For Constraints 2 , it can be rewritten as \(q^b_i(\tilde{x}) + q^s_i(\tilde{x}) \leq p_i\), which remains feasible as every \(q^b_i(\tilde{x})\) and \(q^s_i(\tilde{x})\) remain unchanged. For Constraints 3 , it can be verified that for every \(t \in [T]\), the quantity \(\sum_{i = 0}^{t-1} \sum_{j = t}^T x_{i, j}\) is unchanged, so the constraint remains feasible. ◻

Proof. We prove via contradiction. Assume for interval \([\ell, r]\), we have \[\sum_{i = \ell}^r q^b_i(x) - \sum_{i = \ell}^r q^s_i(x) ~>~ 1.\] If \(r = T\), we may without loss of generality reduce \(r\) to \(T - 1\), as \(q^b_T(x)\) must be \(0\). When \(r \leq T - 1\), note that \[\begin{align} \sum_{i = 0}^r \sum_{j = r+1}^T x_{i, j} ~&\geq~ \sum_{i = \ell}^r \sum_{j = r+1}^T x_{i, j} \\ ~&=~ \sum_{i = \ell}^r q^b_i(x) - \sum_{i = \ell}^{r - 1} \sum_{j = i + 1}^r x_{i,j} \\ ~&\geq~ \sum_{i = \ell}^r q^b_i(x) - \sum_{i = \ell}^r q^s_i(x) ~>~ 1, \end{align}\] which is in contrast to the assumption that \(x\) is feasible as the constraint in the third line of 1 with \(t = r + 1\) is not satisfied. Therefore, there must be \(\sum_{i = \ell}^r q^b_i(x) - \sum_{i = \ell}^r q^s_i(x) ~\leq~ 1\).

Symmetrically, when \(\sum_{i = \ell}^r q^s_i(x) - \sum_{i = \ell}^r q^b_i(x) > 1\) holds, we may assume without loss of generality that \(\ell \geq 1\), as \(q^s_0(x)\) must be \(0\). Then, note that \[\begin{align} \sum_{i = 0}^{\ell - 1} \sum_{j = \ell}^T x_{i, j} ~&\geq~ \sum_{i = 0}^{\ell - 1} \sum_{j = \ell}^r x_{i, j} \\ ~&=~ \sum_{j = \ell}^r q^s_j(x) - \sum_{i = \ell}^{r - 1} \sum_{j = i + 1}^r x_{i, j} \\ ~&\geq~ \sum_{j = \ell}^r q^s_j(x) - \sum_{j = \ell}^r q^b_j(x) ~>~ 1, \end{align}\] which violates the constraint in the third line of 1 with \(t = \ell\). Combining two cases proves 13. ◻

Proof of 12. We first show 12.[item:init-decompose-i], i.e., within each interval \([\ell_d, r_d]\), the summation of \(q^b_i(\tilde{x})\) and \(q^s_i(\tilde{x})\) are both bounded by \(2.5\). Note that if the desired index \(r\) in Line 5 of 2 does not exist, then at least one summation must be bounded by \(1\), and 13 guarantees that another summation is bounded by 2, so 12.[item:init-decompose-i] holds. We then consider the general case where index \(r_d\) can be found. Since taking \(r_d - 1\) is not feasible, there must be \[\sum_{i = \ell_d}^{r_d - 1} q^b_i(\tilde{x}) ~<~ 1 \qquad \text{or} \qquad \sum_{i = \ell_d}^{r_d - 1} q^s_i(\tilde{x}) ~<~ 1.\] By 13, we have \[\begin{align} \sum_{i = \ell_d}^{r_d - 1} q^s_i(\tilde{x}) + \sum_{i = \ell_d}^{r_d - 1} q^b_i(\tilde{x}) ~&=~ \min\left\{ \sum_{i = \ell_d}^{r_d - 1} q^s_i(\tilde{x}), \sum_{i = \ell_d}^{r_d - 1} q^b_i(\tilde{x})\right\} + \max\left\{ \sum_{i = \ell_d}^{r_d - 1} q^s_i(\tilde{x}), \sum_{i = \ell_d}^{r_d - 1} q^b_i(\tilde{x})\right\} \\ ~&\leq~ 2 \cdot \min\left\{ \sum_{i = \ell_d}^{r_d - 1} q^s_i(\tilde{x}), \sum_{i = \ell_d}^{r_d - 1} q^b_i(\tilde{x})\right\} + 1 ~<~ 3. \end{align}\] Note that Constraint 2 guarantees \[q^s_{r_d}(\tilde{x}) + q^b_{r_d}(\tilde{x}) ~\leq~ p_{r_d} ~\leq~ 1.\] Summing the above two inequalities together gives \[\sum_{i = \ell_d}^{r_d} q^s_i(\tilde{x}) + \sum_{i = \ell_d}^{r_d} q^b_i(\tilde{x}) ~\leq~ 4.\] Since 13 guarantees that \[\left |\sum_{i = \ell_d}^{r_d} q^s_i(\tilde{x}) - \sum_{i = \ell_d}^{r_d} q^b_i(\tilde{x}) \right| ~\leq~ 1,\] there must be \[\sum_{i = \ell_d}^{r_d} q^b_i(\tilde{x}) ~\leq~ 2.5 \qquad \text{and} \qquad \sum_{i = \ell_d}^{r_d} q^s_i(\tilde{x}) ~\leq~ 2.5.\]

Next, we prove 12.[item:init-decompose-ii] via contradiction. Assume there exists \(1 \leq i' < j' \leq T\) that satisfies \(\tilde{x}_{i', j'} > 0\), such that \(d' - d \geq 2\) when \(i' \in [\ell_d, r_d]\) and \(j' \in [\ell_{d'}, r_{d'}]\). Consider \(j \in [\ell_{d+1}, r_{d+1}]\), and \(i \leq j\) that satisfies \(\tilde{x}_{i, j} > 0\). Recall that solution \(\tilde{x}\) is given by 1 after finishing the uncrossing process. Since we have \(j \leq r_{d+1} < \ell_{d'} \leq j'\), there must be \(i \leq i' \leq r_d < \ell_{d+1}\). Then, we have \[\begin{align} \sum_{i = 0}^{\ell_{d+1} - 1} \sum_{j = \ell_{d+1}}^T \tilde{x}_{i, j} ~&\geq~ \tilde{x}_{i', j'} + \sum_{i = 0}^{\ell_{d+1} - 1} \sum_{j = \ell_{d+1}}^{r_{d+1}} \tilde{x}_{i, j} \\ ~&=~ \tilde{x}_{i', j'} + \sum_{j = \ell_{d+1}}^{r_{d+1}} q^s_j(\tilde{x}) \\ ~&\geq~ \tilde{x}_{i', j'} + 1 > 1, \end{align}\] where the first inequality uses the fact that \(j' \notin [\ell_{d+1}, r_{d+1}]\), and therefore not counted in the following summation, the second equality uses the fact that \(\tilde{x}_{i, j} > 0\) for \(j \in [\ell_{d+1}, r_{d+1}]\) implies \(i < \ell_{d+1}\), and the last line uses the fact that 2 guarantees that \(\sum_{i = \ell_{d+1}}^{r_{d+1}} q^s_i(\tilde{x}) \geq 1\) (note that \(d+1 < d'\), so \(r_{d+1}\) can’t be \(T\)). Since the above inequality violates the constraint in the third line of 1 with \(t = \ell_{d+1}\), the assumption that \((i', j')\) exists is in contrast to the feasibility of solution \(\tilde{x}\). Therefore, 12.[item:init-decompose-ii] holds. ◻

Proof of 10. To prove 10, we decompose solution \(\tilde{x}\) into three solutions \(\tilde{x}^{(1)}\), \(\tilde{x}^{(2)}\), and \(\tilde{x}^{(3)}\), such that these three solutions satisfy the first and second statements in 10. Then, we use 11, which states that \({\mathsf{LP}}(\tilde{x}) = {\mathsf{LP}}(x^*)\), to prove the third statement.

Constructing \(\tilde{x}^{(1)}\) and proof of 10.[item:decompose-opt-i]. We first give the definition of \(\tilde{x}^{(1)}\) and show that there exists an online algorithm achieving \(\frac{1}{2} \cdot {\mathsf{LP}}(\tilde{x}^{(1)})\). For \(0 \leq i < j \leq T\), we define \[\tilde{x}^{(1)}_{i, j} ~:=~ \tilde{x}_{i, j} \cdot \mathbf{1}[i = 0],\] i.e., \(\tilde{x}^{(1)}\) represents all trades that buys (for free) from request \(0\). Since solution \(\tilde{x}^{(1)}\) only buys from request \(0\) with at most one copy, the selling process given by \(\tilde{x}^{(1)}\) can be viewed as the LP solution of a single-item Prophet Inequality problem, and a standard Prophet Inequality algorithm achieves an expected profit of \(\frac{1}{2} \cdot {\mathsf{LP}}(\tilde{x}^{(1)})\). See e.g. [12] and its references for details.

Constructing \(\tilde{x}^{(2)}, \tilde{x}^{(3)}\) and proof of 10.[item:decompose-opt-ii]. Given \(\tilde{x}\), we run 2 to get the initial decomposition \(\mathcal{I}\) for \(\tilde{x}\), and we assume without loss of generality that \(\mathcal{I}= \{[\ell_1, r_1], \cdots [\ell_D, r_D]\}\), such that intervals are sorted in order, i.e., \(\ell_1 = 1, r_D = T\), and \(r_d + 1 = \ell_{d+1}\) for every \(d \in [D - 1]\). We define \(\tilde{x}^{(2)}\) and \(\tilde{x}^{(3)}\) as follows: \[\begin{align} \tilde{x}^{(2)}_{i, j} ~:=~ \tilde{x}_{i, j} \cdot \mathbf{1}\big[i \in [\ell_d, r_d]: d \text{ is odd}\big], \quad \text{and} \quad \tilde{x}^{(3)}_{i, j} ~:=~ \tilde{x}_{i, j} \cdot \mathbf{1}\big[i \in [\ell_d, r_d]: d \text{ is even}\big]. \end{align}\]

Now, we prove 10.[item:decompose-opt-ii]. We only prove the statement for \(\tilde{x}^{(2)}\), as the proof for \(\tilde{x}^{(3)}\) is identical. Define \(\mathcal{I}_{odd} = \{[\ell_d, r_d] \cup [\ell_{d+1}, r_{d+1}]: d \in [D]\land d \text{ is odd}\}\), where the last interval is refined as \([\ell_D, r_D]\) instead of \([\ell_D, r_D] \cup [\ell_{D+1}, r_{D+1}]\) when \(D\) is odd. Since 12 guarantees that for \((i, j): \tilde{x}_{i, j} > 0 \land i \in [\ell_d, r_d]\), there must be either \(j \in [\ell_d, r_d]\) or \(j \in [\ell_{d+1}, r_{d+1}]\) (if exists), for \((i, j): \tilde{x}^{(2)}_{i, j} > 0\), both \(i\) and \(j\) must belong to one interval in \(\mathcal{I}_{odd}\). Therefore, interval set \(\mathcal{I}_{odd}\) is a feasible decomposition of solution \(\tilde{x}^{(2)}\).

It remains to show that for each interval \([\ell, r] \in \mathcal{I}_{odd}\), solution \(\left\{\tilde{x}^{(2)}_{i, j} \cdot \mathbf{1}\big[i, j \in [\ell, r]\big]\right\}\) is a \(2.5\)-trades solution. Assume \(\ell\) equals to \(\ell_d\), where \(d\) is odd. By the definition of \(\tilde{x}^{(2)}\) and 12.[item:init-decompose-ii], solution \(\left\{\tilde{x}^{(2)}_{i, j} \cdot \mathbf{1}\big[i, j \in [\ell, r]\big]\right\}\) includes all trades of solution \(\tilde{x}\) that buys from a request within interval \([\ell_d, r_d]\), i.e., we have \[\begin{align} \sum_{i, j \in [\ell, r]^2} \tilde{x}^{(2)}_{i, j} \cdot \mathbf{1}\big[i, j \in [\ell, r]\big] ~=~ \sum_{i \in [\ell_d, r_d]} q^b_i(\tilde{x}) ~\leq~ 2.5, \end{align}\] where the inequality follows from 12.[item:init-decompose-i]. Therefore, \(\left\{\tilde{x}^{(2)}_{i, j} \cdot \mathbf{1}\big[i, j \in [\ell, r]\big]\right\}\) is a \(2.5\)-trades solution, and solution \(\tilde{x}^{(2)}\) admits a \(2.5\)-trades decomposition.

Proof of 10.[item:decompose-opt-ii]. We note that it suffices to show \(\tilde{x}^{(1)}+ \tilde{x}^{(2)}+ \tilde{x}^{(3)} = \tilde{x}\), as when the equality holds, we have \[{\mathsf{LP}}(\tilde{x}^{(1)}) + {\mathsf{LP}}(\tilde{x}^{(2)}) + {\mathsf{LP}}(\tilde{x}^{(3)}) ~=~ {\mathsf{LP}}(\tilde{x}) ~=~ {\mathsf{LP}}(x^*),\] where the last equality follows from 11. Note that for every \((i, j): \tilde{x}_{i, j} > 0\), we have \[\begin{align} \tilde{x}_{i, j} ~&=~ \tilde{x}_{i, j} \cdot \left(\mathbf{1}[i = 0] + \mathbf{1}[i \in [\ell_d, r_d]:d \text{ is odd}] + \mathbf{1}[i \in [\ell_d, r_d]:d \text{ is even}]\right) \\ ~&=~ \tilde{x}^{(1)}_{i, j} + \tilde{x}^{(2)}_{i, j} + \tilde{x}^{(3)}_{i, j}, \end{align}\] where the first equality holds since the conditions in three indicator functions partition all possibilities for tuple \((i, j)\). Therefore, equality \(\tilde{x}^{(1)}+ \tilde{x}^{(2)}+ \tilde{x}^{(3)} = \tilde{x}\) holds. ◻

Proof. Consider the structure of the optimal order-independent algorithm. Since the decision of such algorithm does not depend on the arrival order of requests, while every request is identically distributed, in expectation the optimal decision of the algorithm should only depend on the type of each request, rather than the order of their arrivals. Given this observation, we define without loss of generality \(\tilde{y}_k\) to be the probability that the arriving request has type \(k\) and the optimal order-independent algorithm buys at price \(b^{(k)}\), and define \(\tilde{z}_k\) to be the probability that the arriving request has type \(k\) and the optimal order-independent algorithm sells at price \(s^{(k)}\). Then, there must be \(b^{(k)} + s^{(k)} \leq p^{(k)}\), as \(p^{(k)}\) is the probability that type \(k\) is realized. The inequality \[B_0 + T \cdot \sum_{k \in [K]} \tilde{z}_k - \tilde{y}_k ~\in [0, B]\] also holds, as the LHS represents the expected final inventory of the optimal order-independent algorithm. Then, \((\tilde{y}, \tilde{z})\) is a feasible solution of 6 , and therefore \({\mathsf{LP}}(y^*, z^*)\) upper-bounds the expected profit of the optimal offline algorithm, as we have \({\mathsf{LP}}(y^*, z^*) \geq {\mathsf{LP}}(\tilde{y}, \tilde{z})\), while the optimal order-independent profit upper-bounds the expected profit of the optimal offline algorithm. ◻

Proof of 5[item:asym-large-ub] and 4[item:sym-large-ub]. To prove the competitive ratio for the asymmetric case, we apply 3 with an extra pre-processing step: given an ATP instance with i.i.d. requests, we first solve 6 with the original capacity upper bound \(B\), but run 3 with a reduced capacity upper bound \(B_0\). This pre-processing step is feasible, as we recall that the optimal solution \((y^*, z^*)\) of 6 is not constrained by the upper bound \(B\) in constraint 8 . Since \(\Gamma = B_0 + T \cdot \alpha_B\geq B_0\), 3 achieves at least \(1 - O(\frac{\log B_0}{\sqrt{B_0}})\) times the \({\mathsf{LP}}(y^*, z^*)\), and therefore the competitive ratio of 3 is \(1 - O(\frac{\log B}{\sqrt{B_0}})\).

To prove the stronger bound of \(1 - O(\frac{(\log B)}{\sqrt{B}})\) for the symmetric case where \(b^{(k)} = s^{(k)}\), our proof relies on the following observation: given an ATP instance with symmetric prices, let \((y^*, z^*)\) be the optimal solution of 6 . If \(y^*_k + z^*_k < p^{(k)}\) for some \(k \in [K]\), increase \(y^*_k\) and \(z^*_k\) equally until constraint 7 becomes tight; note that the constraint 8 and the objective function value remain unchanged. Therefore, without loss of generality we may assume that constraint 7 is tight, and therefore \[\alpha_S+ \alpha_B~=~ \sum_{k \in [K]} (y^*_k + z^*_k) ~=~ \sum_{k \in [K]} p^{(k)} ~=~ 1,\] which implies \[2\Gamma ~=~ B_0 + T \cdot (\alpha_S+ \alpha_B) ~=~ B_0 + T ~\geq~ B;\] the final inequality uses the assumption from 1.1 that \(B \leq B_0+T\). Therefore, the competitive ratio of 3 for the ATP problem with symmetric prices becomes \(1 - O(\frac{\log B}{\sqrt{B}})\). ◻

Proof. Since \(T\alpha_S\geq 1\), we have that \(y'_k \in [0, y^*_k]\) and hence \(y''_k \leq y^*_k\). Therefore both the non-negativity constraints and constraint (7 ) are satisfied for both solutions. To verify (8 ) for \((y', z')\), note that \(B_0 + T \sum_k (z'_k - y'_k) = B_0 - \sum_k y'_k = B - 1 = 0\). Finally, \(B_0 + T \sum_k (z''_k - y''_k) = B_0 + T(\alpha_B- \alpha_S) + 1 = 0 + 1 \leq B\), where we used the definition of \((y'',z'')\) for the first equality, and (10 ) for the second equality. ◻

Proof. Observe that the fractional process corresponding to \((y', z')\) performs no buying action, and the total number of (fractional) selling action is \(1\). Therefore, solution \((y', z')\) can be viewed as the LP relaxation of a single-item Prophet Inequality instance. To be specific, consider the following independent rounding algorithm: when price tuple \((b_t, s_t)\) is realized with type \(k\), i.e., \((b_t, s_t) = (b^{(k)}, s^{(k)})\), we sell the unit inventory at price \(s^{(k)}\) with probability \(\frac{y'_k}{p^{(k)}}\), and terminate the process once this only copy is sold. Then, given that the inventory is not sold before \((b_t, s_t)\) is revealed, the probability that the inventory get sold is exactly \[\sum_{k \in [K]} p^{(k)} \cdot \frac{y'_k}{p^{(k)}} ~=~ \sum_{k \in [K]} p^{(k)} ~=~ \frac{\sum_{k\in [K]} y^*_k}{T \cdot \alpha_S} ~=~ T^{-1},\] and therefore the inventory remains unsold during the whole process is at least \[\left( 1 - \frac{1}{T} \right)^T ~\leq~ \frac{1}{e}.\] Therefore, the expected profit from this independent rounding process is at least \[\left(1 - \frac{1}{e}\right) \cdot \frac{\sum_{k \in [K]} p^{(k)} \cdot \frac{y'_k}{p^{(k)}} \cdot s^{(k)}}{T^{-1}} ~=~ \left(1 - \frac{1}{e}\right) \cdot {\mathsf{LP}}(y', z') ~\geq~ \frac{1}{2} \cdot {\mathsf{LP}}(y', z').\] where the equality follows from the fact that \(z'_k = 0\) for every \(k \in [K]\). ◻

Proof. Our proof relies on the following key observation: note that \[\begin{align} \sum_{k \in [K]} y''_k ~=~ \sum_{k \in [K]} y^{*}_k - \sum_{k \in [K]} y'_k ~=~ \alpha_S- \frac{B_0}{T} ~=~ \frac{\Gamma - B_0}{T} ~=~ \alpha_B~=~ \sum_{k \in [K]} z''_k, \end{align}\] i.e., regarding each request, following solution \((y'', z'')\) leads to the same probability of buying or selling a copy. Then, the probability that the inventory is \(0\) (or \(1\)) before every request \(t \in [T]\) arrives must be \(0.5\).

We prove the above statement via induction. The base case is \(t = 1\). The statement holds as we drop the initial copy with probability \(0.5\). Now assume \(\mathbf{Pr}[\text{inventory is }0 \text{ before }t] = 0.5\). For request \(t\), we have \[\begin{align} \mathbf{Pr}[\text{inventory is }0 \text{ before }t + 1] ~=~& \mathbf{Pr}[\text{inventory is }0 \text{ before }t] \cdot \Big(1 - \sum_{k \in [K]} p^{(k)} \cdot \frac{z''_k}{p^{(k)}} \Big) \\ ~&+ \mathbf{Pr}[\text{inventory is }1 \text{ before }t] \cdot \sum_{k \in [K]} p^{(k)} \cdot \frac{y''_k}{p^{(k)}} \\ ~=~& \frac{1}{2} \Big(1 - \sum_{k \in [K]} z''_k + \sum_{k \in [K]} y''_k \Big) ~=~ 0.5. \end{align}\] Therefore, \(\mathbf{Pr}[\text{inventory is }0 \text{ before }t + 1] = 0.5\) also holds, which implies the probability that the inventory is \(0\) (or \(1\)) before every request \(t \in [T]\) arrives is \(0.5\). Then, by linearity of expectation, the expected profit of 4 is \[\begin{align} &\sum_{t \in [T]} \sum_{k \in [K]} p^{(k)} \cdot \frac{y''_k}{p^{(k)}} \cdot s^{(k)} \cdot \mathbf{Pr}[\text{inventory is }1 \text{ before }t] \\ &~~- \sum_{t \in [T]} \sum_{k \in [K]} p^{(k)} \cdot \frac{z''_k}{p^{(k)}} \cdot b^{(k)} \cdot \mathbf{Pr}[\text{inventory is }0 \text{ before }t] \\ ~=~& \frac{T}{2} \cdot \Big(\sum_{k \in [K]} y''_k \cdot s^{(k)} - \sum_{k \in [K]} z''_k \cdot b^{(k)} \Big) ~=~ \frac{1}{2}\cdot {\mathsf{LP}}(y''_k, z''_k). \qedhere \end{align}\] ◻

Proof of 3. Running the algorithm from 16 with probability \(\frac{1}{2}\), and 4 otherwise, gives an expected profit of \[\frac{1}{2} \cdot \frac{1}{2} \cdot {\mathsf{LP}}(y'_k, z'_k) + \frac{1}{2} \cdot \frac{1}{2} \cdot {\mathsf{LP}}(y''_k, z''_k) ~=~ \frac{1}{4} \cdot {\mathsf{LP}}(y^*, z^*),\] where the equality uses the fact that \(y^*_k = y'_k + y''_k\) and \(z^*_k = z'_k + z''_k\) for every \(k \in [K]\). ◻

Proof of 1. Consider an ATP instance with \(B_0 = 0\) and \(T = B\), where requests are i.i.d.draws from the following distribution \(\mathcal{D}\): \[\begin{align} (b, s) \sim D = \begin{cases} (1, 0) & \text{w.p. } 1 - \frac{0.1}{B} \\ (+\infty, 2) & \frac{0.1}{B} \\ \end{cases} \end{align}\] Note that if an online algorithm observes a price tuple \((1, 0)\) and decides to buy at price \(1\), the probability that it can sell at price \(2\) in the future is at most \[1 - \Big(1 - \frac{0.1}{B}\Big)^T ~\approx 1 - e^{-0.1} ~\leq~ 0.1.\] This suggests that an online algorithm should never buy at price \(1\), since the expected profit is at most \(-1 + 2 \cdot 0.1 < 0\); consequently, the optimal online algorithm has an expected profit of \(0\). However, an optimal offline algorithm, which can see the future, can check if there is a price tuple \((+\infty, 2)\) following some occurrence of \((1,0)\)—which happens with constant probability—and get unit profit in these scenarios. This implies that no online algorithm can have finite competitiveness with the offline optimum. ◻

Proof of 4[item:asym-large-lb]. For the negative result in 4, note that when we have \(b^{(k)} = +\infty\) for every price tuple \((b^{(k)}, s^{(k)})\) in the support of the identical request distribution \(\mathcal{D}\), the ATP problem degenerates to the \(B_0\)-unit Prophet Inequality problem with identical value distributions, leading to a \(1 - \Omega(1/\sqrt{B_0})\) lower bound (see [9]). ◻

Proof. We give the proof for event \(\mathcal{F}_1\); the proof for \(\mathcal{F}_2\) is similar. The probability of \(\mathcal{E}_0\) is easy to analyze: standard Chernoff bounds ensure that the number of occurrences of each of the tuples deviates by more than \(c_1 \sqrt{B}\) is at most some constant. So it remains to bound the probability of \(\mathcal{E}_1\) given \(\mathcal{E}_0\). Fix the realization of the first half. Let \(B_t\) be the inventory after request \(t\) is processed, assuming we follow the strategy of selling a copy whenever the price equals \(1\), and buying a copy at all other “low” prices. Recall that \(\mathcal{E}_1\) requires two conditions:

1. Final Inventory Constraint: The final inventory \(B_T\) lands in \([0.5 c_2 \sqrt{B}, c_2 \sqrt{B}]\).

2. Intermediate Constraint: \(B_t \ge 0\) for all \(t \in (T/2, T]\).

Conditioned on the starting inventory \(B_{T/2}\), the Final Inventory Constraint requires the final inventory to be off by its expectation by \([c'\cdot \sqrt{B}, c'' \cdot \sqrt{B}]\) for some constants \(c', c''\) satisfying \(c'' - c' = 0.5\cdot c_2\). By a Chernoff bound, this happens with at least a constant probability.

Next, we take the Intermediate Constraint into consideration. We show that the probability that the Final Inventory Constraint holds while the Intermediate Constraint breaks is small enough. Note that if we follow the strategy of selling a copy whenever the price is \(1\) and buying a copy otherwise, in expectation the inventory decreases by \(0.5\) after processing each request. Therefore, when the Final Inventory Constraint holds while the Intermediate Constraint breaks, it indicates that within at most \(T\) steps after first hitting \(B_t = 0\), this random walk process, which has a constant leftward drift in expectation, travels \(0.5 c_2 \cdot \sqrt{B}\) steps to the right. Then, a standard random walk analysis can show that this event happens with probability at most \(e^{-\Omega(\sqrt{B})}\). Therefore, when the realization of the first half is fixed, we have \[\begin{align} &\mathbf{Pr}[\text{Final Inventory OK}\land \text{Intermediate OK}] \\ =~& \mathbf{Pr}[\text{Final Inventory OK}] - \mathbf{Pr}[\text{Final Inventory OK} \land \lnot \text{Intermediate OK}] \\ \geq~&\text{constant} \end{align}\] Finally, since the realizations of the two halves of the instance are independent, \(\mathbf{Pr}[\mathcal{E}_1]\) is at least an absolute constant. Furthermore, an identical analysis can also show that \(\mathbf{Pr}[\mathcal{F}_2]\) is at least an absolute constant. ◻

Proof of 5. Given the symmetric \({\textsf{ATP}}\) instance above. Now, given any online algorithm, we construct the following offline benchmark. When event \(\mathcal{F}_1\) happens, the offline algorithm simply buys whenever the price is \(0\) or \(0.5\), and sells whenever the price is \(1\). Similarly, when the disjoint event \(\mathcal{F}_2\) occurs, the offline algorithm buys whenever the price is \(0\) and sells whenever the price is \(1\). Otherwise, for all outcomes outside \(\mathcal{F}_1 \cup \mathcal{F}_2\), we mimic the online algorithm. It suffices to show that the offline algorithm significantly outperforms the online algorithm on at least one of these events.

We now analyze the performance loss of the online algorithm in these two cases. Observe that at time \(T/2\), the online algorithm cannot distinguish, conditioned on satifying \(\mathcal{E}_0\), whether the realization satisfies \(\mathcal{F}_1\) or \(\mathcal{F}_2\)—indeed, given the initial inventory level of \(B_0\) and the fact that \(T = 2B_0\), even selling at every single timestep would not cause inventory levels to be negative at time \(T/2\). Moreover, given \(\mathcal{E}_0\), the number of timesteps with price \(\frac{1}{2}\) is at least \[K := [(T/2) \cdot (1/\sqrt{B})] - c_1 \sqrt{B} = (1/3 - c_1)\cdot \sqrt{B}.\] We now consider whether the online algorithm purchases at least \(K/2\) copies at price \(\frac{1}{2}\) by \(T/2\).

• If it does buy at least \(K/2\) copies at price \(\frac{1}{2}\), then its profit is less than the profit of the offline algorithm which only buys at 0 by at least \(K/2\), for all outcomes in \(\mathcal{E}_2\).

• On the other hand, if the online algorithm purchases fewer than \(K/2\) copies at price \(\frac{1}{2}\) by time \(T/2\), then it must have rejected at least \(K/2\) copies at price \(\frac{1}{2}\). Now the algorithm that buys all items at prices \(0\) and \(\frac{1}{2}\) on outcomes in \(\mathcal{E}_1\) would buy all \(K\) these copies, and still sell them, thereby making at least \(K/2\cdot \frac{1}{2}\) more profit.

Since \(c_2, c_1 \ll 1\), this implies the regret of the online algorithm (versus an offline algorithm) is at least \(\Omega(\sqrt{B}) \cdot \min(\mathbf{Pr}[\mathcal{F}_1], \mathbf{Pr}[\mathcal{F}_2])\), which is \(\Omega(\sqrt{B})\) by 18, thereby completing the proof. ◻

Proof of 6. It suffices to show that taking \[x_{i, j} ~=~ \mathbf{Pr}\left[\text{optimal offline solution buys from }i \text{ and sells to }j\right]\] gives a feasible solution of 1 .

Constraints 2 are feasible, as the probability that the optimal offline algorithm chooses an action of either buy or sell for request \(i\) is at most \(p_i\). Constraints 3 are feasible, as the quantity of \(\sum_{i = 0}^{t-1} \sum_{j = t}^T x_{i, j}\) represents the expected number of the copy that the optimal offline algorithm carries after request \(t\), which is at most \(1\), as the offline algorithm can carry at most one copy at any time. Therefore, solution \(x\) is feasible. ◻

Proof of 8. Note that it suffices to prove 8 only for \(m = 1\), since when solution \(x\) of 1 is an \(m\)-trades solution, \(x/m\) becomes a \(1\)-trade solution, and applying 8 to solution \(x/m\) gives the desired argument for \(x\).

When solution \(x\) is a \(1\)-trade solution on interval \([\ell, r]\), there must be \(\sum_{i = \ell}^r q^b_i(x) = \sum_{i = \ell}^r q^s_i(x) \leq 1\) (7.[item:mtrades-ii]), and the value of \(q^b_i(x)\) and \(q^s_i(x)\) can be non-zero only when \(i \in [\ell, r]\) (7.[item:mtrades-i]). Our main idea is to apply a standard OCRS algorithm based on the values \(q^b_i(x)\) and \(q^s_i(x)\). To be specific, we show that 5 is the desired algorithm for 8.

Proving the probability of holding a copy. We first prove that after 5 is finished, the algorithm still keeps a copy in hand with probability \(0.5\). To achieve this, we show that when the algorithm holds a copy when 5 begins, the copy is sold by 5 with probability \(\frac{1}{2} \cdot \sum_{i = \ell}^r q^s_i(x)\). We prove by induction that for each \(i\in [l, r]\), after request \(i\) arrives, the copy remains available with probability \(1 - \frac{1}{2} \cdot \sum_{j = \ell}^i q^s_j(x)\). The base case is \(i = \ell - 1\), and the copy is available with probability \(1\). Now assume the claim holds till request \(i-1\). If the item remains available for request \(i\), 5 sells the item with probability \[p_i \cdot \frac{q^s_i(x)}{p_i} \cdot \frac{0.5}{1 - 0.5 \cdot \sum_{j = \ell}^{i-1} q^s_j(x)} ~=~ \frac{0.5\cdot q^s_i(x)}{1 - 0.5 \cdot \sum_{j = \ell}^{i-1} q^s_j(x)}.\] Since whether the price tuple \((b_i, s_i)\) arrives and whether 5 sells the copy is independent to the decisions before request \(i\), the copy remains available after request \(i\) with probability \[\left(1 - \frac{1}{2} \cdot \sum_{j = \ell}^{i-1} q^s_j(x) \right) \cdot \left( 1 - \frac{0.5\cdot q^s_i(x)}{1 - 0.5 \cdot \sum_{j = \ell}^{i-1} q^s_j(x)} \right) ~=~ 1 - \frac{1}{2} \cdot \sum_{j = \ell}^{i} q^s_j(x),\] which proves the claim for the case after request \(i\). Then, applying the claim for request \(r\) shows that the item remains available with probability \(1 - \frac{1}{2} \cdot \sum_{i = \ell}^r q^s_i(x)\), and equivalently the item is sold with probability \(\frac{1}{2} \cdot \sum_{i = \ell}^r q^s_i(x)\).

Symmetrically, when the algorithm does not hold a copy when 5 begins, it buys a copy with probability \(\frac{1}{2} \cdot \sum_{i = \ell}^r q^b_i(x)\). Then, after 5 finishes, the algorithm holds a copy with probability \[0.5 \cdot \left(1 - \frac{1}{2} \cdot \sum_{i = \ell}^r q^s_i(x)\right) + 0.5 \cdot \frac{1}{2} \cdot \sum_{i = \ell}^r q^b_i(x) ~=~ 0.5,\] where we use the fact that \(\sum_{i = \ell}^r q^s_i(x) = \sum_{i = \ell}^r q^b_i(x)\) in the last equality, which is true because every non-zero \(x_{i,j}\) (buy at \(i\), sell at \(j\)) satisfies \(l\leq i<j\leq r\). So the total probability of buys and sells within the internal \([l,r]\) are equal.

Proving the expected profit. Next, we calculate the expected profit achieved by 5. We first calculate the expected selling gain. Recall that an item remains available for request \(i\) with probability \(1 - \frac{1}{2} \cdot \sum_{j = \ell}^{i-1} q^s_j(x)\), and the algorithm sells the item at price \(s_i\) with probability \(\frac{0.5\cdot q^s_i(x)}{1 - 0.5 \cdot \sum_{j = \ell}^{i-1} q^s_j(x)}\). Therefore, the total expected gain (assuming the algorithm holds a copy) is \[\begin{align} \sum_{i = \ell}^r s_i \cdot \frac{0.5\cdot q^s_i(x)}{1 - 0.5 \cdot \sum_{j = \ell}^{i-1} q^s_j(x)} \cdot \left(1 - \frac{1}{2} \cdot \sum_{j = \ell}^{i-1} q^s_j(x)\right) ~=~ \frac{1}{2} \cdot \sum_{i = \ell}^r s_i \cdot q^s_j(x). \end{align}\] Symmetrically, the total expected gain assuming the algorithm does not hold a copy is \[\begin{align} \frac{1}{2} \cdot \sum_{i = \ell}^r b_i \cdot q^b_j(x). \end{align}\] Given that the decision maker holds a copy with probability \(\frac{1}{2}\) before the algorithm begins, the total expected profit achieved by 5 is \[\begin{align} \frac{1}{4} \cdot \sum_{i = \ell}^r (s_i \cdot q^s_j(x) - b_i \cdot q^b_j(x)) ~&=~ \frac{1}{4} \cdot \sum_{i = \ell}^r s_i \cdot \sum_{j = 0}^{i-1} x_{j,i} - \frac{1}{4} \cdot \sum_{i = \ell}^r b_i \cdot \sum_{j = i+1}^{r} x_{i,j} \\ ~&=~ \frac{1}{4} \cdot \sum_{i = \ell}^r \sum_{j = i+1}^r x_{i, j} \cdot (s_j - b_i) ~=~ \frac{1}{4} \cdot {\mathsf{LP}}(x), \end{align}\] where the second-last equality is because \(x_{i,j}=0\) if \(i\) or \(j\) are not in \([l, r]\). ◻

Proof of 9. Let \(x\) be a feasible solution of 1 that admits an \(m\)-trades decomposition corresponding to intervals \([\ell_1, r_1], \cdots, [\ell_D, r_D]\). We assume without loss of generality that the intervals are sorted in order. For \(d \in [D]\), define solution \(\hat{x}^{(d)}\) as \(\hat{x}^{(d)}_{i, j} = x_{i, j} \cdot \mathbf{1}\big[i, j \in [\ell_d, r_d]\big]\). By definition, every \(\hat{x}^{(d)}\) is an \(m\)-trades solution on \([\ell_d, r_d]\).

Consider the algorithm that first buy a free copy from request \(0\) with probability \(0.5\), and then run 5 sequentially for solutions \(\hat{x}^{(1)}, \cdots, \hat{x}^{(D)}\). Then, by 8, the expected total profit of the above algorithm is \[\sum_{d \in [D]} \frac{1}{4m} \cdot {\mathsf{LP}}(\hat{x}^{(d)}) ~=~ \frac{1}{4m} \cdot {\mathsf{LP}}(x),\] where the equality follows from the definition of \(m\)-trades decomposition. ◻

Proof of [thm:iid-large-general]. We first verify that 3 is feasible, which requires \[\tau = T - \left \lceil 13\log B \cdot \sqrt{T/\alpha_S} \right \rceil \geq 0.\] Note that \(\tau \geq 0\) must be satisfied when \(T^2 \geq 14^2 \log^2 B \cdot \frac{T}{\alpha_S}\), which implies \[\Gamma ~\geq~ 196 \log^2 B.\] To fulfill this condition, we make an extra update before running 3: if \(B > 2\Gamma\), we set \(B \gets 2\Gamma\). Note that this update can only degrade the performance of 3, while it does not change our proof of [thm:iid-large-general], as the term \(\log B/B\) is infinitesimal with respect to the term \(\log B/\sqrt{\Gamma}\) when \(B \geq \Omega(\Gamma)\). Therefore, assuming \(B \leq 2\Gamma\) for 3 is without loss of generality, and inequality \(\Gamma ~\geq~ 196 \log^2 B\) holds when \(\Gamma\) is sufficiently large, which is also without loss of generality as 3 trivially holds when \(\Gamma\) is upper-bounded by a constant.

Next, we prove the competitive ratio of 3. By 22 and the fact that \(X_T \in [0, B]\), the value of \(\mathbb{E}[X_T]\) is bounded by \[\mathbb{E}[X_T] ~\leq~ (1 - 2B^{-2}) \cdot \frac{T - \tau}{T} \cdot B_0 + 2B^{-2} \cdot B ~\leq~ \frac{T - \tau}{T} \cdot B_0 + \frac{2B_0}{B},\] where the last inequality uses the assumption that \(B_0 \geq 1\). Then, by 21, the competitive ratio of 3 is at least \[1 - \frac{\mathbb{E}[X_T]}{B_0} - \frac{T - \tau}{T} - \frac{\mathbb{E}[M^+_\tau]}{\Gamma} ~\geq~ 1 - \frac{2(T - \tau)}{T} - \frac{3}{B} - \frac{13\log B}{\sqrt{\Gamma}} ~\geq~ 1 - \frac{3}{B} - \frac{41 \log B}{\sqrt{\Gamma}},\] where the last inequality uses the fact that \[\frac{T - \tau}{T} ~=~ \frac{\left \lceil 13\log B \cdot \sqrt{T/\alpha_S} \right \rceil}{T} ~\leq~ \frac{14\log B \cdot \sqrt{T/\alpha_S}}{T} ~=~ \frac{14 \log B}{\sqrt{\Gamma}}. \qedhere\] ◻

Proof of 21. In 3, we first realize each request’s type, and then decide our action via independent rounding. Since these two sources of randomness are independent, it’s equivalent to first realize our decision \(\xi_t\), and then we realize the type of current request to decide the buying/selling price. By conditional expectation, when \(\xi_t = -1\), the expected selling price is exactly \[\frac{\sum_{k \in [K]} p^{(k)} \cdot \frac{y^*_k}{p^{(k)}} \cdot s^{(k)} }{\sum_{k \in [K]} p^{(k)} \cdot \frac{y^*_k}{p^{(k)}}} ~=~ \bar s,\] and similarly, when \(\xi_t = 1\), the expected buying price is exactly \(\bar b\).

Note that when \(\xi_t\) is fixed, whether the buy/sell action is proceeded only depends on the current inventory, instead of the buying/selling price. Since \(N^+_T\) and \(N^-_T\) represents the number of buys and sells we perform, the expected profit of 3 can be written as \[\begin{align} \mathbb{E}[N^-_T] \cdot \bar s - \mathbb{E}[N^+_T] \cdot \bar b. \end{align}\] Note that for any realization of the instance, there must be \(X_0 + N^+_t - N^-_t = X_T\). By replacing \(N^-_t\) by \(X_0 + N^+_t - X_T\), we further simplify the above expression as \[\begin{align} \big(B_0 + \mathbb{E}[N^+_T] - \mathbb{E}[X_T] \big) \cdot \bar s - \mathbb{E}[N^+_T] \cdot \bar b ~=~ \big(B_0 - \mathbb{E}[X_T] \big) \cdot \bar s + \mathbb{E}[N^+_\tau] \cdot (\bar s - \bar b), \label{eq:alg-bound} \end{align}\tag{14}\] where the equality uses the observation that 3 no longer buys a copy after request \(\tau\), and therefore \(N^+_T = N^+_\tau\). We further note that \[N^+_\tau ~=~ \sum_{t \in [\tau]} \mathbf{1}[\xi_t = 1] - M^+_\tau.\] Since \(\mathbf{Pr}[\xi_t = 1] = \alpha_B\) for every \(t \leq \tau\), taking expectation over the above inequality and applying to 14 further simplifies the expected profit of 3 as \[\begin{align} \big(B_0 - \mathbb{E}[X_T] \big) \cdot \bar s + \big(\alpha_B\cdot \tau - \mathbb{E}[M^+_\tau]\big) \cdot (\bar s - \bar b). \label{eq:alg-bound-final} \end{align}\tag{15}\]

Next, we rewrite the value of \({\mathsf{LP}}(y^*, z^*)\) with newly defined notations. We have \[\begin{align} {\mathsf{LP}}(y^*, z^*) ~&=~ T \cdot \sum_{k \in [K]} \big(s^{(k)} \cdot y_k - b^{(k)} \cdot z_k \big) \notag \\ ~&=~ T \cdot \alpha_S\cdot \bar s - T \cdot \alpha_B\cdot \bar b \notag \\ ~&=~ B_0 \cdot \bar s + T \cdot \alpha_B\cdot (\bar s - \bar b), \label{eq:lp-bound-final} \end{align}\tag{16}\] where the second line follows the definition of \(\alpha_B, \alpha_S, \bar b, \bar s\), and the third line uses the observation that \(T \cdot \alpha_S= \Gamma = T \cdot \alpha_B+ B_0\). Subtracting 15 from 16 gives the profit gap between 3 and \({\mathsf{LP}}(x^*, y^*)\) as \[\begin{align} \mathbb{E}[X_T] \cdot \bar s + \big( (T - \tau) \cdot \alpha_B+ \mathbb{E}[M^+_\tau] \big) \cdot (\bar s - \bar b) \label{eq:loss-bound-final} \end{align}\tag{17}\] Therefore, the competitive ratio of 3 is at least \[\begin{align} 1 - \frac{\text{expr.}~\eqref{eq:loss-bound-final}}{\text{expr.}~\eqref{eq:lp-bound-final}} ~&\geq~ 1 - \frac{\mathbb{E}[X_T] \cdot \bar s}{B_0 \cdot \bar s} - \frac{(T - \tau) \cdot \alpha_B\cdot (\bar s - \bar b)}{T \cdot \alpha_B\cdot (\bar s - \bar b)} - \frac{\mathbb{E}[M^+_\tau]\cdot (\bar s - \bar b)}{(B_0 + T \cdot \alpha_B) \cdot (\bar s - \bar b)} \\ ~&\geq~1 - \frac{\mathbb{E}[X_T]}{B_0} - \frac{T - \tau}{T} - \frac{\mathbb{E}[M^+_\tau]}{\Gamma}. \qedhere \end{align}\] ◻

Proof. We first observe that there must be \(W_t \geq X_t\) for every \(t \in [\tau]\). We show this observation via contradiction: suppose \(t \in [\tau]\) is the smallest index that satisfies \(W_t < X_t\). Since all the random walk processes we defined move by at most one step at each time increment, there must be \(W_{t - 1} = X_{t-1}\), which implies \[X_t - X_{t - 1} ~=~ \xi_t \cdot \mathbf{1}\big[X_{t-1} + \xi_t \in [0, B] \big] ~\leq~ \xi_t \cdot \mathbf{1}\big[W_{t-1} + \xi_t \geq 0 \big] ~=~ W_t - W_{t-1},\] which is in contrast to the assumption of \(W_t < X_t\). Therefore, there must be \(W_\tau \geq X_\tau\).

We further show that \[\begin{align} W_\tau ~\leq~ U_\tau - \min \Big\{0,~ \min_{t \in [\tau]} U_t \Big\} \label{eq:wt-bound} \end{align}\tag{18}\] to finish the proof of 26. Fix the realization of \(\{\xi_t\}_{t \in [\tau]}\). Let \(U_m = \min_{t \in [\tau]} U_t\) be the minimum value attained by \(U_t\). If \(U_m \geq 0\), then there must be \(W_t = U_t\) for every \(t \in [\tau]\), and 18 holds. Otherwise, we define \(\widetilde{U}_t\) and \(\widetilde{W}_t\) to be the unbounded and left-bounded random walk processes with a shifted initial position, i.e., we have \(\widetilde{U}_0 = \widetilde{W}_0 = B_0 - U_m\), while \[\widetilde{U}_t ~=~ \widetilde{U}_{t-1} + \xi_t, \qquad \text{and} \qquad \widetilde{W}_t = \widetilde{W}_{t - 1} + \xi_t \cdot \mathbf{1}\big[\widetilde{W}_{t-1} + \xi_t \geq 0\big]\] for \(t \in [\tau]\). Note that condition \(\widetilde{W}_{t-1} + \xi_t \geq 0\) always holds. If not, let \(t\) be the minimum index such that \(\widetilde{W}_{t - 1} + \xi_t < 0\). Then, there must be \(\widetilde{W}_{t - 1} = \widetilde{U}_{t - 1} = 0\) while \(\xi_t = -1\), and therefore \(\widetilde{U}_t = -1\). This implies \[\begin{align} U_t ~=~ \widetilde{U}_t - \widetilde{U}_0 + U_0 ~=~ -1 - (B_0 - U_m) + B_0 ~=~ U_m - 1, \end{align}\] which is in contrast to the assumption that \(U_m = \min_{t \in [\tau]} U_t\). Therefore, \(\mathbf{1}\big[\widetilde{W}_{t-1} + \xi_t \geq 0\big] = 1\) always holds, implying that \(\widetilde{W}_t = \widetilde{U}_t\).

Finally, note that \(\widetilde{W}_t \geq W_t\) always holds, as \(\widetilde{W}_t\) and \(W_t\) share the same update process, while \(\widetilde{W}_0 = W_0 - U_m > W_0\) (recall that we assume \(U_m < 0\)). Then, \[\begin{align} W_\tau ~\leq~ \widetilde{W}_\tau ~=~ \widetilde{U}_\tau ~=~ U_\tau - U_0 + \widetilde{U}_0 ~=~ U_\tau - U_m, \end{align}\] which proves 18 . ◻

Proof of 24. Recall that for \(t \in [\tau]\), \(\xi_t\) equals to \(-1\) with probability \(\alpha_S\), \(1\) with probability \(\alpha_B\), and \(0\) otherwise. Then, for \(t \in [\tau]\), we have \[\mathbb{E}[U_t] = B_0 + \sum_{t' \in [t]} \mathbb{E}[\xi_{t'}] ~=~ B_0 - t \cdot (\alpha_S- \alpha_B).\]

Define \(Y_t = U_t - \mathbb{E}[U_t]\). Then, \(\{Y_t\}_{t \in [\tau]}\) is a martingale with increments \[\Delta Y_t ~=~ Y_t - Y_{t-1} ~=~ \xi_t - (\alpha_S- \alpha_B).\] Then, the absolute value of the increments is bounded by \[|\Delta Y_t| ~\leq~ |\xi_t| + |\alpha_S- \alpha_B| ~\leq~ 2.\] Furthermore, since \(\xi_t\) is a random variable independent to the history till \(t - 1\), the predictable quadratic variation \(\langle Y \rangle_t\) satisfies \[\begin{align} \langle Y \rangle_t ~=~ \sum_{t' \in [t]} \mathbb{E}\left[ \big(\xi_{t'} - (\alpha_S- \alpha_B)\big)^2\right] ~=~ t \cdot \mathbb{E}[\xi^2_t] - t \cdot (\alpha_S- \alpha_B)^2 ~\leq~ t \cdot (\alpha_S+ \alpha_B) ~\leq~ 2 \Gamma, \end{align}\] where the second equality uses the fact that every \(\xi_t\) is i.i.d. with expectation \(\alpha_S- \alpha_B\), and the last inequality uses the fact that \(t \leq \tau \leq T\), while \(T \cdot (\alpha_S+ \alpha_B) \leq 2T \cdot \alpha_S= 2\Gamma\). Let \(\epsilon = 6\sqrt{\Gamma} \cdot \log B\). By Freedman’s Inequality (20), we have \[\begin{align} \mathbf{Pr}\left[ \max_{t \in [\tau]} |Y_t| \ge \epsilon \text{ and } \langle Y \rangle_\tau \le 2\Gamma \right] \le 2 \exp\left( -\frac{\epsilon^2 / 2}{2\Gamma + 2\epsilon / 3} \right) \leq 2\exp(-3\log B) \leq B^{-2}, \label{eq:xtau-freedman} \end{align}\tag{19}\] where the second inequality uses the fact that \[\epsilon^2/2 ~=~ 18\Gamma \cdot \log^2 B ~\geq~ 3\log B \cdot (2\Gamma + 4\sqrt{\Gamma} \cdot \log B),\] and the last inequality holds when \(B\) is sufficiently large. Then, we have \[\begin{align} &\mathbf{Pr}\left[ X_\tau \leq 12\sqrt{\Gamma} \cdot \log B + \frac{T - \tau}{T} \cdot B_0\right] \\ \geq~& \mathbf{Pr}\left[U_\tau \leq 6 \sqrt{\Gamma} \cdot \log B + \frac{T - \tau}{T} \cdot B_0 ~\land~ \min_{t \in [\tau]} U_t \geq -6 \sqrt{\Gamma} \cdot \log B \right] \\ \geq~& \mathbf{Pr}\left[Y_\tau \leq 6 \sqrt{\Gamma} \cdot \log B ~\land~ \min_{t \in [\tau]} Y_t \geq -6 \sqrt{\Gamma} \cdot \log B \right] \\ \geq~& \mathbf{Pr}\left[ \max_{t \in [\tau]} |Y_t| \leq 6\sqrt{\Gamma} \cdot \log B \right] \\ \geq~& 1 - \mathbf{Pr}\left[ \max_{t \in [\tau]} |Y_t| \geq 6\sqrt{\Gamma} \cdot \log B =\epsilon ~\land~ \langle Y \rangle_\tau \le 2\Gamma \right] ~\geq~ 1 - B^{-2}, \end{align}\] where the first inequality uses 26; the second inequality uses the fact that for every \(t \in [\tau]\), we have \[\mathbb{E}[U_t] ~\geq~ \mathbb{E}[U_\tau] ~=~ B_0 -\tau \cdot (\alpha_S- \alpha_B) ~=~ B_0 - \tau \cdot \frac{B_0}{T} ~=~ \frac{T - \tau}{T} \cdot B_0 ~\geq~ 0,\] and therefore \(Y_\tau \leq \epsilon\) implies \(U_\tau \leq \epsilon + \mathbb{E}[U_\tau]\), while \(Y_t \geq -\epsilon\) implies \(U_t \geq -\epsilon\); the last line uses 19 and the fact that \(\langle Y \rangle_\tau \le 2\Gamma\) always holds. ◻

Proof of 25. When \(t \in [\tau + 1, T]\), 3 attempts to sell one copy with probability \(\alpha_S\). To prove 25, it suffices to show that the total number of selling attempts when \(t \in [\tau + 1, T]\) is at least \(12 \sqrt{\Gamma} \cdot \log B\), i.e., we aim at showing \[\begin{align} \mathbf{Pr}\left[\sum_{t = \tau + 1}^T \mathbf{1}[\xi_t = -1] ~\geq~ 12 \sqrt{\Gamma} \cdot \log B \right] ~\geq~ 1- B^{-2}. \label{eq:clear-inv-bound-target} \end{align}\tag{20}\]

We prove 20 via Bernstein’s Inequality. Note that each \(\mathbf{1}[\xi_t = -1]\) is an independent variable that equals to \(1\) with probability \(\alpha_S\), and \(0\) otherwise. Then, we have \(\mathbb{E}[\mathbf{1}[\xi_t = -1]] = \alpha_S\), and the variance of the summation of mean-zero random variables \(\mathbf{1}[\xi_t = -1]- \alpha_S\) can be bounded as \[\begin{align} \mathsf{Var}\left(\sum_{t = \tau + 1}^T \mathbf{1}[\xi_t = -1] - \alpha_S\right) ~&=~ \mathsf{Var}\left(\sum_{t = \tau + 1}^T \mathbf{1}[\xi_t = -1] \right) \\ ~&\leq~ \sum_{t = \tau + 1}^T \mathbb{E}\big[\mathbf{1}^2[\xi_t = -1] \big]\\ ~&=~ (T - \tau) \cdot \alpha_S~\leq~ 14\sqrt{\Gamma} \cdot \log B. \end{align}\] Then, we have \[\begin{align} \mathbf{Pr}\left[\sum_{t = \tau + 1}^T \mathbf{1}[\xi_t = -1] < 12 \sqrt{\Gamma} \cdot \log B \right] ~&\leq~ \mathbf{Pr}\left[\sum_{t = \tau + 1}^T \big(\mathbf{1}[\xi_t = -1] - \alpha_S\big) ~<~ -\sqrt{\Gamma} \cdot \log B \right] \\ ~&\leq~ \exp \left(-\frac{\Gamma \cdot \log^2 B/2}{14\sqrt{\Gamma} \cdot \log B + \sqrt{\Gamma} \cdot \log B / 3}\right) \\ ~&\leq~ \exp \left(-\frac{ \sqrt{\Gamma }\cdot \log B}{30}\right) ~\leq~ B^{-2}, \end{align}\] where the first inequality uses the fact that \((T - \tau) \cdot \alpha_S~\geq~ 13 \sqrt{\Gamma} \cdot \log B\); the second inequality follows Bernstein’s Inequality (19), which is applicable as every random variable \(\mathbf{1}[\xi_t = -1] - \alpha_S\) is mean-zero; the last line holds when \(\Gamma\) is sufficiently large. Taking the complement of the above inequality gives 20 . ◻

Proof. We prove 27 via constructing a series of random-walk processes. Each of these random walks are restricted to \([0, B]\)—any steps that cause them to move outside this interval are “blocked” and cause the position to remain unchanged. We first initiate \(\{X^{(1)}_t\}_{t \in [\tau]}\) to be the process equivalent to \(\{X_t\}_{t \in [\tau]}\), i.e., we have \(X^{(1)}_0 = B_0\), \(\xi^{(1)}_t\) be an independent random variable that equals to \(-1\) with probability \(\alpha_S\), equals to \(1\) with probability \(\alpha_B\), and equals to \(0\) otherwise. The update rule follows \(X^{(1)}_t = X^{(1)}_{t - 1} + \xi^{(1)}_t \cdot \mathbf{1}[X^{(1)}_{t - 1} + \xi^{(1)}_t \in [0, B]]\). Let \(M^{(1)}_T\) be the number of rounds the random walk step is blocked by the upper boundary \(B\), i.e., the number of \(t \in [T]\) that satisfies \(X^{(1)}_{t - 1} = B\) while \(\xi^{(1)}_t = +1\). Then, there must be \(\mathbb{E}[M^+_\tau] = \mathbb{E}[M^{(1)}_\tau]\).

Now, we start to modify the random walk process. We first construct a process \(\{X^{(2)}_t\}_{t \in [T]}\) identical to the process \(\{X^{(1)}_t\}_{t \in [\tau]}\), except that the number of steps in the random walk increases from \(\tau\) to \(T\). Let \(M^{(2)}_T\) be the number of rounds the random walk step is blocked by the upper boundary \(B\). Since \(\{X^{(2)}_t\}\) follows the same process but with a larger number of steps, there must be \[\mathbb{E}[M^+_\tau] ~=~ \mathbb{E}[M^{(1)}_\tau] ~\leq~ \mathbb{E}[M^{(2)}_T].\]

Next, we construct a process \(\{X^{(3)}_t\}_{t \in [T]}\) identical to the process \(\{X^{(2)}_t\}_{t \in [T]}\), except that the initial position in the random walk shifts from \(X^{(2)}_0 = B_0\) to \(X^{(3)}_0 = B\). Let \(M^{(3)}_T\) be the number of rounds the random walk step is blocked by the upper boundary \(B\). Since \(\{X^{(3)}_t\}\) follows the same process but with an initial position closer to the upper boundary, there must be \[\mathbb{E}[M^+_\tau] ~\leq~ \mathbb{E}[M^{(2)}_T] ~\leq~ \mathbb{E}[M^{(3)}_T].\]

The next process we construct is \(\{X^{(4)}_t\}_{t \in [T]}\), which is identical to the process \(\{X^{(3)}_t\}_{t \in [T]}\), except that the transitioning probability of the random walk process differs: let \(\xi^{(4)}_t\) be the step we aim at taking in round \(t\) for process \(\{X^{(4)}_t\}_{t \in [T]}\), and let \(\xi^{(3)}_t\) be the step we aim at taking for process \(\{X^{(3)}_t\}_{t \in [T]}\). Recall that we have \[\mathbf{Pr}[\xi^{(3)}_t = -1] ~=~ \alpha_S, \quad \text{and} \quad \mathbf{Pr}[\xi^{(3)}_t = 1] ~=~ \alpha_B, \quad \text{and} \quad \mathbf{Pr}[\xi^{(3)}_t = 0] ~=~ 1 - \alpha_S- \alpha_B.\] For process \(\{X^{(4)}_t\}_{t \in [T]}\), we update the probabilities to \[\mathbf{Pr}[\xi^{(4)}_t = -1] ~=~ \mathbf{Pr}[\xi^{(4)}_t = 1] ~=~ \bar \alpha, \quad \text{and} \quad \mathbf{Pr}[\xi^{(4)}_t = 0] ~=~ 1 - \alpha_S- \alpha_B~=~ \mathbf{Pr}[\xi^{(3)}_t = 0],\] where we recall \(\bar \alpha = 0.5 \cdot (\alpha_S+ \alpha_B)\). Since \(\alpha_S\geq \alpha_B\), comparing to process \(\{X^{(3)}_t\}_{t \in [T]}\), process \(\{X^{(4)}_t\}_{t \in [T]}\) keeps the same stay-in-place probability, decreases the probability of going towards \(-1\), while increases the probability of going towards \(+1\). Let \(M^{(4)}_T\) be the number of rounds the random walk step in process \(\{X^{(4)}_t\}_{t \in [T]}\) is blocked by the upper boundary \(B\). Then, there must be \[\mathbb{E}[M^+_\tau] ~\leq~ \mathbb{E}[M^{(3)}_T] ~\leq~ \mathbb{E}[M^{(4)}_T].\]

Finally, note that the process \(\{X^{(4)}_t\}_{t \in [T]}\) and the process \(\{\widetilde{X}_t\}_{t \in [T]}\) exhibit mirror symmetry. Therefore, there must be \[\mathbb{E}[M^+_\tau] ~\leq~ \mathbb{E}[M^{(4)}_T] ~=~ \mathbb{E}[\widetilde{M}^-_T]. \qedhere\] ◻

Proof. For simplicity of the proof, we also define \(\widetilde{M}^+_T\) to be the number of rounds the random walk step in process \(\{\widetilde{X}_t\}_{t \in [T]}\) is blocked by the upper boundary \(B\). By linearity of expectation and the fact that the realization of \(\tilde{\xi}_t\) is independent to the position \(\widetilde{X}_{t-1}\), we have \[\begin{align} \mathbb{E}[\widetilde{M}^-_T] ~=~\sum_{t = 0}^{T - 1} \bar \alpha \cdot \mathbf{Pr}[\widetilde{X}_t = 0], \quad \text{and} \quad \mathbb{E}[\widetilde{M}^+_T] ~=~\sum_{t = 0}^{T - 1} \bar \alpha \cdot \mathbf{Pr}[\widetilde{X}_t = B] \label{eq:balanced-walk-mt} \end{align}\tag{21}\]

To prove 28, we first analyze the drift of \(\widetilde{X}_t\). Note that when \(\widetilde{X}_t\) is neither \(0\) nor \(B\), we have \(\mathbb{E}[\widetilde{X}_{t+1} - \widetilde{X}_t] = 0\). When \(\widetilde{X}_t = 0\), \(\widetilde{X}_{t+1}\) moves to \(1\) with probability \(\bar \alpha\) and stays at \(0\) otherwise, so \(\mathbb{E}[\widetilde{X}_{t+1} - \widetilde{X}_t] = \bar \alpha\). Similarly, when \(\widetilde{X}_t = B\), \(\widetilde{X}_{t+1}\) moves to \(B - 1\) with probability \(\bar \alpha\) and stays at \(B\) otherwise, so \(\mathbb{E}[\widetilde{X}_{t+1} - \widetilde{X}_t] = -\bar \alpha\). By linearity of expectation, we have \[\begin{align} \mathbb{E}[\widetilde{X}_T] ~=~\mathbb{E}[\widetilde{X}_T - \widetilde{X}_0] ~=~ \bar \alpha \cdot \sum_{t = 0}^T \mathbf{Pr}[\widetilde{X}_t = 0] - \bar \alpha \cdot \sum_{t = 0}^T \mathbf{Pr}[\widetilde{X}_t = B] ~=~ \mathbb{E}[\widetilde{M}^-_T] - \mathbb{E}[\widetilde{M}^+_T], \label{eq:balanced-walk-first} \end{align}\tag{22}\] where we apply the fact that \(\widetilde{X}_0 = 0\) in the first equality, and 21 in the last equality.

Net, we analyze the drift of \(\widetilde{X}^2_t\). Fix \(\widetilde{X}_t\). When \(\widetilde{X}_t\) is not at the boundary, we have \[\mathbb{E}[\widetilde{X}^2_{t+1} - \widetilde{X}^2_t] ~=~ \bar \alpha \cdot \big((\widetilde{X}_t - 1)^2 - \widetilde{X}^2_t\big) + \bar \alpha \cdot \big((\widetilde{X}_t + 1)^2 - \widetilde{X}^2_t\big) ~=~ 2\bar \alpha.\] When \(\widetilde{X}_t = 0\), \(\widetilde{X}_{t+1}\) changes to \(1\) with probability \(\bar \alpha\) and stays otherwise, so \(\mathbb{E}[\widetilde{X}^2_{t+1} - \widetilde{X}^2_t] = \bar \alpha = 2\bar \alpha - \bar \alpha\). Similarly, when \(\widetilde{X}_t = B\), we have \(\mathbb{E}[\widetilde{X}^2_{t+1} - \widetilde{X}^2_t] = \bar \alpha \cdot (1 - 2B) = 2\bar \alpha - 2\bar \alpha B - \bar \alpha\). By linearity of expectation, we have \[\begin{align} \mathbb{E}[\widetilde{X}^2_T] ~=~ \mathbb{E}[\widetilde{X}^2_T - X^2_0] ~&=~ 2\bar \alpha\cdot T - \alpha \cdot \sum_{t = 0}^{T-1} \mathbf{Pr}[\widetilde{X}_t = 0] -(2\bar \alpha B + \alpha) \cdot \sum_{t = 0}^{T-1} \mathbf{Pr}[\widetilde{X}_t = B] \notag \\ ~&=~ 2\bar \alpha\cdot T - \mathbb{E}[\widetilde{M}^-_T] -(2B+1) \cdot \mathbb{E}[\widetilde{M}^+_T], \label{eq:balanced-walk-second} \end{align}\tag{23}\] where the last inequality uses 21 . Combining 22 and 23 together gives \[\begin{align} \mathbb{E}[\widetilde{M}^-_T] ~=~ \frac{2 \bar \alpha T + (2B + 1) \cdot \mathbb{E}[\widetilde{X}_T] - \mathbb{E}[\widetilde{X}^2_T]}{2B + 2} ~\leq~ \frac{\bar \alpha T}{B} + \mathbb{E}[\widetilde{X}_T]. \end{align}\] ◻

Proof of 23. By 27 and 28, it remains to upper-bound the value of \(\mathbb{E}[\widetilde{X}_T]\) for the balanced random walk process defined in 27. To achieves this, we introduce the following two random walk processes. Let \(\{\widetilde{U}_t\}_{t \in [T]}\) be the unbounded random walk process w.r.t \(\tilde{\xi}_t\), and \(\{\widetilde{W}_t\}_{t \in [T]}\) be the left-bounded random walk process w.r.t. \(\tilde{\xi}_t\), i.e., we have \(\widetilde{U}_0 = \widetilde{W}_0 = \widetilde{X}_0 = 0\), and for \(t \in [T]\), we have \[\widetilde{U}_t ~=~ \widetilde{U}_{t-1} + \tilde{\xi}_t, \qquad \text{and} \qquad \widetilde{W}_t = \widetilde{W}_{t - 1} + \tilde{\xi}_t \cdot \mathbf{1}\big[W_{t-1} + \xi_t \geq 0\big].\] Then, for any realization of \(\{\tilde{\xi}_t\}_{t \in [T]}\), we have \[\begin{align} \widetilde{X}_T ~\leq~ \widetilde{W}_T ~\leq~ \widetilde{U}_T - \min_{t \in [T]} \widetilde{U}_T. \label{eq:balanced-walk-xt-to-ut} \end{align}\tag{24}\] We omit the proof of 24 , as it is identical to the proof of 26. Then, it remains to bound the \(\mathbb{E}[\widetilde{U}_T]\) and \(\mathbb{E}[\min_{t \in [T]} \widetilde{U}_T]\). We bound these two expectations via Freedman’s Inequality. Since \(\widetilde{U}_t\) is an unbounded and balanced random walk process, which means \(\mathbb{E}[\widetilde{U}_t] = \mathbb{E}[\widetilde{U}_{t-1}]\) for every \(t \in [T]\), the sequence of \(\{\widetilde{U}_t\}_{t \in [T]}\) can be viewed as a martingale process, such that the absolute value of the increments is bounded by \[|\Delta \widetilde{U}_t| ~=~ |\tilde{\xi}_t| ~\leq~ 1,\] and the predictable quadratic variation \(\langle \widetilde{U} \rangle_T\) satisfies \[\begin{align} \langle \widetilde{U} \rangle_T ~=~ \sum_{t \in [T]} \mathbb{E}[\tilde{\xi}^2_t] ~=~ T \cdot 2 \bar \alpha. \end{align}\] Let \(\epsilon = 6\sqrt{\bar \alpha T} \cdot \log B\). By Freedman’s Inequality (20), we have \[\begin{align} \mathbf{Pr}\left[ \max_{t \in [T]} |\widetilde{U}_t| \geq \epsilon \land \langle \widetilde{U} \rangle_T \leq 2\bar \alpha T \right] ~\leq~ 2\exp \left(- \frac{\epsilon^2/2}{2\bar \alpha T + 2\epsilon/3}\right) ~\leq~ 2\exp(-3\log B) ~\leq~ B^{-1}, \end{align}\] where the second inequality uses the fact that \[\epsilon^2/2 ~=~ 18 \bar \alpha T \cdot \log^2 B ~\geq~ 6 \bar \alpha T \cdot \log B + 12 \sqrt{\bar \alpha T} \cdot \log^2 B ~=~ 3\log B \cdot (2 \bar \alpha T + 2\epsilon/3),\] and the last inequality holds when \(B\) is sufficiently large. Then, we have

\[\begin{align} \mathbb{E}[\widetilde{X}_T] ~&\leq~ 2\epsilon \cdot \mathbf{Pr}[\widetilde{X}_T \leq 2\epsilon] + B \cdot \mathbf{Pr}\left[\widetilde{X}_T > 2\epsilon\right] \\ ~&\leq~ 2\epsilon + B \cdot \mathbf{Pr}\left[\widetilde{U}_T \geq \epsilon \lor - \min_{t \in [T]} \widetilde{U}_T \geq \epsilon \right] \\ ~&\leq~ 2\epsilon + B \cdot \mathbf{Pr}\left[ \max_{t \in [T]} |\widetilde{U}_t| \geq \epsilon \land \langle \widetilde{U} \rangle_T \leq 2\bar \alpha T \right] \\ ~&\leq~ 2\epsilon + B \cdot B^{-1} ~=~ 12\sqrt{\bar \alpha T} \cdot \log B + 1 ~\leq~ 13\sqrt{\bar \alpha T} \cdot \log B \end{align}\] where the first inequality uses the fact that \(\tilde{X}_T \leq B\) always holds, the second inequality follows from 24 , and the third inequality uses the fact that \(\langle \widetilde{U} \rangle_T \leq 2\bar \alpha T\) always holds. Finally, combining the above inequality with 27 and 28 gives \[\mathbb{E}[M^+_\tau] ~\leq~ \mathbb{E}[\tilde{M}^-_T] ~\leq~ \frac{\bar \alpha T}{B} + 13\sqrt{\bar \alpha T} \cdot \log B ~\leq~ \frac{\Gamma}{B} + 13\sqrt{\Gamma} \cdot \log B,\] where the last inequality uses the fact that \(\bar \alpha = 0.5(\alpha_S+ \alpha_B) \leq \alpha_S\). ◻