Online Budgeted Matching with General Bids

Authors: jianyi  yang
pengfei  li
adam  wierman
shaolei  ren
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 22:58:38

Abstract: Online Budgeted Matching (OBM) is a classic problem with important applications in online advertising, online service matching, revenue management, and beyond. Traditional online algorithms typically assume a small bid setting, where the maximum bid-to-budget ratio ($\kappa$) is infinitesimally small. While recent algorithms have tried to address scenarios with non-small or general bids, they often rely on the Fractional Last Matching (FLM) assumption, which allows for accepting partial bids when the remaining budget is insufficient. This assumption, however, does not hold for many applications with indivisible bids. In this paper, we remove the FLM assumption and tackle the open problem of OBM with general bids. We first establish an upper bound of $1-\kappa$ on the competitive ratio for any deterministic online algorithm. We then propose a novel meta algorithm, called MetaAd, which reduces to different algorithms with first known provable competitive ratios parameterized by the maximum bid-to-budget ratio $\kappa\in [0,1]$. As a by-product, we extend MetaAd to the FLM setting and get provable competitive algorithms. Finally, we apply our competitive analysis to the design learning- augmented algorithms.

Main paper: 
 introduction: 
 Online Budgeted Matching (OBM) with general bids is a fundamental online optimization problem that generalizes to many important settings, such as online bipartite matching and Adwords with equal bids [23] . It has applications in various domains, including online advertising, online resource allocation, and revenue management among others [5, 16, 32] . OBM is defined on a bipartite graph with a set of offline nodes (bidders) and a set of online nodes (queries). The task is to select an available offline node to match with an online query in each round. When an offline node is matched to an online node, a bid value is subtracted from the budget of the offline node, and a reward equal to the consumed budget is obtained. If the remaining budget of an offline node is less than the bid value of an online query, the offline node cannot be matched to the online query. The goal is to maximize the total reward throughout the entire online matching process.OBM is challenging due to the nature of online discrete decisions. Previous works have studied this problem under one of the following two additional assumptions on bids or matching rules: • Small bids. The small-bid assumption is a special case of general bids corresponding to the maximum bid-budget ratio κ → 0. That is, while the bid values can vary arbitrarily, the size of each individual bid is infinitely small compared to each offline node's budget, and there is always enough budget for matching. Under this assumption, the first online algorithm was provided by [24] , achieving an optimal competitive ratio of 1 -1/e [23] . This competitive ratio has also been attained by subsequent algorithms based on primal-dual techniques [4, 7] . However, the small-bid assumption significantly limits these algorithms for broader applications in practice. Take the application of matching Virtual Machines (VMs) to physical servers as an example. An online VM request typically takes up a non-negligible fraction of the total computing units in a server.• Fractional last match (FLM). Under FLM, if an offline node has an insufficient budget for an online query, the offline node can still be matched to the query, obtaining a partial reward equal to the remaining budget. Given the limitations of small bids, some recent studies [15, 29, 30] have studied competitive algorithms for OBM with general bids by making the additional assumption of FLM. For example, under FLM, the greedy algorithm (Greedy) achieves a competitive ratio of 1/2, while other studies [4, 15, 29, 30] aim to achieve a competitive ratio greater than 1/2 under various settings and/or using randomized algorithms. Although FLM allows fractional matching of a query to an offline node with insufficient budgets, it essentially assumes that any bids are potentially divisible. This assumption may not hold in many real applications, e.g., allocating fractional physical resources to a VM can result in significant performance issues that render the allocation unacceptable, and charging a fractional advertising fee may not be allowed in online advertising.Despite its practical relevance and theoretical importance, OBM with general bids has remained a challenging open problem in the absence of the small-bid and FLM assumptions. Specifically, an offline node may have insufficient budget and cannot be matched to a later query with a large value, potentially causing large sub-optimality in the worst case. This issue does not apply to small bids, as the small-bid setting implies that insufficient budgets will never occur. Additionally, this challenge is alleviated in the FLM setting, where fractional matching in cases of insufficient budgets can reduce sub-optimality. Indeed, removing the small-bid and FLM assumptions fundamentally changes and add significant challenges to the problem of OBM [30] . To further highlight the intrinsic difficulty of OBM with general bids, we formally prove in Proposition 4.1 an upper bound of the competitive ratio, i.e., 1 -κ, achieved by any deterministic online algorithm, where κ ∈ [0, 1] is the maximum bid-budget ratio.In this paper, we address OBM without the small-bid or FLM assumptions and design a meta algorithm called MetaAd, which adapts to different algorithms with provable competitive ratios. To our knowledge, MetaAd is the first provable competitive algorithm for general bids without the FLM assumption. Specifically, MetaAd generates a discounted score for each offline node by a general discounting function, which is then used to select the offline node. The discounting function evaluates the degree of budget insufficiency given a bid-budget ratio κ ∈ [0, 1], addressing the challenge of infeasible matching due to insufficient budgets. Given different discounting functions, MetaAd yields concrete algorithms, and their competitive ratios are derived from Theorem 4.2, established through a novel proof technique. We show that with small bids (i.e., κ → 0), MetaAd recovers the optimal competitive ratio of 1 -1 e . Furthermore, we show that MetaAd, with discounting functions from the exponential and polynomial function classes, achieves a positive competitive ratio for κ ∈ [0, 1). As an extension, we adapt the design of MetaAd to the FLM setting, resulting in a meta-algorithm with provable competitive ratios for κ ∈ [0, 1] (Theorem 4.3). The framework of MetaAd potentially opens an interesting direction for exploring concrete discounting function designs that yield high competitive ratios for settings both with and without FLM. Finally, we apply our competitive analysis to the design of LOBM, a learning-augmented algorithm for OBM, which enhances average performance while still guaranteeing a competitive ratio (Theorem 5.1). We validate the empirical benefits of MetaAd and LOBM through numerical experiments on the applications of an online movie matching an VM placement on physical servers. 
related work: 
 OBM originates from the online bipartite matching problem defined by [19] 30 years ago. In 2007, [24] generalized the online b-matching problem to OBM (a.k.a. Adwords) [17] . Under the special case of small bids, [24] proposes an algorithm that achieves the competitive ratio of 1 -1/e, which is also the optimal competitive ratio under the small-bid setting [17] . In the same year, [4] provides the primal-dual algorithm and analysis for OBM under the small-bid assumption and achieves the competitive ratio of 1 -1 e . Subsequently, [7] gives a randomized primal-dual analysis for online bipartite matching and generalizes it to OBM. In addition, OBM has also been studied under the stochastic settings [9, 8, 6, 14, 25] .It is known to be very challenging to go beyond the small-bid assumption and develop a non-trivial competitive ratio for OBM with general bids in an adversarial setting. Recently, [30] points out the inherent difficulty of OBM with general bids and explains the necessity of the assumption of FLM is needed in easing up the challenges. With the FLM assumption, a greedy algorithm can achieve a competitive ratio of 1/2. Additionally, a deterministic algorithm proposed in [4] achieves a competitive ratio of (1 -κ - 1-κ (1+κ) 1/κ ), increasing the competitive ratio when the maximum bid-budget ratio κ is no larger than 0.17. Some other works on OBM with FLM employ randomized algorithm designs. For example, [15] proposes a semi-random algorithm that achieves a competitive ratio of 0.5016, which is known as the best competitive ratio achieved by randomized algorithms up to now. Besides, [30] extends the random algorithm of Ranking to OBM and achieves a competitive ratio of 1 -1/e with a strong assumption of the "fake" budget. Moreover, [29] proposes a randomized algorithm without the knowledge of budget for the FLM setting with competitive ratio 1 1+κ (1 -1 e ) parameterized by the maximum bid-budget ratios κ, which relies on a strong assumption that the bids are decomposable (i.e. w u,t = w u • w t ).Despite the progress on the OBM settings with FLM, OBM without FLM has remained an open challenge except for under the small-bid assumption. The recent study [30] points out that OBM without FLM is difficult because when the offline node has less leftover budget than the bid value of an online arrival, the offline node is not allowed to be matched to the arrival, potentially causing a loss equivalent the leftover budget. [20] considers multi-tier budget constraints with a laminar structure and provides a competitive ratio without FLM, but the result does not apply to the settings without the laminar structure. Additionally, [18] proves an online randomized algorithm with the competitive ratio (in expectation) upper bound of 0.612, an upper bound for deterministic algorithms is still lacking to formally evaluate the difficulty of OBM without FLM. 
