Competitive Bundle Trading

Azar, Yossi; Buchbinder, Niv; Levin, Roie; Vardi, Or

doi:10.4230/LIPIcs.ICALP.2026.17

Competitive Bundle Trading

Yossi Azar

Department of Computer Science, Tel Aviv University, Israel Niv Buchbinder

Department of Statistics and Operations Research, Tel Aviv University, Israel Roie Levin

Department of Computer Science, Rutgers University, Piscataway, NJ, USA Or Vardi

Department of Computer Science, Tel Aviv University, Israel

Abstract

Allocating a set of resources to an online sequence of customers is a fundamental problem in online algorithms with an extensive history. However, the natural extension where the algorithm is also allowed to purchase inventory from suppliers, who also arrive online, is essentially unexplored. We study this general trading problem under the objective of profit maximization, which is the difference between revenue from sales and cost of purchases. Maximizing the difference between two competing quantities is significantly more challenging than the sell-only case.

We show a logarithmic competitive ratio relative to the optimal offline solution. Our algorithm is an exponential-weight–update dynamic pricing scheme, and our analysis dual-fits the algorithm’s profit with respect to a linear programming relaxation that upper bounds the optimal offline profit; we also prove (nearly) matching lower bounds. Finally, we extend our results by designing an incentive-compatible mechanism for the setting in which customers are strategic and may misreport their true valuations.

Keywords and phrases:

Online algorithms, competitive analysis, algorithmic game theory, mechanism design, dynamic pricing, resource allocation

Category:

Track A: Algorithms, Complexity and Games

Funding:

Niv Buchbinder: Supported by ISF grant 3001/24 and BSF grant 2022418.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Online algorithms ; Theory of computation

\rightarrow

Algorithmic game theory

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Consider the basic task of selling an initial inventory of goods to an online sequence of customers. Every time step, a customer arrives and specifies a bundle of goods they wish to purchase as well as the price they are willing to pay for that bundle. Upon arrival of each customer, the algorithm must immediately and irrevocably decide whether to accept the transaction and sell off the requested bundle, and the goal is to maximize the total revenue obtained over the course of this sequence. This problem, which reduces to a packing integer (or linear) program whose columns arrive in an online fashion, has been studied extensively under a wide range of models, including fully adversarial environments [5, 36, 18, 16, 6], random-arrival settings [22, 26, 2, 34, 1, 32], and various other stochastic assumptions [27, 23, 3] (see also Section 1.3). When the constraint matrix is integral and the RHS is $1$ , even the offline version captures very difficult computational problems such as maximum independent set; hence it is standard to make a “large inventory” assumption that the RHS values are sufficiently large with respect to the matrix entries.

The general, adversarial version of this online inventory-selling problem was introduced by foundational work of Awerbuch, Azar, and Plotkin [5] more than 30 years ago in the context of online routing; they gave logarithmic competitive ratio guarantees. Their model was later generalized by Leonardi and Marchetti-Spaccamela [36] (see also [15], Chapter 13). Subsequent work further extended these results, both in offline and online settings, to capture combinatorial auctions with the objective of maximizing social welfare or revenue [4, 11, 35, 24, 16, 27]. Surprisingly however, the following natural generalization is poorly understood. What happens if the algorithm is not only selling an initial inventory, but also replenishing the inventory over time by buying from suppliers?

From Selling to Trading.

Concretely, suppose that every time step either a customer arrives as before, or a supplier arrives and announces a bundle they wish to sell and the price they wish to sell at. The new goal of the algorithm is to choose when to accept buy/sell transactions so as to maximize the cumulative profit over the online sequence, i.e. the difference between revenue from sales and expenses from purchases. This problem seem significantly harder than the sell-only special case, which might explain why it has not been studied until now. For one, here the number of transactions can be arbitrarily large, whereas in the sell-only case, the number of transactions is limited by the initial number of items. Secondly, max profit objectives of the form $\max_{x}A(x)-B(x)$ are already challenging in offline scenarios with full information; online, an uncareful algorithm may easily incur negative profit. We call this problem online bundle trading. To the best of our knowledge, no competitive online algorithm (or even good offline approximation) is known for this setting.

Further extensions.

The description above already captures many of the important aspects of the online trading problem, but in practice the story is more involved still. For one, customers/suppliers may be willing to buy/sell more than a single kind of bundle (though the reader should remember this so-called single-minded case for simplicity): in general they have a valuation function for bundles and will accept any bundle at the price at which they value that bundle. Since arbitrary valuation functions may be computationally challenging, we assume access to a demand oracle that, given item prices, returns a utility maximizing bundle.¹¹1While answering a demand query may be NP-hard in general, it is natural in our context to assume that customers and suppliers can efficiently identify their preferred bundles; otherwise, it would be unreasonable to expect a mechanism to meet their demands. Second, customers and suppliers may be strategic and unwilling to reveal their true reservation prices. We refer to this variant as the unknown valuation setting, and to the simpler version, where all valuations are known, as the known valuation setting. For the unknown valuation case, the goal is to design incentive compatible mechanisms. A formal definition of our model appears in Section 2.

1.1 Our results

Our main result is logarithmic competitive algorithms for the online trading problem for both the known and unknown valuation settings against optimal offline solutions. Let $d$ be the maximum size of a bundle of any customer and let $v$ be the maximum to minimum ratio of the value of any bundle of a customer. The algorithm is presumed to have access to upper bounds on these values.

Theorem 1 (Main Theorem, informal).

For every instance of the online trading problem with a demand oracle for the valuations, large enough inventory compared with the bundle sizes and every $\epsilon>0$ , there is an

$\blacksquare$

$O\left(\frac{1}{\epsilon}\log(dv)\right)$ -competitive deterministic algorithm for the known valuation case.
$\blacksquare$

$O\left(\frac{1}{\epsilon}\log(\frac{dv}{\epsilon})\right)$ -competitive randomized incentive compatible online algorithm for the unknown valuation case.

The competitive ratio of both algorithms is with respect to an optimal offline fractional solution, where supplier values at any time step are $(1+\epsilon)$ larger.

As in previous work (e.g., [5, 36]), we assume that the inventory is large. The main additional assumption in our analysis is that the optimal offline solution to which we compare our online algorithm’s profit sees the same sequence of customers/suppliers as the online algorithm, except its suppliers’ valuations are $(1+\epsilon)$ higher for some fixed $\epsilon>0$ .²²2Instead of using a $(1+\epsilon)$ value augmentation for the suppliers, we could also use a $(1+\epsilon)$ reduction in the customers’ values and we would obtain similar results. We have arbitrarily chosen the first option. This assumption can be seen as a form of resource augmentation, which is a common assumption for many online problems (see, e.g., [44, Chapter 4], for a survey): beyond providing a tractable benchmark when competing with the true optimum is impossible, resource augmentation analysis concretely quantifies the value of the additional resource. Our lower bounds, presented below, show that without such augmentation, no competitive algorithm can exist. In fact, we do not know how to design even an offline approximation algorithm for our problem without this assumption.

In the unknown valuation setting, our incentive compatible mechanism is (almost) a posted price mechanism. The algorithm posts prices per unit for each item type, and these may change over time between different suppliers and customers. The price of each bundle $s$ , denoted by $p^{t}_{s}$ , is the sum of prices of the items of $s$ .³³3Technically, the prices of the bundles to customers is slightly more complex. See Section 1.2 for more details. Given these prices, each customer purchases a bundle maximizing her utility $v^{t}_{s}-p^{t}_{s}$ (so long as this utility is nonnegative) and is charged price $p^{t}_{s}$ . Similarly, a supplier sells a bundle maximizing her utility $p^{t}_{s}-v^{t}_{s}$ paying a price $p^{t}_{s}$ (as long as this utility is nonnegative).

We complement our algorithmic results with nearly matching lower bounds that show our competitive ratio is best possible up to constant factors.

Theorem 2 (Lower Bound, informal).

For the online trading problem (even for the known valuation setting and single minded customers/suppliers), when comparing to an optimal offline fractional solution for which supplier values are $(1+\epsilon)$ larger:

$\blacksquare$

The competitive ratio of any deterministic or randomized algorithm is $\Omega(\frac{1}{\epsilon}\cdot\log(dv))$ . In particular, no algorithm can achieve a finite competitive ratio without resource augmentation (that is, when $\epsilon=0$ ).
$\blacksquare$

There exists a constant $c>0$ , such that if the inventory from an item type is smaller than $\frac{c}{\epsilon}\cdot\log(dv)$ times the number of items of type $i$ in at least one of the bundles, then the competitive ratio of any deterministic algorithm is unbounded.

1.2 Techniques

Our algorithms are natural to both describe and implement. Assume by scaling that the values of the customers for any bundle is in the range $[1,v]$ , and that this range is known to the algorithm. At any time step $t\in[T]$ , our algorithm maintains values $x_{i}^{t}$ for every item type $i\in[n]$ that can be viewed as a “base” price per one unit of that item type. Our algorithm can be seen as a dynamic pricing algorithm that changes its prices per unit of item type based on the current inventory: when the inventory of an item type $i$ is full, the base price for that item is $0$ , and the price increases exponentially as the inventory of the item type $i$ decreases. Dynamic pricing of this form is a common practice in retail and is used frequently (see e.g. [21] for a survey).

Known valuations.

The base price of any bundle $s$ , denoted by $p_{s}^{t}$ , is the sum of base prices of the items in the bundle $s$ . Upon an arrival of a customer, the customer is allocated a bundle that maximizes $v_{s}^{t}-\max\{1,p_{s}^{t}\}$ if this value is non-negative, and is charged a price of $v_{s}^{t}$ for the bundle. We remark that in the known valuation setting we may choose a bundle that maximizes the standard utility of the customer defined as $v^{t}_{s}-p_{s}^{t}$ . However, $\max\{1,p_{s}^{t}\}$ is used later in the unknown valuation setting in which we do not want to charge a customer with an arbitrarily small price, and would like the base price of a bundle to be at least $1$ . Upon arrival of a supplier, the price per unit of each item type is scaled down by a factor of $(1+\epsilon)$ . The algorithm purchases from the supplier a bundle that maximizes $\frac{p_{s}^{t}}{1+\epsilon}-v_{s}^{t}$ if this value is non-negative, and pays a value of $v_{s}^{t}$ for the bundle.

Our analysis uses a dual fitting approach that significantly generalizes arguments previously used to analyze the customer-only setting [17, 16] (see also [18] for a survey on the primal-dual approach in online algorithms). Here we work with a natural linear programming relaxation for the profit maximization objective which, unlike the customer-only setting, is no longer a pure packing problem. The dual has several moving parts; among other things, it involves the prices $x_{i}^{t}$ generated during the algorithm execution. Interestingly, we relate the primal and dual objectives by way of a weighted generalization of KL divergence whose properties are useful to us.

Unknown valuations.

Obtaining an incentive compatible mechanism requires several technical steps.⁴⁴4We note that some of these ideas extend previous techniques that were used in [4] to obtain an incentive compatible mechanism for the customer-only setting. The algorithm starts by randomly sampling, once and for all before the online sequence begins, a value $\rho\in[0,v]$ from a carefully chosen distribution. Next, when a customer arrives the algorithm sets a price for bundle $s$ of $p^{\prime t}_{s}=\rho+\max\{1,p_{s}^{t}\}$ . The customer purchases a bundle that maximizes her utility $v_{s}^{t}-p^{\prime t}_{s}$ as long as this utility is non-negative, and is charged a price of $p^{\prime t}_{s}$ . A delicate technicality is that even if the customer decides not to purchase the bundle because of this additional additive $\rho\geq 0$ , but would have purchased the bundle if $\rho$ was $0$ , then the algorithm still updates the price per unit to future customers/suppliers as if the bundle was sold to the current customer (hence, our incentive compatible mechanism is not a simple posted price mechanism and requires a bidding phase). In the supplier case, the algorithm behaves almost identically to the known valuation setting, except that the algorithm posts a price of $\frac{p_{s}^{t}}{1+\epsilon}\geq v_{s}^{t}$ rather than the supplier’s true value, $v_{s}^{t}$ .

The algorithm for the known valuation setting has two free parameters that control the base prices $x_{i}^{t}$ . We show that for the unknown valuation setting, if we carefully tune these parameters, the analysis in the known valuation setting extends naturally.

1.3 Related Work

The most relevant related work to our setting is the following.

Customer only setting.

As discussed, the adversarial version of this problem was introduced by Awerbuch, Azar, and Plotkin [5] and later generalized significantly [36, 4, 11, 18, 35, 24, 16] (see also [15], Chapter 13). The “large inventory” assumption is required even for this easier customer-only setting [5, 36, 15, 16]. We note that our large inventory requirement is slightly higher and in particular depends on the value of $\epsilon$ . Additionally, whereas the customer only settings [15, 16] admits a competitive ratio that deteriorates (i.e. increases) smoothly as the size of the inventory shrinks, our setting exhibits a threshold phenomenon. Our theorems show that for large enough $d, v$ , there are constants $c_{1}<c_{2}$ such that if the inventory is larger than $\frac{c_{2}}{\epsilon}\log(2dv)$ times the number of items of type $i$ in any bundle, then our (deterministic) algorithm has logarithmic competitive ratio. However, if the inventory is smaller than $\frac{c_{1}}{\epsilon}\log(2dv)$ times the number of items of type $i$ in any bundle, then no deterministic algorithm can have a finite competitive ratio.

The large inventory assumption is also assumed in relaxed stochastic models such as the random arrival model. In this model the customers are chosen adversarially, but are given to the algorithm in a random order [22, 26, 2, 34, 1, 32]. In this relaxed model, it is possible to obtain a much better $1-\epsilon$ approximation when the inventory of each item type is large enough ( $\Omega(\frac{\log d}{\epsilon^{2}})$ items of each type) [34, 1, 32] which is known to be tight [23]. We also remark that in the random arrival model with only customers, the optimal offline solution does not depend on the order of arrival. In our more general setting in which both customers and suppliers arrive, the optimal offline solution and its value crucially depend on the arrival order. It is an interesting open problem whether improved competitive ratio is possible in our more general setting but with additional stochastic assumptions.

Prophet trading.

Correa et al. [20] initiated the study of a general prophet trading problem in which both buyers and sellers arrive sequentially. In their model (but our notation) the algorithm holds an inventory of at most $w$ items of a single item type, and faces a sequence of $T$ prices for this item. The prices are drawn from known distributions $F_{1},\ldots,F_{T}$ , and the realization of the prices are revealed in a random order. At each time step $t\in T$ , the algorithm is allowed to both buy or sell items at the current price with the goal of maximizing the profit (the revenue obtained from selling the item minus the purchasing costs). They design a static single-threshold price algorithm (i.e. buy or sell depending on whether today’s price is above or below a fixed threshold) that they show is constant competitive, and they also prove a constant lower bound. Recent work [43] extends their setting further to handle multiple item types and matroid constraints on the inventory. Even more recent work by Azar et al. [8] gave a $3$ -competitive algorithm and a matching lower bound for the adversarial order prophet trading problem. As in our setting, they allowed both the algorithm and the adversary to start trading with a full inventory (alternatively, they allow an additive constant of initial inventory cost in the competitive ratio).

