1 Introduction↩︎

Consider an online resource allocation setting where a seller offers \(m\) shared resources for sale, and \(n\) buyers with requests having different preferences over combinations of resources arrive over time. We want to design an online algorithm for allocating the resources to buyers to satisfy their request in order to maximize social welfare, which is the total value obtained by all buyers, while satisfying the predefined budget constraints. When each agent arrives, the seller makes an irrevocable allocation decision and does not wait for future arrivals.

We study a general stochastic setting where the request type of each buyer is drawn independently from unknown and possibly non-identical distributions. Recently, [1] proved the first bounded sample complexity result for such an online resource allocation problem with heterogeneous agents, that under a large-budget constraint (where each type of resource has \(\widetilde{\Omega} (\mathsf{poly}(\epsilon))\) supply), it is possible to design a \((1-\epsilon)\)-approximation algorithm given just a single sample from each of the \(n\) request distributions³. The proposed algorithm is a dynamic pricing algorithm, that decides the prices of the items according to the previous arrivals and the current arriving agent. In particular, the algorithm proposed is based on a pricing scheme, where the price of a resource adjusts exponentially based on the difference between its actual consumption and its expected consumption up to the current time. While this yields a strong theoretical guarantee with minimal samples needed, the resulting mechanism introduces the following two limitations.

• Lack of Anonymity: Two identical agents requesting the same resources with the same value may face different prices simply because they arrived at different positions in the queue. This form of discrimination is often undesirable.

• Sensitivity to Ordering: The learning algorithm proposed by [1] requires knowledge of the arrival sequence to compute the expected consumption at each step. It is not robust to an unknown or adversarial arrival order.

Given the limitations mentioned above, we want to understand whether a simpler mechanism is learnable. In particular, we ask the following question, arising from the above limitations.

Given sample or query access to the agents’ value distributions, is it possible to learn an anonymous pricing mechanism for agents arriving in unknown order with a small number of samples that obtains near-optimal welfare?

1.1 Model↩︎

Before we introduce our main result, we start with introducing the model we study. We will define the online resource allocation problem that we study, different types of item pricing mechanisms, and what we mean by learning through queries.

1.1.1 Online Resource Allocation↩︎

We study an online resource allocation problem, where the seller receives a sequence of \(n\) requests from buyers arriving in arbitrary order, for \(m\) kinds of limited resources with budget \(\mathbf{B}=(B_1,B_2,\cdots,B_m)\in \mathbb{R}^m_{\geq 0}\) for all resources. The request from each buyer \(i \in [n]\) is denoted by \(\gamma_i = (v_i, \boldsymbol{a}_i, \Theta_i)\), where \(\Theta_i\) denotes the decision set, and choosing any decision \(\theta_i\in\Theta_i\) will generate value \(v_i(\theta_i)\in\mathbb{R}_{\geq 0}\) for buyer \(i\), while consuming at most a unit of each resource \(\boldsymbol{a}_i(\theta_i)=(a_{i,1}(\theta_i),a_{i,2}(\theta_i),\cdots,a_{i,m}(\theta_i))\in[0,1]^m\). Without loss of generality assume \(B_j\leq n\) for each resource \(j\). We use \(|\Theta_{\max}|\) to denote the maximum size of the decision set, and always assume that there is a null decision \(\phi\in\Theta_i\) for each buyer, such that \(v_i(\phi)=0\) and \(\boldsymbol{a}_i(\phi)=\mathbf{0}\). The objective of the seller is to maximize social welfare \(\sum_{i=1}^{n} v_i(\theta_i)\), while not exceeding the budget of any resource.

We study the stochastic setting with underlying request distributions \(\boldsymbol{\mathcal{D}}= (\mathcal{D}_1, \cdots, \mathcal{D}_n)\), i.e., the request \(\gamma_i\) of each buyer is drawn independently from a type distribution \(\mathcal{D}_i\) over a type space \(\Gamma_i\). Each type \(\gamma_i = (v_i, \boldsymbol{a}_i, \Theta_i)\sim\mathcal{D}_i\) is realized for each agent \(i \in [n]\). The benchmark of the optimization problem is the hindsight fractional optimal solution \(\mathsf{Opt}\), which is the optimal value of the configuration linear program defined below. Let \(x_{i,\gamma_i, \theta}\) denote the fractional allocation to agent \(i\) with type \(\gamma_i\) and decision \(\theta \in \Theta_i\). Then we can write the configuration LP as follows: \[\begin{align} \mathsf{Opt}\quad:=\quad\text{maximize } \quad \quad & \textstyle \quad\sum_{i \in [n]} \mathbb{E}_{\gamma_i \sim \mathcal{D}_i} \left[ \sum_{\theta \in \Theta_i} v_i(\theta) \cdot x_{i,\gamma_i, \theta} \right],\notag \\ \text{s.t.}\qquad\qquad & \textstyle \quad \sum_{i \in [n]} \mathbb{E}_{\gamma_i \sim \mathcal{D}_i} \left[ \sum_{\theta \in \Theta_i} \boldsymbol{a}_i(\theta) \cdot x_{i,\gamma_i, \theta} \right] \leq \mathbf{B}, _{\mathrm{\small Relax}}} \label{program:ora-ub} \\ \forall i \in [n], \gamma_i\in\Gamma_i, & \textstyle \quad \sum_{\theta \in \Theta_{i}} x_{i,\gamma_i, \theta} \leq 1, \notag \\ \forall i \in [n], \theta \in \Theta_{i},& \quad 0 \leq x_{i,\gamma_i, \theta} \leq 1. \notag \end{align}\tag{1}\]

We use notation 1 \((\boldsymbol{\mathcal{D}}; \mathbf{B})\) to represent the linear program 1 with underlying request distributions \(\boldsymbol{\mathcal{D}}\) and budget \(\mathbf{B}\). Then, given an online resource allocation instance with underlying distributions \(\boldsymbol{\mathcal{D}}\) and budget \(\mathbf{B}\), the fractional solution of 1 \((\boldsymbol{\mathcal{D}}; \mathbf{B})\) is an upper bound of the hindsight optimal solution (i.e. when the seller knows the realization and arrival order of the agents in advance).

Next, we characterize the dual of the primal program 1 . Define the dual variables as follows. Let \(\pmb{\lambda}\in \mathbb{R}^m_{\geq 0}\) be the dual variable associated with the resource budget constraint. For each \(i \in [n]\) and each type \(\gamma_i \in \Gamma_i\), let \(u_{i, \gamma_i} \geq 0\) be the dual variable associated with the demand constraint \(\sum_{\theta \in \Theta_i} x_{i, \gamma_i, \theta} \leq 1\). The dual problem can be written as follows:

\[\begin{align} \mathsf{Opt}_{\mathrm{\small dual}} \quad:=\quad \text{minimize } \quad \quad & \langle\pmb{\lambda},\mathbf{B}\rangle + \sum_{i \in [n]} \mathbb{E}_{\gamma_i \sim \mathcal{D}_i} [u_{i, \gamma_i}] \notag \\ \text{s.t.} \qquad \qquad & \pmb{\lambda}\geq 0, \notag \\ \forall i \in [n], \gamma_i \in \Gamma_i, \theta \in \Theta_i,\quad & u_{i, \gamma_i} + \langle\pmb{\lambda},\boldsymbol{a}_i(\theta)\rangle \geq v_i(\theta), _{\mathrm{\small dual}}} \label{program:dual} \\ \forall i \in [n], \gamma_i \in \Gamma_i,\quad & u_{i, \gamma_i} \geq 0. \notag \end{align}\tag{2}\]

The dual variables \(\pmb{\lambda}\) in the optimal dual solution correspond to the item prices such that under a specific tie-breaking rule, setting static pricing \(\pmb{\lambda}\) to all agents obtains the optimal welfare. Similarly, we use notation 2 \((\boldsymbol{\mathcal{D}}; \mathbf{B})\) to represent the linear program 2 with underlying request distributions \(\boldsymbol{\mathcal{D}}\) and budget \(\mathbf{B}\).

1.1.2 Pricing Mechanisms↩︎

In this paper, when designing the allocation mechanisms for each agent, we consider simple posted pricing mechanisms. When each agent \(i\) with type \(\gamma_i=(v_i,\boldsymbol{a}_i,\Theta_i)\) arrives, she faces a price vector \(\pmb{\lambda}_i\in\mathbb{R}_{\geq 0}^m\) with a non-negative price \(\lambda_{i,j}\) for each resource \(j\in[m]\). The agent then selects the utility-maximizing decision \(\theta_i\in\Theta_i\), i.e. \[\theta_i=\mathop{\arg\max}_{\theta\in\Theta_i} \left(v_i(\theta)-\langle \boldsymbol{a}_i(\theta),\pmb{\lambda}_i\rangle\right),\] which is the decision that maximizes the difference between the agent’s value and the price for the resource consumption.⁴ In this paper, we discuss the following different types of pricing mechanisms:

• Adaptive (Dynamic) Pricing. When each agent \(i\) arrives, the seller sets a price vector \(\pmb{\lambda}_i\in\mathbb{R}_{\geq 0}^m\), depending on the history of previous allocations and possibly the identity of the arriving agent. Then the arriving agent makes a utility-maximizing decision \(\theta_i\).

• Anonymous Pricing. When any agent \(i\) arrives at time \(t\), the seller sets a pricing \(\pmb{\lambda}_t\) that does not depend on the allocation history, the buyer’s identity, and the current time. Then the arriving agent makes a utility-maximizing decision \(\theta_i\).

• Static Pricing. Before any agent arrives, the seller sets a fixed pricing \(\pmb{\lambda}\in\mathbb{R}_{\geq 0}^m\). Any arriving agent \(i\) faces the same price vector \(\pmb{\lambda}\) for the resources, and makes a utility-maximizing decision \(\theta_i\). ⁵

In our main results, we allow adversarial tie breaking, so that when the utility of two decisions is the same for an arriving agent, the agent can choose an arbitrary decision. We may use consistent tie breaking to derive some intermediate results.

1.1.3 Learning from Samples / Queries↩︎

We study the setting where the type distribution \(\mathcal{D}_i\) of each buyer \(i\) is not fully available to the seller, but is available via two types of query access. The first type of access model is the classic sample access model, where the learner is allowed to query each type distribution \(\mathcal{D}_i\) of agent \(i\), and can obtain a fresh type sample \(\gamma_i\sim\mathcal{D}_i\) in each query. The second type of access model is the pricing query access model (and we may slightly abuse the notation and call it the query access model when the context is clear), where the learner is allowed to query each type distribution \(\mathcal{D}_i\) with a price vector \(\pmb{\lambda}\). Then a type sample \(\gamma_i\sim\mathcal{D}_i\) is drawn from the type distribution of an agent, but the learner is only able to observe any utility-maximizing decision of the agent with type \(\gamma_i\). In other words, the output of the query comes from a demand oracle \(\mathcal{O}\) that, given any \(\pmb{\lambda}\) and \(\gamma_i\), \(\mathcal{O}\) returns an arbitrary decision \(\theta_i\in \Theta_i\) in the utility maximizing set \(\mathop{\arg\max}_{\theta\in\Theta_i} \left(v_i(\theta)-\langle \boldsymbol{a}_i(\theta),\pmb{\lambda}_i\rangle\right)\).⁶ The goal of the learner is to learn a pricing strategy, such that for any arrival order of the agent, the expected welfare is at least \((1-\epsilon)\mathsf{Opt}\) under the budget constraint \(\mathbf{B}\).