problem formulation: 
 We consider OBM with general bids. Specifically, there is a bipartite graph described as G(U, V, E), where the vertices u ∈ U (i.e. offline nodes or bidders) are fixed and the vertices v ∈ V (i.e. online nodes or queries) arrive sequentially. The edge corresponding to vertices u ∈ U and v ∈ V has a bid value w u,v ≥ 0 which is the amount the offline node u would like to pay for the online node v if matched. The sizes of the vertex sets are denoted as |U| = U and |V| = V , respectively. We index each online node by its arriving order, i.e. online node t arrives at the t-th round.At the beginning, each offline node u ∈ U has an initial budget b u,0 = B u ≥ 0, which is the maximum amount the offline node can pay in total. At round t, a query t ∈ V arrives, the edges connected to this arrival t are revealed, and the agent chooses to match the arrival to an available offline node from U t = {u ∈ U | w u,t > 0, b u,t-1 ≥ w u,t } or skip this query without any matching. We denote the agent's action as x t ∈ U t {null}, where "null" represents skipping this arrival. If at round t, an offline node x t is matched to the query t, a reward r t = w xt,t is earned and a bid value w xt,t is charged from the offline node x t , i.e., b xt,t = b xt,t-1 -w xt,t ; for the other offline nodes u ̸ = x t , the budget remains unchanged b u,t = b u,t-1 . If x t = null, no reward is earned, i.e. r t = 0 and the budgets of all offline nodes remain the same as the last round, i.e. b u,t = b u,t-1 ∀u ∈ U. The cumulative consumed budget at the end of round t is denoted asc u,t = B u -b u,t , ∀u ∈ U and t ∈ [V ].The agent aims to maximize the total reward P = V t=1 r t over the entire V rounds. The offline version of OBM can be written as Linear Programming (LP) with its primal and dual problems given in (1) , where P is the primal objective and D is the dual objective. While we only need to solve the primal problem for OBM, we present the dual problem with dual variables α u , u ∈ U and β t , t ∈ V to facilitate the subsequent algorithm design and analysis.EQUATIONA common performance metric for online algorithms is the competitive ratio defined asEQUATIONwhere the minimization is taken over the set of all possible bipartite graphs G1 , P (G) = V t=1 w xt,t is the total reward obtained by an (online) algorithm for a graph G ∈ G, andP * (G) = V t=1 w x * t ,tis the corresponding offline optimal total reward with x * t being the offline optimal solution to (1). Next, we formally define the bid-budget ratio κ ∈ [0, 1] in Definition 1 which is the maximum ratio of the bid value of an offline node to its total budget. We use η(κ) to denote the competitive ratio of an algorithm for OBM with bid-budget ratio κ. Definition 1 (Bid-budget ratio). The bid-budget ratio κ ∈ [0, 1] for an example G(U, V, E) is defined as κ = sup u∈U ,t∈V wu,t Bu .Many previous works [23, 24, 15, 4] assume FLM which allows for accepting partial bids when remaining budget is insufficient (i.e. modifying each bid w u,t to wu,t = min{w u,t , b u,t-1 } given the remaining budget b u,t-1 ). Without the FLM assumption, the only known competitive ratio for OBM is for the small-bid setting where κ is infinitely small and approaches zero [23, 24] . However, the small-bid and FLM assumptions do not hold in many real-world applications as illustrated by the following examples: • Online VM placement. In this problem, a cloud manager allocates virtual machines (VMs, online nodes) to heterogeneous physical servers (offline nodes), each with a computing resource capacity of B ′ u [10, 28] . When a VM request with a computing load of z t arrives, the manager assigns it to a server. If the VM is placed on server u, the manager receives a utility of w u,v = r u z v due to the heterogeneity of servers. The goal is to maximize the total utility V t=1 u∈U w u,t x u,t subject to the computing resource constraintV t=1 z t x u,t ≤ B ′u for each server u, which can also be written asV t=1 w u,t x u,t ≤ B u with B u = r u B ′ u .In this problem, VMs are not divisible and consume up a non-negligible portion of the server capacity, violating both the small-bid and FLM assumptions.• Inventory management with indivisible goods. Here, a manager must match several indivisible goods (online nodes) to various resource nodes (offline nodes), each with a limited capacity (e.g., matching parcels to mail trucks or food orders to delivery vehicles). Each good can only be assigned to one node without being split, and a good t can occupy a substantial portion of the resource node's capacity, w u,t . The goal is to maximize the total utilization V t=1 u∈U w u,t x u,t , subject to the capacity constraint V t=1 w u,t x u,t ≤ 1 for each node u. In this problem, neither the small-bid nor FLM assumption applies.In this paper, without relying on the small-bid or FLM assumptions, we move beyond small bids and propose a meta algorithm (MetaAd) for general κ ∈ [0, 1] which can reduce to many concrete competitive algorithms.4 MetaAd: Meta Algorithm for OBM 