We may view [20, 8] as a (very) restricted stochastic case of our known valuation setting in which at each time step both a customer and a supplier arrive, and each wishes to buy/sell any quantity of a single item type at a fixed price per unit. The general problem we study allows for arbitrary bundles containing multiple item types, and adversarial customers/suppliers valuations for bundles. Because our setting is harder, we (a) only obtain logarithmic competitive ratios, and (b) need the additional assumptions of a large inventory, and of a weaker offline benchmark that sees supplier prices that are $(1+\epsilon)$ higher. Our lower bounds show that both (a) and (b) are unavoidable. Unlike [20, 8], our algorithms require a more sophisticated dynamic pricing scheme.

Apart from the related work already discussed, there are several other important lines of work reminiscent of (but distinct from!) our problem.

(Online) Bilateral Trading.

Bilateral Trading has been studied extensively since the seminal work of Myerson and Satterthwaite [41] (see also [14, 9]). Perhaps the closest version to our setting is the online bilateral trade problem, where at every time step a buyer and seller arrive as a pair. Each has a private valuation functions for a good. The algorithm, which plays the role of the trading platform, posts a price for the good, and buyer and seller proceed with trade so long as both are willing to trade at this price. A common goal is to maximize the gain from trade defined as the sum of utilities of the buyer and the seller [19, 12, 10]. This setting is very different from ours (even for a single item type): the objective is different, and furthermore buyers and sellers arrive and depart simultaneously, so the algorithm cannot stockpile goods in inventory for later trades.

Two-Way Trading and Portfolio Selection.

The problem of online portfolio selection has been extensively studied (see e.g., [37] or [15, Chapter 14]). For example, in a simple one way trading model introduced by El-Yaniv et al. [25], a trader faces a a sequence of prices and would like to maximize her profit from selling a single item. Even closer to our setting is the Two-way trading problem in which a trader with an initial one unit of money observes a sequence of prices of a stock, and is allowed to buy/sell the stock at the given price with the goal of maximizing her final wealth [28, 29]. Despite the seeming similarity, the focus on a single-item type, the lack of inventory constraints, and the lack of restrictions on the number of units per transaction make this problem very different from ours.

Other.

In additional nearby work of [42], we wish to allocate goods to buyers, both of whom appear and perish according to a Poisson process; buyers have linear or submodular valuation functions and desire bundles respecting downward closed constraint families (e.g. they only want want independent sets of a matroid). Similar problems have also been studied in the operations research community. See e.g, network revenue management problem ([30, Chapter 7]). This last line of research usually makes stochastic (as opposed to adversarial) assumptions about the input [31, 33, 40, 39, 38].

Finally, we remark that our linear formulation is an extension of the dual formulation of the positive body chasing problem introduced in [13]. A major difference is that in our problem we require an integral solution, and [13] does not maintain an integral dual. Furthermore we seek an incentive compatible mechanism, which is not a concern of [13].

2 Preliminaries

In this section, we formally define the problem considered in this paper and introduce notation.

Problem Statement.

The algorithm maintains an inventory of $n$ item types $i=1,\ldots,n$ , and we use $[n]$ to denote the set $\{1,2,\ldots,n\}$ . At any time $t$ , the algorithm is required to hold an (integral) amount $r^{t}_{i}$ of item type $i$ such that $r^{t}_{i}\in[0,w_{i}]$ for some positive integer inventory $w_{i}\in\mathbb{Z}_{+}$ . The upper bound constraint on the inventory arises naturally from storage limitations, risk management policies, or regulatory restrictions. We assume that initially the inventory of both the algorithm and the adversary are full, $r_{i}^{0}=w_{i}$ for all $i\in[n]$ . Alternatively, this assumption can be replaced by adding an extra additive constant to the competitive ratio that is independent of the length of the sequence. Time steps $t\in[T]$ are partitioned into time steps $t\in\mathcal{T}_{\text{cust}}$ in which a customer arrives, and time steps $t\in\mathcal{T}_{\text{supp}}$ in which a supplier arrives (i.e. $[T]=\mathcal{T}_{\text{cust}}\sqcup\mathcal{T}_{\text{supp}}$ ).

$\blacksquare$

At time steps $t\in\mathcal{T}_{\text{cust}}$ , a customer arrives and provides a menu of bundles $S^{t}$ . Each bundle $s\in S^{t}$ contains $a_{s,i}\in\mathbb{Z}_{+}$ items of type $i$ and has a value $v^{t}_{s}$ to the customer. The customer would like to purchase at most a single bundle $s\in S^{t}$ .
$\blacksquare$

At time steps $t\in\mathcal{T}_{\text{supp}}$ , a supplier arrives and similarly provides a menu of bundles $S^{t}$ . A bundle $s\in S^{t}$ has $a_{s,i}\in\mathbb{Z}_{+}$ items of type $i$ and has a value of $v^{t}_{s}$ to the supplier. The supplier would like to sell at most one bundle $s\in S^{t}$ .

At any time step $t$ , the algorithm can buy/sell up to a single bundle $s\in S^{t}$ from a supplier/customer. The (integral) inventory of items of type $i$ , $r^{t}_{i}$ , must remain in the range $[0,w_{i}]$ at all time steps. However, when the algorithm purchases a bundle from a supplier it may dispose of any items that are not required for free if it already holds an inventory of $w_{i}$ items of type $i$ and cannot increase the inventory of this item type. We use $\mathcal{T}_{\text{cust}}^{\prime}\subseteq\mathcal{T}_{\text{cust}}$ and $\mathcal{T}_{\text{supp}}^{\prime}\subseteq\mathcal{T}_{\text{supp}}$ to refer to time steps in which the algorithm sells or buys a bundle respectively (as opposed to deciding not to buy/sell), and $s^{t}_{*}$ is the bundle allocated to the customer, or bought from the supplier. We study two different settings for this model:

$\blacksquare$

In the known valuation setting the values of the bundles are known to the algorithm and the price it charges or pays is the bundle’s value. Hence, the profit of the algorithm is $v_{alg}=\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}v^{t}_{s^{t}_{*}}-\sum_{t% \in\mathcal{T}_{\text{supp}}^{\prime}}v^{t}_{s^{t}_{*}}$ .
$\blacksquare$

In the unknown valuation setting the algorithm we design an incentive compatible mechanism. Here, at time step $t\in\mathcal{T}_{\text{cust}}$ , the algorithm posts (compactly) a price $p^{t}_{s}$ for each bundle $s\in S^{t}$ and the customer buys a bundle $s\in S^{t}$ maximizing her utility $v_{s}^{t}-p_{s}^{t}$ if this utility is non-negative. Similarly, at time step $t\in\mathcal{T}_{\text{supp}}$ , the algorithm posts prices $p^{t}_{s}$ for the bundles $s\in S^{t}$ and the supplier sells a bundle $s\in S^{t}$ that maximizes her utility $p_{s}^{t}-v_{s}^{t}$ if this utility is non-negative. The goal of the algorithm is maximizing its profit $v_{alg}=\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}p^{t}_{s^{t}_{*}}-\sum_{t% \in\mathcal{T}_{\text{supp}}^{\prime}}p^{t}_{s^{t}_{*}}$ .

A special case of our setting is when the customers (or suppliers) are single minded, meaning that each customer would like to purchase a single bundle of items $s$ (or a bundle containing $s$ ) and has a value $v^{t}_{s}$ to this bundle. Similarly, a supplier would like to sell to the algorithm a single bundle $s$ (or a subset of the bundle $s$ ) and has a value $v^{t}_{s}$ to this bundle.

In the simpler setting of single minded customers/suppliers the bundle that maximizes the utility can be computed trivially. In case that the number of bundles in the menu is exponential, we assume that we are given a demand oracle to the customers/suppliers. That is, given a price per unit of each item type $x_{i}^{t-1}$ at the arrival of a customer, the customer is able to output a bundle maximizing its utility $v_{s}^{t}-\sum_{i=1}^{n}a_{i,s}\cdot x_{i}^{t-1}$ . Similarly, upon an arrival of a supplier at time step $t$ , it may output a bundle that maximizes $\sum_{i=1}^{n}a_{i,s}\cdot x_{i}^{t-1}-v_{s}^{t}$ .

Our algorithm is given a parameter $\epsilon\in(0,1]$ , and we compare the profit obtained by our algorithm with an optimal solution that maximizes the profit, but the value of each supplier to each bundle $s\in S^{t}$ is $(1+\epsilon)\cdot v_{s}^{t}$ instead of $v_{s}^{t}$ . We note that instead of using a $(1+\epsilon)$ value augmentation for the suppliers, we could also use a $(1+\epsilon)$ reduction in the customers’ values to achieve similar results, and we arbitrarily have chosen the first option. As our proof is via duality of a fractional relaxation of the problem, the optimal solution can be fractional.

Additional Notation.

Define $d\triangleq\max_{t\in\mathcal{T}_{\text{cust}},s^{t}\in S^{t}}\left\{\sum_{i=1% }^{n}a_{s,i}\right\}$ be the largest size of a bundle of a customer, as well as $v_{\min}\triangleq\min_{t\in\mathcal{T}_{\text{cust}},s\in S^{t},v_{s}^{t}\neq 0% }v^{t}_{s}$ and $v\triangleq\max_{t\in\mathcal{T}_{\text{cust}},s\in S^{t}}v^{t}_{s}$ to be the minimum and maximum value of a bundle to a customer. We assume the values $d,v_{\min},v$ are all known to the algorithm upfront. Without loss of generality we scale these values and assume that $v_{\min}=1$ .

All logarithms in this paper are base $e$ . We use a weighted generalization of KL divergence. Given a weight function $w$ , define

\textsc{KL}_{w}\left(x\mid\mid y\right):=\sum_{i=1}^{n}w_{i}\left[x_{i}\log% \left(\frac{x_{i}}{y_{i}}\right)-x_{i}+y_{i}\right].

(2.1)

It is known that $\textsc{KL}_{w}\left(x\mid\mid y\right)\geq 0$ for nonnegative vectors $x, y$ (one can check this is true term by term above).

3 The Algorithm

In this section we prove our main theorem that we state here formally.

Theorem 3.

For every instance of the online trading problem with a demand oracle for the valuations, and for every $\epsilon>0$ , there is

$\blacksquare$

Known valuations: A deterministic online algorithm that is $O\left(\frac{1}{\epsilon}\log(2dv)\right)$ -competitive provided that the inventory for any item type $i\in[n]$ is $\frac{c}{\epsilon}\cdot\log(2vd)$ times the number of items of type $i$ in any bundle for some large enough constant $c$ .
$\blacksquare$

Unknown valuations: A randomized incentive compatible online algorithm that is $O\left(\frac{1}{\epsilon}\log(\frac{2dv}{\epsilon})\right)$ -competitive in expectation provided that the inventory for any item type $i\in[n]$ is $\frac{c}{\epsilon}\cdot\log(\frac{2dv}{\epsilon})$ times the number of items of type $i$ in any bundle for some large enough constant $c$ .

The competitive ratio of both algorithms is with respect to an optimal offline fractional solution, where supplier valuations at any time step are $(1+\epsilon)$ larger.

In Section 3.1 we present our main algorithm for the known valuation setting proving the first part of the theorem. In Section 3.2 we show how to modify our algorithm in order to design an incentive compatible algorithm for the unknown valuations setting proving the second part of the theorem.

3.1 The Known Valuation Setting

We first consider known valuation setting. Our algorithm has two parameters $\mu\geq 1$ and $\eta\geq 1+\log(1+vd\mu)$ that are chosen later. The algorithm requires the following assumption on the inventory size of each item type $i\in[n]$ compared with the number of items of type $i\in[n]$ in bundles presented to the algorithm.

Assumption 4 (Large inventory).

For any item type $i\in[n]$ , time $t\in[T]$ , and a bundle $s\in S^{t}$ , we require that $w_{i}\geq\frac{8\eta}{\epsilon}\cdot a_{s,i}$ .

The formal description of our algorithm appears as Algorithm 1, and we first describe it less formally. At any time step $t$ , the algorithm maintains values $x_{i}^{t}$ for each item type $i$ that depends on the current inventory $r_{i}^{t}$ . When the inventory of item $i$ is full $x_{i}^{t}=0$ , and $x_{i}^{t}$ increases exponentially as the inventory decreases to 0. Intuitively, at this point, the reader may think of the value $x_{i}^{t-1}$ as the base price per one unit of an item of type $i$ just before the arrival of the customer/supplier at time step $t$ (although our incentive compatible version of the algorithm in Section 3.2 requires a more delicate setting of the prices). Using this intuition, the price for a bundle $s\in S^{t}$ is $p_{s}^{t}=\sum_{i=1}^{n}a_{s,i}\cdot x_{i}^{t-1}$ . Next,

$\blacksquare$

Customer arrival: As $v^{t}_{s}\geq 1$ , the algorithm allocates a bundle that maximizes the utility of the customer $v^{t}_{s}-\max\{1,p_{s}^{t}\}$ if this utility is non-negative and charge the customer $v_{s}^{t}$ . Otherwise, no bundle is allocated.
$\blacksquare$

Supplier arrival: The algorithm offers to the supplier prices that are $1+\epsilon$ times smaller, and buys a bundle that maximizes the utility of the supplier $\frac{p^{t}_{s}}{1+\epsilon}-v^{t}_{s}$ if it is non-negative, and otherwise no bundle is bought.

Algorithm 1 Trade

(v,d,\epsilon)

.

Let $\mathcal{T}_{\text{cust}}^{\prime}\subseteq\mathcal{T}_{\text{cust}}$ and $\mathcal{T}_{\text{supp}}^{\prime}\subseteq\mathcal{T}_{\text{supp}}$ be the time steps in which the algorithm sells or buys a bundle respectively (as opposed to deciding not to buy/sell), and let $s^{t}_{*}$ be the bundle that was sold/bought from the customer/supplier. In order to make our subsequent presentation simpler, define for every $t\in\mathcal{T}_{\text{cust}}^{\prime}\cup\mathcal{T}_{\text{supp}}^{\prime}$ the quantity

P^{t}\triangleq\sum_{i=1}^{n}a_{s^{t}_{*},i}\cdot x_{i}^{t-1}.

We prove the following theorem.

Theorem 5.