1.2 Main Results↩︎

In this paper, we give an affirmative answer to the question we asked in two slightly different settings. Our first result shows that when each agent has a generic valuation distribution ⁷, it is possible to learn a static item pricing through polynomial number of samples. In particular, it is close to the dual prices computed from the configuration LP of the optimization problem.

We remark that our sample complexity depends on the maximum size \(|\Theta|_{\max}\) of each request’s action set. While this dependence may prevent a direct application of our result to settings with continuous action sets, a logarithmic dependence on \(|\Theta|_{\max}\) still suffices to yield a polynomial sample complexity bound for a broad class of online resource allocation problems. In particular, our result applies even when the action set is exponentially large, such as in online combinatorial auctions, where \(|\Theta|_{\max} \le 2^m\). We present our proofs of the sample complexity bound in 2.

Our second result shows that if we only have query access to the value distributions, we can still obtain an anonymous pricing mechanism through a polynomial number of queries, even for request distributions beyond generic.

The detailed algorithm underlying our query complexity result is presented in 3. The anonymous pricing mechanism we construct takes the following form. We first learn, from samples, a set of \(T\) price vectors \(\Lambda = \{\pmb{\lambda}^{(1)}, \pmb{\lambda}^{(2)}, \ldots, \pmb{\lambda}^{(T)}\} \subseteq \mathbb{R}^m\). Upon the arrival of each agent, the seller selects a price vector from \(\Lambda\) uniformly at random and posts it to the agent.

This mechanism is anonymous and non-adaptive: it does not depend on the identity of the arriving agent or on the current state of the remaining resources. Moreover, despite having access only to limited query feedback, our algorithm does not require solving the computationally expensive configuration LP (1 ). To the best of our knowledge, this is the first algorithm for online resource allocation with non-identical requests that avoids solving the configuration LP altogether.

1.3 Technical Overview↩︎

Ideas for sample complexity. Our proof of a polynomial sample complexity consists of the following three ingredients:

• Converting the learning objective. Instead of aiming to learn a price vector that approximates the dual prices, i.e., the optimal solution to 2 , we focus on learning a price vector whose expected consumption is close to, but does not exceed, the budget constraint \(\mathbf{B}\). By applying weak duality, we show that ensuring the expected consumption is close to \(\mathbf{B}\) is sufficient to guarantee an expected welfare close to \(\mathsf{Opt}\).

• Uniform convergence via pseudo-dimension. We bound the sample complexity by determining the number of samples required to construct an empirical distribution such that the expected consumption under the empirical distribution is close to that under the true distribution. To this end, we follow a similar approach of [4] and establish a uniform convergence result for the expected consumption over all price vectors by bounding the pseudo-dimension of the entire allocation process.

• Improving sample complexity via truncating the consumption. Observe that the expected consumption takes values in the range \([0, n]\). A uniform convergence guarantee over this range would lead to a sample complexity that depends polynomially on \(n\). However, our interest is restricted to price vectors whose expected consumption is close to \(B_j\), which may be much smaller than \(n\). To improve the sample complexity, we truncate the consumption at \(O(B_j)\) and show that establishing uniform convergence for the truncated consumption suffices. This refinement yields an improved sample complexity bound that no longer depends polynomially on \(n\).

Ideas for pricing query complexity. The main algorithm for pricing query feedback is a learning algorithm that runs for \(T\) rounds. In each round \(t\), we present an identical price vector \(\pmb{\lambda}^{(t)}\) to \(n\) requests independently drawn from distributions \(\mathcal{D}_1, \ldots, \mathcal{D}_n\). Based on the query feedback, i.e., the consumption of each request, we update the price vector to \(\pmb{\lambda}^{(t+1)}\) for round \(t+1\).

It remains to specify the rule for updating the price vector. Our main intuition is to view the above learning algorithm as a large online resource allocation problem with identical distributions: there are \(T\) identical large requests, \(m\) resources, and each resource \(j\) has a total budget of \(T \cdot B_j\). The \(t\)-th large request corresponds to the \(n\) small requests independently sampled in round \(t\), and hence all large requests are identically distributed.

To update prices for this online resource allocation problem with identical distributions, we apply the exponential pricing algorithm introduced in [1]. Exponential pricing is a dynamic pricing algorithm that aims to match the optimal expected consumption, with the key idea being to adjust prices exponentially according to the discrepancy between the current consumption and the optimal expected consumption. Since all large requests are identical, the optimal expected consumption for each request is \(\mathbf{B}\). Applying this optimal expected consumption, scaled down by a factor of \(1 - \epsilon\), yields our price update rule.

Since exponential pricing achieves a \(1 - O(\epsilon)\) competitive ratio when the budget is at least \(\widetilde{\Omega}(\epsilon^{-2})\) times the maximum consumption of a single request (see [1]), our learning algorithm achieves a total welfare of \((1 - \epsilon)\cdot T \cdot \mathsf{Opt}\) whenever \[T \cdot B_j \ge \widetilde{\Omega}(\epsilon^{-2}) \cdot n,\] noting that each large request consumes at most \(n\) units of any resource. This condition in particular implies that \(T \ge n\).

The final step of the proof is to convert the price vectors learned over the \(T\) rounds into an anonymous pricing mechanism. Specifically, we show that independently selecting a price vector uniformly at random from the set \(\{\pmb{\lambda}^{(1)}, \ldots, \pmb{\lambda}^{(T)}\}\) and presenting it to incoming requests still achieves a \(1 - O(\epsilon)\) competitive ratio. Establishing this result constitutes the main technical challenge we face: [1] establishes strong performance guarantees for the exponential pricing algorithm in a dynamic online resource allocation setting. However, in our setting, the learned price vector set \(\{\pmb{\lambda}^{(1)}, \ldots, \pmb{\lambda}^{(T)}\}\) is subsequently evaluated on a fresh batch of requests. This requires an additional guarantee showing that prices learned via exponential pricing continue to perform well when the online resource allocation instance is effectively re-run on new data.

We establish such a guarantee by modeling the exponential pricing process as a martingale. Using a martingale-based concentration bound together with careful analysis to bypass some correlation issues we introduced during the analysis, we show that the performance in the re-running phase and the learning phase both cannot deviate significantly from its expectation. As a result, the welfare achieved in the re-running phase is comparable to that attained during the learning phase.

1.4 Discussion on Static Pricing Assumptions↩︎

If we compare Theorem 1 and Theorem 2, we find that to get the static pricing result, we need a stronger access model (sample vs. query) and the assumption that the distribution is generic. Here, we elaborate on why both requirements are necessary.

1.4.1 Why Not Query Complexity Bound?↩︎

In Theorem 1, we obtain a polynomial sample complexity for agents with generic value distributions. With query access, such a finite bound is typically not achievable without additional assumptions. For example, consider a seller with \(B\) units of a single resource. There are \(\frac{3}{2}B\) agents arriving, each consuming 1 unit of the resource when allocated. \(\frac{1}{2}B\) agents have a deterministic value of 1, and \(B\) agents have a value drawn from a uniform distribution \(U[t,t+\delta]\), where \(t\) is an unknown constant. The static welfare-optimal price falls in the range \([t,t+\delta]\), as the optimal offline allocation has all agents with value \(1\) allocated, and half of the other agents with value around \(t\) allocated. However, when \(\delta\to0\), it is impossible to find \(t\) with a number of queries that does not depend on \(\delta\). We leave it as an open question to explore whether it is possible to obtain a polynomial pricing query complexity for static pricing via some definition of “degree of genericness”.

1.4.2 Why Do We Need Generic Distributions?↩︎

While we have designed an anonymous pricing mechanism with nice properties with pricing queries in Theorem 2, we may ask whether an even simpler static pricing mechanism is possible without the generic assumption. When value distributions are publicly known, setting item prices through the dual optimal solution of the configuration LP can give a \((1-\epsilon)\) approximation to the optimal welfare. However, even for this known-distribution setting, there is a subtle point that such a static pricing mechanism is actually not anonymous. How is this even possible?

In fact, to make dual pricing work, an important observation is that the pricing mechanism needs to have an accurate tie-breaking rule. That is, for any arriving agent that has two favorite actions with different allocations, the seller has the power to decide which allocation the agent selects. Such a tie-breaking can be discriminatory, making the dual pricing mechanism not truly anonymous. In fact, such an observation has been studied in combinatorial auctions. [5] points out that in a matching market (where all agents have fixed unit-demand valuations), while a static item pricing (which are usually called Walrasian prices) that clears the market with optimal welfare exists, it is critical that the seller has the tie-breaking power and breaks ties in a coordinated fashion. Suppose the buyers hold the tie-breaking power and can select any utility-maximizing bundle of items at arrival, there exist instances that no static pricing can obtain more than \(\frac{2}{3}\) of the optimal welfare in hindsight, and the result holds when each resource has a large supply. ⁸ To solve this problem, [5] proposes an adaptive item pricing mechanism, that adjusts the prices of each item based on the current remaining, and obtains the optimal welfare for the online matching market, and the result can be further generalized to buyers with gross-substitute valuations [6]. In a more complicated tollbooth setting, where each agent demands an interval on a line graph, [7] shows that while the static item pricing can achieve the optimal welfare when the seller has tie-breaking power, it can only obtain a tight \(\frac{2}{3}\) fraction of the optimal welfare when the buyers hold the tie-breaking power.

On the other hand, our mechanism for Theorem 2 has a pre-determined set of price vectors, and when each agent arrives, the seller randomly draws a price vector from the set, and neither needs to know the identity of the arriving buyer, nor needs to adjust the price based on the current inventory constraint. Each arriving agent can also select any utility-maximizing action. This means that our mechanism is truly anonymous.

1.5 Related Work↩︎

Online Resource Allocation through Samples For the online resource allocation model studied in our paper, [1] was the first paper to study almost optimal online resource allocation through samples for heterogeneous agents in the large-budget setting. There have been many papers studying online resource allocation with i.i.d. agents or non-identical agents arriving in random order, E.g., [2], [8]–[16]. The main ideas of this series of works are either to use the first \(\epsilon n\) arriving agents as samples to learn an empirical distribution, and then to use a mechanism constructed from the empirical distribution on the rest of the agents; or to run a no-regret learning algorithm on all of the agents and obtain an overall \((1-\epsilon)\) approximation.