an upper bound on the competitive ratio: 
 In the absence of small-bid and FLM assumptions, OBM faces a unique challenge: when an online query with large bid arrives, there may be no offline node that both connects to the query and has sufficient remaining budgets for it. This leads to missed matches for the queries with large bids, ultimately resulting in a low competitive ratio. To formally show the inherent difficulty of OBM without the small-bid and FLM assumptions, we present an upper bound on the competitive ratio for any deterministic online algorithms in the following proposition. Proposition 4.1. For OBM without small-bid or FLM assumptions, the competitive ratio of any deterministic online algorithm is upper bounded by 1 -κ for κ ∈ (0, 1]. Specifically, the competitive ratio for any deterministic algorithm is zero when κ = 1 without the FLM assumption.The proof of the upper bound is deferred to Appendix A.1. The key ingredients of the proof is given below. The best competitive ratio for any deterministic algorithm is max π min G∈G CR(π, G) which For u ∈ U, set s u,t = w u,t ϕ( bu,t-1 Bu ) if b u,t-1 -w u,t ≥ 0, and s u,t = 0 otherwise.if ∀u ∈ U, s u,t = 0 then 5:Skip the online arrival t (x t = null). Update budget:If x t ̸ = null, b xt,t = b xt,t-1 -w xt,t; and ∀u ̸ = x t , b u,t = b u,t-1 . 10: end for is no larger than max π min G∈G ′ CR(π, G) where G ′ ⊂ G. Thus, we can prove the upper bound by constructing a subset G ′ with difficult instances and deriving the best competitive ratio among the deterministic algorithms for this subset G ′ . In our constructed G ′ , each example has one offline node and the bid values for the first V -1 rounds sum up to 1 -κ + ϵ with ϵ > 0 being infinitely small. We letG ′ = G ′ 1 G ′2 where we have w u,V = κB u for examples in G ′ 1 , andw u,V = 0 for examples in G ′ 2 .The instances in G ′ illustrate the dilemma between matching a query for immediate reward or saving the budget for future matches. If an algorithm chooses to match all the queries in the first V -1 rounds, it can lose a bid of κB u for instances in G ′ 1 because there is no sufficient budget to match the final query. Conversely, if an algorithm chooses to skip some queries in the first V -1 rounds to save the budget, it can lose a bid of κB u for the instances in G ′ 2 because matching the final query of instances in G ′ 2 earns zero bid. For these difficult instances in G ′ , we formally derive the largest reward ratio of a deterministic algorithm to the offline optimal one which is the upper bound of the competitive ratio.The upper bound of the competitive ratio 1 -κ shows that OBM becomes more difficult when the bid-budget ratio κ gets larger. Intuitively, since the bid value is not fractional for each matching, given a larger κ ∈ [0, 1], it is more likely for offline nodes to have insufficient budgets (i.e., unable to be matched to a query with a large bid value). Skipping a query to save budget is also risky because it can happen that the following queries have no positive bid. The FLM assumption can alleviate this difficulty because the remaining budget can be fully spent even if it is insufficient. A greedy algorithm can achieve a competitive ratio of 1/2 for general bids with FLM [23] . By contrast, the upper bound of the competitive ratio without FLM cannot reach 1/2 when the bid-budget ratio κ is larger than 1/2. There is even no non-zero competitive ratio when κ = 1. These observations reveal that without FLM, OBM becomes more difficult. The analysis without FLM assumption will help us to understand OBM better.We now present MetaAd in Algorithm 1, which is a meta online algorithm that reduces to many concrete algorithms with provable competitive ratios for OBM in the absence of small-bid and FLM assumptions.MetaAd relies on a general discounting function ϕ : [0, 1] → [0, 1]. Given a new query t, MetaAd uses ϕ to score each offline node by discounting its bid value in Line 3, and selects the node with the largest score s u,t from Line 4 to Line 7. An offline node is scored zero if it has insufficient budget for the query t (b u,t-1 -w u,t < 0) or it has zero bid for the query t (w u,t = 0). If all the offline nodes are scored zero, the algorithm skips this query t.The scoring in MetaAd reflects a balance between selecting an offline node with a large bid and saving budget for future. To select offline nodes with large bids, the score scales with the bid value w u,t . Simultaneously, an increasing function ϕ maps the normalized remaining budget : [0, 1] → [0, 1], φ(x) = 1 -ϕ(1 -x), ρ ≥ 1. 1: Initialization: ∀u ∈ U, α u,0 = 0, b u,0 = B u , U • = ∅, and ∀t ∈ [V ], β t = 0. 2: for t=1 to V , a new vertex t ∈ V arrives do 3: Append {u | b u,t-1 -w u,t < 0} into U • . 4:Score s u,t , select x t for the arrival t, and update budget b u,t by Algorithm 1.Set the dual variable β t = s xt,t , and set the dual variable α u,t = φ( cu,t Bu ). 6: end for 7: For u / ∈ U • , set α u = α u,V ; and for u ∈ U • , set α u = 1.Given any monotonically increasing function ϕ : [0, 1] → [0, 1] in Algorithm 1, we can get a concrete algorithm for OBM. For different bid-budget ratio κ, the competitive ratio of MetaAd is given in the main theorem below. Theorem 4.2. If the function ϕ : [0, 1] → [0, 1] in Algorithm 1 satisfies that given an integer n ≥ 1, ∀i ≤ n, φ (i) (x) > 0 where φ(x) = 1 -ϕ(1 -x), the competitive ratio of Algorithm 1 isη(κ) = 1 1 + κ n+1 R + max y∈[0,1] ∆(y) + ϕ(κ) 1-κ , where R is the Lipschitz constant of φ (n) (x) if φ (n) (x)is not monotonically decreasing, and R = 0 otherwise. Additionally, ∆(y) = φ(y) y -1y y x=0 φ(x)dx + 1 y n i=1 κ i φ (i-1) (y) -φ (i-1) (0) .By Theorem 4.2, we can easily get a competitive algorithm for OBM with any bid-budget ratio κ by choosing a function ϕ. The only requirement is that the function ϕ is a monotonically increasing function. In the next section, we will give some concrete examples of competitive algorithms by assigning ϕ with different function classes.We defer the complete proof of Theorem 4.2 to Appendix A.2. The analysis is based on the fundamental conditions in Lemma 1 that guarantee the competitive ratio and presents new challenges due to the absence of the small-bid and FLM assumptions. Lemma 1 (Conditions for competitive ratio). An online algorithm achieves a competitive ratio of η ∈ [0, 1] if it selects a series of feasible actions {x 1 , . . . , x V } and there exist dual variables{β 1 , • • • , β V }, {α 1 , • • • , α U } such that • (Dual feasibility) ∀u ∈ U, t ∈ [V ], β t ≥ w u,t (1 -α u ) • (Primal-Dual Ratio ) P ≥ η•D, where P = V t=1 w xt,t and D = u∈U B u α u + V t=1 β t .Without the small-bid and FLM assumptions, the competitive analysis presents the following new challenges to satisfy the conditions in Lemma 1:• Dual construction for general bids. When an offline node has an insufficient budget to match a query, the remaining budget is almost zero for the small-bid setting, but it can be large and uncertain without the small-bid assumption. This introduces a new challenge to construct dual variables that satisfy the dual feasibility due to budget insufficiency.To address this challenge, we present a new dual construction in Algorithm 2 where dual variables are determined based on the remaining budget and adjusted at the end of the algorithm. The constructed dual variables satisfy the dual feasibility in Lemma 1, as explained below. We define β t as the score of selected offline node u. For any u with sufficient remaining budget (b u,t-1 ≥ w u,t ), we haveβ t ≥ s u,t = w u,t (1 -φ( cu,t-1 Bu )). By choosing α u,t = φ( cu,tBu ), the dual feasibility in Lemma 1 is satisfied for t and u with sufficient budget (b u,t-1 ≥ w u,t ) since by an increasing function φ, it holds that α u ≥ α u,t for any t ∈ [T ].Different from the small-bid setting, we need to adjust the dual variables at the end of the dual construction (Line 7 in Algorithm 2) to satisfy dual feasibility. We set α u = 1 for any u with insufficient budget (b u,t-1 < w u,t ) at the end of the dual construction. This ensures that the dual feasibility is always satisfied without FLM.• Guarantee the primal-dual ratio. The challenges in guaranteeing the primal-dual ratio in Lemma 1 come from the unspecified discounting function ϕ and the absence of the small-bid and FLM assumptions. To solve this challenge, we derive a condition to satisfy the primal dual ratio P t ≥ EQUATIONwhere φ(x) = 1 -ϕ(1 -x) and ϕ is the discounting function. Given that the dual increase due to the final dual adjustment (Line 7 in Algorithm 2) is bounded by ϕ(κ) 1-κ • P , we can bound the final primal-dual ratio as P ≥1 γ+ ϕ(κ) 1-κ D.This leads to a competitive ratio of1 γ+ ϕ(κ) 1-κ. Given any discounting function ϕ, we can solve for γ that satisfies the condition in (3), thereby obtaining the competitive ratio of MetaAd.In this section, we assign ϕ with different functions to get concrete algorithms and competitive ratios.We first verify that MetaAd reduces to the optimal algorithm for small-bid setting (κ → 0) [24, 23] .Corollary 4.2.1. By choosing ϕ(x) = e-e 1-xe-1 , MetaAd reduces to the algorithm in [24] and achieves the optimal competitive ratio of 1 -1 e for small-bid setting (κ → 0). Corollary 4.2.1 shows that the competitive ratio in Theorem 4.2 is consistent with the classical results for small bids. Interestingly, our analysis shows how the optimal ϕ is obtained which is explained as follows. By solving (3) with "=" and κ = 0, we getEQUATIONwhere γ ≤ e e-1 to make sure ϕ(x) ≥ 0 for x ∈ [0, 1]. By Theorem 4.2, we get the competitive ratio as lim κ→01 γ+ ρϕ(κ) 1-κ = 1(2-e)γ+e . By optimally choosing γ = e e-1 , we get the optimal competitive ratio as 1 -1 e .Next, we consider an exponential function class φ(x) = C 1 e θx + C 2 with 0 ≤ θ ≤ 1. To ensure φ(x) is an increasing function, we choose C 1 ≥ 0. Also, we choose C 2 = -C 1 to simplify the expression of the competitive ratio. We can observe that φ(x) has positive n-th derivative for any n ≥ 1. Thus, we choose n = ∞ in Theorem 4.2 to eliminate the term κ n+1 R. By substituting φ(x) into η(κ) in Theorem 4.2, we get the corollary below. Corollary 4.2.2. If we assign φ(x) = Ce θx -C with C ≥ 0 and 0 ≤ θ ≤ 1 in MetaAd in Algorithm 1, we get the competitive ratio asEQUATIONWe numerically solve the optimal η(κ) for each κ ∈ [0, 1] by adjusting the parameters θ and C and show the results in Figure 1 . We observe that MetaAd achieves a non-zero competitive ratio for κ ∈ [0, 1). The competitive ratio for κ = 0 is the optimal competitive ratio of 1 -1 e for small-bid setting. The competitive ratio monotonically decreases with κ. This coincides with the intuition that when κ gets larger, it is more likely to trigger budget insufficiency and the problem becomes more challenging. Also, we can find that for a large enough κ, the competitive ratio of MetaAd with the exponential function is very close to the upper bound. However, there can exist other forms of exponential discounting function that can achieve higher competitive ratio. Interestingly, the optimal choices of the exponential function φ(x) for different κ reveal the insights into designing deterministic algorithms for OBM. When κ is less than a critical point κ ≈ 0.26, the optimal choice of the exponential function is φ(x) = 1-e θx 1-e θ and the optimal choice of θ decreases with κ ∈ [0, κ]. In this range, as κ becomes larger in [0, κ], the discounting ϕ(bu,t-1 Bu ) = 1 -φ(1 - bu,t-1Bu ) becomes smaller, indicating a more conservative approach to budget usage in preparation for potentially high future bids. However, as κ gets larger than κ, the optimal choice of the discounting function becomes ϕ(x) = 1 with C = 0, yielding a greedy algorithm. This suggests that for large enough κ, the algorithm benefits more by matching a node with a large bid immediately than by conserving more budget for future.In this section, we explore another function class to show that MetaAd is general enough to provide competitive algorithms given different discounting functions. We consider a function class of n-th polynomial function, i.e. φ(x) = n j=0 C j x j . We set n j=1 C j ≤ 1 to ensure φ(1) ≤ 1 and set C 0 = 0 to simplify the competitive ratio. We summarize the competitive ratio of the polynomial function class and provide a concrete example for quadratic function in the next corollary.EQUATIONwhere∆(y) = -Cn n+1 y n + ((1 + κ)C n -Cn-1 n )y n-1 + n-2 j=0 ((1 + κ)C j+1 - Cj j+1 + n-j i=2 κ i C i+j (i+j)!(j+1)! )y j . Specifically, given a quadratic example φ(x) = Cx 2 , by optimally choosing C = 1, we haveEQUATIONWe numerically show the results of η(κ) in Figure 1 . We observe that MetaAd with a simple quadratic function φ(x) = x 2 can also achieve non-zero competitive ratio for κ ∈ [0, 1). However, this competitive ratio is lower than the best competitive ratio achieved by the exponential functionφ(x) = C(e θx -1).The examples of exponential functions and quadratic functions demonstrate the strength of MetaAd in providing competitive algorithms for OBM with general bids. While MetaAd provides the first framework to get non-zero competitive ratio for OBM with κ ∈ [0, 1) (in the absence of the FLM assumption), it is interesting to explore other functions ϕ under the MetaAd framework with better competitive ratios.While MetaAd is designed for the more challenging OBM without FLM, this section demonstrates that MetaAd can be extended to provide competitive algorithms for OBM with FLM.Due to the space limitation, we defer the algorithm of MetaAd with FLM (Algorithm 3) and its analysis to Appendix B. Instead of scoring based on the true bid w u,t , Algorithm 3 determines the scores based on a modified bid min{w u,t , b u,t-1 }. Based on the modified dual construction in Algorithm 4, we can get the competitive ratio for OBM with FLM in the next theorem.Theorem 4.3. If the function ϕ : [0, 1] → [0, 1] in Algorithm 1 satisfies that given an integer n ≥ 2, ∀i ≤ n -1, φ (i) (x) > 0 and R = max x∈[0,1] φ (n) (x) where φ(x) = 1 -ϕ(1 -x), the competitive ratio of Algorithm 1 is η(κ) = 1 1 + κ n R + max y∈[0,1] ∆(y) + ϕ(κ) ,where and BJN2007 represents the algorithm in [4] .∆(y) = φ(y) y -1 y y x=0 φ(x)dx + 1 y n i=1 κ i φ (i-1) (y) -φ (i-1) (0) .The competitive ratio with FLM in Theorem 4.3 differs from that in Theorem 4.2 only in the final terms of the denominators, which are ϕ(κ) and ϕ(κ)1-κ respectively. Thus, the competitive ratio with FLM is always larger than that without FLM given the same values of κ and ϕ. This improvement arises because FLM allows for accepting partial bids when budgets are insufficient, thereby reducing the potential budget waste.Similar as MetaAd without FLM, we assign an exponential function class φ(x) = C(e θx -1) to get a concrete algorithm with competitive ratio in Corollary B.1.1. We numerically solve the optimal η(κ) for each κ ∈ [0, 1] by adjusting θ and C and compare the results with an existing competitive algorithm BJN2007 [4] for FLM in Figure 2 . As κ → 0, both MetaAd and BJN2007 achieve the optimal competitive ratio 1 -1/e in the small-bid setting. However, as κ approaches 1, the competitive ratio of BJN2007 decreases to zero while MetaAd, reducing to a greedy algorithm, maintains a competitive ratio of 1 2 , the best known competitive ratio of the deterministic algorithms for the OBM with FLM. 