Given parameter $\mu\geq 1$ and $\eta\geq 1+\log(1+vd\mu)$ , and assuming that for any item type $i\in[n]$ , time $t\in[T]$ , and a bundle $s\in S^{t}$ , $w_{i}\geq\frac{8\eta}{\epsilon}\cdot a_{s,i}$ , Algorithm 1 maintains a feasible integral inventory, such that

	$\displaystyle OPT$	$\displaystyle=O\left(\frac{\eta}{\epsilon}\right)\left[\sum_{t\in\mathcal{T}_{% \text{cust}}^{\prime}}\left(\left(1-\frac{\epsilon}{4}\right)P^{t}+\frac{% \epsilon v^{t}_{s_{*}^{t}}}{\eta}+\frac{1}{\mu}\right)-\sum_{t\in\mathcal{T}_{% \text{supp}}^{\prime}}\frac{P^{t}}{1+\epsilon}\right]$
		$\displaystyle=O\left(\frac{\eta}{\epsilon}\right)\left[\sum_{t\in\mathcal{T}_{% \text{cust}}^{\prime}}v^{t}_{s_{}^{t}}-\sum_{t\in\mathcal{T}_{\text{supp}}^{% \prime}}v^{t}_{s_{}^{t}}\right].$

where $O P T$ is an optimal offline fractional solution whose buying costs from a supplier at any time step $t\in\mathcal{T}_{\text{supp}},s\in S^{t}$ is $(1+\epsilon)v^{t}_{s}$ .

The first part of Theorem 3 follows by setting $\mu=1$ , and $\eta=1+\log(1+vd\mu)=1+\log(1+vd)$ .

We start with a couple of simple observations.

Observation 6.

Item prices are always positive, i.e. for all $t\in[T]$ and $i\in[n]$ , we have $x_{i}^{t}\geq 0$ .

Proof.

The algorithm explicitly maintains that $r_{i}^{t}\leq w_{i}$ in Line 9, which in turn implies that $x^{t-1}_{i}\triangleq\frac{1}{d\cdot\mu}\left(\exp\left((1-\frac{r_{i}^{t-1}}{% w_{i}})\cdot\eta\right)-1\right)\geq 0$ . $\hfill\blacktriangleleft$

We make another observation that comes from rearranging the price update rule (3.1).

Observation 7.

Define $\widehat{x}_{i}^{t}\triangleq x_{i}^{t}+\frac{1}{d\cdot\mu}$ . Then, for all $t\in[T]$ and $i\in[n]$ , it holds that $\frac{1}{\eta}\cdot\log\left(\frac{\widehat{x}_{i}^{t}}{\widehat{x}_{i}^{t-1}}% \right)=\frac{r_{i}^{t-1}-r_{i}^{t}}{w_{i}}$ .

Proof.

Manipulating the price update rule (3.1), we get $\log(\widehat{x}_{i}^{t-1})=\log(x_{i}^{t-1}+\frac{1}{d\cdot\mu})=\left(1-% \frac{r_{i}^{t-1}}{w_{i}}\right)\eta+\log(1/d\mu)$ . Subtracting $\log(\widehat{x}_{i}^{t-1})$ from $\log(\widehat{x}_{i}^{t})$ and dividing by $\eta$ yields the claim. $\hfill\blacktriangleleft$

Before bounding the competitive ratio, one might worry whether Algorithm 1 even maintains a feasible integral solution (namely why $r_{i}^{t}$ never goes below $0$ ). We prove that this is indeed the case.

Lemma 8.

Algorithm 1 produces a feasible integral solution.

Proof.

Clearly, $r_{i}^{t}$ is integral since all bundles are integral. Furthermore, as already noted, we maintain $r_{i}^{t}\leq w_{i}$ explicitly. The only thing remaining to argue is that $r_{i}^{t}\geq 0$ .

We claim that whenever the algorithm decides to sell a bundle $s^{t}_{*}$ with $a_{s^{t}_{*},i}\geq 1$ to a customer, we have that $x_{i}^{t-1}\leq v\triangleq\max_{t\in\mathcal{T}_{\text{cust}},s\in S^{t}}v^{t% }_{s}$ . To see this, note that otherwise since $a_{s^{t}_{*},i}\geq 1$ and by Observation 6 $x_{i}^{t-1}\geq 0$ we have, $\max\{1,\sum_{i=1}^{n}a_{s^{t}_{*},i}\cdot x_{i}^{t-1}\}\geq a_{s^{t}_{*},i}% \cdot x_{i}^{t-1}>v\geq v_{s_{*}^{t}}$ , which means that the algorithm does not sell the bundle to the customer (see Line 6).

Rearranging (3.1), whenever the algorithm decides to sell a bundle $s^{t}_{*}$ with $a_{s^{t}_{*},i}\geq 1$ :

\displaystyle r_{i}^{t-1}

\displaystyle\geq w_{i}\left(1-\frac{\log\left(1+vd\mu\right)}{\eta}\right)% \geq w_{i}\left(\frac{1+\log(1+vd\mu)-\log\left(1+vd\mu\right)}{\eta}\right)% \geq w_{i}\cdot\frac{\epsilon}{8\eta},

where the second equality follows since $\eta\geq 1+\log(1+vd\mu)$ , and the last inequality follows since $\epsilon\leq 1$ . By Assumption 4 we have that $a_{s^{t}_{*},i}\leq w_{i}\cdot\frac{\epsilon}{8\eta}$ , and we conclude that $r_{i}^{t}=r_{i}^{t-1}-a_{s^{t}_{*},i}\geq 0$ . We remark that the analysis here does not require the full strength of Assumption 4 that is used later in the proof. $\hfill\blacktriangleleft$

Analysis via Duality

To prove the competitiveness stated in Theorem 5 we present an LP formulation $\mathcal{P}$ for the fractional version of the problem in which supplier valuations are inflated by $(1+\epsilon)$ . We then construct a feasible solution to the dual problem $\mathcal{D}$ whose value is $O(\frac{c+\log\mu}{\epsilon})$ times the value obtained by the algorithm. Theorem 5 then follows directly by weak duality.

In the LP below, we may think of $\overline{y}^{t}_{s}$ and $\overline{z}_{s}^{t}$ respectively as the indicators for whether bundle $s\in S^{t}$ is allocated to the customer and supplier at time $t$ , and as before, $\overline{r}_{i}^{t}$ as the number of items of type $i$ in inventory at time $t$ . The constraints are straightforward updating the inventory (which is in $[0,w_{i}]$ ), and requiring that at most a single bundle is allocated at any time $t$ . Note that by making (3.2) and (3.3) inequalities (as opposed to equalities) we are allowing a free disposal of items.

(\mathcal{P}):\max\sum_{t\in\mathcal{T}_{\text{cust}}}\sum_{s\in S^{t}}v^{t}_{% s}\cdot\overline{y}^{t}_{s}-(1+\epsilon)\cdot\sum_{t\in\mathcal{T}_{\text{supp% }}}\sum_{s\in S^{t}}v^{t}_{s}\cdot\overline{z}^{t}_{s}

$\displaystyle\overline{r}_{i}^{t+1}$	$\displaystyle\leq\overline{r}_{i}^{t}-\sum_{s\in S^{t}}a_{s,i}\cdot\overline{y% }^{t}_{s}$	$\displaystyle\forall i\in[n],\ t\in\mathcal{T}_{\text{cust}},$	(3.2)
$\displaystyle\overline{r}_{i}^{t+1}$	$\displaystyle\leq\overline{r}_{i}^{t}+\sum_{s\in S^{t}}a_{s,i}\cdot\overline{z% }^{t}_{s}$	$\displaystyle\forall i\in[n],\ t\in\mathcal{T}_{\text{supp}},$	(3.3)
$\displaystyle\sum_{s\in S^{t}}\overline{y}^{t}_{s}$	$\displaystyle\leq 1$	$\displaystyle\forall t\in\mathcal{T}_{\text{cust}},$	(3.4)
$\displaystyle\sum_{s\in S^{t}}\overline{z}^{t}_{s}$	$\displaystyle\leq 1$	$\displaystyle\forall t\in\mathcal{T}_{\text{supp}},$	(3.5)
$\displaystyle\overline{r}_{i}^{t}$	$\displaystyle\leq w_{i}$	$\displaystyle\forall t\in[T],$	(3.6)
$\displaystyle\overline{y}_{s}^{t},\overline{z}_{s}^{t},\overline{r}_{i}^{t}$	$\displaystyle\geq 0$	$\displaystyle\forall t\in[T],s\in S^{t}.$

The dual formulation has variables $x_{i}^{t}$ that correspond to Constraints (3.2) and (3.3), variables $\alpha^{t}$ and $\beta^{t}$ corresponding to constraints (3.4) and (3.5), and variables $\ell_{i}^{t}$ that correspond to Constraints (3.6).

(\mathcal{D}):\min\sum_{t=1}^{T}\sum_{i=1}^{n}w_{i}\cdot\overline{\ell}_{i}^{t% }+\sum_{t\in\mathcal{T}_{\text{cust}}}\overline{\alpha}^{t}+\sum_{t\in\mathcal% {T}_{\text{supp}}}\overline{\beta}^{t}

$\displaystyle\sum_{i=1}^{n}a_{s,i}\cdot\overline{x}_{i}^{t}+\overline{\alpha}^% {t}$	$\displaystyle\geq v^{t}_{s}$	$\displaystyle\forall t\in\mathcal{T}_{\text{cust}},s\in S^{t},$	(3.7)
$\displaystyle\sum_{i=1}^{n}a_{s,i}\cdot\overline{x}_{i}^{t}-\overline{\beta}^{t}$	$\displaystyle\leq v^{t}_{s}\cdot(1+\epsilon)$	$\displaystyle\forall t\in\mathcal{T}_{\text{supp}},s\in S^{t},$	(3.8)
$\displaystyle\overline{\ell}_{i}^{t}$	$\displaystyle\geq\overline{x}_{i}^{t}-\overline{x}_{i}^{t-1}$	$\displaystyle\forall i\in[n],\ t\in[T],$	(3.9)
$\displaystyle\overline{x}_{i}^{t},\overline{\ell}_{i}^{t},\overline{\alpha}^{t% },\overline{\beta}^{t}$	$\displaystyle\geq 0$	$\displaystyle\forall i\in[n],\ t\in[T].$

We have suggestively reused the name $x$ for the dual variables: indeed, we will soon use the values $x_{i}^{t}$ from (3.1) to set these.

Constructing the dual solution.

We fit the following dual to Algorithm 1. Recall that $\mathcal{T}_{\text{cust}}^{\prime}\subseteq\mathcal{T}_{\text{cust}}$ and $\mathcal{T}_{\text{supp}}^{\prime}\subseteq\mathcal{T}_{\text{supp}}$ are the time steps in which Algorithm 1 decides to sell or buy a bundle $s^{t}_{*}$ respectively. We set

	$\displaystyle\overline{x}_{i}^{t}$	$\displaystyle=x_{i}^{t},$
	$\displaystyle\overline{\ell}_{i}^{t}$	$\displaystyle=\max\{0,x_{i}^{t}-x_{i}^{t-1}\},$
	$\displaystyle\overline{\alpha}^{t}$	$\displaystyle=\begin{cases}v^{t}_{s^{t}_{*}}&\text{if }t\in\mathcal{T}_{\text{% cust}}^{\prime}\\ 0&\text{otherwise}\end{cases},$
	$\displaystyle\overline{\beta}^{t}$	$\displaystyle=\begin{cases}\sum_{i=1}^{n}a_{s^{t}_{},i}\cdot x_{i}^{t-1}-(1+% \epsilon)v_{s^{t}_{}}&\text{if }t\in\mathcal{T}_{\text{supp}}^{\prime}\\ 0&\text{otherwise}\end{cases}.$

We need to show dual feasibility, and that the cost of the algorithm is related to the dual cost. We start with the first.

Lemma 9.

The solution $(\overline{x},\overline{\ell},\overline{\alpha},\overline{\beta})$ is feasible to $\mathcal{D}$ .

Proof.

By construction we have $\overline{\alpha}^{t}\geq 0$ , $\overline{\ell}_{i}^{t}\geq 0$ , and $\overline{\ell}_{i}^{t}\geq x_{i}^{t}-x_{i}^{t-1}$ , and by Observation 6 also $x^{t-1}_{i}\geq 0$ .

By the behavior of the algorithm (Line 9), if $t\in\mathcal{T}_{\text{supp}}^{\prime}$ , then $\sum_{i=1}^{n}a_{s^{t}_{*},i}\cdot x_{i}^{t-1}-(1+\epsilon)v_{s^{t}_{*}}\geq 0$ and hence $\overline{\beta}^{t}\geq 0$ . Hence, it remains to check constraints (3.7) and (3.8).

Consider first any time $t\in\mathcal{T}_{\text{cust}}\setminus\mathcal{T}_{\text{cust}}^{\prime}$ in which no bundle is sold. In this case, by line 6 of Algorithm 1, for all $s\in S^{t}$ we have $\max\{1,\sum_{i=1}^{n}a_{s,i}\cdot x_{i}^{t-1}\}>v^{t}_{s}$ (note the strict inequality), as $v^{t}_{s}\geq 1$ for any bundle $s\in S^{t}$ , it means that for every $s\in S^{t}$ , $\sum_{i=1}^{n}a_{s,i}\cdot x_{i}^{t-1}>v^{t}_{s}$ and therefore setting $\overline{\alpha}^{t}=0$ and noticing that in this case $x_{i}^{t}=x_{i}^{t-1}$ satisfies constraints (3.7). Next, consider any time $t\in\mathcal{T}_{\text{cust}}^{\prime}$ in which a bundle $s^{t}_{*}=\arg\max_{s\in S^{t}}\left\{v^{t}_{s}-\max\{1,\sum_{i=1}^{n}a_{s,i}% \cdot x_{i}^{t-1}\}\right\}$ is allocated to a customer. By the definition of $s^{t}_{*}$ , we have for any $s\in S^{t}$

	$\displaystyle\overline{\alpha}^{t}$	$\displaystyle=v^{t}_{s^{t}_{}}\geq v^{t}_{s}+\max\{1,\sum_{i=1}^{n}a_{s^{t}_{% },i}\cdot x_{i}^{t-1}\}-\max\{1,\sum_{i=1}^{n}a_{s,i}\cdot x_{i}^{t-1}\}$
		$\displaystyle\geq v^{t}_{s}+1-\max\{1,\sum_{i=1}^{n}a_{s,i}\cdot x_{i}^{t-1}\}% \geq v^{t}_{s}-\sum_{i=1}^{n}a_{s,i}\cdot x_{i}^{t-1}.$