Another line of research studies the online resource allocation problem with regret minimization objectives. [17] and [18] are the two prior works closest to our setting. Specifically, [17] studies the regret minimization version of the online resource allocation problem with a single resource and non-identical request distributions and designs a static pricing algorithm that requires only a single sample from each request distribution. However, it remains unclear whether their static pricing algorithm can be generalized beyond the single-resource setting. Meanwhile, [18] investigates the online resource allocation problem with multiple resources. Rather than discussing the sample complexity required to learn a high-quality empirical distribution, [18] focuses on how the Wasserstein distance between the learned empirical distribution and the true distribution impacts the regret. Additionally, they propose a dynamic pricing algorithm that is not directly comparable to our results, as their algorithm is non-anonymous.

Online Resource Allocation with Less LP Solving A distinct line of research focuses on reducing the computational burden of solving large-scale LPs in the online resource allocation problem. While early heuristics based on frequently re-solving the certainty-equivalent LP were shown to achieve small regret in different settings [19]–[21], the high computational cost of frequent re-optimization limits their applicability. To address this, [22] demonstrated that re-solving the LP only a constant number of times is sufficient to maintain a uniformly bounded revenue loss. More recently, literature has challenged the necessity of re-solving altogether. [23] and [24] established that simple primal-dual policies, which dynamically update dual variables based on resource consumption without ever re-solving the LP, can effectively achieve asymptotic optimality. This line of work highlights the effectiveness of low-complexity policies in i.i.d. settings, while our query complexity algorithm does not even solve the LP in a non-i.i.d. environment.

Sample Complexity of Multi-dimensional Mechanism Design Since [25] introduced sample complexity to the mechanism design literature, there has been much work on learning (approximately) optimal mechanisms. For multi-dimensional mechanism design, the proof of sample complexity follows two very different techniques. One line of papers [26]–[31] focus on showing that the empirical distribution that is close to the original distribution can be efficiently learned from samples, while the optimal objective of the mechanism design problem satisfies some kind of smoothness with respect to the input distributions. The other line of works [32]–[37] utilize the pseudo-dimension style analysis to prove uniform convergence bounds for specific mechanism hypotheses classes. The proof of our sample complexity result exactly follows the second line of work.

Query Complexity Recently, there has been an increasing attention to learning distributions or mechanisms through pricing / threshold queries [31], [38]–[44]. The closest work to our setting is [31], in which they prove a tight bound on learning the optimal item pricing algorithm for unit-demand buyers through pricing queries on single distributions. Our online resource allocation algorithm works on general preference that goes well beyond unit-demand agents. In addition, we use a demand oracle that takes in price vectors instead of querying individual distributions. This also solves an open question from [31] on getting reasonable pricing query complexity results with the more natural query access in a multi-dimensional setting.

Anonymous Pricing for Multi-Dimensional Online Resource Allocation The anonymous pricing mechanism we have is a special case of Sequential Posted Pricing mechanisms [45], where the seller has a posted pricing mechanism for each arriving agents. In the multi-dimensional setting, there has been much literature focusing on combinatorial prophet inequality, where the distribution of the arriving agents are known, but the arriving order is unknown. In the single-unit supply setting, it is known that static item pricing achieves a \(1/2\)-approximation to the optimal welfare in hindsight for agents with XOS valuations [46], [47], and the result is obtainable through samples [4]. For subadditive agents, static item pricing can achieve an \(\Omega(1/\log\log m)\) approximation [48], and whether it can achieve constant approximation is still open. Beyond subadditive agents, [49] shows that static bundle pricing gives an \(\Omega(\log \log L/\log L)\) approximation for allocating intervals of length at most \(L\). In the multi-unit setting, there are much fewer works in the literature. [3] shows that static item pricing gives \((1-\epsilon)\) approximation for online interval allocation in the large budget setting. The closest work to our setting is [50], which gives a non-adaptive anonymous item pricing for XOS-valued agents in a large budget setting. As in our setting they allow the anonymous pricing to be not static, but they permit the prices to be updated when the remaining budget of each resource changes.

2 Sample Complexity for Learning Dual Prices↩︎

In this section, we prove our sample complexity result. To be specific, we show the following:

2.1 Proving 3↩︎

Notations. To prove 3, we rely on the following notations:

• \(\theta^*(\pmb{\lambda};\gamma_i)\): It represents the best action for request \(\gamma_i\) that maximizes the utility, with \(\pmb{\lambda}\) being the price vector for each resource, i.e., \[\theta^*(\pmb{\lambda};\gamma_i) ~\in~ \arg \max_{\theta \in \Theta_i} \left(v_i(\theta) - \langle \boldsymbol{a}_i(\theta), \pmb{\lambda}\rangle \right).\] When there are multiple actions with the same utility, function \(\theta^*(\pmb{\lambda};\gamma_i)\) represents the (possibly random) tie-breaking rule of request \(i\), i.e., \(\theta^*(\pmb{\lambda};\gamma_i)\) can be viewed as a sample drawn from a fixed distribution over those actions that maximizes the utility. We will specify the tie-breaking rule we use when using notation \(\theta^*(\pmb{\lambda};\gamma_i)\).

• \(\mathsf{Wel}(\pmb{\lambda})\) and \(\mathsf{Wel}_i(\pmb{\lambda})\): \(\mathsf{Wel}_i(\pmb{\lambda})\) represents the expected welfare achieved by satisfying request \(\gamma_i\), with \(\pmb{\lambda}\) being the price vector for each resource, i.e., \[\mathsf{Wel}_i(\pmb{\lambda}) ~:=~ \mathbb{E}_{\gamma_i}\left[v_i\big(\theta^*(\pmb{\lambda}; \gamma_i)\big) \right].\] \(\mathsf{Wel}(\pmb{\lambda})\) represents the summation of \(\mathsf{Wel}_i(\pmb{\lambda})\), i.e., \(\mathsf{Wel}(\pmb{\lambda}) = \sum_{i \in [n]} \mathsf{Wel}_i(\pmb{\lambda})\).

• \(\boldsymbol{c}_i(\pmb{\lambda})\) and \(\boldsymbol{c}(\pmb{\lambda})\): \(\boldsymbol{c}_i(\pmb{\lambda})\) represents the expected consumption vector of request \(\gamma_i\), with \(\pmb{\lambda}\) being the price vector for each resource, i.e., \[\boldsymbol{c}_i(\pmb{\lambda}) = (c_{i, 1} (\pmb{\lambda}), \cdots, c_{i, m}(\pmb{\lambda})) ~:=~ \mathbb{E}_{\gamma_i}\left[\boldsymbol{a}_i\big(\theta^*(\pmb{\lambda}; \gamma_i)\big) \right].\] We further define \[\boldsymbol{c}(\pmb{\lambda}) = (c_{1} (\pmb{\lambda}), \cdots, c_{m}(\pmb{\lambda})) ~:=~ \sum_{i \in [n]} \boldsymbol{c}_i(\pmb{\lambda})\] to be the expected total consumption vector for all requests.

Pre-processing. Given an online resource allocation instance, we first add \(m\) groups of dummy requests into the instance. For \(j \in [m]\), the \(j\)-th group contains \(B_j + 1\) dummy requests, such that each request is a unit-demand request which is only interested in taking one unit of resource \(j\), with a valuation independently drawn from \([\delta, 2\delta]\) uniformly at random, where \(\delta\to 0\) is an arbitrarily small parameter that does not change the objective of 1 . The main purpose for us to introduce these groups of dummy requests is to guarantee that each resource has enough demand, and therefore the optimal dual prices with respect to either the original distributions or the empirical distributions must be non-zero. Throughout this chapter, we assume that all online resource allocation instances under consideration have undergone this pre-processing step. Consequently, the dual prices corresponding to the optimal solution of 2 with respect to both the original distributions and the empirical distributions are guaranteed to be strictly positive.

Near-optimal allocation implies near-optimal value. To show the learnability of the dual prices, a standard approach is to directly analyze the convergence of the optimal dual price vector itself. However, because static pricing can be highly sensitive in an online resource allocation setting, convergence of the dual price vector alone does not guarantee good performance.

For example, consider a \(B\)-unit Single-Item Prophet Inequality problem, which is a special case of an online resource allocation problem with a single resource and \(n\) unit-demand requests. Assume that each request’s value is independently drawn uniformly at random from an interval \([\ell, r]\), where \(r\) and \(\ell\) are arbitrarily close, i.e., \(r - \ell \to 0\). Let \(\lambda^* \in [\ell, r]\) denote the optimal dual price, and let \(\widehat{\lambda}\) be an estimate of it. When \(r - \ell \to 0\), any convergence bound of the form \(|\lambda^* - \widehat{\lambda}| \le \varepsilon\) for a fixed \(\varepsilon\) fails to provide a performance guarantee for posting the price \(\widehat{\lambda}\). Indeed, it is possible that \(\lambda^* - \varepsilon < \ell\), resulting in a price that may over-allocate the resource, or that \(\lambda^* + \varepsilon > r\), resulting in a price that allocates nothing.

The above observation motivates us to directly consider the convergence of the expected consumption, i.e., we wish to find a price vector \(\widehat \pmb{\lambda}\) via samples, such that the expected consumption is close but no more than the budget constraint \(\mathbf{B}\), i.e., we hope \[\begin{align} \boldsymbol{c}(\widehat \pmb{\lambda}) ~\in~ \left[(1 - O(\epsilon)) \cdot \mathbf{B}, \mathbf{B}\right]. \end{align}\]

We show the feasibility of the above idea by presenting the following 4, which suggests that if the expected consumption of \(\widehat \pmb{\lambda}\) is indeed close to \(\mathbf{B}\), the resulting welfare is also sufficiently large.

Uniform convergence for truncated consumption. Now, we show how to learn a price vector with expected consumption close to \(\mathbf{B}\) via samples. Our core idea is a uniform convergence argument via Pseudo Dimension, similar to the proofs in [4] on proving sample complexity for combinatorial prophet inequalities. To be specific, we show the following:

We remark that an easier way to derive a polynomial sample complexity bound is to directly argue the uniform convergence for \(\boldsymbol{c}(\pmb{\lambda})\) and \(\hat{\boldsymbol{c}}(\pmb{\lambda})\). However, since \(c_j(\pmb{\lambda})\) and \(\hat{c}_j(\pmb{\lambda})\), representing the expected consumption of resource \(j\) with respect to the original distribution and the empirical distribution respectively, both lie in the range of \([0, n]\), to prove uniform convergence using Pseudo dimension, we must normalize both \(c_j(\pmb{\lambda})\) and \(\hat{c}_j(\pmb{\lambda})\) to the interval \([0, 1]\). This implies a super high accuracy requirement for \(\hat{c}_j\) in the form of \(|\hat{c}_j (\pmb{\lambda}) - c_j(\pmb{\lambda})| \leq O(1)\), resulting in a sample complexity with a polynomial dependency on \(n\).