competitive learning-augmented design: 
 In this section, we demonstrate the application of our competitive analysis for designing learningaugmented algorithms which guarantee a competitive ratio of ML-based solutions for OBM.Our competitive analysis directly motivates a learning-augmented algorithm for OBM called LOBM. The algorithm of LOBM and analysis are deferred to Appendix C. In LOBM, we apply a ML model which at each round takes the features of the arriving query and the offline nodes as inputs and gives the output zu,t . Directly using 1 -zu,t as a discounting value to set the score as w u,t (1 -zu,t ) can result in arbitrarily bad worst-case performance for adversarial examples. To provide a competitive guarantee for OBM, LOBM projects the ML output zu,t into a competitive solution space D u,t in (28) and obtains a projected value z u,t . The score is then set as w u,t (1 -z u,t ) based on the projected ML output z u,t . The key design of the competitive solution space is motivated by the conditions in Lemma 1, which ensures that any z value in D u,t leads to the satisfactions of the dual feasibility and primal-dual ratio. The competitive solution space is based on the dual construction given the discounting function φ(x) = e θx -1 e θ -1 where θ > 0 in Algorithm 2. Importantly, we introduce a slackness parameter λ ∈ [0, 1] in the design of D u,t in (28) . The parameter λ controls the size of the competitive space D u,t and further regulates the competitive ratio of LOBM. Given a smaller λ, we can get a larger competitive space D u,t , and so LOBM has more flexibility to exploit the benefits of ML predictions. However, a smaller λ also leads to a smaller competitive ratio shown in the theorem below.Theorem 5.1. Given the maximum bid-budget ratio κ ∈ [0, 1], θ > 0, and the slackness parameter λ ∈ [0, 1], with any ML predictions, LOBM in Algorithm 5 achieves a competitive ratio of Theorem 5.1 shows that LOBM with a slackness parameter λ ∈ [0, 1] can guarantee a competitiveness ratio of η(κ) regardless of the ML prediction quality. The parameter λ ∈ [0, 1] determines the worst-case competitive ratio and the degree of flexibility to exploit the benefit of ML predictions. When λ = 0, there is no competitive ratio guarantee and LOBM reduces to a pure ML-based algorithm. This can also be seen from the inequalities in the competitive solution space (28) , which are all satisfied automatically when λ = 0. On the other hand, when λ = 1, LOBM achieves the highest competitive ratio. When λ increases from 0 to 1, the competitive solution space in (28) varies from whole solution space (with λ = 0) to the smallest competitive solution space (with λ = 1). Therefore, the choice of the slackness parameter λ provides a trade-off between the competitive guarantee and the average performance by adjusting the level of exploiting the ML predictions.EQUATION 
empirical results: 
 We evaluate the empirical performance of MetaAd and LOBM on two applications. The first application is Online Movie Matching where the platform needs to match each query to a movie advertiser with limited budget. The empirical results are obtained based on the MovieLens Dataset [12] . The main empirical results are shown in Table 1 . We compare MetaAd with the algorithms without using ML (Greedy and PrimalDual introduced in Section D.1.1) and show that MetaAd achieves the best worstcase and average performance among them. Additionally, we validate that LOBM with a guarantee of competitive ratio in Theorem 5.1 achieves the best worst-case reward with a good average reward.Other empirical ablation studies can be found in Section D.1.2.The second application is Online VM Placement introduced in Section 3. We generate the bipartite graphs with connections between physical servers and VMs by the Barabási-Albert method [3] and assign utility values according to the prices of Amazon EC2 compute-optimized instances [2] . We defer the empirical results and ablation studies to Appendix D.2.3.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: The training and test details are summarized in Section D.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