Thus, we get that for any $s\in S^{t}$ , $\sum_{i=1}^{n}a_{s,i}\cdot x_{i}^{t}+\overline{\alpha}^{t}\geq\sum_{i=1}^{n}a_% {s,i}\cdot x_{i}^{t-1}+\overline{\alpha}^{t}\geq v^{t}_{s}$ , where the first inequality holds since the values $x_{i}^{t}$ only increase at time steps $t\in\mathcal{T}_{\text{cust}}$ .

Similarly, let $t\in\mathcal{T}_{\text{supp}}\setminus\mathcal{T}_{\text{supp}}^{\prime}$ be a time in which no bundle is allocated to the supplier. Line 9 of Algorithm 1 guarantees that in this case for all $s\in S^{t}$ we have $\sum_{i=1}^{n}a_{s,i}\cdot x_{i}^{t-1}<(1+\epsilon)\cdot v_{s}$ , and therefore setting $\overline{\beta}^{t}=0$ satisfies constraints (3.8). Finally, at times $t\in\mathcal{T}_{\text{supp}}^{\prime}$ , in which a bundle $s^{t}_{*}=\arg\max_{s\in S^{t}}\left\{\frac{1}{1+\epsilon}\cdot\sum_{i=1}^{n}a% _{s,i}\cdot x_{i}^{t-1}-v^{t}_{s}\right\}$ is bought from the supplier, we have for all $s\in S^{t}$ ,

\sum_{i=1}^{n}a_{s,i}\cdot x_{i}^{t}-\overline{\beta}^{t}\leq\sum_{i=1}^{n}a_{% s,i}\cdot x_{i}^{t-1}-\max_{s\in S^{t}}\left\{\sum_{i=1}^{n}a_{s,i}\cdot x_{i}% ^{t-1}-(1+\epsilon)\cdot v^{t}_{s}\right\}\leq(1+\epsilon)\cdot v^{t}_{s}.

The first inequality holds since the values $x_{i}^{t}$ only decrease at time steps $t\in\mathcal{T}_{\text{supp}}$ . Hence, we satisfy the dual constraints (3.7) and (3.8). $\hfill\blacktriangleleft$

The remaining challenge is to relate the cost of the algorithm to the cost of the dual solution. This is proved in Lemma 10. Theorem 5 follows directly by combining Lemma 9 and Lemma 10 along with weak duality.

Lemma 10.

Let $P^{t}\triangleq\sum_{i=1}^{n}a_{s^{t}_{*},i}\cdot x_{i}^{t-1}$ for every time step $t\in\mathcal{T}_{\text{supp}}^{\prime}\cup\mathcal{T}_{\text{cust}}^{\prime}$ . Then, the value of the dual solution is bounded as

	$\displaystyle\sum_{\begin{subarray}{c}t\in[T]\\ i\in[n]\end{subarray}}w_{i}\cdot\overline{\ell}_{i}^{t}+\sum_{t\in\mathcal{T}_% {\text{cust}}}\overline{\alpha}^{t}+\sum_{t\in\mathcal{T}_{\text{supp}}}% \overline{\beta}^{t}$
		$\displaystyle=O\left(\frac{\eta}{\epsilon}\right)\cdot\left[\sum_{t\in\mathcal% {T}_{\text{cust}}^{\prime}}\left(\left(1-\frac{\epsilon}{4}\right)P^{t}+\frac{% \epsilon\cdot v^{t}_{s_{*}^{t}}}{\eta}+\frac{1}{\mu}\right)-\sum_{t\in\mathcal% {T}_{\text{supp}}^{\prime}}\frac{P^{t}}{1+\epsilon}\right]$
		$\displaystyle=O\left(\frac{\eta}{\epsilon}\right)\cdot\left[\sum_{t\in\mathcal% {T}_{\text{cust}}^{\prime}}v^{t}_{s_{}^{t}}-\sum_{t\in\mathcal{T}_{\text{supp% }}^{\prime}}v^{t}_{s_{}^{t}}\right].$

Proving Lemma 10 requires several intermediate claims.

Claim 11.

Recall that $\widehat{x}_{i}^{t}\triangleq x_{i}^{t}+\frac{1}{d\cdot\mu}$ . For time steps in which the trader allocates a bundle to a customer or a supplier we have the following.

	$\displaystyle\forall t\in\mathcal{T}_{\text{cust}}^{\prime}\qquad$	$\displaystyle\frac{1}{\eta}\sum_{i=1}^{n}w_{i}\cdot\widehat{x}_{i}^{t}\log% \left(\frac{\widehat{x}_{i}^{t}}{\widehat{x}_{i}^{t-1}}\right)\leq e^{\epsilon% /8}\cdot\left(P^{t}+\frac{1}{\mu}\right),$		(3.10)
	$\displaystyle\forall t\in\mathcal{T}_{\text{supp}}^{\prime}\qquad$	$\displaystyle\frac{1}{\eta}\left[\sum_{i\mid x_{i}^{t}>0}w_{i}\cdot\widehat{x}% _{i}^{t}\log\left(\frac{\widehat{x}_{i}^{t}}{\widehat{x}_{i}^{t-1}}\right)-% \sum_{i\mid x_{i}^{t}=0}w_{i}\cdot x_{i}^{t-1}\right]\leq-e^{\epsilon/8}\cdot P% ^{t}.$		(3.11)

Proof.

Consider a time step $t\in\mathcal{T}_{\text{cust}}^{\prime}$ . Then,

$\displaystyle\frac{1}{\eta}\sum_{i=1}^{n}w_{i}\cdot\widehat{x}_{i}^{t}\log% \left(\frac{\widehat{x}_{i}^{t}}{\widehat{x}_{i}^{t-1}}\right)$	$\displaystyle=\sum_{i=1}^{n}a_{s^{t}_{},i}\cdot\widehat{x}_{i}^{t}=\sum_{i=1}% ^{n}a_{s^{t}_{},i}\cdot\widehat{x}_{i}^{t-1}\cdot\exp\left(\frac{a_{s^{t}_{*}% ,i}}{w_{i}}\cdot\eta\right)$	(3.12)
	$\displaystyle\leq e^{\epsilon/8}\cdot\sum_{i=1}^{n}a_{s^{t}_{},i}\cdot% \widehat{x}_{i}^{t-1}=e^{\epsilon/8}\cdot\sum_{i=1}^{n}a_{s^{t}_{},i}\cdot% \left(x_{i}^{t-1}+\frac{1}{d\cdot\mu}\right)$	(3.13)
	$\displaystyle\leq e^{\epsilon/8}\cdot\left(P^{t}+\frac{1}{\mu}\right).$	(3.14)

Step (3.12) follows by using Observation 7 twice, and the fact that $r_{i}^{t-1}-r_{i}^{t}=a_{s^{t}_{*},i}$ . Inequality (3.13) follows by Assumption 4. Inequality (3.14) follows since $d\geq\sum_{i=1}^{n}a_{s^{t}_{*},i}$ Next, at a time step $t\in\mathcal{T}_{\text{supp}}^{\prime}$ we have,

	$\displaystyle\frac{1}{\eta}\sum_{i\mid x_{i}^{t}>0}w_{i}\cdot\widehat{x}_{i}^{% t}\log\left(\frac{\widehat{x}_{i}^{t}}{\widehat{x}_{i}^{t-1}}\right)-\frac{1}{% \eta}\sum_{i\mid x_{i}^{t}=0}w_{i}\cdot x_{i}^{t-1}$
	$\displaystyle\leq\frac{1}{\eta}\sum_{i\mid x_{i}^{t}>0}w_{i}\cdot\widehat{x}_{% i}^{t}\log\left(\frac{\widehat{x}_{i}^{t}}{\widehat{x}_{i}^{t-1}}\right)-\sum_% {i\mid x_{i}^{t}=0}a_{s^{t}_{*},i}\cdot x_{i}^{t-1}$		(3.15)
	$\displaystyle=-\sum_{i\mid x_{i}^{t}>0}a_{s^{t}_{},i}\cdot\widehat{x}_{i}^{t}% -\sum_{i\mid x_{i}^{t}=0}a_{s^{t}_{},i}\cdot x_{i}^{t-1}$		(3.16)
	$\displaystyle=-\sum_{i\mid x_{i}^{t}>0}a_{s^{t}_{},i}\cdot\widehat{x}_{i}^{t-% 1}\cdot\exp\left(-\frac{a_{s^{t}_{},i}}{w_{i}}\cdot\eta\right)-\sum_{i\mid x_% {i}^{t}=0}a_{s^{t}_{*},i}\cdot x_{i}^{t-1}$		(3.17)
	$\displaystyle\leq-e^{-\epsilon/8}\sum_{i\mid x_{i}^{t}>0}a_{s^{t}_{},i}\cdot% \widehat{x}_{i}^{t-1}-\sum_{i\mid x_{i}^{t}=0}a_{s^{t}_{},i}\cdot x_{i}^{t-1}$		(3.18)
	$\displaystyle\leq-e^{-\epsilon/8}\sum_{i=1}^{n}a_{s^{t}_{*},i}\cdot x_{i}^{t-1% }=-e^{-\epsilon/8}\cdot P^{t}.$

Inequality (3.15) follows by Assumption 4 and the fact that $\epsilon\leq 1$ . Equalities (3.16) and (3.17) follow by using Observation 7, and by the fact that if $x_{i}^{t}>0$ then $r_{i}^{t}<w_{i}$ , which means $r_{i}^{t-1}-r_{i}^{t}=-a_{s^{t}_{*},i}$ . Inequality (3.18) follows from Assumption 4. The final inequality follows since $\widehat{x}_{i}^{t-1}\geq x_{i}^{t-1}$ . $\hfill\vartriangleleft$

Claim 12.

The following inequality holds: $\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}\left(P^{t}+\frac{1}{\mu}\right)-% e^{-\epsilon/4}\sum_{t\in\mathcal{T}_{\text{supp}}^{\prime}}P^{t}\geq 0$ .

Proof.

By the non-negativity of the KL divergence, we have that for all $t\in\mathcal{T}_{\text{cust}}^{\prime}\cup\mathcal{T}_{\text{supp}}^{\prime}$ ,
$\displaystyle 0\leq\frac{1}{\eta}\sum_{i\mid x_{i}^{t}>0}w_{i}\cdot\left[% \widehat{x}_{i}^{t}\log\left(\frac{\widehat{x}_{i}^{t}}{\widehat{x}_{i}^{t-1}}% \right)-\widehat{x}_{i}^{t}+\widehat{x}_{i}^{t-1}\right]=\frac{1}{\eta}\sum_{i% \mid x_{i}^{t}>0}w_{i}\cdot\left[\widehat{x}_{i}^{t}\log\left(\frac{\widehat{x% }_{i}^{t}}{\widehat{x}_{i}^{t-1}}\right)-x_{i}^{t}+x_{i}^{t-1}\right].$

Summing up the inequalities for all time steps $t\in\mathcal{T}_{\text{cust}}^{\prime}\cup\mathcal{T}_{\text{supp}}^{\prime}$ , we get

$\displaystyle 0\leq$	$\displaystyle\frac{1}{\eta}\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}\cup% \mathcal{T}_{\text{supp}}^{\prime}}\sum_{i\mid x_{i}^{t}>0}w_{i}\cdot\left[% \widehat{x}_{i}^{t}\cdot\log\left(\frac{\widehat{x}_{i}^{t}}{\widehat{x}_{i}^{% t-1}}\right)-x_{i}^{t}+x_{i}^{t-1}\right]$
	$\displaystyle+\frac{1}{\eta}\sum_{t\in\mathcal{T}_{\text{supp}}^{\prime}}\sum_% {i\mid x_{i}^{t}=0}w_{i}\cdot\left[-x_{i}^{t-1}-x_{i}^{t}+x_{i}^{t-1}\right]$	(3.19)
$\displaystyle=$	$\displaystyle\frac{1}{\eta}\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}\sum_{% i=1}^{n}w_{i}\cdot\widehat{x}_{i}^{t}\cdot\log\left(\frac{\widehat{x}_{i}^{t}}% {\widehat{x}_{i}^{t-1}}\right)+\frac{1}{\eta}\sum_{t\in\mathcal{T}_{\text{supp% }}^{\prime}}\left[\sum_{i\mid x_{i}^{t}>0}w_{i}\cdot\widehat{x}_{i}^{t}\log% \left(\frac{\widehat{x}_{i}^{t}}{\widehat{x}_{i}^{t-1}}\right)-\sum_{i\mid x_{% i}^{t}=0}x_{i}^{t-1}\right]$
	$\displaystyle-\frac{1}{\eta}\sum_{i=1}^{n}w_{i}\cdot(x^{T}_{i}-x^{0}_{i})$	(3.20)
$\displaystyle\leq$	$\displaystyle e^{\epsilon/8}\cdot\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}% \left(P^{t}+\frac{1}{\mu}\right)-e^{-\epsilon/8}\cdot\sum_{t\in\mathcal{T}_{% \text{supp}}^{\prime}}P^{t}.$	(3.21)

Inequality (3.19) follows by adding the term $x_{i}^{t-1}-x_{i}^{t-1}$ that equals 0. Equality (3.20) is a telescoping sum. Finally, inequality (3.21) follows by plugging inequalities (3.10) and (3.11) from Claim 11, and since $x_{i}^{T}-x_{i}^{0}=x_{i}^{T}\geq 0$ . Dividing by $e^{\epsilon/8}$ concludes the proof. $\hfill\vartriangleleft$

We are finally ready to prove Lemma 10.

Proof of Lemma 10.

First, for all time steps $t\in\mathcal{T}_{\text{cust}}^{\prime}$ , we have

	$\displaystyle\sum_{i=1}^{n}w_{i}\overline{\ell}_{i}^{t}$	$\displaystyle=\sum_{i=1}^{n}w_{i}(x_{i}^{t}-x_{i}^{t-1})=\sum_{i=1}^{n}w_{i}(% \widehat{x}_{i}^{t}-\widehat{x}_{i}^{t-1})\leq\sum_{i=1}^{n}w_{i}\cdot\widehat% {x}_{i}^{t}\log\left(\frac{\widehat{x}_{i}^{t}}{\widehat{x}_{i}^{t-1}}\right)$
		$\displaystyle\leq 2\eta\left(P^{t}+\frac{1}{\mu}\right).$		(3.22)

The penultimate inequality follows because for any $a\geq b>0$ , we have $(a-b)\leq a\log(\nicefrac{{a}}{{b}})$ . The last inequality is due to Claim 11 and since $\epsilon\leq 1$ .