However, for proving 3, a much looser accuracy in the form of \(|\hat{c}_j (\pmb{\lambda}) - c_j(\pmb{\lambda})| \leq O(\epsilon) \cdot B_j\) is already sufficient. To bridge this gap, we introduce the truncated expected consumption functions \(\boldsymbol{c}'(\pmb{\lambda})\) and \(\hat{\boldsymbol{c}}'(\pmb{\lambda})\). Since both \(\boldsymbol{c}'(\pmb{\lambda})\) and \(\hat{\boldsymbol{c}}'(\pmb{\lambda})\) are bounded in \([0, 2B_j]\), 5 gives an accuracy bound in the form of \(|\hat{c}'_j (\pmb{\lambda}) - c'_j(\pmb{\lambda})| \leq O(\epsilon) \cdot B_j\) with a sample complexity that does not depend polynomially on \(n\). We will further show in the proof of 3 that the accuracy bound for the truncated consumption can be converted to an accuracy bound for the original consumption function, and therefore a uniform convergence for \(\boldsymbol{c}'(\pmb{\lambda})\) and \(\hat{\boldsymbol{c}}'(\pmb{\lambda})\) is sufficient.

Proving 3. We defer the proofs of 4 and 5 to 5, and first prove 3 via 4 and 5.

3 Pricing Query Complexity for Online Resource Allocation↩︎

In this section, we prove our main pricing query complexity result. To be specific, we show the following:

We remark that 6 requires an estimate \(\widehat{\mathsf{Opt}}\) of the optimal value \(\mathsf{Opt}\). Such an estimate is necessary because it provides the scale of the problem: without any information about the scale, it is impossible to determine, using only a polynomial number of queries, whether the values in the underlying online resource allocation instance are on the order of \(10^{-100}\) or \(10^{100}\). To give a more concrete intuition, consider a simple online resource allocation instance with single resource having \(B\) supplies. There are \(n = 1.5 B\) requests, where each request requires one unit of resource. \(B\) requests are with value \(w = 10^k\) for some arbitrary \(k \in \mathbb{R}\), while the remaining \(0.5 B\) requests are with value \(10w\). The arrival order of requests are random. Then, as the optimal algorithm needs to save \(0.5 B\) units of the resource for high-value requests, it’s necessary for the algorithm to determine the value of \(w\) (up to a constant factor). However, as \(w = 10^k\) while \(k\) can be some arbitrary real number, it’s impossible for the algorithm to determine \(w\) using \(\mathsf{poly}(B)\) pricing queries with only comparison feedback. Therefore, an estimate of \(\mathsf{Opt}\) is necessary.

Importantly, only a coarse approximation of \(\mathsf{Opt}\) is needed. If the estimate \(\widehat{\mathsf{Opt}}\) differs from \(\mathsf{Opt}\) by a multiplicative factor of \(\beta\), this inaccuracy results in only an additional \(\log \beta\) factor in our large-budget requirement.

We show that 1 is the desired algorithm for 6. As discussed in 1.3, the learning phase of 1 is a \(T\)-rounds learning algorithm that can be viewed as a large online resource allocation problem. We use the exponential pricing algorithm to update prices between rounds. In the auction phase, we collect all the price vectors appeared in the learning phase as set \(\Lambda\), and present to each newly arriving request a price vector independently drawn from \(\Lambda\).

3.1 Notations.↩︎

To prove 6, we will reuse some notations used in the proof of 3, which are briefly restated below for convenience:

• \(\theta^*(\pmb{\lambda};\gamma_i)\): It represents the best action for request \(\gamma_i\) that maximizes the utility, with \(\pmb{\lambda}\) being the price vector for each resource, i.e., \[\theta^*(\pmb{\lambda};\gamma_i) ~\in~ \arg \max_{\theta \in \Theta_i} \left(v_i(\theta) - \langle \boldsymbol{a}_i(\theta), \pmb{\lambda}\rangle \right).\] When there are multiple actions with the same utility, we assume in this section that each request applies an arbitrary (and possibly random) but consistent tie-breaking rule.

• \(\mathsf{Wel}(\pmb{\lambda})\) and \(\mathsf{Wel}_i(\pmb{\lambda})\): \(\mathsf{Wel}(\pmb{\lambda})\) \(\mathsf{Wel}_i(\pmb{\lambda})\) represents the expected welfare achieved by satisfying all requests and request \(\gamma_i\) respectively, with \(\pmb{\lambda}\) being the price vector for each resource, i.e., \[\mathsf{Wel}_i(\pmb{\lambda}) ~:=~ \mathbb{E}_{\gamma_i}\left[v_i\big(\theta^*(\pmb{\lambda}; \gamma_i)\big) \right], \quad \text{and} \quad \mathsf{Wel}(\pmb{\lambda}) ~:=~ \sum_{i \in [n]} \mathsf{Wel}_i(\pmb{\lambda}).\]

• \(\boldsymbol{c}_i(\pmb{\lambda})\) and \(\boldsymbol{c}(\pmb{\lambda})\): \(\boldsymbol{c}_i(\pmb{\lambda})\) and \(\boldsymbol{c}(\pmb{\lambda})\) represents the expected consumption vector of all requests/request \(\gamma_i\) respectively, with \(\pmb{\lambda}\) being the price vector for each resource, i.e., \[\boldsymbol{c}_i(\pmb{\lambda}) ~:=~ \mathbb{E}_{\gamma_i}\left[\boldsymbol{a}_i\big(\theta^*(\pmb{\lambda}; \gamma_i)\big)\right], \quad \text{and} \quad \boldsymbol{c}(\pmb{\lambda}) ~:=~ \sum_{i \in [n]} \boldsymbol{c}_i(\pmb{\lambda}).\]

We also introduce the following new notations:

• \(\{x^*_{i, \gamma_i, \theta} \}\). We use \(x^*_{i, \gamma_i, \theta}\) to represent the optimal solution of 1 \((\boldsymbol{\mathcal{D}}; \mathbf{B})\). We define \(\{x^*_{i, \gamma_i, \theta} \}\) for analytical purposes only, without the need to actually solve for the values.

• \(\mathsf{Alg}(\Lambda)\): It represents the expected welfare gained in the auction phase of 1, assuming the set of price vector is \(\Lambda\). To prove 6, it’s equivalent to show that \[\mathbb{E}_{\Lambda}[\mathsf{Alg}(\Lambda)] ~\geq~ (1 - O(\epsilon)) \cdot \mathsf{Opt}.\] We remark that the exact value of \(\mathsf{Alg}(\Lambda)\) may also depend on the arrival order of requests in the auction phase. We will later show that the arrival order does not affect our analysis of lower bounding \(\mathsf{Alg}(\Lambda)\), and for simplicity, we assume \(\mathsf{Alg}(\Lambda)\) represents the expected reward achieved in the worst possible arrival order.

• \(\mathsf{Alg}^{(T)}_i(\Lambda)\) and \(\mathsf{Alg}^{(T)}(\Lambda)\): We define \[\mathsf{Alg}^{(T)}_i(\Lambda) ~:=~ \sum_{t \in [T]} \mathsf{Wel}_i(\pmb{\lambda}^{(t)}) \qquad \text{and} \qquad \mathsf{Alg}^{(T)}(\Lambda) ~:=~ \sum_{i \in [n]} \mathsf{Alg}^{(T)}_i(\Lambda)\] to be the sum of expected welfare gained via playing price vectors in \(\Lambda\) from request \(i\) and all requests, respectively.

• \(P_\mathtt{BE}(\Lambda)\): We define \(P_\mathtt{BE}(\Lambda)\), where \(\mathtt{BE}\) is short for “budget exhaustion”, to be the probability that the auction phase of 1 exhaust the budget when the set of price vectors is \(\Lambda\), i.e., assuming we don’t execute the “Terminate” step in Line 14 of 1 and let the algorithm go through all requests, \(P_\mathtt{BE}(\Lambda)\) represents the probability that there exists \(j \in [m]\) such that the auction phase allocated at least \(B_j\) unit of resource \(j\).

3.2 Proof of 6↩︎

Now, we provide a formal proof of 6. Recall that we aim at showing \[\mathbb{E}_{\Lambda}[\mathsf{Alg}(\Lambda)] ~\geq~ (1 - O(\epsilon)) \cdot \mathsf{Opt}.\] We first lower-bound \(\mathsf{Alg}(\Lambda)\) as \[\begin{align} \label{eq:alg-lower} \mathsf{Alg}(\Lambda) ~=~ \sum_{i \in [n]}\mathbf{Pr}\left[\text{algorithm reaches request }i\right] \cdot \frac{1}{T} \cdot \mathsf{Alg}^{(T)}_i(\Lambda) ~\geq~ \frac{1 - P_\mathtt{BE}(\Lambda)}{T} \cdot \mathsf{Alg}^{(T)}(\Lambda), \end{align}\tag{9}\] where the inequality follows from the fact that the probability that the auction phase reaches request \(i\) is at least the probability that the auction phase never exhaust the budget, which is exactly \(1 - P_\mathtt{BE}(\Lambda)\). Therefore, to prove 6, it’s equivalent to show that \[\begin{align} \mathbb{E}_{\Lambda} \left[(1 - P_\mathtt{BE}(\Lambda)) \cdot \mathsf{Alg}^{(T)}(\Lambda) \right] ~\geq~ (1 - O(\epsilon)) \cdot T \cdot \mathsf{Opt}. \end{align}\]