conclusion: 
 In this paper, we consider a challenging setting for OBM without the FLM and small-bid assumption. First, we highlight the challenges by proving an upper bound on the competitive ratio for any deterministic algorithms in OBM. Then, we design the first meta algorithm MetaAd that achieves a provable competitive ratios parameterized by the maximum bid-budget ratio κ ∈ [0, 1]. We also extend LOBM under the additional FLM assumption. Additionally, based on the competitive analysis, we propose LOBM to take advantage of ML predictions to improve the performance with a competitive ratio guarantee, followed by its empirical validations.Limitations and Future Directions. While we provide the first provable meta algorithms for OBM with general bids, determining the best choice of the discounting function ϕ remains an open question and an interesting problem for future exploration.Broader impacts. By introducing a provable algorithm for OBM under more general settings, our work has the potential to advance the applications and motivate new algorithms. For applications like advertising, if large budget disparities among offline nodes exist, those with larger initial budgets could have a higher chance of being matched due to their smaller bid-to-budget ratios. This fairness issue, also observed in prior algorithms [23, 4, 24] , warrants further investigation.Example 1. Consider a setting with only one offline node and a total budget of 1. The agent needs to decide whether or not to match an online node with a bid value w u,t ≤ κ, κ ∈ (0, 1] to the offline node for V ≥ 2 rounds. The bid values for the first V -1 rounds are equivalent to ω and sum up to 1 -κ + ϵ where ϵ is infinitely small, so we have ω ∈ (0, (1-κ + ϵ)/ 1-κ+ϵ κ ].The bid value w u,V in the last round is either zero or κ and is not known to the agent. Thus, the constructed example subset is composed of two smaller subsets, i.e.G ′ = G ′ 1 + G ′ 2 .In the example of the subset G ′ 1 , we have w u,V = κ, and in the examples of the subset G ′ 2 , we have w u,V = 0.The offline optimal solutions are different for G ′ 1 and G ′ 2 in Example 1. For G ′ 1 with the last bid value as w u,V = κ, the optimal solution is to skip one of the first (V -1) rounds. In this way, the last online node with bid κ can be matched and the total reward is 1 + ϵ -ω. For G ′ 2 with the last bid value as w u,V = 0, the optimal solution is to match all the online nodes for the first V -1 rounds and obtain a total reward of 1 -κ + ϵ.For the examples in G ′ in Example 1, the optimal online algorithm can be chosen from the following two. First, the algorithm can choose to match the online node to the offline node in all the first (V -1) rounds. This algorithm is optimal for G ′ 2 , but for G ′ 1 with w u,V = κ, the total reward is 1 -κ + ϵ which is less than the offline optimal reward 1 + ϵ -ω. Therefore, the competitive ratio of this algorithm in the worst case is lim ϵ→0 min ω∈(0,(1-κ+ϵ)/⌈ 1-κ+ϵ κ ⌉]1-κ+ϵ 1+ϵ-ω → 1 -κ when ω is infinitely small. Second, the algorithm can choose to skip one round in the first V -1 rounds such that the last online node can be matched if it has a bid value of κ in G ′ 1 . However, for G ′ 2 with w u,V = 0 and the total reward is 1 -κ + ϵ -ω which is less than the optimal reward as 1 -κ + ϵ. Thus, the competitive ratio of this algorithm is lim ϵ→0 min ω∈(0,(1-κ+ϵ)/(⌈ 1-κ+ϵκ ⌉]) 1-κ+ϵ-ω 1-κ+ϵ = 1 -1 ⌈ 1-κ κ ⌉ for κ ∈ (0, 1). When κ = 1, the competitive ratio of this algorithm is min ω∈(0,ϵ) 1-κ+ϵ-ω 1-κ+ϵ = min ω∈(0,ϵ) ϵ-ω ϵ = 0.Therefore, the competitive ratio for any deterministic algorithm forG ′ is max π min G∈G ′ CR(π, G) = max{1 -κ, 1 -1 ⌈ 1-κ κ ⌉ } = 1 -κ for κ ∈ (0, 1), and 0 for κ = 1.Combining both cases of κ ∈ (0, 1) and κ = 1, we get the upper bound of the competitive ratio for any deterministic algorithm for G ′ as 1 -κ, which is also an upper bound of the competitive ratio of any deterministic algorithm for OBM. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: The experiments can be reproduced by a personal computer with CPU.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: We do not foresee negative societal impacts or the need of safeguards due to the theoretical nature of our work.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We didn't foresee the need of safeguards due to the theoretical nature of our work.Answer: [NA] Justification: Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: To prove Theorem A.2, we first prove Lemma 1.Proof of Lemma 1.Proof. The first condition guarantees that the dual variables are feasible. The second condition is to guarantee the competitive performance. Let D * and P * be the optimal dual and primal objectives. If the second condition is satisfied, then we haveEQUATIONwhere the second inequality holds since D * is the minimum dual objective, and the third inequality comes from weak duality. This completes the proof.Proof. To satisfy the primal-dual ratio P t ≥ 1 γ D t , we can get an inequality of α u,t as below.u∈UEQUATIONwherec u,t = t i=1,xi=u w xi,i . Since α u,t = φ( cu,tBu ), we get the condition of φ as below.EQUATIONFurther, since φ is an increasing function, we have the following bound for the discrete sum.EQUATIONwhere the inequality holds by the integral inequalityEQUATIONwhere the first inequality holds since φ ′′ (x) ≤ 0 for x ∈ [0, 1], the second inequality holds by the bid bound κ and another integral inequality In this section, we extend MetaAd to the setting with FLM by allowing offline nodes with insufficient budgets to accept fractional bid values equal to their remaining budgets in their last matching. In other words, by matching an online arrival t to an offline node u ∈ U, the agent receives an actual reward of min{w u,t , b u,t-1 }, where w u,t is the bid value and b u,t-1 is the available budget at the beginning of round t.y x=0 φ(x)dx ≥ N i=1 x i φ( i-1 j=1 x j ) with y = N i=1 x i .Even under the FLM assumption, OBM with general bids is challenging because when an online node t arrives, if the remaining budget b u,t-1 of an offline node u is smaller than the bid w u,t , matching the arrival to this offline node can cause a reward loss of w u,t -b u,t-1 , which increases with the bid value w u,t . With FLM, the greedy algorithm (Greedy) can achieve a competitive ratio of 0.5 [23] . The competitive ratio achieved by a deterministic algorithm in [4] is (1 -κ -1-κ (1+κ) 1/κ ). For OBM with FLM, we use a different meta algorithm as in Algorithm 3. When the remaining budget b u,t-1 for an offline node u is enough to accept arrival t (i.e. b u,t-1 ≥ w u,t ), the scoring strategy is the same as Algorithm 1 which sets the score as s u,t = w u,t ϕ( bu,t-1 Bu ). Nonetheless, the scoring strategy is different from Algorithm 1 when the remaining budget b u,t-1 of an offline node u is insufficient for an online arrival t (i.e. b u,t-1 < w u,t ). Without FLM, Algorithm 1 directly sets the score s u,t as zero to avoid the selection of offline node u. However, FLM allows matching an offline node u to the online arrival t and consuming all the remaining budget b u,t-1 to obtain a reward of b u,t-1 . Thus, Algorithm 3 can be greedier and sets the score as s u,t = b u,t-1 ϕ( bu,t-1 Bu ) to balance the actual reward increment and the budget consumption. Given an increasing function ϕ, the score increases with the remaining budget, and it is still possible to select an offline node with an insufficient but large enough remaining budget.In this section, we provide the competitive ratio of Algorithm 3 for OBM with FLM and discuss the insights and analysis techniques. The competitive ratio is given in Theorem B.1 with its proof deferred to Appendix B.3.To prove the competitive ratio of MetaAd for FLM, we still need to construct dual variables α u , u ∈ U β t , t ∈ [V ], which assists with online matching with a provable competitive ratio. The dual construction procedure is given in Algorithm 4. At each round t, same as the dual construction without FLM in Algorithm 2, β t is set as the score of the selected offline node and α u,t is set as φ( cu,t Bu ). Different from Algorithm 2, α u is set at the end of the algorithm as below to satisfy dual feasibility with the FLM assumption.EQUATIONAlgorithm 4 Dual Construction (with FLM) Require: The function ϕ : where t ∈ T • is the round when budget insufficiency happens. This is to guarantee the dual feasibility[0, 1] → [0, 1], φ(x) = 1 -ϕ(1 -x), ρ ≥ 1. Initialization: ∀u ∈ U, α u,0 = 0, b u,0 = B u , U • = ∅, T • = ∅,β t ≥ b u,t-1 (1 -α u,t-1 ) ≥ w u,t (1 -α u )when the offline node has an insufficient budget for an arrival. Note that the dual increment Λ u = α u -α u,V at the end of the Algorithm 4 can be less than the dual increment at the end of Algorithm 2, thus resulting in a better competitive ratio for OBM with FLM than without FLM.With the constructed dual variables, the competitive ratio of MetaAd for OBM with FLM is given in the next theorem.Theorem B.1. If the function ϕ : [0, 1] → [0, 1] in Algorithm 1 satisfies that given an integer n ≥ 2, ∀i ≤ n -1, φ (i) (x) > 0 and R = max x∈[0,1] φ (n) (x) where φ(x) = 1 -ϕ(1 -x), the competitive ratio of Algorithm 1 is η(κ) = 1 1 + κ n R + max y∈[0,1] ∆(y) + ϕ(κ) ,where∆(y) = φ(y) y -1 y y x=0 φ(x)dx + 1 y n i=1 κ i φ (i-1) (y) -φ (i-1) (0) .Given different φ, we can get concrete competitive algorithms for OBM with FLM. In this paper, we show the example of the competitive algorithm where φ is from the exponential function class. EQUATIONProof. Denote an equivalent bid as wu,t = min{w u,t , b u,t-1 }. To guarantee the primal-dual ratio P t ≥ 1 γ D t , we get the condition as below.u∈UEQUATIONwhere c u,t = t i=1,xi=u wxi,i .replace the manual design of score assignment. More we can utilize an ML model to predict a discounting factor z u,t and set the score as s u,t = w u,t (1 -z u,t ) for matching when the offline node u has a sufficient budget for the online arrival t. That is, we incorporate ML predictions into MetaAd (i.e., LOBM) to explore alternative score assignment strategies that can outperform manual designs on average while still offering guaranteed competitiveness.In learning-augmented online algorithms [31, 21] , there exists an intrinsic trade-off between following ML predictions for average performance improvement and achieving better robustness in the worst case. Such trade-off between average and worst-case performances also exist in learning-augmented OBM ( LOBM). To better control the trade-off, we introduce a slackness parameter λ ∈ [0, 1] to relax the competitiveness requirement while allowing LOBM to improve the average performance through ML-based scoring within the competitive solution space.If we blindly use the ML prediction as the discounting factor for matching, competitive ratio cannot be satisfied due to the lack of worst-case competitiveness for ML predictions. Thus, to ensure that LOBM still offers guaranteed competitiveness, we consider a competitive solution space based on the conditions for dual variables specified in Lemma 1.Based on the competitive analysis with the exponential function class, we design a learning-augmented algorithm (i.e., LOBM) in Algorithm 5, which leverages ML prediction zu,t to improve the average performance while guaranteeing the worst-case competitive ratio. The key idea is to construct dual variables as we solve the primal problem online and utilize the dual variables to calibrate the ML prediction zu,t . In this way, the matching decisions by LOBM are guaranteed to be competitive in the worst case while utilizing the potential benefits of ML predictions.We describe LOBM in Algorithm 5 as follows. At the beginning, we initialize the dual variables as zero. Whenever an online node arrives, the agent receives a ML prediction zu,t indicating the discounting factors for all the offline nodes u ∈ U. Instead of directly using the ML prediction to set the scores and selecting the offline node, LOBM projects the ML prediction zu,t into the competitive space D u,t by solving the following for all u ∈ U,EQUATIONwhich is a key step to ensure the competitive ratio. In order to better utilize the potential benefit of ML predictions, we use the projection operation in (27) to select the discounting factor z u,t out of competitive space D u,t , such that the selected z u,t is the closest to the ML prediction zu,t . Then, the projected value z u,t is used to set the scores s u,t for offline nodes with sufficient budgets for the online arrival t, and the scores for offline nodes with insufficient budgets are set as zero and these offline nodes are appended to U • . The scores based on calibrated ML predictions are then used to select the offline node for matching.As the key design to guarantee the competitive ratio, the competitive space D u,t is based on the conditions for dual variables in Lemma , leading to a bounded ratio of the primal objective to the dual objective at the end of each round. The parameter λ can be used to adjust the bound of primal-dual ratio, leading to different competitive ratios.Next, we need to ensure that conditions in Lemma 1 are always satisfied no matter which offline node u ∈ U is selected at each round t. Thus, we construct the competitive space D u,t as below and Algorithm 5 Learning-Augmented OBM (LOBM, w/o FLM) 1:Initialization: ∀u ∈ U, b u,0 = B u , ∀u ∈ U, α u,0 = 0, β 0 , • • • , β V = 0. 2: for t=1 to V , a new request t ∈ V arrives do 3:Get the ML prediction zu,t , ∀u ∈ UProject zu,t into D u,t in (28) and get z u,t , ∀u ∈ U.For all u ∈ U, if b u,t-1 -w u,t ≥ 0, set score s u,t = w u,t (1 -z u,t ); otherwise, set score s u,t = 0 and append {u | b u,t-1 -w u,t < 0} into U • .if ∀u ∈ U, s u,t = 0 then 7:Skip the online arrival t (x t = null). EQUATIONSince the dual variable β t is set as 1 λρ θ s xt,t after selecting the offline node x t with the highest s u,t and sufficient budgets, β t is no less than 1 λρ θ s u,t = 1 λρ θ w u,t (1 -z u,t ) for any u ∈ U. Thus, as long as the first inequality in ( 28) is satisfied, we always have the dual feasibility β t ≥ w u,t -w u,t α u,t-1 in Lemma 1 if all the offline nodes have sufficient budgets for the arrival t. For the offline nodes with insufficient budgets for the online arrival t, we ensure the dual feasibility β t ≥ w u,t -w u,t α u,t-1 by setting their corresponding dual variable α u as one after the matching process (Line 14 in Algorithm 5).The second inequality in (28) sets a target for the increment of the dual variables α u,t , which forces the dual variable α u,t to be larger when the remaining budget becomes less. In this way, the score of an offline node u with fewer remaining budgets can be set lower to be conservative in consuming budgets. Also, since α u,t is larger when the remaining budget is less, the second inequality in (28) guarantees a large enough dual variable α u,t when u has insufficient budget for an arrival t. This keeps the additional dual increment after the matching process (Line 14 in Algorithm 5) bounded and further guarantees a bounded primal-dual ratio in the second condition of Lemma 1.As we discussed, if the discounting factor z u,t at each round satisfies the inequalities in (28) , the primal variables and the constructed dual variables will satisfy the conditions in Lemma 1, and so a competitive ratio for OBM is guaranteed. The size of the set D u,t is controlled by the hyper-parameter λ: with smaller λ, the size of D u,t becomes larger because the inequalities are easier to be satisfied. We will rigorously prove that D u,t is always non-empty given any λ ∈ [0, 1] to enable feasible competitive solutions that guarantee the competitive ratio bound in (29) in the robustness analysis of LOBM in Section C.2.Given any ML predictions, Algorithm 5 provides a guarantee for the competitive ratio. Nonetheless, the average performance E G [P (π, G)] depends on the ML model that yields the ML prediction. Here, we briefly discuss how to achieve high average performance by training the ML model in an environment that is aware of the design of Algorithm 5. Note first that the projection operation is differentiable while the discrete matching decision is not differentiable. Thus, we apply policy gradient to train the ML model. Once the ML model is trained offline, it can be applied online to provide zu,t as advice for scoring and matching by LOBM (Line 3 in Algorithm 5).Now, we provide a robustness analysis of LOBM and formally show that LOBM always guarantees the competitive ratio.A learning-augmented algorithm is robust if its competitive ratio is guaranteed for any problem instance given arbitrary ML predictions. We show that LOBM is robust in the sense that it offers competitive guarantees regardless of the quality of ML predictions.Theorem C.1. Given the maximum bid-budget ratio κ ∈ [0, 1] and the slackness parameter λ ∈ [0, 1], with any ML predictions, LOBM in Algorithm 5 achieves a competitive ratio ofEQUATIONwhere[x] + = x if x > 0 and [x] + = 0 if x ≤ 0.Theorem C.1 shows that LOBM can guarantee a competitiveness ratio of η(κ) regardless of the ML prediction quality for any slackness parameter λ ∈ [0, 1]. The parameter λ ∈ [0, 1] determines the requirement for the worst-case competitive ratio and the flexibility to exploit the benefit of ML predictions. When λ = 0, there is no competitiveness requirement, the inequalities in the competitive space ( 28) always hold, and LOBM reduces to a pure ML-based algorithm with no competitive ratio guarantee. On the other hand, when λ = 1, LOBM achieves the highest competitive ratio. When λ is flexibly chosen between the competitive solution space also varies from whole solution space (with λ = 0) to the smallest competitive solution space (with λ = 1) in ( 28). Thus, LOBM achieves a flexible trade-off between the competitive guarantee and average performance by varying the levels of trust in ML predictions. • The dual feasibility is satisfied,i.e. ∀u ∈ U, t ∈ [V ], w u,t α u + β t ≥ w u,t .• The primal-dual ratio is guaranteed, i.e. P ≥ ηD.• The solution of projection (28) always exists, i.e. the feasible set of ( 28) is not empty for each round.First, we prove the feasibility of dual variables (The first condition in Lemma 1). If β t = 0 for a round t ∈ [T ], we have either w u,t = 0 or w u,t > 0 and α u = α u,V ≥ 1 holds for a slot u ∈ U by Line 14, so β t = 0 ≥ w u,t (1 -α u ) holds for the dual construction. On the other hand, if β t > 0 holds for round t ∈ [T ], then the score s xt,t must be calculated based on the projected z xt,t . Thus, we haveβ t = 1 λρ θ s xt,t ≥ 1 λρ θ s u,t = 1 λρ θ w u,t (1 -z u,t ) ≥ w u,t (1 -α u,t ) ≥ w xt,t (1 -α u ) where ρ θ = e θ -1e θ and the second inequality holds by the first inequality of the set (28) . This proves the feasibility of the dual variables Next, we prove the primal-dual ratio (the second condition in Lemma 1 ) is satisfied. At round t, if no vertex is selected for a vertex t, the primal objective P and dual objective D do not increase. Otherwise, the primal objective increases by w xt,t and dual objective increases byB xt (α xt,t - α xt-1,t-1 ) + β t = wx t ,t λρ θ + B xt δ xt,t where δ xt,t = exp(θ(1-bx t ,t-1 /Bx t )) e θ -1 (exp( θwx t ,t Bx t ) -1 - wx t ,t Bx t). By Line 14 at the end of Algorithm 5, the dual variable α u,V increases to α u by Λ u = α u -α u,V . Thus, the dual objective can be written asD = 1 λρ θ V t=1 w xt,t + V t=1 B xt δ xt,t + u∈U B u Λ u ,and further we haveEQUATIONTo bound the right-hand-side, we haveEQUATIONFor each u ∈ U, we sum up B u δ u,t and getEQUATIONwhere the first inequality holds because e θx x -1x -1 is an increasing function for x ∈ [0, 1], θ ∈ [0, 1], the second inequality holds sinceV t=1,xt=u exp(θ(1 - bu,t-1 Bu )) • wu,t Bu = V t=1,xt=u exp(θ cu,t Bu ) • wu,t Bu ≤ c u,V Bu x=0 exp(θx)dx = 1 θ (exp(θ c u,VBu ) -1), and the last inequality holds because B u exp(θc u,V Bu )-1 θ(e θ -1) = c u,V • exp(θ c u,V Bu )-1 θ(e θ -1) c u,V Bu ≤ c u,V • 1 θ .By summing up all bidders in U, we getEQUATION)Continuing with inequality (30), we haveEQUATIONThus, by moving terms, we haveEQUATION)This proves the second condition in Theorem 1.Finally, we prove that the solution of the projection into (28) always exists, i.e. the feasible set of ( 28) is not empty for each round. To do this, we prove by induction thatEQUATIONis always feasible for the set (28) . For the first round, the initialized dual variable α u,0 = 0, the initialized remaining budget b u,0 = B u , so we have where the inequality holds because λ 1 ≥ λ, so the second inequality of ( 28) holds for t = 1.EQUATIONAlso, it holds thatEQUATIONwhere the first inequality holds since λ 1 ≤ 1 and the second inequality holds since λ ≤ 1. Thus, we can prove the first inequality of ( 28) holds for initialization.Then if the constraints are satisfied for the round before arrival t, then we haveα u,t-1 ≥ exp(θ(1-bu,t-1/Bu))-1 e θ -1, and thus we haveEQUATIONwhere the inequality holds because λ 1 ≥ λ. Thus the second inequality of (28) holds.Then, since α u,t-1 ≥ exp(θ(1-bu,t-1/Bu))-1 e θ -1, we haveEQUATIONwhere the inequality holds since λ ≤ 1 and λ 1 ≤ 1. Thus we prove the first inequality of (28) holds.In conclusion, we can always find a feasible dual variable update z † u,t in the projection set (28) .To complement the theoretical analysis, we validate the empirical benefits of proposed algorithms by conducting numerical experiments for an online movie matching application.We evaluate the performances of our algorithms on the online movie matching application based on the MovieLens Dataset [12] .In the application of online movie matching, each movie (i.e., an offline node) has a maximum budget set by advertisers. Once an online query arrives, the bid values of the query for all the movies are revealed to the matching platform agent. The platform agent needs to match a movie to each query, generating a reward equivalent to the bid value and consuming a budget of the bid value from the total budget of the matched movie. The bid value is determined by the relevance of the movie and the query. For example, if a movie is more relevant to the online query, there is a potentially higher value. The goal of the advertising platform is to maximize the total reward while satisfying the budget constraints of each movie. In this application, the platform agent does not allow a fractional fee for any matching. Thus, this matching problem is a OBM without FLM.We run the online movie matching application based on a real dataset of MovieLens [12] . The MovieLens dataset provides data on the relevance of movies and users. We generate bipartite graphs, each with U = 10 offline nodes (movies) and V = 100 online nodes (queries/users) based on the MovieLens dataset. For each graph instance, we sample 10 movies uniformly without replacement and 100 users uniformly with replacement. A bid value scaled based on relevance is assigned to each edge between the offline node and the online node. The total budget for each offline node is sampled from a normal distribution with a mean of 1 and a standard deviation of 0.1, and the maximum bid value is 0.1 (i.e., κ = 0.1). We generate 10k, 1k, and 1k samples of graph instances based on the MovieLens dataset for training, validation and testing, respectively. To test the ML performance with out-of-distribution/adversarial examples, we also create examples by modifying 10% examples in the testing dataset and randomly removing edges and/or rescaling the weights.We compare our algorithms with the most common baselines for OBM as listed below.• OPT: The offline optimal solution is obtained using Gurobi [11] for each graph instance.• Greedy: The greedy algorithm [23] matches an online node to the available offline node that is connected to the node and has the highest bid value. Greedy has a strong empirical performance and is a special case of MetaAd with θ → ∞. • PrimalDual: PrimalDual [23] calculates the scores of each bidder for each online node based on both the bid values and the remaining budgets, and then selects for an online node the available bidder with the highest score. It is a special case of MetaAd with θ → 1. • ML: A policy-gradient algorithm that solves the OBM problem [1] . The inputs to the policy model are the available history information including the current bid value, the remaining budget of each offline node and the average matched bid value.We evaluate the performances of MetaAd with the discounting function φ(x) = e θx -1 e θ -1 and LOBM in Algorithm 5. The illustration of MetaAd for round t is shown in Figure 3(a) . LOBM-λ is LOBM with the slackness parameter λ in the competitive solution space (28) . The illustration of LOBM for round t is given in Figure 3(b) . The The optimal parameter θ governing the level of conservativeness in MetaAd is tuned based on the validation dataset. We also evaluate the performance of MetaAd under different choices of θ, and evaluate LOBM with ML predictions under different choices of the hyper-parameter λ ∈ [0, 1] and use LOBM-λ to represent LOBM with the hyper-parameter λ in D u,t in (28) . For a fair comparison, we use the same neural architecture as ML in LOBM. The neural network has two layers, each with 200 hidden neurons. The neural networks are trained by Adam optimizer with a learning rate of 10 -3 for 50 epochs. The training process on a laptop takes around 1 hour, while the inference process over each instance takes less than one second.The empirical worst-case and average reward (normalized by the optimal reward) based on the MovieLens dataset are shown in Table 2 . In this table, the parameter θ of MetaAd is 0.7 by default which is obtained by tuning on a validation dataset. We find that MetaAd can achieve a higher worst-case reward ratio than alternative competitive algorithms without predictions (i.e., Greedy and PrimalDual). Through training, ML can achieve a higher average reward than competitive algorithms without predictions. However, due to the existence of out-of-distribution testing examples, ML has a lower worst-case reward ratio than competitive algorithms that have theoretical worst-case performance guarantees. LOBM can significantly improve the worst-case performance of ML. This is because the projection of ML predictions onto the competitive solution space in 28 corrects low-quality ML predictions. Interestingly, LOBM with λ = 0.8 achieves the best empirical worstcase and average performance, demonstrating the superiority of LOBM despite that its competitive ratio is lower than that of MetaAd. The high average performance of LOBM shows that LOBM can effectively utilize the benefits of good ML predictions to improve the average performance while offering guaranteed competitiveness. Importantly, when λ ∈ [0, 1] decreases, the requirements for the worst-case performance are more relaxed, and hence LOBM achieves a higher average reward but a lower worst-case reward.The effects of θ in MetaAd. To validate the effects of the hyper-parameter θ on the performance of MetaAd with φ(x) = e θx -1 e θ -1 , we give more details of the performances of MetaAd under different choices of θ in Fig. 4(a) . We give both the empirical worst-case and average reward of MetaAd with different choices of θ. The results show that the average reward of MetaAd is not significantly affected by the choice of θ, but θ has a large effect on the empirical worst-case reward. This is because θ controls the conservativeness of MetaAd and hence is crucial for the worst-case competitive ratio when κ ̸ = 0 as discussed in Section 4.2. More specifically, a larger worst-case reward can be obtained with a smaller θ for the MovieLens dataset. The reason is that a higher level of conservativeness is needed when the maximum bid-budget ratio κ is not zero.The effects of θ and λ in LOBM. The empirical worst-case and average rewards of LOBM with different choices of θ and λ are provided in Fig. 4 (b) and Fig. 4 (c), respectively. Different choices of θ yield different competitive solution spaces, while the choices of λ specify the relaxed robustness requirements of the worst-case competitive ratio for LOBM. Thus, we can get a different competitive ratio for LOBM by setting different θ and λ as shown in Theorem C.1. These theoretical findings are validated by our numerical results. , when λ = 0, the inequalities in the robust region (28) always hold, and hence LOBM reduces to pure ML and gives the same competitive ratio and average reward as ML. When λ = 1, LOBM guarantees the same competitive ratio as MetaAd, but does not necessarily always follow the solutions of MetaAd for each problem instance, since there exist other solutions that also satisfy the robustness requirement for certain problem instances. Therefore, when λ = 1, the competitive ratio and average reward of LOBM are close to but can be higher than those of MetaAd when the ML model used by LOBM is well trained. When λ lies between 0 and 1, we can find that for some choices of θ, LOBM can achieve an even better average reward than ML. This improvement comes from the fact that the competitive solution space in (28) can correct some low-quality ML predictions on certain problem instances. Also, for certain choices of θ, LOBM can empirically achieve a better worst-case reward than MetaAd, because LOBM can perform well due to ML predictions on some problem instances where MetaAd does not perform well. This observation validates that LOBM can effectively utilize the ML predictions to improve the average performance while guaranteeing a worst-case competitive ratio.Tail reward performance. Last but not least, to evaluate the performance on adversarial/out-ofdistribution instances, we show in Fig. 5 the reward (normalized by the offline optimal reward) at high percentiles from 95% to 100%. We observe that the reward of ML quickly decreases when the percentile becomes higher and becomes the lowest at the high percentiles (larger than 98%), showing that ML is vulnerable to adversarial instances. Due to the worst-case competitiveness guarantees, MetaAd achieves a relatively higher reward even at high percentiles. Moreover, since LOBM guarantees the worst-case performance by the competitive solution space, the rewards of LOBM with different λ are all higher than ML at high percentiles. The high percentile reward of LOBM increases with λ because a larger choice of λ guarantees a higher competitive ratio according to Theorem C.1. Interestingly, we can find that the rewards of LOBM at high percentiles are even larger than MetaAd when λ is 0.6 or 0.8. This validates that when the ML model is well trained to provide high-quality predictions, LOBM can become more powerful and explore better matching decisions than the purely manual design of MetaAd.Virtual Machine (VM) placement is the process of matching the newly-created VMs to the most suitable servers in cloud data centers [13, 22, 26] . In this problem, once an end user send a VM request, the cloud operator needs to select a physical server for it. Different VM requests require different amount of physical computing resources. For example, the compute-optimized instances of Amazon EC2 [2] have different sizes, each requires different amount of computing resources. Due to the hardware heterogeneity [27] , the available computing resources on different servers are different and the utilities of different servers can also be different. Our goal is to optimize the total utility of VM placement.We consider a setup where the cloud manager allocates V VMs (online nodes) to U different physical servers (offline nodes). Based on the requirement of VMs, a VM request can be matched to a subset of the physical servers. The connections between VM requests and physical servers are represented by a bipartite graph G. A VM request t at round t, t ≤ V has a computing load in the number of computing units denoted as z t . Each server u ∈ U has a limited capacity of the computing units (e.g., virtual cores) denoted as B ′ u . If the VM request v is placed on a server u, the manager receives a utility proportional to the computing load w u,t = r u • z t where r u is the utility of one computing unit on server u. Denoting x u,t ∈ {0, 1} as the decision on whether to place request t on server u, the objective of the VM placement problem can be formulated as an OBM:EQUATIONwhere w u,t = r u • z t and B u = r u • B ′ u . In this OBM, the VM request is not divisible, which means fractional matching is not allowed at any time and FLM does not apply.In the experiment, the cloud manager allocates V = 100 VMs (online nodes) to U = 10 different physical servers (offline nodes). We randomly generate graphs by Barabási-Albert method [3] . For an online node v, we sample its degree (the number of offline nodes connected to it) by a Binomial distribution B(U, d v /U ) where d v is the average degree of node v. The average degrees of online nodes are chosen from 4, 2, and 0.5. Each server has a capacity on the number of the computing units. The capacity B ′ u is sampled from a uniform distribution on the range [20, 40] . The computing load of a VM request is sampled from a uniform distribution on the range [1, 4] . The utility per computing unit r u is the price of a computing unit on the server u. We choose the price (in dollars) in the range [0.08, 0.12] according to the prices of the compute-optimized instances on Amazon EC2 rewards are normalized by optimal rewards. We compare MetaAd with the algorithms without using ML (Greedy and PrimalDual introduced in Section D.1.1). Additionally, we compare our learning-augmented algorithm LOBM with the ML algorithm. LOBM-λ means LOBM with a slackness parameter λ in Eqn. (28) . [2] . We randomly generate 20k, 1k, and 1k samples of BA graphs for training, validation and testing, respectively.We compare our algorithms with baselines for OBM listed below. We compare our algorithms with the most common baselines for OBM as listed below.• OPT: The offline optimal solution is obtained using Gurobi [11] for each graph instance.• Greedy: The greedy algorithm [23] matches an online node to the available offline node that is connected to the node and has the highest bid value. Greedy has a strong empirical performance and is a special case of MetaAd with θ → ∞. • PrimalDual: PrimalDual [23] calculates the scores of each bidder for each online node based on both the bid values and the remaining budgets, and then selects for an online node the available bidder with the highest score. It is a special case of MetaAd with θ → 1. • ML: A policy-gradient algorithm that solves the OBM problem [1] . The inputs to the policy model are the available history information including the current bid value, the remaining budget of each offline node and the average matched bid value.For learning-based algorithms, we use the neural networks which have two layers, each with 200 hidden neurons for fair comparison. The neural networks are trained by Adam optimizer with a learning rate of 10 -3 for 50 epochs. Likewise, we use LOBM-λ to refer to LOBM with a hyper-parameter λ governing the competitiveness requirement in (28) .We first show Worst-case and average rewards of different algorithms for VM placement in Table 3 . We observe that MetaAd achieves a higher worst-case and average reward than the the other algorithms without using ML (i.e., Greedy and PrimalDual). This is because MetaAd is more flexible to adjust the discounting function. Additionally, we can find that ML predictions can significantly improve the average performance compared to algorithms without ML predictions. In particular, ML even has an empirically higher worst-case reward than Greedy and PrimalDual, although it does not have a theoretical guarantee in terms of the worst-case competitive ratio. Note also that the worstcase reward ratio on the finite testing dataset is an empirical evaluation, and the true competitive ratio of ML without the theoretical guarantee can be even much lower than presented in the table. Importantly, we can find that LOBM can achieve a high average performance while guaranteeing a worst-case competitive ratio theoretically as shown in Theorem 5.1. Moreover, LOBM achieves the highest empirical worst-case reward among all the algorithms, because LOBM can effectively correct low-quality ML predictions for some difficult testing examples by learning augmented design and meanwhile also leverage good ML predictions to improve the performance for other testing examples.Effects of θ and λ. Next, we give the ablation study of MetaAd and LOBM for different choices of parameters θ and λ in Fig. 6 . The parameter θ is the constant in the exponential discounting function and the parameter λ is the slackness parameter in the competitive space in Eqn. (28) . First, we give the worst-case and average rewards of MetaAd under different choices of θ in Fig. 6 (a). We can find that compared with PrimalDual (i.e., θ = 1), MetaAd can further improve the worst-case performance for the general bid settings by decreasing θ which is consistent with the competitive analysis in Corollary4.2.2.Moreover, we provide the worst-case and average rewards for LOBM under different θ and λ in Fig. 6 (b) and Fig. 6 (c), respectively. The results show that when λ = 0, LOBM reduces to pure ML and achieves the same worst-case and average performances as ML. The worst-case performance can be improved by increasing λ since LOBM with a larger λ has a higher competitive ratio guarantee according to Theorem C.1. However, the average performance can be affected when λ becomes larger, because a larger λ results in a smaller solution space for increased robustness and hence may exclude some solutions with high rewards for average cases. When λ = 1, LOBM shares the same theoretical competitive ratio bound as MetaAd, but it can still achieve better empirical worst-case and average rewards than MetaAd when the ML model is well trained.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.In this paper, two graphs with different orders of online nodes are considered as two different graphs. 