Using this together with Claim 12, we bound the value of the dual solution (except for the value of $\overline{\alpha}^{t}$ ) as follows:

	$\displaystyle\sum_{\begin{subarray}{c}t\in[T]\\ i\in[n]\end{subarray}}w_{i}\cdot\overline{\ell}_{i}^{t}+\sum_{t\in\mathcal{T}_% {\text{supp}}}\overline{\beta}^{t}\leq\sum_{t\in\mathcal{T}_{\text{cust}}^{% \prime}}\left[2\eta\cdot\left(P^{t}+\frac{1}{\mu}\right)\right]+\sum_{t\in% \mathcal{T}_{\text{supp}}^{\prime}}\left(P^{t}-(1+\epsilon)v_{s_{*}^{t}}\right)$		(3.23)
	$\displaystyle\leq\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}\left[2\eta\cdot% \left(P^{t}+\frac{1}{\mu}\right)\right]+\sum_{t\in\mathcal{T}_{\text{supp}}^{% \prime}}P^{t}+\frac{30\eta}{\epsilon}\cdot\left[\sum_{t\in\mathcal{T}_{\text{% cust}}^{\prime}}\left(P^{t}+\frac{1}{\mu}\right)-e^{-\epsilon/4}\cdot\sum_{t% \in\mathcal{T}_{\text{supp}}^{\prime}}P^{t}\right]$		(3.24)
	$\displaystyle=\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}\left[\left(2\eta+% \frac{30\eta}{\epsilon}\right)\cdot\left(P^{t}+\frac{1}{\mu}\right)\right]-% \sum_{t\in\mathcal{T}_{\text{supp}}^{\prime}}\left(\frac{30\eta}{\epsilon}% \cdot(1+\epsilon)e^{-\epsilon/4}-(1+\epsilon)\right)\frac{P^{t}}{1+\epsilon}$
	$\displaystyle\leq\left(2\eta+\frac{30\eta}{\epsilon}\right)\cdot\sum_{t\in% \mathcal{T}_{\text{cust}}^{\prime}}\left(P^{t}+\frac{1}{\mu}\right)-\sum_{t\in% \mathcal{T}_{\text{supp}}^{\prime}}\left(\frac{30\eta}{\epsilon}+15\eta-2% \right)\frac{P^{t}}{1+\epsilon}$		(3.25)
	$\displaystyle\leq\left(2\eta+\frac{30\eta}{\epsilon}\right)\cdot\sum_{t\in% \mathcal{T}_{\text{cust}}^{\prime}}\left(P^{t}+\frac{1}{\mu}\right)-\left(13% \eta+\frac{30\eta}{\epsilon}\right)\cdot\sum_{t\in\mathcal{T}_{\text{supp}}^{% \prime}}\frac{P^{t}}{1+\epsilon}$		(3.26)
	$\displaystyle\leq\left(13\eta+\frac{30\eta}{\epsilon}\right)\cdot\left(1-\frac% {\epsilon}{4}\right)\cdot\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}\left(P^% {t}+\frac{1}{\mu}\right)-\left(13\eta+\frac{30\eta}{\epsilon}\right)\cdot\sum_% {t\in\mathcal{T}_{\text{supp}}^{\prime}}\frac{P^{t}}{1+\epsilon}.$		(3.27)

Step (3.23) follows from (3.22) and the fact that $\overline{\ell}^{t}$ , $\overline{\beta}^{t}$ are all $0$ when $t\not\in\mathcal{T}_{\text{cust}}^{\prime}\cup\mathcal{T}_{\text{supp}}^{\prime}$ . Step (3.24) follows from adding $\frac{30\eta}{\epsilon}$ times the inequality of Claim 12. Step (3.25) holds since $\epsilon\leq 1$ and $(1+\epsilon)e^{-\epsilon/4}\geq(1+\epsilon)(1-\epsilon/4)\geq(1+\epsilon/2)$ , and (3.26) since $\eta\geq 1$ . Step (3.27) follows since

2\eta+\frac{30\eta}{\epsilon}\leq\frac{30\eta}{\epsilon}+13\eta-\frac{30}{4}% \eta-\frac{13}{4}\eta\leq\frac{30\eta}{\epsilon}+13\eta-\frac{30}{4}\eta-\frac% {13\epsilon}{4}\eta=\left(13\eta+\frac{30\eta}{\epsilon}\right)\cdot\left(1-% \frac{\epsilon}{4}\right).

Finally, by the construction of the dual solution, we have $\sum_{t\in\mathcal{T}_{\text{cust}}}\overline{\alpha}^{t}=\sum_{t\in\mathcal{T% }_{\text{cust}}^{\prime}}v^{t}_{s_{*}^{t}}$ . Adding this to the final inequality, we get:

	$\displaystyle\sum_{\begin{subarray}{c}t\in[T]\\ i\in[n]\end{subarray}}w_{i}\cdot\overline{\ell}_{i}^{t}+\sum_{t\in\mathcal{T}_% {\text{supp}}}\overline{\beta}^{t}+\sum_{t\in\mathcal{T}_{\text{cust}}}% \overline{\alpha}^{t}$
	$\displaystyle\leq\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}v^{t}_{s_{*}^{t}% }+\left(13\eta+\frac{30\eta}{\epsilon}\right)\cdot\left[\left(1-\frac{\epsilon% }{4}\right)\cdot\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}\left(P^{t}+\frac% {1}{\mu}\right)-\sum_{t\in\mathcal{T}_{\text{supp}}^{\prime}}\frac{P^{t}}{1+% \epsilon}\right]$
	$\displaystyle=O\left(\frac{\eta}{\epsilon}\right)\cdot\left[\sum_{t\in\mathcal% {T}_{\text{cust}}^{\prime}}\left(\left(1-\frac{\epsilon}{4}\right)P^{t}+\frac{% \epsilon\cdot v^{t}_{s_{*}^{t}}}{\eta}+\frac{1}{\mu}\right)-\sum_{t\in\mathcal% {T}_{\text{supp}}^{\prime}}\frac{P^{t}}{1+\epsilon}\right]$
	$\displaystyle=O\left(\frac{\eta}{\epsilon}\right)\cdot\left[\sum_{t\in\mathcal% {T}_{\text{cust}}^{\prime}}v^{t}_{s_{}^{t}}-\sum_{t\in\mathcal{T}_{\text{supp% }}^{\prime}}v^{t}_{s_{}^{t}}\right].$

The last inequality follows firstly since as $\eta\geq 1,\mu\geq 1$ , $\epsilon\leq 1$ , and $v^{t}_{s^{t}_{*}}\geq 1$ for $t\in\mathcal{T}_{\text{cust}}$ . For every $t\in\mathcal{T}_{\text{cust}}^{\prime}$ , we have $\epsilon\cdot v^{t}_{s_{*}^{t}}/\eta+1/\mu\leq 2v^{t}_{s_{*}^{t}}$ . More crucially, by the properties of the algorithm at each time step $t\in\mathcal{T}_{\text{cust}}^{\prime}$ in which the algorithm sells a bundle to a customer, we have $P^{t}=\sum_{i=1}^{n}a_{s^{t}_{*},i}\cdot x_{i}^{t-1}\leq\max\{1,\sum_{i=1}^{n}% a_{s^{t}_{*},i}\cdot x_{i}^{t-1}\}\leq v^{t}_{s^{t}_{*}}$ (see Line 6), and at each time step $t\in\mathcal{T}_{\text{supp}}^{\prime}$ in which the algorithm buys a bundle from a supplier, we have $P^{t}=\sum_{i=1}^{n}a_{s^{t}_{*},i}\cdot x_{i}^{t-1}\geq(1+\epsilon)\cdot v^{t% }_{s^{t}_{*}}$ (see Line 9). $\hfill\blacktriangleleft$

3.2 The Unknown Valuation Setting

In this section we prove the second part of Theorem 3 by designing an incentive compatible algorithm. Our incentive compatible algorithm is based on Algorithm 1 and its analysis with the following changes. We initially sample a random threshold $\rho\geq 0$ (in a way that is described formally later). Then,

$\blacksquare$

When a customer arrives, the algorithm sets a price for each bundle $p^{t}_{s}\triangleq\rho+\max\{1,\sum_{i=1}^{n}a_{s,i}\cdot x_{i}^{t-1}\}$ for every bundle $s\in S^{t}$ . The customer buys the bundle $s_{*}^{t}$ maximizing her utility $v^{t}_{s}-p^{t}_{s}$ if this utility is nonnegative. Additionally, regardless of whether any bundle is allocated in round $t$ , if $v^{t}_{s_{*}^{t}}-\max\{1,\sum_{i=1}^{n}a_{s_{*}^{t},i}\cdot x_{i}^{t-1}\}$ is non-negative, the algorithm subtracts the bundle contents from the inventory and updates the values $x_{i}^{t}$ accordingly as done by our algorithm for the known value setting, Algorithm 1. Note that as $\rho\geq 0$ , then whenever $v^{t}_{s_{*}^{t}}-(\rho+\max\{1,\sum_{i=1}^{n}a_{s^{t}_{*},i}\cdot x_{i}^{t-1}% \})\geq 0$ , then $v^{t}_{s_{*}^{t}}-\max\{1,\sum_{i=1}^{n}a_{s^{t}_{*},i}\cdot x_{i}^{t-1}\}$ is also non-negative. Formally, as the machanism may update the prices even if a bundle is not allocated to the customer, the incentive compatible mechanism is not a posted price mechanism, and requires a bidding phase.
$\blacksquare$

When a supplier arrives, the algorithm sets a price $p^{t}_{s}\triangleq\frac{1}{1+\epsilon}\sum_{i=1}^{n}a_{s,i}\cdot x_{i}^{t-1}$ for every bundle $s\in S^{t}$ . The supplier sells the bundle $s_{*}^{t}$ maximizing his utility $p^{t}_{s}-v^{t}_{s}$ if this utility is nonnegative.

In addition to the above changes, the algorithm chooses the parameters $\mu$ and $\eta$ carefully as we describe in the formal description of Algorithm 2.

Algorithm 2 Trade-Truthful

(v,d,\epsilon)

.

$\blacktriangleright$ Remark 13.

We remark that in Step 8 the inventory is updated even if eventually in Step 9 the algorithm does not allocate the bundle to the customer (since $\rho$ is too large). The algorithm can be lazy and delay disposing items until the inventory exceeds the capacity. However, for our analysis, we require that the algorithm updates the values $x_{i}^{t}$ as if the items were allocated.

We begin with the following observation.

Observation 14.

Algorithm 2 is incentive compatible.

Proof.

We observe that Algorithm 2 sets prices for each bundle in Steps 6 and 11 allocates to the customers/suppliers a bundle $s^{t}_{*}$ that maximizes their utility with respect to these prices (if it is non-negative). Hence, we get that the algorithm is incentive compatible. $\hfill\blacktriangleleft$ Next, we have the following claim.

Claim 15.

At any time step $t\in[T]$ , the inventory of the algorithm $r_{i}^{t}$ , the values $x_{i}^{t}$ and the identity of $s^{*}_{t}$ is the same in Algorithm 2 as in Algorithm 1.

Proof.

The claim follows inductively on the time steps $t\in T$ . We observe that whenever a supplier arrives, the allocation is identical in both algorithms (only the price paid is different). Whenever a customer arrives at time step $t\in\mathcal{T}_{\text{cust}}$ , as $\rho\geq 0$ is simply an additive shift, the bundle $s^{t}_{*}$ chosen in Step 5 in Algorithm 1 is the same as the bundle chosen by Algorithm 2 in Step 7. Moreover, even if the bundle $s^{t}_{*}$ is not allocated to the customer in Step 9 (which can happen if $\rho$ is too large), the algorithm still updates its inventory in Step 8 (as in Step 6 of Algorithm 1) as well as the values $x_{i}^{t}$ that depend on the inventory. $\hfill\vartriangleleft$

By the above claim, we get by the analysis of Algorithm 1 that the inventory of Algorithm 2 is always feasible. Moreover, the dual solution $\mathcal{D}$ as constructed in Section 3.1 is also feasible. Therefore, setting the parameters $\mu=\nicefrac{{32}}{{\epsilon}}\cdot(1+\log v)$ , and $\eta=32(1+\log(1+dv\mu))$ (Line 2 of Algorithm 2) we get, by Theorem 5 that,

OPT=O\left(\frac{\eta}{\epsilon}\right)\cdot\left[\sum_{t\in\mathcal{T}_{\text% {cust}}^{\prime}}\left(\left(1-\frac{\epsilon}{4}\right)\cdot P^{t}+\frac{% \epsilon\cdot v^{t}_{s_{*}^{t}}}{\eta}+\frac{1}{\mu}\right)-\sum_{t\in\mathcal% {T}_{\text{supp}}^{\prime}}\frac{P^{t}}{1+\epsilon}\right].

Next, let $\mathcal{T}_{\text{cust}}^{\prime},\mathcal{T}_{\text{supp}}^{\prime}$ be the time steps in which Algorithm 1 sells bundle $s^{t}_{*}$ to the customer at price $v^{t}_{s^{t}_{*}}$ or pays the supplier a cost of $v^{t}_{s^{t}_{*}}$ . Algorithm 2 updates its inventory the same way in these steps. However, it pays the supplier a higher price of $p_{s^{t}_{*}}^{t}\geq v^{t}_{s^{t}_{*}}$ and charges the customer a (random) lower price of $p_{s^{t}_{*}}^{t}\leq v^{t}_{s^{t}_{*}}$ if the bundle $s^{t}_{*}$ is allocated to the customer. Nevertheless, the next lemma bounds from below the expected profit of Algorithm 2.

Lemma 16.

The expected profit of Algorithm 2 is at least,

\left[\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}\left(\left(1-2\delta\right% )\cdot\max\{1,P^{t}\}+\frac{\delta}{2(1+\log v)}\cdot v^{t}_{s^{t}_{*}}\right)% -\sum_{t\in\mathcal{T}_{\text{supp}}^{\prime}}\frac{P^{t}}{1+\epsilon}\right].

Proof.

By construction, for all time steps $t\in\mathcal{T}_{\text{supp}}^{\prime}$ , the algorithm pays $\frac{P^{t}}{1+\epsilon}$ . Consider a time step $t\in\mathcal{T}_{\text{cust}}^{\prime}$ in which $\max\{1,P^{t}\}=\max\{1,\sum_{i=1}^{n}a_{s^{t}_{*},i}\cdot x_{i}^{t-1}\}\leq v% ^{t}_{s^{t}_{*}}$ . If $\max\{1,P^{t}\}\leq v^{t}_{s^{t}_{*}}\leq\max\{1,P^{t}\}+2^{0}=1+\max\{1,P^{t}\}$ then the algorithm’s expected revenue is at least

	$\displaystyle(1-\delta)\cdot\max\{1,P^{t}\}$	$\displaystyle\geq(1-2\delta)\cdot\max\{1,P^{t}\}+\frac{\delta}{2}\cdot\left(1+% \max\{1,P^{t}\}\right)$
		$\displaystyle\geq(1-2\delta)\cdot\max\{1,P^{t}\}+\frac{\delta}{2}\cdot v^{t}_{% s^{t}_{*}}.$