Bounding \(\mathsf{Alg}^{(T)}(\Lambda)\). Fix \(\Lambda\). We first give a lower bound for \(\mathsf{Wel}_i({\pmb{\lambda}}^{(t)})\). To achieve this, we define the following randomized action \(\widehat \theta_i\), which only depends on the type of request \(i\): \[\begin{align} \widehat \theta_i ~:=~ \begin{cases} \phi & \text{with probability } \epsilon \\ \theta \in \Theta_{i} & \text{with probability } x^*_{i,\gamma_i, \theta} \cdot (1 - \epsilon), \text{ assuming } \gamma_i \text{ is the true realization} \end{cases}~, \end{align}\] i.e., we ask \(\widehat \theta_i\) to take the null action with probability \(\epsilon\), and follow the optimal solution of 1 otherwise. To bound \(\mathsf{Wel}_i({\pmb{\lambda}}^{(t)})\), the main idea is that the utility achieved by playing action \(\widehat \theta_i\) can’t be more than playing \(\theta^*({\pmb{\lambda}}^{(t)}, \gamma_i)\). Then, we have \[\begin{align} \mathsf{Wel}_i({\pmb{\lambda}}^{(t)}) ~&=~ \mathbb{E}_{\gamma_i}\left[v_i\big(\theta^*({\pmb{\lambda}}^{(t)}; \gamma_i) \big) - \left \langle \boldsymbol{a}_i\big(\theta^*({\pmb{\lambda}}^{(t)}; \gamma_i)\big), {\pmb{\lambda}}^{(t)}\right \rangle \right] + \mathbb{E}_{\gamma_i}\left[ \left \langle \boldsymbol{a}_i\big(\theta^*({\pmb{\lambda}}^{(t)}; \gamma_i)\big), {\pmb{\lambda}}^{(t)}\right\rangle \right] \notag \\ ~&\geq~ \mathbb{E}_{\gamma_i}\left[v_i\big(\widehat \theta_i \big) - \left \langle \boldsymbol{a}_i\big(\widehat \theta_i\big), {\pmb{\lambda}}^{(t)}\right \rangle \right] + \mathbb{E}_{\gamma_i}\left[ \left \langle \boldsymbol{a}_i\big(\theta^*({\pmb{\lambda}}^{(t)}; \gamma_i)\big), {\pmb{\lambda}}^{(t)}\right\rangle \right] \notag \\ ~&=~ \mathbb{E}_{\gamma_i}\left[v_i\big(\widehat \theta_i \big) \right] - \mathbb{E}_{\gamma_i} \left[ \left \langle \boldsymbol{a}_i\big(\widehat \theta_i\big), {\pmb{\lambda}}^{(t)}\right \rangle \right] + \mathbb{E}_{\gamma_i}\left[ \left \langle \boldsymbol{a}_i\big(\theta^*({\pmb{\lambda}}^{(t)}; \gamma_i)\big), {\pmb{\lambda}}^{(t)}\right\rangle \right].\label{eq:wel-lower-1} \end{align}\tag{10}\]

To further simplify 10 , for the first term in 10 , we have \[\mathbb{E}_{\gamma_i}\left[v_i\big(\widehat \theta_i \big) \right] ~=~ (1 - \epsilon) \cdot \mathbb{E}_{\gamma_i} \left[\sum_{\theta \in \Theta_i} x^*_{i, \gamma_i, \theta} \cdot v_i(\theta)\right].\]

For the second term in 10 , we have \[\begin{align} \mathbb{E}_{\gamma_i} \left[ \left \langle \boldsymbol{a}_i\big(\widehat \theta_i\big), {\pmb{\lambda}}^{(t)}\right \rangle \right] ~&=~ \left \langle \mathbb{E}_{\gamma_i} \left[ \sum_{\theta \in \Theta_{i}}(1 - \epsilon) \cdot x^*_{i, \gamma_i, \theta} \cdot \boldsymbol{a}_{i} (\theta) \right], {\pmb{\lambda}}^{(t)}\right \rangle \\ ~&=~ \left \langle (1 - \epsilon) \cdot \mathbb{E}_{\gamma_i} \left[ \sum_{\theta \in \Theta_{i}} x^*_{i, \gamma_i, \theta} \cdot \boldsymbol{a}_{i} (\theta) \right], {\pmb{\lambda}}^{(t)}\right \rangle. \end{align}\]

For the third term in 10 , we have \[\mathbb{E}_{\gamma_i}\left[ \left \langle \boldsymbol{a}_i\big(\theta^*({\pmb{\lambda}}^{(t)}; \gamma_i)\big), {\pmb{\lambda}}^{(t)}\right\rangle \right] ~=~ \left \langle \mathbb{E}_{\gamma_i}\left[ \boldsymbol{a}_i\big(\theta^*({\pmb{\lambda}}^{(t)}; \gamma_i)\big) \right], {\pmb{\lambda}}^{(t)}\right\rangle ~=~ \left \langle \boldsymbol{c}_i({\pmb{\lambda}}^{(t)}), {\pmb{\lambda}}^{(t)}\right\rangle.\] Applying the above three equalities to 10 , we have

\[\begin{align} \mathsf{Wel}_i({\pmb{\lambda}}^{(t)}) ~\geq~ (1 - \epsilon) \cdot \mathbb{E}_{\gamma_i} \left[ \sum_{\theta \in \Theta_{i}} x^*_{i, \gamma_i, \theta} \cdot v_{i}(\theta) \right] + \left \langle \boldsymbol{c}_i({\pmb{\lambda}}^{(t)}) - (1 - \epsilon) \cdot \mathbb{E}_{\gamma_i} \left[ \sum_{\theta \in \Theta_{i}} x^*_{i, \gamma_i, \theta} \cdot \boldsymbol{a}_{i} (\theta) \right], {\pmb{\lambda}}^{(t)}\right\rangle. \end{align}\]

Now summing the above inequality over \(i \in [n]\) and \(t \in [T]\), we have

\[\begin{align} \mathsf{Alg}^{(T)}(\Lambda) ~=~& \sum_{t \in [T]} \sum_{i \in [n]} \mathsf{Wel}_i({\pmb{\lambda}}^{(t)}) \notag \\ ~\geq~& (1 - \epsilon) \cdot T \cdot \sum_{i \in [n]} \mathbb{E}_{\gamma_i} \left[ \sum_{\theta \in \Theta_{i}} x^*_{i, \gamma_i, \theta} \cdot v_{i}(\theta) \right] \notag \\ &+ \sum_{t \in [T]} \left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) - (1 - \epsilon) \cdot \sum_{i \in [n]} \mathbb{E}_{\gamma_i} \left[ \sum_{\theta \in \Theta_{i}} x^*_{i, \gamma_i, \theta} \cdot \boldsymbol{a}_{i} (\theta) \right], {\pmb{\lambda}}^{(t)}\right\rangle \notag \\ ~\geq~& (1 - \epsilon) \cdot T \cdot \mathsf{Opt}+ \sum_{t \in [T]} \left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) - (1 - \epsilon) \cdot \mathbf{B}, {\pmb{\lambda}}^{(t)}\right\rangle \notag \\ ~=~& (1 - \epsilon) \cdot T \cdot \mathsf{Opt}\tag{11}\\ &+ \sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}- (1 - \epsilon) \cdot \mathbf{B}, {\pmb{\lambda}}^{(t)}\right\rangle \tag{12}\\ &+ \sum_{t \in [T]} \left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) - \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle. \tag{13} \end{align}\]

Recall that our goal is to show \[\begin{align} \mathbb{E}_{\Lambda} \left[(1 - P_\mathtt{BE}(\Lambda)) \cdot \mathsf{Alg}^{(T)}(\Lambda) \right] ~\geq~ (1 - O(\epsilon)) \cdot T \cdot \mathsf{Opt}. \end{align}\] Then, it’s sufficient to separately lower bound the expectation of \((1 - P_\mathtt{BE}(\Lambda)) \cdot \eqref{eq:first}\), \((1 - P_\mathtt{BE}(\Lambda)) \cdot \eqref{eq:second}\), and \((1 - P_\mathtt{BE}(\Lambda)) \cdot \eqref{eq:third}\).

Bounding \(\mathbb{E}_{\Lambda}[(1 - P_\mathtt{BE}(\Lambda)) \cdot \eqref{eq:first}]\). This is the relatively easier case. We have \[\begin{align} \mathbb{E}_{\Lambda} \left[(1 - P_\mathtt{BE}(\Lambda)) \cdot (1 - \epsilon) \cdot T \cdot \mathsf{Opt}\right] ~\geq~ (1 - \epsilon) \cdot T \cdot \mathsf{Opt}- T \cdot \mathsf{Opt}\cdot \mathbb{E}_{\Lambda} \left[P_\mathtt{BE}(\Lambda)\right]. \label{eq:first-1} \end{align}\tag{14}\]

It remains to bound \(\mathbb{E}_{\Lambda} \left[P_\mathtt{BE}(\Lambda)\right]\). We use the following [lma:pbesmall] to bound \(\mathbb{E}_{\Lambda} \left[P_\mathtt{BE}(\Lambda)\right]\):

The proof of [lma:pbesmall] requires arguing the concentration of a martingale process. We defer the proof of [lma:pbesmall] to Section 6.1. Then, applying [lma:pbesmall] to 14 gives \[\begin{align} \mathbb{E}_{\Lambda} \left[(1 - P_\mathtt{BE}(\Lambda)) \cdot (1 - \epsilon) \cdot T \cdot \mathsf{Opt}\right] ~\geq~ (1 - 4 \epsilon) \cdot T \cdot \mathsf{Opt}. \label{eq:first-final} \end{align}\tag{15}\]

Bounding \(\mathbb{E}_{\Lambda}[(1 - P_\mathtt{BE}(\Lambda)) \cdot \eqref{eq:second}]\). Before taking the expectation for \((1 - P_\mathtt{BE}(\Lambda)) \cdot \eqref{eq:second}\), we further apply the idea of “no-regret w.r.t. zero vector” from [1] to simplify 12 . To be specific, we rely on the following lemma:

For every \(j \in [m]\), we apply 7 with \(r_{t, j} = \frac{1}{n} \cdot ({d}^{(t)}_j - (1 - \epsilon) \cdot B_j)\) and \(\delta = \epsilon\), where the required condition \(r_{t,j} \in [-1, 1]\) follows from the fact that it’s impossible to consume more than \(n\) unit of resource \(j\) in one round, and \(B_j \leq n\). Then, 7 is applicable by noting that \(\lambda_{t,j} = \lambda^{\mathtt{INIT}}\cdot \exp \left(\epsilon \cdot \sum_{\ell < t} \frac{1}{n} \cdot ({d}^{(t)}_j - (1 - \epsilon) \cdot B_j)\right)\), and the inequality in 7 gives \[\sum_{t \in [T]} \lambda^{(t)}_j \cdot ({d}^{(t)}_j - (1 - \epsilon) \cdot B_j) ~\geq~ -\frac{2n \lambda^{\mathtt{INIT}}}{\epsilon} - 4\epsilon \cdot \sum_{t \in [T]} \lambda_{t, j} \cdot ({d}^{(t)}_j - (1 - \epsilon) \cdot B_j)^+.\]