Decision: Majority of reviewers are positive about the paper. They think the paper's idea is novel, theoretical results are sound, and the paper is well-written. The reviewers do have some concerns on the practical applicability of the results, and I have similar concerns. The paper could be further improved if these concerns can be addressed.

Reviews: review: paper_summary: paper_summary: **Problem Studied**

This paper studies the online budgeted matching problem (also known as AdWords). The input to the problem is a bipartite graph, where one side of the graph (the advertisers) is known in advance. Each advertiser has a budget, which is the maximum amount of money they are able to spend. The nodes on the other side of the graph (the ad impressions) arrive one by one in an online manner. When an online node arrives, each advertiser submits a bid, which is the amount they are willing to pay for the ad impression. The algorithm then irrevocably decides which advertiser to match the impression to, and the advertiser pays their bid. The goal of the algorithm is to maximize the total amount of money that is spent.

**Main Results/Contributions**

Adwords has been most commonly studied under a "small-bids" assumption, which essentially states that the ratio of the bid of any advertiser to their budget is small. Under this assumption, there are deterministic algorithms which achieve a $1-\frac{1}{e}$ competitive ratio. This paper studies Adwords under general bids. The main results are:
1. An upper bound on the competitive ratio of any deterministic algorithm parameterized by the bid-budget ratio, and
2. A "meta algorithm" which is parameterized by a discounting function $\phi$, and a competitive ratio bound for the algorithm that is parameterized by some properties of $\phi$ and the bid-budget ratio.
strength_weakness: strength_weakness: The main criticism I have of the paper is that it is unclear why it is useful to study Adwords in the setting with general bids and without the FLM assumption. The setting of general bids makes sense to me. However (and please correct me if I am wrong), it seems like the FLM assumption is the same as assuming that the bid of any advertiser cannot exceed their remaining budget. This assumption seems very reasonable to me; why would any advertiser submit a bid that is greater than their remaining budget? In any case, since the algorithm knows the total budgets of the advertisers, it could just prevent an advertiser from bidding above their remaining budget.
questions: questions: 1. Why is it interesting to study the setting with general bids and no FLM? (see above)
2. In the paper "AdWords in a Panorama" [10], the authors give a 0.5016-competitive algorithm for Adwords with general bids. However, since the current paper claims to be the first to give a competitive algorithm for Adwords with general bids and without the FLM assumption, it must be the case that [10] uses the FLM assumption. Can you clarify where [10] needs to use the FLM assumption? I think this would be useful to understand the importance of the FLM assumption.
limitations: limitations: Yes.
paper_summary: paper_summary: The paper studies the classic online budgeted matching problem (OBM), relaxing the small bid assumption and the FLM assumption. Precisely, an upper bound on the competitive ratio is proven for any deterministic algorithms. Then a framework of algorithms for OBM is proposed to solve OBM with general bids, which uses various discounting function to represent the degree of budget insufficiency given a bid-budget ratio. Correpondingly, the competitive ratios of the algorithms are proved. Finally, the learning augmented algorithm, LOBM, is extended under the FLM assumption, achieving better performance..
strength_weakness: strength_weakness: 1. In the motivation scenario, such as online advertising, online service matching, revenue management, the small bid assumption usually holds. This means relaxing such an assumption may be not much motivative.
questions: questions: NA
limitations: limitations: NA
paper_summary: paper_summary: This paper studies the online budgeted matching problem without the small-budget or Fractional Last Matching (FLM) assumption. The authors propose a meta algorithm called MetaAd, which uses a discount function to assign each node with a score. The authors perform competitive analysis for their meta algorithm and show how the algorithm performs under different discount functions. They also provide theoretical competitive ratios for the FLM setting, and a learning-augmented setting.
strength_weakness: strength_weakness: 1. My main concern for this work lies in its contribution. More specifically,
- I feel that the main contribution of the meta algorithm is in the introduction of the discounting function $\phi$ and using it to regulate the matching decision. However, as the authors suggest, how to choose the discounting function is unclear. Without a clear understanding of how to choose the best $\phi$, the proposed algorithm will be much less practical.
- Following the points above, I also find the competitive ratios provided in Theorem 4.2 and Corollary 4.2.2, 4.2.3 a bit difficult to digest. While the authors provided numerical evaluations of these competitive ratios, it is still unclear why the authors decided to pick the functional form $C(\exp(\theta x) -1)$ and $C x^2$ and how the constants $C$ are determined. As a result, evaluating how well the meta algorithm actually performs become less straightforward.
- Since the main proof techniques come from primal-dual analysis, I also wonder whether the proof also contains technical novelty.