Otherwise, let $k\in\{0,1,\ldots,\lfloor\log v\rfloor\}$ be such that, $\max\{1,P^{t}\}+2^{k}\leq v_{s^{t}_{*}}\leq\max\{1,P^{t}\}+2^{k+1}$ . The total expected revenue of the algorithm is:

	$\displaystyle(1-\delta)\cdot\max\{1,P^{t}\}+\frac{\delta}{1+\lfloor\log v% \rfloor}\cdot\left(\max\{1,P^{t}\}+\sum_{i=0}^{k}2^{i}\right)$
	$\displaystyle\geq(1-\delta)\cdot\max\{1,P^{t}\}+\frac{\delta}{1+\log v}\cdot% \left(\max\{1,P^{t}\}+2^{k}\right)$
	$\displaystyle\geq(1-\delta)\cdot\max\{1,P^{t}\}+\frac{\delta}{2+2\log v}\cdot v% ^{t}_{s^{t}_{*}}.$

The last inequality follows since $v^{t}_{s^{t}_{*}}\leq\max\{1,P^{t}\}+2^{k+1}\leq 2\cdot(\max\{1,P^{t}\}+2^{k}).$ $\hfill\blacktriangleleft$ Plugging $\delta=\nicefrac{{\epsilon}}{{8}}$ into Lemma 16, the algorithm’s expected revenue is at least,

	$\displaystyle E[V_{alg}]$	$\displaystyle\geq\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}\left(\left(1-2% \delta\right)\cdot\max\{1,P^{t}\}+\frac{\delta}{2(1+\log v)}\cdot v^{t}_{s^{t}% _{*}}\right)-\sum_{t\in\mathcal{T}_{\text{supp}}^{\prime}}\frac{P^{t}}{1+\epsilon}$
		$\displaystyle=\sum_{t\in\mathcal{T}_{\text{cust}}^{\prime}}\left(\left(1-\frac% {\epsilon}{4}\right)\cdot\max\{1,P^{t}\}+\frac{\epsilon\cdot v^{t}_{s^{t}_{*}}% }{16(1+\log v)}\right)-\sum_{t\in\mathcal{T}_{\text{supp}}^{\prime}}\frac{P^{t% }}{1+\epsilon}.$

Combining this with the upper bound on the optimal profit we get,
$\displaystyle OPT=O\left(\frac{\eta}{\epsilon}\right)\cdot\left[\sum_{t\in% \mathcal{T}_{\text{cust}}^{\prime}}\left(\left(1-\frac{\epsilon}{4}\right)% \cdot P^{t}+\frac{\epsilon\cdot v^{t}_{s_{*}^{t}}}{\eta}+\frac{1}{\mu}\right)-% \sum_{t\in\mathcal{T}_{\text{supp}}^{\prime}}\frac{P^{t}}{1+\epsilon}\right]$ $\displaystyle=O\left(\frac{\eta}{\epsilon}\right)\cdot\left[\sum_{t\in\mathcal% {T}_{\text{cust}}^{\prime}}\left(\left(1-\frac{\epsilon}{4}\right)\cdot\max\{1% ,P^{t}\}+\frac{\epsilon\cdot v^{t}_{s_{*}^{t}}}{32(1+\log v)}+\frac{\epsilon}{% 32(1+\log v)}\right)-\sum_{t\in\mathcal{T}_{\text{supp}}^{\prime}}\frac{P^{t}}% {1+\epsilon}\right]$ $\displaystyle=O\left(\frac{\eta}{\epsilon}\right)\left[\sum_{t\in\mathcal{T}_{% \text{cust}}^{\prime}}\left(\left(1-\frac{\epsilon}{4}\right)\max\{1,P^{t}\}+% \frac{\epsilon\cdot v^{t}_{s_{*}^{t}}}{16(1+\log v)}\right)-\sum_{t\in\mathcal% {T}_{\text{supp}}^{\prime}}\frac{P^{t}}{1+\epsilon}\right]=O\left(\frac{\eta}{% \epsilon}\right)E[V_{alg}],$

where the final inequality uses the fact that $v^{t}_{s_{*}^{t}}\geq 1$ for $t\in\mathcal{T}_{\text{cust}}$ . Finally, note that $\eta=O(\log(dv/\epsilon))$ . Hence, the algorithm is $O\left(\eta/\epsilon\right)=O\left(\log(dv/\epsilon)/\epsilon\right)$ -competitive concluding the proof of the second part of Theorem 3.

4 Lower Bounds

In this section, we prove our lower bound theorem.

Theorem 17.

For the online trading problem (even for the known valuation setting and single minded customers/suppliers), when comparing to an optimal offline fractional solution for which supplier values are $(1+\epsilon)$ larger:

$\blacksquare$

The competitive ratio of any deterministic or randomized algorithm is $\Omega(\frac{1}{\epsilon}\cdot\log(dv))$ . This holds even if all the items are of a single type. In particular, without the $1+\epsilon$ supplier value augmentation, the competitive ratio of any algorithm is unbounded.
$\blacksquare$

There exists a constant $c$ , such that if the inventory from an item type is less than $\frac{c}{\epsilon}\cdot\log(dv)$ times the number of items of type $i$ in some of the bundles, then the competitive ratio of any deterministic algorithm is unbounded. This holds even with respect to an optimal solution that can hold a single item from each type.

In Section 4.1 we prove the first statement of the theorem. Due to space considerations, we leave the second part of the proof (which is similar) to the full version [7].

4.1 $\Omega(\frac{1}{\epsilon}\cdot\log{dv})$ Lower Bound

In this section we prove that the competitive ratio of any deterministic or randomized algorithm is $\Omega(\frac{1}{\epsilon}\cdot\log(dv))$ , even in the special case where all items are of a single type. In particular, without the $1+\epsilon$ value augmentation of the suppliers, the competitive ratio is unbounded. We prove two lower bounds separately: (a) $\Omega(\frac{1}{\epsilon}\cdot\log v)$ even when all customers and suppliers wish to buy or sell a single item ( $d=1$ ), but the value for the item is in $[1,v]$ for some arbitrary value $v>1$ ; (b) $\Omega(\frac{1}{\epsilon}\cdot\log d)$ even when the value of the bundles requested are in the range $[1,2]$ (i.e. $v=2$ ), but the bundles may contain up to $d$ items for an arbitrary $d\in\mathbb{Z}_{+}$ . The two lower bounds are very similar, but we show them separately for clarity.

Our bounds hold even when the algorithm is allowed to sell or buy items fractionally. Observe that any randomized algorithm $\mathcal{R}$ for the trading problem (against an oblivious adversary!) induces a feasible fractional solution $r$ , where $r^{t}_{i}$ is the expected inventory item type $i$ that algorithm $\mathcal{R}$ holds at time $t$ . Therefore, the lower bound we prove holds even for randomized algorithms.

Intuition.

In the hard input sequence we construct, there are unbounded number of phases. In each phase, the adversary presents to the algorithm a stream of suppliers each selling at exponentially decreasing cost a full inventory’s worth of the same item. As long as the algorithm purchases “enough” of the items, the phase continues. Otherwise, the adversary presents a set of customers offering to buy items at a price $(1+\epsilon)^{2}$ times the last (cheapest) supplier’s price, and the phase ends. If the last suppliers arrive with a cheapest price per unit of item of $x$ , then the optimal solution purchases a full inventory for a price per unit of $(1+\epsilon)x$ (paying $(1+\epsilon)$ times the price paid by the algorithm), and immediately sells at a price per unit of $(1+\epsilon)^{2}\cdot x$ , making profit of $\epsilon\cdot(1+\epsilon)x$ per unit. On the other hand, we argue that we can define “enough” such that the algorithm needs to spend too much money over the course of the sequence to make more than a fraction of this optimal profit. We repeat this construction an arbitrary number of times in phases to amortize away any initialization constants.

In the $\Omega(\frac{1}{\epsilon}\log v)$ lower bound the decreasing prices per unit are achieved via suppliers with decreasing values. In the $\Omega(\frac{1}{\epsilon}\log d)$ lower bound, the decreasing prices are instead achieved via suppliers with (roughly) fixed values but increasing sizes of bundles. There is an additional technical complexity in the second bound that stems from the fact that bundle sizes must be integral, and to achieve this we vary valuations slightly in the range $[1,2]$ .

4.1.1 Proof of the $\Omega(\frac{1}{\epsilon}\log v)$ lower bound

Lemma 18.

The competitive ratio of any deterministic or randomized algorithm is $\Omega(\frac{1}{\epsilon}\cdot\log v)$ . This holds even if $d=1$ , all the items are of a single type, and the customers/supplier are single minded.

Proof.

We assume that $v$ is such that $v\geq(1+\epsilon)^{8}$ , and let $c=\lfloor\nicefrac{{1}}{{2}}\cdot\log_{1+\epsilon}v\rfloor-1$ be an integer (thus larger than 3). The input sequence is divided into phases, each of which consists of an adaptive sequence of steps in which suppliers arrive, followed by one single step in which customers arrive. We denote by $y_{0}\in[0,w]$ the inventory of the algorithm at the beginning of the phase (before step $0$ ), and let $y_{t}\in[y_{0},w]$ be the (potentially fractional) inventory of the algorithm before the $t$ -th step. Let $i_{t}=\lfloor\frac{y_{t}}{w}\cdot c\rfloor$ (so that $\frac{y_{t}}{w}\cdot c\in[i_{t},i_{t}+1)$ and $i_{t}\in[0,c]$ ).

At the $t$ -th step, $w$ suppliers arrive, each offering to sell a single item with value $\frac{v}{(1+\epsilon)^{2(i_{t}+1)}}\in[\frac{v}{(1+\epsilon)^{2}},1]$ . The algorithm may purchase some fraction of items from the suppliers, thus increasing its inventory to $y_{t+1}\geq y_{t}$ . If $\frac{y_{t+1}}{w}\cdot c\leq i_{t}+1$ , then $w$ customers arrive, each wanting to purchase a single item with value $\frac{v}{(1+\epsilon)^{2i_{t}}}\in[v,(1+\epsilon)^{2}]$ , and the phase ends. Otherwise we continue to step $t+1$ . Let $F$ be the final time step in which suppliers arrive. Thus the inventory of the algorithm before the arrival of the last $w$ suppliers is $y_{F}$ . These suppliers have value $\frac{v}{(1+\epsilon)^{2(i_{F}+1)}}$ , and thus the customers have value $\frac{v}{(1+\epsilon)^{2i_{F}}}$ .

Note that every phase must eventually end because at each step in which no customer arrives (and the phase continues) we have $i_{t+1}\geq i_{t}+1$ , and for all $t$ , we have $i_{t}\leq c$ . Note also that due to our choice of $c=\lfloor\nicefrac{{1}}{{2}}\cdot\log_{1+\epsilon}v\rfloor-1$ , the values of all the suppliers and customer are indeed in the range $[1,v]$ .

Let $\Delta v_{alg}$ and $\Delta v_{adv}$ be the profit of the algorithm and the adversary in a single phase. To complete the proof of the lower bound, we compare these two quantities.

Bounding.

$\Delta v_{adv}$ : The adversary can buy $w$ items from the last $w$ suppliers and then immediately sell the entire inventory to the $w$ customers.⁵⁵5Technically, in the first phase, the adversary’s inventory is full and it does not need to pay to fill its inventory, which only helps our analysis. In every subsequent phase, the inventory of the adversary is initially empty. To purchase the $w$ items, it pays $w\cdot(1+\epsilon)\cdot\frac{v}{(1+\epsilon)^{2(i_{F}+1)}}$ (this is $(1+\epsilon)$ times the price offered to the algorithm by the suppliers in the last step). Hence, its total trading profit in the phase is

\Delta v_{adv}=w\cdot\left(\frac{v}{(1+\epsilon)^{2i_{F}}}-(1+\epsilon)\cdot% \frac{v}{(1+\epsilon)^{2(i_{F}+1)}}\right)=w\cdot\frac{\epsilon\cdot v}{(1+% \epsilon)^{2i_{F}+1}}.

Bounding.

$\Delta v_{alg}$ : To analyze the profit of Alg, we imagine that it represents the inventory it holds as a subset of the interval $[0,w]$ . We further imagine that when buying, it fills the interval $[0,w]$ from left to right, and when it sells it clears inventory from right to left (i.e. LIFO, see Figure 1). This is purely for accounting purposes and will not change the total profit of the algorithm. Next, we partition the inventory in the interval $[0,w]$ into $c$ (sub-)intervals indexed by $j=0,1,\ldots,c-1$ , where the $j$ th interval is the inventory between $[\frac{j}{c}\cdot w,\frac{j+1}{c}\cdot w]$ . The algorithm maintains the following invariant.⁶⁶6Note that the algorithm did not pay for its starting inventory: to account for this, we can imagine the algorithm starts the game with a profit of $\sum_{j=0}^{c-1}\frac{w}{c}\frac{v}{(1+\epsilon)^{2(j+1)}}$ which it then pays to ensure the invariant holds. This adds an absolute constant to the profit of the algorithm, which can be amortized to $0$ after sufficiently many phases.

Invariant 1.

The price paid per unit for the $j$ -th interval is at least $\frac{v}{(1+\epsilon)^{2(j+1)}}$ .

Proof.

Since the algorithm fills its inventory $[0,w]$ according to the LIFO policy, the occupied inventory at time $t$ is always the interval $[0,y_{t}]$ . Suppose that $[y_{t},y_{t+1}]\cap[\frac{j}{c}\cdot w,\frac{j+1}{c}\cdot w]\neq\emptyset$ , in other words the algorithm partially fills the interval $j$ in time step $t$ . Then $\frac{y_{t}}{w}\cdot c<j+1$ , so by construction the suppliers in time step $t$ have value at least $\frac{v}{(1+\epsilon)^{2(j+1)}}$ , and hence the fraction of the $j$ -th interval covered by $[y_{t},y_{t+1}]$ is bought at no less than this price. $\hfill\blacktriangleleft$

Figure 1: Illustration of the accounting scheme. We imagine the algorithm fills its inventory from left to right. By construction, the price at which the algorithm can fill any fraction of the

j

-th interval is at least

\frac{v}{(1+\epsilon)^{2(j+1)}}

.