Summing the above inequality for all \(j \in [m]\), we have \[\begin{align} \sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}- (1 - \epsilon) \cdot \mathbf{B}, {\pmb{\lambda}}^{(t)}\right\rangle ~\geq~ -\frac{2nm \lambda^{\mathtt{INIT}}}{\epsilon} - 4\epsilon \cdot \sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle, \label{eq:furtheruse} \end{align}\tag{16}\] where we also use the fact that \(({d}^{(t)}_j - (1 - \epsilon) \cdot B_j)^+ \leq {d}^{(t)}_j\) to simplify the right hand side. Now we multiply \(1 - P_\mathtt{BE}(\Lambda)\) to both sides of 16 , which gives \[\begin{align} &(1 - P_\mathtt{BE}(\Lambda)) \cdot \sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}- (1 - \epsilon) \cdot \mathbf{B}, {\pmb{\lambda}}^{(t)}\right\rangle \\ ~\geq~& - (1 - P_\mathtt{BE}(\Lambda)) \cdot \left(\frac{2nm \lambda^{\mathtt{INIT}}}{\epsilon} + 4\epsilon \cdot \sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle\right)\\ ~\geq~& - \frac{2nm \lambda^{\mathtt{INIT}}}{\epsilon} - 4\epsilon \cdot \sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle. \end{align}\] Taking the expectation over \(\Lambda\), we have \[\begin{align} \mathbb{E}_{\Lambda} \left[(1 - P_\mathtt{BE}(\Lambda)) \cdot \sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}- (1 - \epsilon) \cdot \mathbf{B}, {\pmb{\lambda}}^{(t)}\right\rangle\right] ~&\geq~ - \frac{2nm \lambda^{\mathtt{INIT}}}{\epsilon} - 4\epsilon \cdot \mathbb{E}_{\Lambda} \left[\sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle \right] \notag \\ ~&=~ - \frac{2nm \lambda^{\mathtt{INIT}}}{\epsilon} - 4\epsilon \cdot \mathbb{E}_{\Lambda} \left[\sum_{t \in [T]} \left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) , {\pmb{\lambda}}^{(t)}\right\rangle \right] \notag \\ ~&\geq~ - \frac{2nm \lambda^{\mathtt{INIT}}}{\epsilon} - 4\epsilon \cdot \mathbb{E}_{\Lambda} \left[\mathsf{Alg}^{(T)}(\Lambda) \right], \label{eq:second-1} \end{align}\tag{17}\] where the second line uses the fact that when \({\pmb{\lambda}}^{(t)}\) is fixed, the realization of \(\boldsymbol{d}^{(t)}\), which only depends on samples \(\{\gamma^{(t)}_i\}_{i \in [n]}\), is a random vector with \(\boldsymbol{c}({\pmb{\lambda}}^{(t)})\) being its expectation, and the last line uses the fact that \(\left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) , {\pmb{\lambda}}^{(t)}\right\rangle\) represents the expected total revenue collected by presenting price vector \({\pmb{\lambda}}^{(t)}\) to every request \(i \in [n]\), which is further upper-bounded by the total welfare collected by presenting \({\pmb{\lambda}}^{(t)}\) to every request \(i \in [n]\).

It remains to upper-bound \(\mathbb{E}_{\Lambda} \left[\mathsf{Alg}^{(T)}(\Lambda) \right]\). To achieve this, we rely on the following [lma:algtsmall]:

The proof of [lma:algtsmall] is deferred to Section 6.2. Applying [lma:algtsmall] to 17 gives \[\begin{align} \mathbb{E}_{\Lambda} \left[(1 - P_\mathtt{BE}(\Lambda)) \cdot \sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}- (1 - \epsilon) \cdot \mathbf{B}, {\pmb{\lambda}}^{(t)}\right\rangle\right] ~\geq~ - \frac{2nm \lambda^{\mathtt{INIT}}}{\epsilon} - 8\epsilon \cdot T \cdot \mathsf{Opt}. \label{eq:second-final} \end{align}\tag{18}\]

Bounding \(\mathbb{E}_{\Lambda}[(1 - P_\mathtt{BE}(\Lambda)) \cdot \eqref{eq:third}]\). This is the case where the correlation issue arises. Note that if we simply want to lower bound \(\mathbb{E}_{\Lambda}\left[\sum_{t \in [T]} \left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) - \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle\right]\), the expectation is exactly zero. The key observation is that after the first \(t - 1\) rounds in the learning phase are finished, the price vector \({\pmb{\lambda}}^{(t)}\) and the expected consumption \(\boldsymbol{c}({\pmb{\lambda}}^{(t)})\) are both fixed, and therefore the expectation is zero because \(\boldsymbol{d}^{(t)}\) is an unbiased estimator of \(\boldsymbol{c}({\pmb{\lambda}}^{(t)})\). When the factor \((1 - P_\mathtt{BE}(\Lambda))\) is multiplied, note that the price vectors \(\pmb{\lambda}^{(t+1)} , \cdots, \pmb{\lambda}^{(T)}\) all depend on the realization of \(\boldsymbol{d}^{(t)}\). Therefore, \(P_\mathtt{BE}(\Lambda)\) is correlated to the inner product \(\left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) - \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle\), making it impossible to simply treat the expectation \(\mathbb{E}_{\Lambda}\left[(1 - P_\mathtt{BE}(\Lambda)) \cdot \sum_{t \in [T]} \left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) - \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle\right]\) as \(0\).

To bypass this correlation issue, we crucially rely on the observation that after the price vector \({\pmb{\lambda}}^{(t)}\) is fixed, the realization \(\boldsymbol{d}^{(t)}\) in the learning phase should be close to the expectation \(\boldsymbol{c}({\pmb{\lambda}}^{(t)})\). This is simply because \(\boldsymbol{d}^{(t)}= \sum_{i \in [n]}\boldsymbol{d}^{(t)}_{i}\), while each \(\boldsymbol{d}^{(t)}_{i}\) is an unbiased estimator of \(\boldsymbol{c}_i({\pmb{\lambda}}^{(t)})\). To apply this idea, fix \(\Lambda\), we first lower-bound \((1 - P_\mathtt{BE}(\Lambda)) \cdot \eqref{eq:third}\) as \[\begin{align} (1 - P_\mathtt{BE}(\Lambda)) \cdot \sum_{t \in [T]} \left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) - \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle ~&=~ -(1 - P_\mathtt{BE}(\Lambda)) \cdot \sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}- \boldsymbol{c}({\pmb{\lambda}}^{(t)}) , {\pmb{\lambda}}^{(t)}\right\rangle \notag\\ ~&\geq~ -(1 - P_\mathtt{BE}(\Lambda)) \cdot \sum_{t \in [T]} \left \langle (\boldsymbol{d}^{(t)}- \boldsymbol{c}({\pmb{\lambda}}^{(t)}))^+ , {\pmb{\lambda}}^{(t)}\right\rangle \notag \\ ~&\geq~ -\sum_{t \in [T]} \left \langle (\boldsymbol{d}^{(t)}- \boldsymbol{c}({\pmb{\lambda}}^{(t)}))^+ , {\pmb{\lambda}}^{(t)}\right\rangle, \label{eq:third-1} \end{align}\tag{19}\] where notation \(r^+\) represents \(\max\{r, 0\}\) when \(r\) is a single value, and we extend this notation to a vector, where notation \(\boldsymbol{r}^+\) represents the vector obtained by taking the maximum of each coordinate and \(0\), i.e., \(\boldsymbol{r}^+ = (r_1, \cdots, r_m)^+ = (r_1^+, \cdots, r^+_m)\).

The benefit of introducing 19 is to use the non-negativity of \((\boldsymbol{d}^{(t)}-\boldsymbol{c}({\pmb{\lambda}}^{(t)}) )^+\) to eliminate the term \(P_\mathtt{BE}(\Lambda)\). Then, the following lemma suggests that the expectation of 19 is not too small:

The proof of [lma:plussmall] relies on the observation that \(\boldsymbol{d}^{(t)}\) should be close to its expectation \(\boldsymbol{c}({\pmb{\lambda}}^{(t)})\), because the realization of \(\boldsymbol{d}^{(t)}\) consists of the realization of \(n\) independent requests, and therefore \((\boldsymbol{d}^{(t)}- \boldsymbol{c}({\pmb{\lambda}}^{(t)}))^+\) can’t be too large. We defer the proof of [lma:plussmall] to Section 6.3.

Now we take the expectation over \(\Lambda\) for 19 and apply [lma:plussmall], which gives

\[\begin{align} \mathbb{E}_{\Lambda}\left[(1 - P_\mathtt{BE}(\Lambda)) \cdot\sum_{t \in [T]} \left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) - \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle \right] ~&\geq~ -\mathbb{E}_{\Lambda}\left[\sum_{t \in [T]} \left \langle \epsilon \cdot \boldsymbol{c}({\pmb{\lambda}}^{(t)}) + \epsilon \cdot \mathbf{B}, {\pmb{\lambda}}^{(t)}\right\rangle \right]. \label{eq:third-2} \end{align}\tag{20}\]

The expectation \(\mathbb{E}_{\Lambda}\left[\sum_{t \in [T]} \left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) , {\pmb{\lambda}}^{(t)}\right\rangle \right]\) can be further upper-bounded by \(\mathbb{E}_{\Lambda}[\mathsf{Alg}^{(T)}(\Lambda)]\), because \(\left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) , {\pmb{\lambda}}^{(t)}\right\rangle\) represents the expected revenue collected by presenting \({\pmb{\lambda}}^{(t)}\) to every request \(i \in [n]\), which is further upper-bounded by the welfare collected by presenting \({\pmb{\lambda}}^{(t)}\) to every request \(i \in [n]\). Therefore, it remains to upper-bound \(\mathbb{E}_{\Lambda}\left[\sum_{t \in [T]} \left \langle \mathbf{B}, {\pmb{\lambda}}^{(t)}\right\rangle \right]\). Note that rearranging 16 implies that for every fixed \(\Lambda\), we have \[\begin{align} \sum_{t \in [T]} \left \langle \mathbf{B}, {\pmb{\lambda}}^{(t)}\right\rangle ~&\leq~ \frac{1}{1- \epsilon} \cdot \sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle + \frac{2nm \lambda^{\mathtt{INIT}}}{\epsilon \cdot (1 - \epsilon)} + \frac{4\epsilon}{1 - \epsilon} \cdot \sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle \\ ~&\leq~ 6\sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle + \frac{4nm \lambda^{\mathtt{INIT}}}{\epsilon}, \end{align}\] where the second inequality holds when \(\epsilon \leq 0.5\). Then, taking expectation over \(\Lambda\) on both sides of the above inequality and applying to 20 gives \[\begin{align} \mathbb{E}_{\Lambda}\left[(1 - P_\mathtt{BE}(\Lambda)) \cdot\sum_{t \in [T]} \left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) - \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle \right] ~&\geq~ -7\epsilon \cdot \mathbb{E}_{\Lambda}[\mathsf{Alg}^{(T)}(\Lambda)] - 4nm\lambda^{\mathtt{INIT}}, \end{align}\] where we also use \[\mathbb{E}_{\Lambda}\left[\sum_{t \in [T]} \left \langle \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle \right] = \mathbb{E}_{\Lambda}\left[\sum_{t \in [T]} \left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) , {\pmb{\lambda}}^{(t)}\right\rangle \right] \leq \mathbb{E}_{\Lambda}[\mathsf{Alg}^{(T)}(\Lambda)]\] in the above inequality. Finally, applying [lma:algtsmall] gives \[\begin{align} \mathbb{E}_{\Lambda}\left[(1 - P_\mathtt{BE}(\Lambda)) \cdot\sum_{t \in [T]} \left \langle \boldsymbol{c}({\pmb{\lambda}}^{(t)}) - \boldsymbol{d}^{(t)}, {\pmb{\lambda}}^{(t)}\right\rangle \right] ~&\geq~ -14\epsilon \cdot T \cdot \mathsf{Opt}- 4nm\lambda^{\mathtt{INIT}}. \label{eq:third-final} \end{align}\tag{21}\]