2. No numerical experiments are provided in the main body of the paper. On a related note, I also have concerns over the practicality of such an algorithm to real-world ads systems due to (i) lack of knowledge of the discounting function; (ii) scalability of the problem, especially when the node set can have enormous size. I wonder if the authors might also comment on these.
questions: questions: See weakness.
limitations: limitations: See weakness.
paper_summary: paper_summary: This paper addresses the Online Budgeted Matching (OBM) problem with general bids, which is fundamental in applications like online advertising and resource allocation. Traditional algorithms typically assume a very small bid-to-budget ratio κ, limiting their practicality. The authors remove the Fractional Last Matching (FLM) assumption, which allows for partial bids, and present a novel meta-algorithm called MetaAd. MetaAd is designed to adapt to different bid-to-budget ratios, achieving provable competitive ratios. The paper establishes an upper bound on the competitive ratio for any deterministic online algorithm. By introducing a general discounting function that adjusts based on the remaining budget, MetaAd matches offline nodes with the largest discounted scores. The algorithm’s effectiveness is demonstrated through theoretical proofs and numerical experiments, showing non-zero competitive ratios for κ in the range [0, 1). Additionally, the paper extends MetaAd to the FLM setting, achieving provable competitive ratios and improving the flexibility of the algorithm. Finally, the authors apply their competitive analysis to design a learning-augmented algorithm, LOBM, which leverages machine learning predictions to enhance average performance while maintaining a competitive ratio guarantee. The empirical validation on an online movie matching scenario demonstrates the practical benefits of the proposed approaches.
strength_weakness: strength_weakness: Originality
While the paper introduces innovative approaches, its novelty primarily stems from the combination and adaptation of existing techniques rather than entirely new methodologies. The removal of the FLM assumption and the introduction of the MetaAd algorithm, although significant, build on a foundation of well-established concepts in online matching and competitive analysis. To enhance originality, the authors could explicitly discuss how their contributions fundamentally differ from prior work beyond the removal of specific assumptions. For instance, more emphasis on the unique aspects of their discounting function ϕ(x) and its derivation could underscore the novel elements of their approach.