To conclude the proof, recall $F$ is the final time step in which suppliers arrive, and the inventory of the algorithm before the arrival of the last $w$ suppliers is $y_{F}$ . As the phase ends this means that $\frac{y_{F+1}}{w}\cdot c\leq i_{F}+1$ meaning that $y_{F+1}\leq\frac{i_{F}+1}{c}\cdot w$ (the algorithm did not fill more than a single sub-interval). The profit the algorithm can make from selling items in the interval $[\frac{i_{F}}{c}\cdot w,y_{F+1}]$ is at most

	$\displaystyle\left(y_{F+1}-\frac{i_{F}}{c}\cdot w\right)\cdot\left(\frac{v}{(1% +\epsilon)^{2i_{F}}}-\frac{v}{(1+\epsilon)^{2(i_{F}+1)}}\right)\leq\frac{w}{c}% \cdot\left(\frac{v}{(1+\epsilon)^{2i_{F}}}-\frac{v}{(1+\epsilon)^{2(i_{F}+1)}}\right)$
	$\displaystyle=\frac{w}{c}\cdot\frac{v}{(1+\epsilon)^{2i_{F}+1}}\left(1+% \epsilon-\frac{1}{1+\epsilon}\right)\leq\frac{2w}{c}\cdot\frac{\epsilon\cdot v% }{(1+\epsilon)^{2i_{F}+1}}=\frac{2}{c}\cdot\Delta v_{adv}$

If the algorithm chooses to further sell inventory the range $[0,\frac{i_{F}}{c}\cdot w]$ , which was purchased at a price per item of at least $\frac{v}{(1+\epsilon)^{2i_{F}}}$ , the algorithm makes no profit (and will even lose money for selling from the range $[0,\frac{i_{F}-1}{c}\cdot w]$ ).

We conclude that the competitive ratio of the algorithm is at least $c/2=\Omega(\frac{1}{\epsilon}\log v)$ . $\hfill\blacktriangleleft$

4.1.2 Proof of the $\Omega(\frac{1}{\epsilon}\log d)$ lower bound

Lemma 19.

The competitive ratio of any deterministic or randomized algorithm is $\Omega(\frac{1}{\epsilon}\cdot\log d)$ . This holds even if $v=2$ , all the items are of a single type, and the customers/supplier are single minded.

Proof.

This time we construct an instance for every $d\geq 2$ . We assume that $d$ is a power of $2$ that divides $w$ , and $\epsilon$ is such that $d\geq(1+\epsilon)^{8}$ . Let $c=-1+\lfloor\frac{1}{2}\cdot\log_{1+\epsilon}d\rfloor$ be an integer, which by this assumption is at least $3$ .

Again, the input is divided into phases, each of which consists of an adaptive sequence of suppliers, followed by one set of customers. We denote by $y_{0}\in[0,w]$ the inventory of the algorithm at the beginning of the phase (before step $0$ ), and let $y_{t}\in[y_{0},w]$ be the (potentially fractional) inventory of the algorithm before the $t$ -th step. Let $i_{t}=\lfloor\frac{y_{t}}{w}\cdot c\rfloor$ (so that $\frac{y_{t}}{w}\cdot c\in[i_{t},i_{t}+1)$ and $i_{t}\in[0,c]$ ). Additionally define $x_{t}=\frac{1}{(1+\epsilon)^{2i_{t}}}$ . By our choice of $c=-1+\lfloor\frac{1}{2}\cdot\log_{1+\epsilon}d\rfloor$ , we have $1\leq\frac{1}{x_{t}}\leq d$ , for $t=0,\ldots,c+1$ . Let $d_{t}$ be the smallest power of $2$ greater than $1/x_{t}$ , and define $v_{t}=x_{t}\cdot d_{t}\in[1,2]$ . We have $d_{t}\in[1,d]$ .

At the $t$ -th step, $w/d_{t+1}$ suppliers arrive, each offering to sell $d_{t+1}$ items at value $v_{t+1}$ . Note $d$ divides $w$ and $d_{t}$ is also a power of 2 less than $d$ , so $\frac{w}{d_{t}}$ is integral. The algorithm may purchase some fraction of items from the suppliers, thus increasing its inventory to $y_{t+1}\geq y_{t}$ . If $\frac{y_{t+1}}{w}\cdot c\leq i_{t}+1$ , then $\frac{w}{d_{t}}$ customers arrive, each offering to buy a bundle of $d_{t}$ items for a price of $v_{t}$ , and the phase ends. Otherwise we continue to step $t+1$ . Note that every phase must eventually end because at each step in which no customer arrives (and the phase continues) we have $i_{t+1}\geq i_{t}+1$ , and for all $t$ we have $i_{t}\leq c$ . Once again let $F$ be the final time step in which suppliers arrive.

Bounding $\Delta v_{adv}$ .

The adversary can buy $d_{F+1}$ items from each of the last $\frac{w}{d_{F+1}}$ suppliers, thus buying $w$ items in total and filling its inventory.⁷⁷7Once again, in the very first phase the adversary starts with a full inventory and does not have to make any purchases. Then it can sell $d_{F}$ items to each of the $\frac{w}{d_{F}}$ customers, thus selling $w$ items in total and clearing its inventory. Its total profit (it pays $1+\epsilon$ times more than the algorithm to the suppliers) is:

\Delta v_{adv}=\frac{w}{d_{F}}\cdot v_{F}-(1+\epsilon)\frac{w}{d_{F+1}}\cdot v% _{F+1}=w\left(\frac{1}{(1+\epsilon)^{2i_{F}}}-\frac{1+\epsilon}{(1+\epsilon)^{% 2(i_{F}+1)}}\right)=w\cdot\frac{\epsilon}{(1+\epsilon)^{2i_{F}+1}},

where we used that $v_{t}/d_{t}=x_{t}=(1+\epsilon)^{-2i_{t}}$ by definition.

Bounding $\Delta v_{alg}$ .

Once again, to analyze the profit of Alg we imagine that it fills the interval $[0,w]$ from left to right when buying, and clears it from right to left when selling. We again partition $[0,w]$ into $c$ (sub-)intervals indexed by $j=0,1,\ldots,c-1$ , where the $j$ th interval is the inventory between $[\frac{j}{c}\cdot w,\frac{j+1}{c}\cdot w]$ . The invariant we maintain this time is very similar to the one before.⁸⁸8The algorithm does not pay for its initial inventory, but this adds a constant to the algorithm’s profit which amortizes to $0$ after enough phases.

Invariant 2.

The price paid per unit for the $j$ -th interval is at least $\frac{1}{(1+\epsilon)^{2(j+1)}}$ .

Proof.

The LIFO policy ensures that the occupied portion of the inventory $[0,w]$ at time step $t$ is the interval $[0,y_{t}]$ . Suppose that $[y_{t},y_{t+1}]\cap[\frac{j}{c}\cdot w,\frac{j+1}{c}\cdot w]\neq\emptyset$ (the algorithm fills some part of the $j$ th interval at time $t$ ). Then $\frac{y_{t}}{w}\cdot c<j+1$ , so the suppliers at time step $t$ offer a bundle of $d_{t+1}$ items with value $v_{t+1}$ such that the price per unit is $\frac{v_{t+1}}{d_{t+1}}=x_{t+1}=\frac{1}{(1+\epsilon)^{2(i_{t}+1)}}\geq\frac{1% }{(1+\epsilon)^{2(j+1)}}$ . This is precisely the price per unit paid for the portion of the $j$ -th interval covered in this step. $\hfill\blacktriangleleft$

Hence, when the $\frac{w}{d_{F}}$ customers arrive at the end of the phase with wishing to buy a bundle of size $d_{F}$ at price $v_{F}$ , their value per item is $\frac{v_{F}}{d_{F}}=x_{F}=\frac{1}{(1+\epsilon)^{2i_{F}}}$ . By construction, the customers arrive at time $t=F+1$ when $\frac{y_{F+1}}{w}\cdot c\leq i_{F}+1$ ( $y_{F+1}\leq w\cdot\frac{i_{F}+1}{c}$ ), so the profit of the algorithm from selling the cheapest items in the interval $[\frac{i_{F}}{c}\cdot w,y_{F+1}]$ is at most,

	$\displaystyle\left(y_{F+1}-\frac{w}{c}\cdot i_{F}\right)\cdot\left(\frac{1}{(1% +\epsilon)^{2i_{F}}}-\frac{1}{(1+\epsilon)^{2\cdot(i_{F}+1)}}\right)\leq\frac{% w}{c}\cdot\left(\frac{1}{(1+\epsilon)^{2i_{F}}}-\frac{1}{(1+\epsilon)^{2\cdot(% i_{F}+1)}}\right)$
	$\displaystyle=\frac{w}{c}\cdot\frac{1}{(1+\epsilon)^{2i_{F}+1}}\left(1+% \epsilon-\frac{1}{1+\epsilon}\right)\leq\frac{2w}{c}\cdot\frac{\epsilon}{(1+% \epsilon)^{2i_{F}+1}}=\frac{2}{c}\cdot\Delta v_{adv}$

If the algorithm chooses to further sell inventory the range $[0,\frac{i_{F}}{c}\cdot w]$ , which was purchased at a price per item of at least $\frac{v}{(1+\epsilon)^{2i_{F}}}$ , the algorithm makes no profit (and will even lose money for selling from the range $[0,\frac{i_{F}-1}{c}\cdot w]$ ).

We conclude that the competitive ratio of the algorithm is at least $c/2=\Omega(\frac{1}{\epsilon}\log d)$ . $\hfill\blacktriangleleft$

References

[1] Shipra Agrawal and Nikhil R. Devanur. Fast algorithms for online stochastic convex programming. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1405–1424. SIAM, 2015. doi:10.1137/1.9781611973730.93.
[2] Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Oper. Res., 62(4):876–890, 2014. doi:10.1287/OPRE.2014.1289.
[3] C. J. Argue, Anupam Gupta, Marco Molinaro, and Sahil Singla. Robust secretary and prophet algorithms for packing integer programs. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1273–1297. SIAM, 2022. doi:10.1137/1.9781611977073.53.
[4] Baruch Awerbuch, Yossi Azar, and Adam Meyerson. Reducing truth-telling online mechanisms to online optimization. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 503–510. ACM, 2003. doi:10.1145/780542.780616.
[5] Baruch Awerbuch, Yossi Azar, and Serge A. Plotkin. Throughput-competitive on-line routing. In 34th Annual Symposium on Foundations of Computer Science, pages 32–40. IEEE Computer Society, 1993. doi:10.1109/SFCS.1993.366884.
[6] Yossi Azar, Niv Buchbinder, T.-H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, and Debmalya Panigrahi. Online algorithms for covering and packing problems with convex objectives. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, Hyatt Regency, New Brunswick, New Jersey, USA, October 9-11, 2016, pages 148–157. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.24.
[7] Yossi Azar, Niv Buchbinder, Roie Levin, and Or Vardi. Competitive bundle trading. CoRR, abs/2507.23047, 2025. doi:10.48550/arXiv.2507.23047.
[8] Yossi Azar, Niv Buchbinder, Roie Levin, and Or Vardi. Trading prophets with initial capital. In To appear in the SIAM Symposium on Simplicity in Algorithms (SOSA26), 2026.
[9] Moshe Babaioff, Amitai Frey, and Noam Nisan. Learning to maximize gains from trade in small markets. In Dirk Bergemann, Robert Kleinberg, and Daniela Sabán, editors, Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024, page 195. ACM, 2024. doi:10.1145/3670865.3673463.
[10] François Bachoc, Nicolò Cesa-Bianchi, Tommaso Cesari, and Roberto Colomboni. Fair online bilateral trade. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024. URL: http://papers.nips.cc/paper_files/paper/2024/hash/419ce7cb77aa90868c16882ce4257a69-Abstract-Conference.html.
[11] Yair Bartal, Rica Gonen, and Noam Nisan. Incentive compatible multi unit combinatorial auctions. In Joseph Y. Halpern and Moshe Tennenholtz, editors, Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2003), Bloomington, Indiana, USA, June 20-22, 2003, pages 72–87. ACM, 2003. doi:10.1145/846241.846250.
[12] Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. No-regret learning in bilateral trade via global budget balance. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 247–258. Association for Computing Machinery, 2024. doi:10.1145/3618260.3649653.
[13] Sayan Bhattacharya, Niv Buchbinder, Roie Levin, and Thatchaphol Saranurak. Chasing positive bodies. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1694–1714. IEEE, 2023. doi:10.1109/FOCS57990.2023.00103.
[14] Liad Blumrosen and Shahar Dobzinski. (almost) efficient mechanisms for bilateral trading. Games Econ. Behav., 130:369–383, 2021. doi:10.1016/J.GEB.2021.08.011.
[15] Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998.
[16] Niv Buchbinder and Rica Gonen. Incentive compatible mulit-unit combinatorial auctions: A primal dual approach. Algorithmica, 72(1):167–190, 2015. doi:10.1007/S00453-013-9854-4.
[17] Niv Buchbinder and Joseph Naor. Improved bounds for online routing and packing via a primal-dual approach. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 293–304. IEEE Computer Society, 2006. doi:10.1109/FOCS.2006.39.
[18] Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing. Math. Oper. Res., 34(2):270–286, 2009. doi:10.1287/MOOR.1080.0363.
[19] Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade: A regret minimization perspective. Math. Oper. Res., 49(1):171–203, 2024. doi:10.1287/MOOR.2023.1351.
[20] José Correa, Andrés Cristi, Paul Duetting, MohammadTaghi Hajiaghayi, Jan Olkowski, and Kevin Schewior. Trading prophets. In Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson, editors, Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, pages 490–510. ACM, 2023. doi:10.1145/3580507.3597813.
[21] Arnoud V Den Boer. Dynamic pricing and learning: historical origins, current research, and new directions. Surveys in operations research and management science, 20(1):1–18, 2015.
[22] Nikhil R. Devanur and Thomas P. Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In John Chuang, Lance Fortnow, and Pearl Pu, editors, Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6–10, 2009, pages 71–78. ACM, 2009. doi:10.1145/1566374.1566384.
[23] Nikhil R. Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A. Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM, 66(1):7:1–7:41, 2019. doi:10.1145/3284177.
[24] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Truthful randomized mechanisms for combinatorial auctions. J. Comput. Syst. Sci., 78(1):15–25, 2012. doi:10.1016/J.JCSS.2011.02.010.
[25] Ran El-Yaniv, Amos Fiat, Richard M. Karp, and G. Turpin. Optimal search and one-way trading online algorithms. Algorithmica, 30(1):101–139, 2001. doi:10.1007/S00453-001-0003-0.
[26] Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Clifford Stein. Online stochastic packing applied to display ad allocation. In Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I, volume 6346 of Lecture Notes in Computer Science, pages 182–194. Springer, 2010. doi:10.1007/978-3-642-15775-2_16.
[27] Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 123–135. SIAM, 2015. doi:10.1137/1.9781611973730.10.
[28] Stanley P. Y. Fung. Optimal online two-way trading with bounded number of transactions. Algorithmica, 81(11-12):4238–4257, 2019. doi:10.1007/S00453-018-00534-9.
[29] Stanley P. Y. Fung. Online two-way trading: Randomization and advice. Theor. Comput. Sci., 856:41–50, 2021. doi:10.1016/J.TCS.2020.12.016.
[30] Guillermo Gallego and Huseyin Topaloglu. Revenue Management and Pricing Analytics. Springer New York, NY, 2019.
[31] Guillermo Gallego and Garrett J. van Ryzin. A multiproduct dynamic pricing problem and its applications to network yield management. Oper. Res., 45(1):24–41, 1997. doi:10.1287/OPRE.45.1.24.
[32] Anupam Gupta and Marco Molinaro. How the experts algorithm can help solve lps online. Math. Oper. Res., 41(4):1404–1431, 2016. doi:10.1287/MOOR.2016.0782.
[33] Stefanus Jasin. Reoptimization and self-adjusting price control for network revenue management. Oper. Res., 62(5):1168–1178, 2014. doi:10.1287/OPRE.2014.1297.
[34] Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. Primal beats dual on online packing lps in the random-order model. SIAM J. Comput., 47(5):1939–1964, 2018. doi:10.1137/15M1033708.
[35] Ron Lavi and Chaitanya Swamy. Truthful and near-optimal mechanism design via linear programming. J. ACM, 58(6):25:1–25:24, 2011. doi:10.1145/2049697.2049699.
[36] Stefano Leonardi and Alberto Marchetti-Spaccamela. On-line resource management with application to routing and scheduling. Algorithmica, 24(1):29–49, 1999. doi:10.1007/PL00009270.
[37] Bin Li and Steven C. H. Hoi. Online portfolio selection: A survey. ACM Comput. Surv., 46(3):35:1–35:36, 2014. doi:10.1145/2512962.
[38] Will Ma, Calum MacRury, and Jingwei Zhang. Online contention resolution schemes for network revenue management and combinatorial auctions. CoRR, abs/2403.05378, 2024. doi:10.48550/arXiv.2403.05378.
[39] Yuhang Ma, Paat Rusmevichientong, Mika Sumida, and Huseyin Topaloglu. An approximation algorithm for network revenue management under nonstationary arrivals. Oper. Res., 68(3):834–855, 2020. doi:10.1287/OPRE.2019.1931.
[40] Constantinos Maglaras and Joern Meissner. Dynamic pricing strategies for multiproduct revenue management problems. Manuf. Serv. Oper. Manag., 8(2):136–148, 2006. doi:10.1287/MSOM.1060.0105.
[41] Roger B. Myerson and Mark A. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 29(2):265–281, 1983.
[42] Neel Patel and David Wajc. Combinatorial stationary prophet inequalities. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 4605–4630. SIAM, 2024. doi:10.1137/1.9781611977912.164.
[43] Surbhi Rajput, Ashish Chiplunkar, and Rohit Vaish. Trading prophets: How to trade multiple stocks optimally. In Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA25), pages 238–252, 2025. doi:10.1137/1.9781611978315.19.
[44] Tim Roughgarden, editor. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020.