Putting everything together. Summing 15 , 18 , and 21 , we have

\[\begin{align} \mathbb{E}_\Lambda \left[\mathsf{Alg}(\Lambda)\right] ~\geq~ \mathbb{E}_{\Lambda}\left[(1 - P_\mathtt{BE}(\Lambda)) \cdot \mathsf{Alg}^{(T)}(\Lambda)\right] ~&\geq~ \mathbb{E}_{\Lambda}\left[(1 - P_\mathtt{BE}(\Lambda)) \cdot (\eqref{eq:first} + \eqref{eq:second} + \eqref{eq:third})\right] \\ ~&\geq~ (1 - 26 \epsilon) \cdot T \cdot \mathsf{Opt}- \frac{2nm \lambda^{\mathtt{INIT}}}{\epsilon} - 4nm \lambda^{\mathtt{INIT}}\\ ~&\geq~ (1 - 32\epsilon) \cdot T \cdot \mathsf{Opt}, \end{align}\] where the last inequality uses the definition of \(\lambda^{\mathtt{INIT}}=\widehat{\mathsf{Opt}}\cdot \frac{\epsilon^2}{m}\), the fact that \(T \geq n\), and the assumption that \(\mathsf{Opt}\geq \widehat \mathsf{Opt}\).

4 Basic Probability Inequalities↩︎

5 Omitted proofs in 2↩︎

5.1 Proof of 4↩︎

5.2 Proof of 5↩︎

6 Omitted Proofs from 3↩︎

6.1 Proof of [lma:pbesmall]↩︎

We decompose the proof of [lma:pbesmall] into the following three claims:

Combining 10, 11, 12 proves [lma:pbesmall]:

Now, we finish the proofs of 10, 11, and 12.

6.1.1 Proof of 10↩︎

It’s sufficient to show that for every \(j \in [m]\), we have \[\begin{align} \mathbf{Pr}_{\Lambda}\left[\sum_{t \in [T]} {d}^{(t)}_j > (1 - 3\epsilon/4) \cdot T \cdot B_j\right] ~\leq~ \frac{\epsilon}{n\cdot m}, \label{eq:realalloc-sum-bounded} \end{align}\tag{25}\]

as applying the union bound over all \(j \in [m]\) proves 10.