Quality
The theoretical analysis is robust, but the empirical validation lacks breadth. The experiments focus on a single application scenario (online movie matching), which limits the generalizability of the results. Expanding the experimental evaluation to include a broader range of real-world applications would strengthen the paper’s claims and demonstrate the versatility of the proposed algorithms. For instance, additional experiments in online advertising or resource allocation contexts would provide a more comprehensive evaluation of MetaAd's performance. Moreover, while the paper provides clear proofs, some parts could be made more accessible by including step-by-step explanations, especially in complex derivations such as the proof of Proposition 4.1.

Clarity
Although the paper is generally well-organized, certain sections, particularly those involving complex theoretical concepts, could benefit from additional explanatory figures or diagrams. For example, visual aids illustrating the MetaAd algorithm's decision-making process and its competitive ratio calculations would enhance understanding. Additionally, some technical terms and mathematical notations could be more thoroughly explained to ensure accessibility to a broader audience. Clarifying the notation and providing more intuitive explanations for key concepts such as the discounting function ϕ(x) and its impact on the competitive ratio would help readers better grasp the core ideas.

Significance
The paper’s significance is somewhat limited by the scope of its empirical validation. While the theoretical contributions are substantial, the practical impact could be more convincingly demonstrated through a wider array of applications. Focusing on a single scenario limits the immediate relevance to other domains, potentially reducing the paper's broader appeal. To maximize its significance, the paper could include more diverse examples and discuss potential real-world implications in greater detail. For instance, illustrating how the MetaAd algorithm can be adapted and applied to various domains such as dynamic pricing or network routing would highlight its broader applicability and impact.
questions: questions: 1. In Section 2, you mention several existing algorithms for OBM. Could you provide a specific example comparing MetaAd’s performance and approach to one of these algorithms under the same conditions?
2. In the derivation of the discounting function ϕ(x) on page 5, could you include a step-by-step derivation or an illustrative example to clarify how ϕ(x) is constructed and why it is effective in maintaining competitive ratios?
3. In Section 4.2, you extend MetaAd to the FLM setting. Can you explain, with a specific example, how the algorithm adjusts when dealing with fractional bids? A flowchart or diagram showing this process would be helpful.
4. Your experiments focus on an online movie matching scenario. Could you provide results from a secondary domain, such as an online advertising campaign, where the budget constraints vary significantly? Including statistical metrics like precision and recall in this context would strengthen the empirical validation.
5. On page 8, you discuss the impact of κ on the competitive ratio. Could you include a graph showing how the competitive ratio changes with varying values of κ?
6. In your conclusion, you briefly touch on potential applications of MetaAd. Could you expand this section to include a detailed case study showing MetaAd’s implementation in a dynamic pricing model or a network routing problem?
7. Can you conduct a sensitivity analysis to show how changes in key parameters, such as the initial budget or the bid distribution, affect the algorithm’s performance?
8. Complex processes, such as the decision-making flow in MetaAd, could be better understood with visual aids. Could you create a figure or diagram that illustrates the algorithm’s workflow, including how decisions are made at each step in Appendix?
limitations: limitations: The authors acknowledge several limitations in their work. The authors did not explicitly discuss the potential negative societal impacts of their work. The paper does not discuss the potential impact on market competition. Favoring well-funded advertisers could lead to monopolistic behaviors and harm smaller competitors. Strategies to maintain a balanced competitive environment should be considered, such as setting caps on budget allocations or implementing measures to support smaller advertisers.

Comments: comment: Thank you very much for reading our rebuttal. We're glad that we have addressed your concerns.
Thank you to the authors for their thorough rebuttal, which has addressed most of my concerns. I will maintain my positive rating and raise my confidence level to 5.
Thanks for your response.
Dear Reviewer,

Thank you very much for taking the valuable time to review our paper. We hope our responses have satisfactorily addressed your concerns. As the discussion deadline approaches, we are more than pleased to answer any remaining questions you may have.
Dear Reviewer,

Thank you very much for taking the valuable time to review our paper. We hope our responses have satisfactorily addressed your concerns. As the discussion deadline approaches, we are more than pleased to answer any remaining questions you may have.
Dear Reviewer,

Thank you very much for taking the valuable time to review our paper. We hope our responses have satisfactorily addressed your concerns. As the discussion deadline is about to conclude, we are more than pleased to answer any remaining questions you may have.
Thank you very much for taking the time to consider our responses! We’re glad to have addressed your concerns, and we appreciate your decision to increase the score. Please don’t hesitate to let us know if you have any remaining questions.
Thank you for the detailed response! It is very helpful and I appreciate it. The authors have addressed my main question, and I have decided to increase my score to a 6.