[bib.bib1] [1] Shipra Agrawal and Nikhil R. Devanur. Fast algorithms for online stochastic convex programming. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1405–1424. SIAM, 2015. doi:10.1137/1.9781611973730.93.

[bib.bib2] [2] Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Oper. Res., 62(4):876–890, 2014. doi:10.1287/OPRE.2014.1289.

[bib.bib3] [3] C. J. Argue, Anupam Gupta, Marco Molinaro, and Sahil Singla. Robust secretary and prophet algorithms for packing integer programs. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1273–1297. SIAM, 2022. doi:10.1137/1.9781611977073.53.

[bib.bib4] [4] Baruch Awerbuch, Yossi Azar, and Adam Meyerson. Reducing truth-telling online mechanisms to online optimization. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 503–510. ACM, 2003. doi:10.1145/780542.780616.

[bib.bib5] [5] Baruch Awerbuch, Yossi Azar, and Serge A. Plotkin. Throughput-competitive on-line routing. In 34th Annual Symposium on Foundations of Computer Science, pages 32–40. IEEE Computer Society, 1993. doi:10.1109/SFCS.1993.366884.

[bib.bib6] [6] Yossi Azar, Niv Buchbinder, T.-H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, and Debmalya Panigrahi. Online algorithms for covering and packing problems with convex objectives. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, Hyatt Regency, New Brunswick, New Jersey, USA, October 9-11, 2016, pages 148–157. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.24.

[bib.bib7] [7] Yossi Azar, Niv Buchbinder, Roie Levin, and Or Vardi. Competitive bundle trading. CoRR, abs/2507.23047, 2025. doi:10.48550/arXiv.2507.23047.

[bib.bib8] [8] Yossi Azar, Niv Buchbinder, Roie Levin, and Or Vardi. Trading prophets with initial capital. In To appear in the SIAM Symposium on Simplicity in Algorithms (SOSA26), 2026.

[bib.bib9] [9] Moshe Babaioff, Amitai Frey, and Noam Nisan. Learning to maximize gains from trade in small markets. In Dirk Bergemann, Robert Kleinberg, and Daniela Sabán, editors, Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024, page 195. ACM, 2024. doi:10.1145/3670865.3673463.

[bib.bib10] [10] François Bachoc, Nicolò Cesa-Bianchi, Tommaso Cesari, and Roberto Colomboni. Fair online bilateral trade. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024. URL: http://papers.nips.cc/paper_files/paper/2024/hash/419ce7cb77aa90868c16882ce4257a69-Abstract-Conference.html.

[bib.bib11] [11] Yair Bartal, Rica Gonen, and Noam Nisan. Incentive compatible multi unit combinatorial auctions. In Joseph Y. Halpern and Moshe Tennenholtz, editors, Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2003), Bloomington, Indiana, USA, June 20-22, 2003, pages 72–87. ACM, 2003. doi:10.1145/846241.846250.

[bib.bib12] [12] Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. No-regret learning in bilateral trade via global budget balance. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 247–258. Association for Computing Machinery, 2024. doi:10.1145/3618260.3649653.

[bib.bib13] [13] Sayan Bhattacharya, Niv Buchbinder, Roie Levin, and Thatchaphol Saranurak. Chasing positive bodies. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1694–1714. IEEE, 2023. doi:10.1109/FOCS57990.2023.00103.

[bib.bib14] [14] Liad Blumrosen and Shahar Dobzinski. (almost) efficient mechanisms for bilateral trading. Games Econ. Behav., 130:369–383, 2021. doi:10.1016/J.GEB.2021.08.011.

[bib.bib15] [15] Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998.

[bib.bib16] [16] Niv Buchbinder and Rica Gonen. Incentive compatible mulit-unit combinatorial auctions: A primal dual approach. Algorithmica, 72(1):167–190, 2015. doi:10.1007/S00453-013-9854-4.

[bib.bib17] [17] Niv Buchbinder and Joseph Naor. Improved bounds for online routing and packing via a primal-dual approach. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 293–304. IEEE Computer Society, 2006. doi:10.1109/FOCS.2006.39.

[bib.bib18] [18] Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing. Math. Oper. Res., 34(2):270–286, 2009. doi:10.1287/MOOR.1080.0363.

[bib.bib19] [19] Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade: A regret minimization perspective. Math. Oper. Res., 49(1):171–203, 2024. doi:10.1287/MOOR.2023.1351.

[bib.bib20] [20] José Correa, Andrés Cristi, Paul Duetting, MohammadTaghi Hajiaghayi, Jan Olkowski, and Kevin Schewior. Trading prophets. In Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson, editors, Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, pages 490–510. ACM, 2023. doi:10.1145/3580507.3597813.

[bib.bib21] [21] Arnoud V Den Boer. Dynamic pricing and learning: historical origins, current research, and new directions. Surveys in operations research and management science, 20(1):1–18, 2015.

[bib.bib22] [22] Nikhil R. Devanur and Thomas P. Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In John Chuang, Lance Fortnow, and Pearl Pu, editors, Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6–10, 2009, pages 71–78. ACM, 2009. doi:10.1145/1566374.1566384.

[bib.bib23] [23] Nikhil R. Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A. Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM, 66(1):7:1–7:41, 2019. doi:10.1145/3284177.

[bib.bib24] [24] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Truthful randomized mechanisms for combinatorial auctions. J. Comput. Syst. Sci., 78(1):15–25, 2012. doi:10.1016/J.JCSS.2011.02.010.

[bib.bib25] [25] Ran El-Yaniv, Amos Fiat, Richard M. Karp, and G. Turpin. Optimal search and one-way trading online algorithms. Algorithmica, 30(1):101–139, 2001. doi:10.1007/S00453-001-0003-0.

[bib.bib26] [26] Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Clifford Stein. Online stochastic packing applied to display ad allocation. In Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I, volume 6346 of Lecture Notes in Computer Science, pages 182–194. Springer, 2010. doi:10.1007/978-3-642-15775-2_16.

[bib.bib27] [27] Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 123–135. SIAM, 2015. doi:10.1137/1.9781611973730.10.

[bib.bib28] [28] Stanley P. Y. Fung. Optimal online two-way trading with bounded number of transactions. Algorithmica, 81(11-12):4238–4257, 2019. doi:10.1007/S00453-018-00534-9.

[bib.bib29] [29] Stanley P. Y. Fung. Online two-way trading: Randomization and advice. Theor. Comput. Sci., 856:41–50, 2021. doi:10.1016/J.TCS.2020.12.016.

[bib.bib30] [30] Guillermo Gallego and Huseyin Topaloglu. Revenue Management and Pricing Analytics. Springer New York, NY, 2019.

[bib.bib31] [31] Guillermo Gallego and Garrett J. van Ryzin. A multiproduct dynamic pricing problem and its applications to network yield management. Oper. Res., 45(1):24–41, 1997. doi:10.1287/OPRE.45.1.24.

[bib.bib32] [32] Anupam Gupta and Marco Molinaro. How the experts algorithm can help solve lps online. Math. Oper. Res., 41(4):1404–1431, 2016. doi:10.1287/MOOR.2016.0782.

[bib.bib33] [33] Stefanus Jasin. Reoptimization and self-adjusting price control for network revenue management. Oper. Res., 62(5):1168–1178, 2014. doi:10.1287/OPRE.2014.1297.

[bib.bib34] [34] Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. Primal beats dual on online packing lps in the random-order model. SIAM J. Comput., 47(5):1939–1964, 2018. doi:10.1137/15M1033708.

[bib.bib35] [35] Ron Lavi and Chaitanya Swamy. Truthful and near-optimal mechanism design via linear programming. J. ACM, 58(6):25:1–25:24, 2011. doi:10.1145/2049697.2049699.

[bib.bib36] [36] Stefano Leonardi and Alberto Marchetti-Spaccamela. On-line resource management with application to routing and scheduling. Algorithmica, 24(1):29–49, 1999. doi:10.1007/PL00009270.

[bib.bib37] [37] Bin Li and Steven C. H. Hoi. Online portfolio selection: A survey. ACM Comput. Surv., 46(3):35:1–35:36, 2014. doi:10.1145/2512962.

[bib.bib38] [38] Will Ma, Calum MacRury, and Jingwei Zhang. Online contention resolution schemes for network revenue management and combinatorial auctions. CoRR, abs/2403.05378, 2024. doi:10.48550/arXiv.2403.05378.

[bib.bib39] [39] Yuhang Ma, Paat Rusmevichientong, Mika Sumida, and Huseyin Topaloglu. An approximation algorithm for network revenue management under nonstationary arrivals. Oper. Res., 68(3):834–855, 2020. doi:10.1287/OPRE.2019.1931.

[bib.bib40] [40] Constantinos Maglaras and Joern Meissner. Dynamic pricing strategies for multiproduct revenue management problems. Manuf. Serv. Oper. Manag., 8(2):136–148, 2006. doi:10.1287/MSOM.1060.0105.

[bib.bib41] [41] Roger B. Myerson and Mark A. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 29(2):265–281, 1983.

[bib.bib42] [42] Neel Patel and David Wajc. Combinatorial stationary prophet inequalities. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 4605–4630. SIAM, 2024. doi:10.1137/1.9781611977912.164.

[bib.bib43] [43] Surbhi Rajput, Ashish Chiplunkar, and Rohit Vaish. Trading prophets: How to trade multiple stocks optimally. In Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA25), pages 238–252, 2025. doi:10.1137/1.9781611978315.19.

[bib.bib44] [44] Tim Roughgarden, editor. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020.

Competitive Bundle Trading

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

From Selling to Trading.

Further extensions.

1.1 Our results

Theorem 1 (Main Theorem, informal).

Theorem 2 (Lower Bound, informal).

1.2 Techniques

Known valuations.

Unknown valuations.

1.3 Related Work

Customer only setting.

Prophet trading.

(Online) Bilateral Trading.

Two-Way Trading and Portfolio Selection.

Other.

2 Preliminaries

Problem Statement.

Additional Notation.

3 The Algorithm

Theorem 3.

3.1 The Known Valuation Setting

Assumption 4 (Large inventory).

Theorem 5.

Observation 6.

Proof.

Observation 7.

Proof.

Lemma 8.

Proof.

Analysis via Duality

Constructing the dual solution.

Lemma 9.

Proof.

Lemma 10.

Claim 11.

Proof.

Claim 12.

Proof.

Proof of Lemma 10.

3.2 The Unknown Valuation Setting

▶ Remark 13.

Observation 14.

Proof.

Claim 15.

Proof.

Lemma 16.

Proof.

4 Lower Bounds

Theorem 17.

4.1 𝛀⁢(𝟏ϵ⋅𝐥𝐨𝐠⁡𝒅⁢𝒗) Lower Bound

Intuition.

4.1.1 Proof of the 𝛀⁢(𝟏ϵ⁢𝐥𝐨𝐠⁡𝒗) lower bound

Lemma 18.

Proof.

Bounding.

Bounding.

Invariant 1.

Proof.

4.1.2 Proof of the 𝛀⁢(𝟏ϵ⁢𝐥𝐨𝐠⁡𝒅) lower bound

Lemma 19.

Proof.

Bounding 𝚫⁢𝒗𝒂⁢𝒅⁢𝒗.

Bounding 𝚫⁢𝒗𝒂⁢𝒍⁢𝒈.

Invariant 2.

Proof.

References

$\blacktriangleright$ Remark 13.

4.1 $\Omega(\frac{1}{\epsilon}\cdot\log{dv})$ Lower Bound

4.1.1 Proof of the $\Omega(\frac{1}{\epsilon}\log v)$ lower bound

4.1.2 Proof of the $\Omega(\frac{1}{\epsilon}\log d)$ lower bound

Bounding $\Delta v_{adv}$ .

Bounding $\Delta v_{alg}$ .