Fix the realization of requests \(\{\gamma^{(t)}_i\}\). Suppose the inequality \[\sum_{t \in [T]} {d}^{(t)}_j > (1 - 3\epsilon/4) \cdot T \cdot B_j\] holds. Let \(\hat{t} < T\) be the index that satisfies \[\sum_{t = \hat{t}}^T {d}^{(t)}_j \in [0.1 \epsilon \cdot T \cdot B_j, 0.2 \epsilon \cdot T \cdot B_j].\] Such index \(\hat{t}\) must exist, as each \({d}^{(t)}_j\), which represents the unit of consumed resource in round \(t\), must fall between \([0, n]\), and there must be \[0.1 \cdot \epsilon \cdot T \cdot B_j ~\geq~ n\] when \(T \geq n\) and \(B_j \geq \frac{10}{\epsilon^2} \geq 10/\epsilon\) holds. Then, for every \(t' \in [\hat{t}, T]\), the price \(\lambda^{(t')}_j\) for resource \(j\) must satisfy \[\begin{align} \lambda^{(t')}_j ~&=~ \lambda^{\mathtt{INIT}}\cdot \exp \left(\frac{\epsilon}{n} \cdot \Big( \sum_{t = 1}^{t' - 1} {d}^{(t)}_j - (1 - \epsilon) \cdot (t' - 1) \cdot B_j \Big)\right) \\ ~&\geq~ \lambda^{\mathtt{INIT}}\cdot \exp \left(\frac{\epsilon}{n} \cdot \Big( \sum_{t \in [T]} {d}^{(t)}_j - (1 - \epsilon) \cdot T \cdot B_j - 0.2 \epsilon \cdot T \cdot B_j \Big)\right) \\ ~&\geq~ \lambda^{\mathtt{INIT}}\cdot \exp \left(\frac{\epsilon}{n} \cdot 0.05\epsilon \cdot T \cdot B_j \right) \\ ~&\geq~ \lambda^{\mathtt{INIT}}\cdot \exp\big(10 \log(n \cdot m \cdot \beta/\epsilon) \big) ~\geq~ \frac{10nm \cdot \mathsf{Opt}}{\epsilon^2}, \end{align}\] where the last line holds when \(T \geq n\) and \(B_j \geq 200 \log (nm \beta/\epsilon) \cdot \epsilon^{-2}\), and we use the assumption that \(\mathsf{Opt}\leq \beta \cdot \widehat \mathsf{Opt}\) in the last inequality.

With the above lower bound for \(\lambda^{(t')}_j\), note that the total value collected from round \(\hat{t}\) to round \(T\) is at least the payment for buying resource \(j\). Then, when the inequality \(\sum_{t \in [T]} {d}^{(t)}_j > (1 - 3\epsilon/4) \cdot T \cdot B_j\) holds, the total value collected in the learning phase of 1 is at least \[\frac{10nm \cdot \mathsf{Opt}}{\epsilon^2} \cdot 0.1 \epsilon \cdot T \cdot B_j ~\geq~ \frac{nm}{\epsilon} \cdot T \cdot \mathsf{Opt}.\] Note that the above inequality implies \[\mathbf{Pr}_{\Lambda}\left[\sum_{t \in [T]} {d}^{(t)}_j > (1 - 3\epsilon/4) \cdot T \cdot B_j\right] ~\leq~ \frac{\epsilon}{n\cdot m},\] as if the bound does not hold, the expected value collected in the learning phase of 1 is at least \(T \cdot \mathsf{Opt}\), which is in contrast to the fact that no algorithm can collect more than \(T \cdot \mathsf{Opt}\) value in the learning phase.

6.1.2 Proof of 11↩︎

It’s sufficient to show that for every \(j \in [m]\), we have \[\begin{align} \label{eq:real-exp-diff-small} \mathbf{Pr}_{\Lambda}\left[\sum_{t \in [T]} {d}^{(t)}_j + \epsilon/4 \cdot T \cdot B_j \leq \sum_{t \in [T]} c_j({\pmb{\lambda}}^{(t)})\right] ~\leq~ \frac{\epsilon}{m}. \end{align}\tag{26}\] Then, taking union bound over \(j \in [m]\) proves 11.

Fix \(j\) and the realization in the learning phase. To prove 26 , note that when the event \(\sum_{t \in [T]} {d}^{(t)}_j + \epsilon/4 \cdot T \cdot B_j \leq \sum_{t \in [T]} c_j({\pmb{\lambda}}^{(t)})\) happens, there must be either \[\sum_{t \in [T]} {d}^{(t)}_j > (1 - 3\epsilon/4) \cdot T \cdot B_j \quad \text{or} \quad \Big| \sum_{t \in [T]} {d}^{(t)}_j - \sum_{t \in [T]} c_j({\pmb{\lambda}}^{(t)}) \Big| ~\geq~ \frac{0.1n\epsilon \cdot B_j + 0.1\epsilon \cdot \sum_{t \in [T]} {d}^{(t)}_j}{1 - 0.1\epsilon},\] as if neither of the two events hold, there must be \[\begin{align} \Big| \sum_{t \in [T]} {d}^{(t)}_j - \sum_{t \in [T]} c_j({\pmb{\lambda}}^{(t)}) \Big| ~&\leq~ 0.11 T\epsilon \cdot B_j + 0.11 \epsilon \cdot \sum_{t \in [T]} {d}^{(t)}_j \\ ~&\leq~ 0.22 \epsilon \cdot T \cdot B_j ~\leq~ \epsilon/4 \cdot T \cdot B_j, \end{align}\] where the first inequality holds when \(\epsilon \leq 0.5\) and \(T \geq n\), and the second inequality uses the assumption that \(\sum_{t \in [T]} {d}^{(t)}_j \leq (1 - 3\epsilon/4) \cdot T \cdot B_j \leq T \cdot B_j\).

Therefore, we have \[\begin{align} \mathbf{Pr}_{\Lambda} &\left[\sum_{t \in [T]} {d}^{(t)}_j + \epsilon/4 \cdot T \cdot B_j \leq \sum_{t \in [T]} c_j({\pmb{\lambda}}^{(t)})\right] ~\leq~ \mathbf{Pr}_{\Lambda}\left[\sum_{t \in [T]} {d}^{(t)}_j > (1 - 3\epsilon/4) \cdot T \cdot B_j\right]\\ & + \mathbf{Pr}_{\Lambda}\left[\Big| \sum_{t \in [T]} {d}^{(t)}_j - \sum_{t \in [T]} c_j({\pmb{\lambda}}^{(t)}) \Big| ~\geq~ \frac{0.1n\epsilon \cdot B_j + 0.1\epsilon \cdot \sum_{t \in [T]} {d}^{(t)}_j}{1 - 0.1\epsilon}\right] \\ \leq& ~\frac{\epsilon}{n \cdot m} + \mathbf{Pr}_{\Lambda}\left[\Big| \sum_{t \in [T]} {d}^{(t)}_j - \sum_{t \in [T]} c_j({\pmb{\lambda}}^{(t)}) \Big| ~\geq~ \frac{0.1n\epsilon \cdot B_j + 0.1\epsilon \cdot \sum_{t \in [T]} {d}^{(t)}_j}{1 - 0.1\epsilon}\right], \end{align}\] where the second inequality follows from 25 , and it remains to show \[\begin{align} \mathbf{Pr}_{\Lambda}\left[\Big| \sum_{t \in [T]} {d}^{(t)}_j - \sum_{t \in [T]} c_j({\pmb{\lambda}}^{(t)}) \Big| ~\geq~ \frac{0.1n\epsilon \cdot B_j + 0.1\epsilon \cdot \sum_{t \in [T]} {d}^{(t)}_j}{1 - 0.1\epsilon}\right] ~\leq~ \frac{\epsilon}{m}. \label{eq:ineq-via-martingale} \end{align}\tag{27}\]

To prove 27 , we model the consumption of resource \(j\) as a martingale process. Let \(\{Y_t\}_{t \in [T]}\) be a martingale, such that \[\Delta Y_t ~=~ Y_t - Y_{t-1} ~:=~ \frac{{d}^{(t)}_j - c_j({\pmb{\lambda}}^{(t)})}{n}\] is a mean-zero random variable bounded between \([-1, 1]\), since when the requests till round \(t - 1\) are realized, \(c_j({\pmb{\lambda}}^{(t)})\) represents the expectation of \({d}^{(t)}_j\), and we allocate at most \(n\) unit of resource \(j\) in round \(t\). Let \(\mathcal{H}_{t}\) denote the history of requests till round \(t\), and let \[V_t ~:=~ \sum_{t' = 1}^t \mathsf{Var}(\Delta Y_{t'} ~|~ \mathcal{H}_{t' - 1})\] be the conditional variance of the martingale process. Note that when the requests till round \(t - 1\) are realized, we have \[\begin{align} \mathsf{Var}(\Delta Y_{t} ~|~ \mathcal{H}_{t-1}) = \mathsf{Var}\left( \frac{{d}^{(t)}_j}{n} ~|~ \mathcal{H}_{t-1} \right) \leq \mathbb{E}\left[\frac{{d}^{(t)}_j}{n} \cdot \frac{{d}^{(t)}_j}{n} ~|~ \mathcal{H}_{t-1} \right] \leq \mathbb{E}\left[\frac{{d}^{(t)}_j}{n} ~|~ \mathcal{H}_{t-1} \right] = \frac{c_j({\pmb{\lambda}}^{(t)})}{n}, \end{align}\] where the first equality uses the fact that \(c_j({\pmb{\lambda}}^{(t)})\) is deterministic when the history \(\mathcal{H}_{t-1}\) till round \(t - 1\) is fixed and does not affect the conditional variance; the second inequality uses the fact that \(\mathsf{Var}(X)\leq \mathbb{E}(X^2)\) for any random variable \(X\); and the second inequality uses the fact that \(\frac{{d}^{(t)}_j}{n} \in [0, 1]\). Therefore, \[\begin{align} V_T ~=~ \sum_{t \in [T]} \mathsf{Var}(\Delta Y_{t} ~|~ \mathcal{H}_{t-1}) ~\leq~ \frac{1}{n} \cdot \sum_{t \in [T]} c_j({\pmb{\lambda}}^{(t)}) ~\leq~ \frac{1}{n} \cdot \sum_{t \in [T]} {d}^{(t)}_j + |Y_T|. \label{eq:martingale-var-bound} \end{align}\tag{28}\]

Now, we apply 8 with \(\eta = 0.1\epsilon \cdot B_j\) and \(\zeta = B_j\) to prove 27 . We have \[\begin{align} &\mathbf{Pr}_\Lambda \left[\Big| \sum_{t \in [T]} {d}^{(t)}_j - \sum_{t \in [T]} c_j({\pmb{\lambda}}^{(t)}) \Big| ~\geq~ \frac{0.1n\epsilon \cdot B_j + 0.1\epsilon \cdot \sum_{t \in [T]} {d}^{(t)}_j}{1 - 0.1\epsilon} \right] \\ ~=~& \mathbf{Pr}_\Lambda \left[|Y_T| ~\geq~ \eta + 0.1\epsilon \cdot \left( \frac{1}{n} \cdot \sum_{t \in [T]} {d}^{(t)}_j + |Y_T|\right) \right] \\ ~\leq~& \mathbf{Pr}_\Lambda \left[|Y_T| ~\geq~ \eta + 0.1\epsilon \cdot V_T \right] \\ ~\leq~& \mathbf{Pr}_\Lambda \left[|Y_T| ~\geq~ \eta + \frac{\eta/\zeta - \log(1 + \eta/\zeta)}{\log(1 + \eta/\zeta)} \cdot (V_T - \zeta) \right] \\ ~\leq~& 2\exp \left( -\frac{\eta^2}{\zeta + \eta/3} \right) \\ ~=~& 2\exp\left(-\frac{0.01\epsilon^2B_j^2}{B_j+0.1\epsilon B_j/3}\right) \\ ~\leq~& 2\exp \left(-\epsilon^2 B_j / 1000 \right) ~\leq~ \epsilon/m, \end{align}\] where the third line uses 28 ; the fourth line uses the fact that \(\eta/\zeta = 0.1\epsilon \leq 1\), and inequality \(\frac{x - \log (1 + x)}{\log(1 + x)} \leq x\) holds when \(x \in (0, 1]\); the fifth line applies 8; the sixth line applies the value of \(\eta\) and \(\zeta\); and the last inequality holds when \(B_j \geq 10000 \log (m/\epsilon) \cdot \epsilon^{-2}\).

6.1.3 Proof of 12↩︎

It’s sufficient to show that for each resource \(j \in [m]\), the probability that the auction phase allocates more than \(B_j - 1\) unit of resource \(j\) is at most \(\epsilon/m\). Then, applying union bound over \(j \in [m]\) proves 12.

Fix \(j\) and \(\Lambda\). Let \(X_{i,j} \in [0, 1]\) be the random variable representing the unit of resource \(j\) consumed by request \(i\) in the auction phase. Then, the desired inequality is \[\mathbf{Pr}\left[ \sum_{i \in [n]} X_{i, j} ~\geq~ B_j - 1\right] ~\leq~ \frac{\epsilon}{m}.\]

We prove the above inequality via concentration. Since request \(i\) faces a price vector chosen from \(\Lambda\) uniformly at random, we have \[\mathbb{E}[X_{i,j}] ~=~ \frac{1}{T} \cdot \sum_{t \in [T]} c_{i,j} ({\pmb{\lambda}}^{(t)}), \quad \text{and} \quad \mathsf{Var}(X_{i, j}) = \mathbb{E}[X^2_{i, j}] ~\leq~ \mathbb{E}[X_{i, j}] ~=~ \frac{1}{T} \cdot \sum_{t \in [T]} c_{i,j} ({\pmb{\lambda}}^{(t)}).\] Then, since 12 assumes \(\sum_{t \in [T]} \boldsymbol{c}({\pmb{\lambda}}^{(t)}) \leq (1 - \epsilon/2) \cdot T \cdot \mathbf{B}\), we have \[\begin{align} \sum_{i \in [n]} \mathsf{Var}(X_{i, j}) ~\leq~ \sum_{i \in [n]} \mathbb{E}[X_{i,j}] ~=~ \frac{1}{T} \cdot \sum_{t \in [T]} c_j({\pmb{\lambda}}^{(t)}) ~\leq~ (1 - \epsilon/2) \cdot B_j \label{eq:consbase-sum-bounded} \end{align}\tag{29}\]

Now, we apply 9 to the summation of mean-zero random variables \(X_{i, j} - \mathbb{E}[X_{i, j}]\), which gives \[\begin{align} \mathbf{Pr}\left[ \sum_{i \in [n]} X_{i, j} ~\geq~ B_j - 1\right] ~&\leq~ \mathbf{Pr}\left[ \sum_{i \in [n]} X_{i, j} ~\geq~ (1 - \epsilon/4) \cdot B_j\right] \\ ~&=~ \mathbf{Pr}\left[ \sum_{i \in [n]} \left(X_{i, j} - \mathbb{E}[X_{i,j}]\right) ~\geq~ (1 - \epsilon/4) \cdot B_j - \sum_{i \in [n]} \mathbb{E}[X_{i,j}]\right] \\ ~&\leq~ \mathbf{Pr}\left[ \sum_{i \in [n]} \left(X_{i, j} - \mathbb{E}[X_{i,j}]\right) ~\geq~ \epsilon/4 \cdot B_j \right] \\ ~&\leq~ \exp \left(-\frac{\epsilon^2 \cdot B^2_j /32}{\sum_{i \in [n]} \mathsf{Var}(X_{i, j}) + \epsilon \cdot B_j / 12} \right) \\ ~&\leq~ \exp\left( -\epsilon^2 \cdot B_j/32\right) ~\leq~ \epsilon/m, \end{align}\] where the third line and the last line follows 29 , the fourth line follows 9, and the last inequality holds when \(B_j \geq 32 \log(m/\epsilon) \cdot \epsilon^{-2}\).

6.2 Proof of [lma:algtsmall]↩︎

6.3 Proof of [lma:plussmall]↩︎

References↩︎

---

1. Google Research. Email: yifengt@google.com.↩︎

2. School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA. Email: ywang3782@gatech.edu. Supported in part by NSF awards CCF-2327010 and CCF-2440113.↩︎

3. We remark that it is possible to obtain a \((1-\epsilon)\)-approximation for online resource allocation problem only when the supply of each resource is at least \(\Omega(\epsilon^{-2})\), even if there is only single resource; see, e.g., [2].↩︎

4. We require that the agent respects the inventory constraints, that the agent makes the utility-maximizing decision with resource consumption capped by the current remaining units for each resource. While this may result in overload cascades in the online resource allocation problems [3], in the analysis of our algorithms we will treat the overload of any resource as a bad event in the online process, and exclude the overall welfare contribution whenever a bad event happens.↩︎

5. It can be a little confusing that Static Pricing and Anonymous Pricing are defined differently. In fact, this is due to the fact that Static Pricing has a canonical meaning in the literature, that refers to a fixed deterministic pricing mechanism that does not change over time. It is not the same as the meaning of “static” in the online learning literature, which corresponds to algorithms that do not change over time. Therefore, in this paper we use Anonymous Pricing to denote the pricing algorithms that are possibly randomized, but are oblivious to the arrival order, allocation history, and the identity of the current agent.↩︎

6. As noted by [1] this is enough to solve the configuration LP efficiently.↩︎

7. The generic property is the condition that, for any item pricing, the probability that at least two decisions of an agent are both utility-maximizing is 0. This kind of atomless property is usually needed to deal with the tie breaking (Eg. in [4]). We will discuss more in Section 1.4 why this is needed.↩︎

8. One simple example is as follows. Consider a seller who wants to sell 3 items with one copy each to 3 unit-demand buyers. Buyer 1 has value \(1\) for either item 2 or 3; buyer 2 has value 1 for either item 1 or 3; buyer 3 has value 1 for either item 1 or 2. While a static pricing mechanism with price 1 for each item can obtain the optimal welfare 3, the seller needs to hold the tie-breaking power to decide which item to sell when each agent arrives. In fact, for any static item pricing mechanism, there always exists an arrival order of the buyers such that at most two of the three items are sold. The example can be generalized to the setting where each item has \(B\) copies, by having \(B\) copies of each buyer.↩︎

9. Note that notations \(\hat{\boldsymbol{c}}(\widehat \pmb{\lambda})\) or \(\theta^*(\widehat \pmb{\lambda};\gamma_i)\) can’t be applied, as we are performing a different tie-breaking rule, instead of the predefined deterministic tie-breaking rule that defines \(\hat{\boldsymbol{c}}(\widehat \pmb{\lambda})\) and \(\theta^*(\widehat \pmb{\lambda};\gamma_i)\).↩︎