Online Budgeted Matching with General Bids
Authors: Jianyi Yang
Pengfei Li
Adam Wierman
Shaolei Ren
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Budgeted Matching
General Bids
Competitive Ratio
Primary area: online_learning

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.

Online Budgeted Matching with General Bids
Jianyi Yang
Pengfei Li University of California, Riverside Riverside, CA, USA pli081@ucch 11i081Qucr.edu
University of Houston Houston, TX, USA jyang71@central uh. edu
Adam Wierman
Shaolei Ren University of California, Riverside Riverside, CA, USA shaolei@ucr.edt
California Institute of Technology
Pasadena, CA, USA
adamv0caltech.co edu
Abstract
Online Budgeted Matching (OBM) is 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 (x) 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 k 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 E [0, 1J. As a by-product, we extend MetaAd to the FLM setting and get provable competitive algorithms. Finally, we apply competitive analysis to the design learning- augmented algorithms.
Introduction
Online Budgeted Matching (OBM) with general bids fundamental online optimization problem that generalizes to many important settings, such as online bipartite matching and Adwords with equal bids (23]. has applications in various domains, including online advertising, online resource OBM is defined on a bipartite graph with a set of offline nodes (bidders) and set of online nodes (queries). The task is select an available offline node to match with an online query in each round. When an offline node is matched an online node, bid value subtracted from the budget of the offline node, and 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 maximize the total reward throughout the entire online matching process.
allocation, and revenue management among others [5 16 32
OBM 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 λ - O. That is, while the bid values can vary arbitrarily, the size of each individual bid infinitely small compared to each offline node's budget, and there always enough budget for matching. Under this assumption, the first online algorithm was provided by [4].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 44 77. 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 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 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 30 aim to achieve competitive ratio greater than 1/2 under various settings and/or using randomized algorithms. Although FL.M 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 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.
other studies 4 15
29
Despite its practical relevance and theoretical importance, OBM with general bids has remained 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 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 FLMM 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- - K. achieved by any deterministic online algorithm, where k E [0, 1] is the maximum bid-budget ratio.
In this paper, we address OBM without the small-bid or FLM assumptions and design meta algorithm called MetaAd, which adapts 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 general discounting function, which is then used to select the offline node. The discounting function evaluates the degree of budget insufficiency given bid-budget ratio E [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., K- - 0), Metaad recovers the optimal competitive ratio of 1 e. Furthermore, we show that MetaAd, with discounting functions from the exponential and polynomial function classes, achieves a positive competitive ratio for K E [0. 1). As an extension, we adapt the design of MetaAd to the FLM setting, resulting in meta-algorithm with provable competitive ratios for E [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 FL.. Finally, we apply our competitive analysis to the design of LOBM, a augmeented algorithm for OBM, which enhances average performance while still guaranteeing competitive ratio (Theorem (.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.
Contributions:
2 Related Work
OBM originates from the online bipartite matching problem defined by 19
30 years ago. In 2007,
24 generalized the online b- 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/c, which is also the optimal competitive ratio under the mid 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 - !. Subsequently, 77) gives 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] g 6 [4 25
2

---

It is known to be very challenging to go beyond the small-bid bid assumption and develop non-trivial competitive ratio for OBM with general bids in an adversarial setting. Recently, [0] points out the inherent difficulty of OBM with general bids and explains the necessity of the assumption of FLMM is needed in easing up the challenges. With the FL.M assumption, a greedy algorithm can achieve a competitive ratio of 1 1/2. Additionally, deterministic algorithm proposed in E achieves a competitive ratio of (1 K - 1-N (T+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 semi-random algorithm that achieves a competitive ratio of O. 0,5016, which is known as the best competitive ratio achieved by randomized algorithms up to now. Besides, 300 extends the random algorithm of Ranking to OBM and achieves a competitive ratio of 1 - 1/c with 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 2) parameterized by the maximum bid bid-budget ratios K, which relies on a strong assumption that the bids are decomposable (i.e. Wu, = We w...
1-x
Despite the progress on the OBM settings with FLM, OBM without FLM has remained 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 loss equivalent the leftover budget. (20] considers multi-tier budget constraints with laminar structure and provides a competitive ratio without FLM, but the result does not apply to the settings without the laminar structure. Additionally, [8 proves an online randomized algorithm with the competitive ratio (in expectation) upper bound of 0.612, an upper bound for deterministic algorithms still lacking formally evaluate the difficulty of OBM without FLM.
3 Problem Formulation
We consider OBM with general bids. Specifically, there is a bipartite graph described as G(U, V, E), where the vertices u (i.e. offline nodes or bidders) are fixed and the vertices E V (i.e. online nodes or queries) arrive sequentially. The edge corresponding to vertices u E U and v E V has a bid value Wa.r 2 0 which is the amount the offiin node u would like to pay for the online node if matched. The sizes of the vertex sets are denoted as |4|| = U and |V] = V. respectively. We index each online node by its arriving order, i.e. online node arrives the 1-th round.
At the beginning, each offline node u E l has an initial budget 6w.0 = B, 2 O, which is the maximum amount the offline node can pay in total. At round t, query t E V arrives, the edges connected to this arrival are revealed, and the agent chooses to match the arrival to an available offline node from Ug = {u U Wa,t >> 0, bu.1-1 2 Wu,e} skip this query without any matching. We denote the agent's ' action as D2 E U4 U [mill], where "null" represents skipping this arrival. If at round t, an offline node x, is matched to the query t, reward r, Wa.,t is carned and bid value Wx,,t3 for the other offline nodes * F4, the budget remains unchanged bu.a bu,t-1- If x4 = null, reward is earned, i.e. r,- 0 and the budgets of all offline nodes remain the same as the last round, i.e. bu, = bu,e-1 Yu E U. The cumulative consumed budget at the end of round is denoted as Ca.t Ba bu,t, Vu U and
Wa,, is charged from the offline node F2, i.e., b = b
t E [V]. The agent aims to maximize the total reward P = Σ Tr 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 ( where P the primal objective and 1) the dual objective. While we only need to solve the primal problem for OBM, we present the dual problem with dual variables au, u E l and Br, t E V to facilitate the subsequent algorithm design and analysis.
max P=
Σ
Watt
min
D: EB
Buy Σ
3
NEl
V
s.t. Vu E U,)
Σ
Watt S Bur
s.t. Vu E U t E [V], Wa, + 31 2 Wr,t. (I)
[=1
Vi E [V,,
Σ Fu,t S 1,
Eue U, a, 2 0,
uEU
Yu E U U E [V], Lu,t 2 0.
WE [V] 3, 2 0.
3

---

A common performance metric for online algorithms is the competitive ratio defined as
min P(G)/P"(G))
(2)
GEg
where the minimization is taken over the set of all possible bipartite graphs 9 P(G) Σ Wast
the total reward obtained by an (online) algorithm for a graph E 9, and =G) is the corresponding offline optimal total reward with zz being the offline optimal solution to ①
=1=1 Waj
Next, we formally define the bid-budget ratio [0, 1] in Definition I which is the maximum ratio of the bid value of an offline node to its total budget. We use 17k)) to denote the competitive ratio of an algorithm for OBM with bid-budget ratio Definition 1 (Bid-budget ratio). The bid- bid-budget ratio E [0, for an example G(U,V, E) is defined as A = SUV B
assume FLM which allows for accepting partial bids when remaining budget is insufficient (i.e. modifying each bid Wu, to T. min Ww,t, bu,t-1) given the remaining budget bu. 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 FL.M assumptions do not hold in many real-world applications as illustrated by the following examples:
Many previous works [23
24 13
Online VM placement. In this problem, cloud manager allocates virtual machines (VMs, online nodes) to heterogeneous physical servers (offline nodes), each with computing resource capacity of B3 TO 28). When a VM request with a computing load of arrives, the manager assigns it to a server. the VM is placed on server u, the manager receives a utility of Wa,v = ruze due to the heterogeneity of servers. The goal is to maximize the total utility Σ Eneu Lu, subject to the computing resource constraint Σ ut $ B", for each server u. which can also be written as EV= Wa. S B, with B = B. In this problem, VMs are not divisible and consume up non-negligible portion of the server capacity. violating both the small-bid and FLM assumptions. Inventory management with indivisible goods. Here, manager must match several indivisible goods (online nodes) to various resouree nodes (offline nodes), each with 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 i. can occupy a substantial portion of the resource node's capacity, Wa,t. The goal is to maximize the total utilization ΣY= Eneu Wu,tDu,t subject to the
capacity constraint --1 Wn, 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 x E [o, 1] which can reduce to many concrete competitive algorithms.
4 MetaAd: Meta Algorithm for OBM
4.1 An Upper Bound on the Competitive Ratio
In the absence of small-bid and FLM assumptions, OBM faces 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 k E (0, 1). Specifically, the competitive ratio for any deterministic algorithm is zero when x = without the FLM assumption.
The proof of the upper bound is deferred Appendix A.I The key ingredients of the proof is given below. The best competitive ratio for any deterministic algorithm is max, mingeg CR G) which
In this paper. graphs with different orders of online nodes are considered two different graphs.

---

Algorithm 1 Meta Algorithm (MetaAd)
Require: The function [0,1] [0,1]
1: Initialization: Vu E U, the remaining budget bu,0 Bu-
2: for t=1 V, a new vertex E V arrives do
3: For E 2. set S,, 1. hed
B. bu,t-1 Wu,t 2 and Su,t 0 otherwise.
4: if Vu U, Su,t then
5: Skip the online arrival & (It = mull).
6: else
7: Select = arg maX Su,t-
8: end if
9: Update budget: If xt o null, barst = ba Wxasti and Vu o Ii, but b
10:
end for
no larger than max, mingee CR(T,, G) where G' C G. Thus, we can prove the upper bound by constructing 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 - rounds sum up to 1 + with > 0 being infinitely small. We let g' = gi U 9 where we have Wu, = R.,,, for examples in Gí. and W.,V = 0 for examples in G/z The instances in G' illustrate the dilemma between matching 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 bid of R,B,, for instances in 9j because there is sufficient budget to match the final query. Conversely, if an algorithm chooses to skip some queries in the first V - rounds to save the budget, it can lose bid of xBB,, for the instances in 9/22 because matching the final query of instances in 92 earns zero bid. For these difficult instances in g', we formally derive the largest reward ratio of deterministic algorithm to the offline optimal one which the upper bound of the competitive ratio.
The upper bound of the competitive ratio shows that OBM becomes more difficult when the bid-budeet ratio K gets larger. Intuitivelly since the bid value is not fractional for each matching. given 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 happen that the following queries have positive bid. The FLM assumption can alleviate this difficulty because the remaining budget can be fully spent even if it is insufficient. greedy algorithm can achieve a competitive ratio of 1 1/2 for general bids with FLM [23]. By contrast, the upper bound of the competitive ratio without FLM cannot reach 1 1/2 when the bid-budget ratio is larger than 1/2. There is even no non-zero competitive ratio when K 1. These observations reveal that without FLM, OBM becomes more difficult. The analysis without FLM assumption will help us
to understand OBM better.
4.2 Meta Algorithm Design
We now present MetaAd in Algorithm I which is 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 general discounting function [0, 1] uses Φ to score each offline node by discounting its bid value in Line 3, and selects the node with the largest score Sa,t from Line 4 to Line An offline node is scored zero if it has insufficient budget for the query t (bu,2-1 Wh.t < 0) or it has zero bid for the query t (w..t 0). If all the offline nodes scored zero, the algorithm skips this query
J0. 1]. Given
query f, MetaAd
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 Wa,t- Simultancously, an increasing function é maps the normalized remaining budget b to B, discounting value within [o, 1). If an offline node u has less remaining budget, a smaller discounting value is obtained to encourage conserving budget for
5

---

Algorithm 2 Dual Construction
Require: The function ø [0, 1] 00, 11, (xxx)
x1 2), p= 1: Initialization: Vu E UG 0u.0 = 0, b..0 B.. u1 - 9. and VI E [V] 3r 0.
2: for (=1 V. new vertex E V arrives do
3: Append {u bu,t-1 Wa.t < 0) into UP.
4: Score Su.t. select H; for the arrival t. and update budget du. by Algorithm
5: Set the dual variable B, Sm,t, and set the dual variable auut = 40( (mu
(
6: end for
7: For u & UP, set au V and for u E U1, set au 1.
4.3 Competitive analysis
Given any monotonically increasing function Ø [0, + [0 in Algorithm [ 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 functtion Φ [0, [0, 1] Algorithm satisfies that given an integer n
Vi n,, (0)) (x) O where <p(x) 6(1 x), the competitive ratio of Algorithm is
1
()k) 1 + kn++ R m00.1 (
600) I-K
where R is the Lipschitz constant of ( (x) if ( is not monotonically decreasing, and It 0
otherwise. Additionally, (1y) =p(v) ry ((x)dx , - X² (10(6-1 (i-1)) (0)).
By Theorem 4.2
we can easily get a competitive algorithm for OBM with any bid-budger 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 Appendix A.2
The analysis is based the fundamental conditions in Lemma 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 orn n E [0, 1] if it selects a series of feasible actions (f1....,vv) and there exist dual variables (31, ",Bv,,, fa..".,, . such that
(Dual feasibility) Yu e U, [V], Wn.e an)
(Primal-Dual Ratio P 2 n-D, D, where P = ΣV Wxg,t and D D= Eneu Bu Ev= Bi-
Without the small-bid and FLM assumptions, the competitive analysis presents the following new challenges to satisfy the conditions in Lemma
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 new challenge to construct dual variables that satisfy the dual feasibility due to budget insufficiency.
To address this challenge, we present new dual construction Algorithm where dual variables are determined based on the remaining budget and adjusted the end of the algorithm. The constructed dual variables satisfy the dual feasibility in Lemma [ as explained below. We define 3r as the score of selected offline node u. For any with sufficient remaining budget (b,,t-1 Wu,)).
have 3, 2 Su,t = Wa,e - (p(" B_ )). ) By choosing a,,t = kp( (( the dual fcasibility in Lemma is satisfied for and u with sufficient budget (bu,t-1 2 Wu,t) since by an increasing function ço, it holds that Or, 2 Ou,, 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 o,, 1 for any with insufficient budget (ba,e-1 < (.,r) the end of the dual construction. This ensures that the dual fcasibility is always satisfied without FLM.

---

Guarantee the primal-dual ratio. The challenges in guaranteeing the primal-dus ratio in Lemma come from the unspecified discounting function and the absence of the small-bid and FLM assumptions. To solve this challenge, we derive condition to satisfy the primal dual ratio P. 2 Dr for any round where Y 2 1, P. E Way, is the cumulative primal reward and D: Eusu Buaua + Ei=ı Pe is the cumulative dual. Thus, we prove that the primal dual ratio Pt 2 Dr is satisfied for any L E (7') if for any [0. 1] it holds that,
((v) fr" ((z)dx + Σ k x2pp00 1) (v) + (x= R Σ R ( (0).
+1
x=
where ()x) = 1- 61 2)) and @ is the discounting function. Given that the dual increase due to the final dual adjustment (Line 7 in Algorithm 2
is bounded by d(x)
1-K P,
bound the Given any
final primal-dual ratio as P
D. This leads to a competitive ratio of *+ *+
* sioy
OLKT
discounting function o, we can solve for y that satisfies the condition in 33. thereby obtaining the competitive ratio of MetaAd.
4.4
Competitive Algorithm Examples
In this section, we assign ø with different functions to get concrete algorithms and competitive ratios.
4.4.1 Small Bid
We first verify that MetaAd reduces to the optimal algorithm for small-bid setting (K - 0) 24
23
c-c--- Corollary 4.2.1. By choosing (xx) e-I Met aA reduces to the algorithu in 24 and achieves
the optimal competitive ratio of for umall-bid setting (R - 0).
Corollary 4.2. 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 obtained which is explained as follows. By solving (3) with "=" and O, we get
((x) = (7 1)e" + 1 -,,, 7, d(x) = (7 1)e*
(4)
where Y S e
to make sure <(x) 2 0 for x E [o, 1]. By Theorem 4.2 we get the competitive ratio c-1
as lim, +0 T (2-e)x+e- By optimally choosing 7 -- get the optimal competitive
ratio as 1-
4.4.2 Exponential Function Class
Next, consider exponential function class (xx) Cie + C2 with 0 < 0 1. To ensure px()) is an increasing function, we choose C₁ 2 0. Also, we choose C2 -C to simplify the expression of the competitive ratio. We can observe that (px)) has positive n th derivative for any n 2 1. Thus, we choose n oo in Theorem 4.2 to eliminate the term - R. By substituting s(x)
into (Ks) in Theorem 4.2 get the corollary below.
Corollary 4.2.2. If we assign sp(z) Cz C with C 2 0 and 0 s 0 I 1 in KetaAd in Algorithm
I we get the competitive ratio as
+
K T 2
0
rem Me 1)t 14c G.a of (n))= 1+0+00 r'n
I-x
(5)
140+0(1-++ nn 104 140-0-91-07
x0
We numerically solve the optimal 7Tx) for each x E [o, 1] by adjusting the parameters 9 and and show the results in Figure [ We observe that MetaAd achieves non-zero competitive ratio for i E [0. 1). The competitive ratio for e = 0 is the optimal competitive ratio of 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 large enough k, 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.
for small-bid
7

---

Interestingly, the optimal choices of the expo- nential function ((()) for different K reveal the insights into designing deterministic algorithms for OBM. When x is less than critical point R 2 0.26, the optimal choice of the exponen- --e
0.8
CR (w/o FLM)
MetaAd (Exp)
MetaAd (Quad)
0.6
Upper Bound
0.4
tial function (x(x) I-ex and the optimal
0.2
choice decreases with K E [0, R]. In this range, K becomes larger in [0, R), the dis- counting Φ0 (
0.8.0
0.2 0.4 0.6 0.8 1.0
1 g0(1 bu. B_ 1) be-
Bid-budget ratio
comes smaller, indicating more conservative approach to budget usage in preparation for po- tentially high future bids. However, as к gets larger than R, the optimal choice of the discount- ing function becomes 6(x)
Figure I: Competitive ratio without FLM. MetaAd (Exp) represents the MetaAd with yp(x) C(e 1) and MetaAd (Quad) represents the MetaAd with (fx)) Ca²).
with C O, yielding greedy algorithm. This suggests that for large enough K, the algorithm benefits more by matching a node with a large bid immediately than by conserving more budget for future.
4.4.3 Polynomial Function Class
In this section, we explore another function class show that MetaAd is general enough provide competitive algorithms given different discounting functions. We consider a function class of n-th polynomial function, i.e. ()()) Dÿ= Cjæl. We set Σj=1 Cj S 1 to ensure (p1) S and set Co 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.
Corollary 4.2.3. If we assign p(z) Σn= Cjxl with Σj= Cj S and i-th derivative op (x) >
(0 < i < n), Metadd d achieves competitive ratio as
n((E) = 1+ max (vy) I Ej= -
(6)
where Aly) Criv" + ((1 + k)Cn, n
D + EE=0(1 + k)C - C2
j+1
E 2= n² RCCi+j (i+ي]] (rti)))e'. )ar Specifically, given a quadratic example (xx) Ca² by optimally choosing
C ==1, 1, we have
5
3
1
(k)) = 12
-1 1-K K
2
4
We numerically show the results of (x) in Figure ! We observe that MetaAd with a simple quadratic function (zx) x² can also achieve non-zero competitive ratio for E j0, However, this competitive ratio is lower than the best competitive ratio achieved by the exponential function (p(x) = C 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 x E [o, 1) (in the absence of the FLM assumption), it is interesting explore other functions under the MetaAd framework with better competitive ratios.
4.5 Extension to OBM with FLM
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 3p and its analysis to Appendix B Instead of scoring based on the true bid Watt. Algorithm 3 determines the scores based on modified bid min (wn,t b Based on the modified dual construction in Algorithm 4 get the competitive ratio for OBM with FLM in the next theorem.

---

Theorem 4.3. If the function o [0, - [0, 1] in Algorithm |
satisfies that given an integer n 2 2,
vi S. 1,, ( (x) > 0 and R = maxxe((01] (m()))) where ((x) = - 1-1(111111111 x). the competitive
ratio of Algorithm is
(())
+ 1Tth R+ ma. A + Ø(x)'
where Aly) s(v) 1 - ((x)dx - n² (g) - (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
0.8
(Exp)
CR (w/ (w/FFF FLM)
((x) and 6(x) I-x respectively. Thus, the compet- itive 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 in- sufficient, thereby reducing the potential budget waste.
0.6
Greedy
BJN2007
0.4
0.2
0.0
0.0
0.2 0.4 0.6 0.8 1.0
Bid-budget ratio
Similar MetaAd without FLM, assign exponential function class (pxx) C(e"=-1) 1) to get a concrete algorithm with competitive ratio in Corollary [B..I] We numerically solve the optimal 17(k) for each
Figure 2: Competitive ratio with FLM. MetaAd (Exp) represents MetaAd with ((x) = C(e and BJN2007 represents the algorithm in 4
[0. 1] by adjusting and C' and compare the results with an existing competitive algorithm BJN2007 4 for FLM in F As ς - 0, both MetaAd and BJN2007 achieve the optimal competitive ratio 1 1/e in the small-bid setting. However, while MetaAd, reducing to a greedy algorithm, maintains a competitive ratio of J the best known competitive ratio of the deterministic algorithms for the OBM with FLM.
approaches 1, the competitive ratio of BJN2007 decreases to zero
Competitive
Design
In this section, we demonstrate the application of our competitive analysis for designing learning- augmented algorithms which guarantee competitive ratio of ML-based solutions for OBM.
Our competitive analysis directly motivates learning augmmentd algorithm for OBM called LOBM. The algorithm of LOBM and analysis are deferred to Appendix C In LOBM, we apply ML model which at each round takes the features of the arriving query and the offline nodes as inputs and gives the output بn,t. Directly using 1 - εu,t as discounting value to set the score as W, Eu,r) can result in arbitrarily bad worst-case performance for adversarial examples. To provide a competitive guarantee for OBM, LOBM projects the MI. output ε,, into a competitive solution space Du,: in (28) and obtains a projected value =,,t- The score is then set as w,, 2u,c) based on the projected ML output Zu,t. The key design of the competitive solution space is motivated by the conditions in Lemma which ensures that any z value in Du.t leads to the satisfactions the dual feasibility and primal-dual ratio. The competitive solution space is based on the dual construction given the
E where > in Algorithm 2 Importantly, we introduce slackness parameter À E [o, 1] in the design of Du., in 28) The parameter À controls the size the competitive space Du,t and further regulates the competitive ratio of LOBM. Given a smaller X, can get a larger competitive space Du,t, and so LOBM has more flexibility to exploit the benefits of MI predictions. However, smaller \ also leads smaller competitive ratio shown in the theorem below.
discounting funetion <p(x)
Theorem 5.1. Given the maximum bid-budget ratio k E [0. 1), 0 > 0, and the slackness parameter [0, 1], with any ML predictions, LOBM in Algorithm 5 achieves a competitive ratio of
X(1
(x))
(8)
1
Lee-Ox I-R + (1
1
ox
11)

---

Algorithms w/o ML Predictions
ML-based
Algorithms
Greedy
PrimalDual
MetaAd
LOBM-0.8
LOBK-0.5
LOBK-0.3
Worst-case 0.7941
0.8429
0.8524
0.7903
0.8538
0,8324
0,8113
Average
0.9329
0.9340
0.9344
0.9355
0.9372
0.9371
0.9343
Table I: Worst-case and and average normalized reward on the MovieLens dataset. The best
results among algorithms w/o ML predictiso and the best results among ML-based algorithms are highlighted in bold font.
Theorem 5.1 shows that LOBM with slackness parameter À E [0, 1] can guarantee competitiveness ratio of (x)) regardless of the MI. prediction quality. The parameter E [0, determines the worst-case competitive ratio and the degree of flexibility to exploit the benefit of MI 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 incqualities 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 I, 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
off between the competitive guarantee and the average performance by adjusting the level of exploiting the MI. predictions.
6 Empirical Results
We evaluate the empirical performance of MetaAd and LOBM on two applications. The first application Online Movie Matching where the platform needs match each query movie advertiser with limited budget. The empirical results are obtained based on the MovieLens Dataset [12.. The main empirical results shown in Table [ We compare MetaAd with the algorithms without using ML (Greedy and PrimalDual introduced in Section D.I.I] and show that MetaAd achieves the best worst- case and average performance among them. Additionally, we validate that LOBM with a guarantee of competitive ratio in Theorem [.] 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-Aller 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 Appendix D.2.3
Conclusion
In this paper, consider 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, design the first meta algorithm MetaAd that achieves a provable competitive ratios parameterized by the maximum bid-budget ratio x E [0, 1]. We also extend LOBM under the additional FLM assumption. Additionally, based on the competitive analysis, we propose LOBM to take advantage of MI. 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 open question and an interesting problem for future exploration.
Broader impacts. By introducing 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 being matched due to their smaller bid-to- touuege ratios. This fairness warrants further investigation.
issue, also observed in prior algorithms [23
24
10

---

Aknowledgement
Jianyi Yang, Pengfei Li and Shaolei Ren were supported in part by NSF grants CNS-2007115 and CCF-2324941. Adam Wierman was supported by NSF grants CCF-2326609, CNS-21446114 14, CPS- 2136197, CNS-2106403, and NGSDI-2105648 as well as funding from the Resnick Sustainability Institute.
References
[1] Mohammad Ali Alomrani, Reza Moravej, and Elias B Khalil. Deep policies for online bipartite matching: A reinforcement learning approach. arXiv preprint arXiv:2109.10333 2021.
[2] Amazon EC2. https://aass amazon. com/ec2/
[3] Allan Borodin, Christodoulos Karavasilis, and Denis Pankratov. An experimental study of algorithms for online bipartite matching. Journal of Experimental Algorithmics (JEA), 25:1-37, 2020.
[4] Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. Online primal-dual algorithms for maxi- mizing ad-auctions revenue. In European Symposium on Algorithms, pages 253-264. Springer, 2007.
[5] Nikhil Devanur and Aranyak Mehta. Online matching in advertisement auctions, 2022.
[6] Nikhil Devanur and Thomas P Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce, pages 71-78, 2009.
[7] Nikhil R Devanur, Kamal Jain, and Robert Kleinberg. Randomized primal-dual analysis of ranking for online bipartite matching. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 101-107. SIAM, 2013.
[8] Gagan Goel and Aranyak Mehta. Adwords auctions with decreasing valuation bids. In International Workshop on Web and Internet Economics, pages 335-340, Springer, 2007.
[9] Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In SODA, volume pages 982-991. Citeseer, 2008.
[10] Robert Grandl, Ganesh Ananthanarayanan, Srikanth Kandula, Sriram Rao, and Aditya Akella. Multi-resource packing for cluster schedulers. ACM SIGCOMM Computer Communication Review, 4664) 2014.
[11] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024.
[12] Maxwell Harper and Joseph Konstan. The movielens datasets: History and context, Acm transactions on interactive intelligent systems (tiis) 5(4):1-19, 2015.
[13] Nguyen Trung Hieu, Mario Di Francesco, and Antti Ylä Jääski. A virtual machine placement algorithm for balanced resource utilization in cloud data centers. 2014 IEEE 7th International Conference Cloud Computing, pages 474-481. IEFF, 2014.
[14] Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online vertex weightee bipartite matching: Beating 1-1/e with random arrivals. ACM Transactions on Algorithms (TALG), 15(3):1-15, 2019.
[15] Zhiyi Huang, Qiankun Zhang, and Yuhao Zhang. Adwords in panorama. In 2020 IEEE 6l Annual Symposium on Foundations of Computer Science (FOCS), pages 1416-1426. IEEE, 2020.
[16] Patrick Jaillet and Xin Lu. Online resource allocation problems. Rock & Soil Mechanics, 86:3701-3704, 2011.
[17] Bala Kalyanasundaram and Kirk Pruhs. optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1-2):319325 2000.

---

[18] Michael Kapralov, Ian Post, and Jan Vondrák. Online submodular welfare maximization: Greedy is optimal. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1216-1225. SIAM, 2013.
[19] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-secows annual ACM symposium on Theory of computing, pages 352-358. 1990.
[20] Nathaniel Kell and Debmalya Panigrahi. Online budgeted allocation with general budgets. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 419-436, 2016.
[21] Pengfei Li, Jianyi Yang, Adam Wierman, and Shaolei Ren. Robust learning for smoothed online convex optimization with feedback delay. In NeurIPS, 2023.
[22] Wubin Li, Johan Tordsson, and Erik Elmroth. Modeling for dynamic cloud scheduling via mi- gration of virtual machines. In 20// IEEE Third International Conference on Cloud Computing Technology and Science, pages 163-171. IEEE, 2011.
[23] Aranyak Mchta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265-368, 2013.
[24] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22ess 2007.
[25] Vahab Mirrokni, Shayan Oveis Gharan, and Morteza Zadinoghaddam. Simultaneous ap- proximations for adversarial and stochastic online budgeted allocation. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithmss, pages 1690-1701. SIAM, 2012.
[26] Mayank Mishra and Anirudha Sahoo. On theory of vm placement: Anomalies in existing methodologies and their mitigation using novel vector based approach. In 2011 IEEE 4th International Conference Cloud Computing, pages 275-282. 282.. IEEE, 2011.
[27] Zhonghong Ou, Hao Zhuang, Jukka K Nurminen, Antti Ylä-Jääski, and Pan Hui. Exploiting hardware heterogeneity within the same instance type of amazon ec2. In 4th USENIX Workshop on Hot Topics in Cloud Computing (HorCloud 12), 2012.
[28] Benjamin Speitkamp and Martin Bichler. A mathematical programming approach for server consolidation problems in virtualized data centers. IEEE Transactions on services computing, 3(4::266-27 278, 2010.
[29] Rajan Udwani. Adwords with unknown budgets and beyond. arXiv preprint arXiv:21 10.00504 2021.
[30] Vijay V Vazirani. Towards practical, budget-oblivious algorithm for the adwords problem under small bids.
[31] Alexander Wei and Fred Zhang. Optimal robustness-consistennyy trade-offs for learning- augmented online algorithms. In NeurlPS, 2020.
[32] Dan Zhang and William L Cooper. Revenue management for parallel flights with customer- choice behavior. Operations Research, 53(3):415 431, 2005.
12

---

A Proof of theorems in Section 4
A.1 Proof of Proposition 4.1
Proof. Proposition 4.1 can be proved as follows. Denote CR(T;; G) as the competitive ratio of deterministic algonithm on the graph instance G. The competitive ratio for any deterministic algorithm max, mingeg CR( G) which is no larger than max, mingeg CRR(TT G) where G' C G. Thus, we can prove the upper bound of the competitive ratio by constructing an example subset G' and deriving the resulting competitive ratio for any deterministic algorithm. Specifically, an example subset G' is constructed as below.
Example 1. Consider setting with only one offline node and total budget of 1. The agent needs to decide whether or not to match an online node with a bid value Wu,t S K. R E (0, 1] to the offline node for V 2 2 rounds. The bid values for the first V - 1 rounds are equivalent to and sum up to 1 - K + e where is infinitely small, so we have w E (0, (1 - K +t)// [_x+e] |]. The bid value Wu.V in the last round is either zero
and is not known to the agent. Thus, the constructed example subset is composed of two smaller subsets, i.e. g' = g + G2- In the example of the subset Gr, we have W.y K, and in the examples of the subset Z2. we have Wu,V O.
The offline optimal solutions are different for 91 and G22 in Example For Gj with the last bid value as W K, the optimal solution to skip one of the first (V rounds. In this way, the last online node with bid can be matched and the total reward is 1 + e w. For G2 with the last bid value as W = O, the optimal solution to match all the online nodes for the first V rounds and obtain total reward of K +
For the examples in G' in Example D 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 G221 but for 9j with Wa.V k. the total reward is 1 1- &whih which is less than the offline optimal reward 1 + c - W. Therefore, the competitive ratio of this algorithm in the worst case lim.-+o min (e (1000)(0100_/_/_____))))) -
1- -K- + 1 K when w is < l+c-w infinitely small. Second, the algorithm can choose to skip one round in the first V- rounds such that the last online node can be matched if it has bid value of x in Gj. However, for 922 with Wn,V V = and the total reward is 1 - + 6 which is less than the optimal reward as competitive ratio of this algorithm is lim.-0 min w00_ee0,(0-tt//// ((==2)
+ 6. Thus, the I-x+e = 1
--tte-w
for (0. When x
the competitive ratio of this algorithm is minwe(0.e) 1-kte-w
1-x+r minwe(0.e)) شيك 0. Therefore, the competitive ratio for any deterministic algorithm for g' is max, mingeg CR(TT, G) = max{1 - K,
- k for k E (0, 1). and 0 for 1.
Combining both cases of (0, 1) and 1, get the upper bound of the competitive ratio for any deterministic algorithm for G' as 1 - K, which is also an upper bound of the competitive ratio of any deterministic algorithm for OBM.
A.2 Proof of Theorem 4.2
To prove Theorem A.2
we first prove Lemma]
Proof of Lemma I
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 have
P D D' 2 n).
where the second inequality holds since D* is the minimum dual objective, and the third inequality comes from weak duality. This completes the proof.
Proof of Theorem A.2
13

---

Proof. To satisfy the primal Hhimal-dual dual ratio Pt 2 1 Dr. we can get an inequality of au, as below.
Σ NEl
Buautt +
Σ 3 5
W
1=1
Σ Bu +
Wn - 40( ( )) 5. Σ
Cu.t
Ba
MEl
uell im m
WEM
(10)
Yuu E U, Bug
Σ ==,,;==
8p(
C )) S 7 - Cu.t
Bu
+&uu au,
Whii 1p(
Ca,i-1 + (7 - 1)
Cu.t
Bu
By
Ba
==,,,,=
where Cu, = Ei Wasss. Since Cu,t = sp( Cu.f B,
) we get the condition of &p as below.
Cail B
Wa Cu,s-1) + (7 - 1) Cu.t
pp(
(1I)
Bu
Bu
B,
i= 1=1,z==
Further, since yp is an increasing function, we have the following bound for the discrete sum.
Wu.i up(
Ca,i-1)
Bu
Bu
=
Wuii (p( Cu.i
Σ
Wusi (sp( Ca.é
Ca.i-1 ))
(12)
Bu
Bu
Bu
Ba
=
==,,,==
p(x)ddx
Wuek
(vp(
Cuid
- :p(
Cuii-1
Bu
Bir
B,
2=0
i= 1, =0
where the inequality holds by the integral inequality f-= p(z)dr S E =x zz) with Ei I; for a positive increasing function sp. If (fr)) S 0 for x E [0, 11. we have
Wu.i
Cu.i-1
(
B
B
Ba
(xx)
Σ
Wudt 220
Cu.i-1
Bu
Bu
==
1,
(13)
cutt
cu.t
((x)dr
('xx)dx
==0
1==0
Cu.t
((x)dr (Kep( Cant
(o)(
B,
where the first inequality holds since "²(x) < 0 for x E [0, 1]. the second inequality holds by the bid bound and another integral inequality f (xx)dxx > En x (E)= 2z) with y > Tz
14

---

0 < (x) S R for x E [0, 1], following Eqn.
12
we have
Wu,i
Cu,i-1)
pp
Bu
Bu
((2)dz -
Σ
Wu.i o0( Cu,i-1)
Σ
Wu.i
( Cu.s
- 10l(
((,i-11) 1),
Bu
By
Bu
Bu
Ba
0=
im 1at
im 1,
(14)
cust
Bu
Bu
Wu,i )²R Bu
(xx)ddx - 1
(x))) - K
0=
xx=
1,
p(x)dxx (Kip( Cutt
kip(0)) x²²
Craft
Bu
B
where the second inequality holds by the integral inequality and ("(x)) S R.
Therefore, we can extend to the case where yp has nhehe derivative. If (x) Vi S n, Vo [0, 1]. then we have
Wu,i s
Cu,i-1)
Bu
Bu
=1,,==u
(15)
Bu
((z)dd
n En'plli-1
Guil
n
x (6 - =
Cu.t B..
Bu
i=1
where R is the Lipschitz constant of (ln) if (l is not monotonically decreasing and R otherwise.
Substituting
15 into
III. the condition becomes
Gu. p
S
(1
1)
Cu.t
Bu
c(z)dx
Σ Entoli-1) Cuit Bu
n
+ E
n
(0)) xx Cut
Bu
Bu
Ba
(16)
Thus, a yp function satisfies the primal dual ratio P. 2 7 Di if it satisfies for any 10, 1],
y ((y) (x))dr=
Σ (i-1 + (pn m+ R - + 1)y S i=1
r Hi 1) (0).
(17)
===
Finally, we bound Evetr B, where An = an au, is the dual increase at the end of the dual
construction 2 A, > can hold for u E Ut because ane 1 for E 212 Thus, after the V loops,
have for E E
B, B, (1 av.v)= B, (1- lp( Cu.VV
BN
(18)
=Bubl bn.V S Brd(ks)
where the inequality holds since bu. / S SKBu for any E UP Thus, we have
Eney B. d(x)) P,
Σ WEW
BA S Σ B.d(k)) S (()) P
(19)
Eneyo -K) Bn K
WEL!"
where the second inequality holds because P Ener By given that Cu,V 2 (1 k) for u E Up.
Putting them together, we have P 2 (D
d(x) I-E
P) which leads to the primal dual ratio as
P ME D. To satisfy 17 for any sp, choose > 1 ++*** #+1 R+ p(y) f (p(x) ((z)dz
V
E N² (w) (0) for any y E [0. 1]. Combining with Lemma !
we get the
competitive ratio in Theorem 4.2
D
15

---

Algorithm 3 Meta Algorithm (MetaAd with FLM)
Require: The function [0,1] [0,
Initialization: Vu E U, the remaining budget bu,o = Bu- for t=1 to V. a new vertex t arrives do
For 21 set Su,t 1r Bus if b Wu,t 2 and set Su,t 1u. otherwise.
Bu
if Vu E UG Su,t =0 0 then
Skip the online arrival t (r, mull).
else
Select 2; = arg maXueu Su,t-
end if
Update budget: xt + null, Uzes 1ost-1 Wxyt and Vu of 2iz, Dust = 1. end for
B MetaAd for OBM with FLM
In this section, extend MetaAd 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 online arrival to offline node Ut the agent receives actual reward of min Wa.t; bu where Wa,t is the bid value and bu,t-1 1 is the available budget at the beginning round
B.1 Algorithm Design
Even under the FLM assumption, OBM with general bids challenging because when online node t arrives, if the remaining budget bu,t-1 of an offline node u smaller than the bid Worrs matching the arrival this offline node can cause reward loss of Wh,; b.,t-1, which increases with the bid value Wa,t- With FLM, the greedy algorithm (Greedy) can achieve competitive ratio of 0.5 [23] The competitive ratio achieved by deterministic algorithm in is (1
1-x
(1+6)177
For OBM with FLM, we use different meta algorithm as in Algorithm
3 When the remaining
budget bu,t-1 for an offline node u is enough accept arrival (i.e. Dy,
z wu,t). the scoring
b strategy is the same as Algorithm which sets the score Su,t = 1 B. Nonetheless, the scoring strategy is different from Algorithm when the remaining budget bu.t-1 of an offline node is insufficient for online arrival (i.e. bu,-11 W.,). Without FLM, Algorithm directly sets the score Su, as zero to avoid the selection of offline node u. However, FLM allows matching an offline node u to the online arrival and consuming all the remaining budget b,,t- to obtain
reward of bu.r-1. Thus, Algorithm can be greedier and sets the score as Su, bu,e- ( 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 select offline node with an insufficient but large enough remaining budget.
(w.(-1) to B.
B.2 Competitive Analysis
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 Theorem B. with its proof deferred to Appendix [B.
To prove the competitive ratio of MetaAd for FLM, still need to construct dual variables Ou, Br. t E [V], which assists with online matching with a provable competitive ratio. The dual construction procedure is given in Algorithm
At each round t, same as the dual construction without FLM in Algorithm 2 3, is set as the score of the selected offline node and o is set as sp( (uuz) Different from Algorithm Oa set at the end of the algorithm as below satisfy dual feasibility with the FLM assumption.
Og max (ouvv:{
bu.l-1 bu,c-1
) D.E 1
(20)
Wa,t
B,d
16

---

Algorithm 4 Dual Construction (with FLM)
Require:
The function ø [0, 1] 0. 11, ((x)
@ 2),
Initialization: Yu E U. Qa,0 = 0, 6,.0 B,, Up = 0. T = 0, and vt E [V] B. = 0.
for (=1 to V, new vertex & V arrives do
If there exist such that ba.e-1 W',t < 0, append {u bu,e-1 - wutt < 0} into 21 and append to T
Score Su.t. select 24 for the arrival t, and update budget bu,t by Algorithm 3
Set the dual variable Be = 8x,,t, and set the dual variable Cutt yp B,
end for
For u & UP set On Vu, and for E UP, set au as Eqn. 20
where E T the round when budget insufficiency happens. This is to guarantee the dual feasibility 8e 2 (1 Ou,,-1) 2 (1, a.) when the offline node has an insufficient budget for an arrival. Note that the dual increment A,, = Ou aa, at the end of the Algorithm 4 can be less than the dual increment at the end of Algorithm 2 thus resulting in 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. Ifthe th function é [0, + -0, 1] in Algorithm Satisfies that given an integer n 2 Vi
1, up(0 (x) > and R max (n) (x) where ((x)) = -6(1 x), the competitive ratio of A
(kK) 1 kDh R+ ma A o(x)'
where Aly) = plv) 1 S d( + Ei= n² (1) - (0))
Given different yp, can get concrete competitive algorithms for OBM with FLM. In this paper, show the example of the competitive algorithm where is from the exponential function class.
Corollary B.1.1. If we assign cfx)) Ce C with C 2 0 and 0 < 0 < 1 in Metald d in Algorithm
we get the competitive ratio as
1+0+C(1- I-xI 1)11C--CM(111 1
T-x0 20 0
((K)=
(21)
1 + 1-x0 < 0
1+0+C(1 1t. -H14C-Cc0(1-))
0
B.3 Proof of Theorem B.I (Thorem 4.3)
Proof. Denote an equivalent bid as W.,t min bu,t1) To guarantee the primal-dual ratio
Pt 2 1 Dr. we get the condition as below.
Σ Beaut +
Σ 1=1
B
W
well
1=1
Bu
w. - l0( (a.i-1)) 54 54 Σ Cu.t
Ba
well
well i= ii1,,
uEll
(22)
Cu.i-11 )) S 7 Cu.
Yuu E U, BuCrut
Bu
i=1,:==u
YYu E a,, S
Σ
Was
By p
Cu.i-1 ) + (y- 11) Cu.t
Bn
Ba
==,,0==
where Cu. = Ei=,,, Way.f.
17

---

Since au, [p( we get the condition of (p as below.
Cu.t
Wu.i
vp( (ui--) + (7 - 1)
Cu.t
g
(23)
Bu
Bu
Bu
Bu
i=1,2==
Same the setting with FLM, we can bound the discrete sum as below. for S n 1, (x) > E [0, 1|, then we have
Wa.i Bu
Cu,i-1)
Bu
i=
(24)
n--
n-1
(xx)d
Σ net (xppl-11)
Cunt Bu
+
k² p ( (0)
Cu.t B.
where R is the Lipschitz constant of () (x) if (1 is not monotonically decreasing and R otherwise. Thus, a ip function satisfies the primal dual ratio P. 2 Dr if it holds for any y E [0, that
(Q1)= I ((x)dxx
Σ
x (i + (n. - + pIy
k (ip(i-1(0))
(25)
==
Finally, we bound Eneup BuAu where Au = On - Ou.VV. Au > 0 can hold for u E U because
au = max (au,v, {1 bu.e 0i (eeaat)) "), To ] by Equ. 20 Thus, for a request t E T we have bu,t-1 Wh.t < and buce- S KB... Since an increasing function, holds that Vu,V 2 au, for & [V]. Thus, after the V loops, have for u1
Was
ba.t-1
Φf Dust-1) Okr,V
B,A Bu
Wu,t
Bu
butt-1
bu
Bu
Ocr,t-1 1-
Whet
Bu
b 1
I spl butt-1
(26)
Bu
Wh,t
Bu
bu-211
$ (Bu bu, 1 11
pp(
Bu
G.V (k))
where the third inequality holds since Wh,t S B, and the last inequality holds since B, bu,t-1 Ca.t-1 S C. Thus, we have Ener B.An I P. (1 sp(1 k)).
Putting them together, we have 2 (D Φ(k) P) which leads to the primal dual
ratio as P 2 D. D. Since we have 2 1 + * R e(v) f p(x)dr
En n² (gll))(0)) - (0)) for any y [0, 1] to satisfy 25 Combining with Lemma
I we get the competitive ratio in Theorem
C Learning Augmented OBM
In this section, exploit the competitive solution space in MetaAd and propose augment MetaAd with ML predictions (called LOBM) to improve the average performance while still offering a guaran- teed competitive ratio in the worst case.
C.1 Algorithm Design
main technical challenge for OBM is to estimate the discounting value that discounts the bid values by factor for the matching decision at round t. Thus, ML model can be potentially leveraged to
18

---

replace the manual design of score assignment. More specifically, we can utilize an ML model to predict a discounting factor z,,t and set the score as Su,t = Wa,t zn,t) for matching when the offline node has a sufficient budget for the online arrival 1. That is, we incorporate MI. 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 leaming-augmentted online algorithms [3 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
OBM ( LOBM). To better control the trade-off, we introduce slackness parameter À E [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 MI. prediction the discounting factor for matching, competitive ratio cannot be satisfied due to the lack of worst-case competitiveness for MI. 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] I
Based the competitive analysis with the exponential function class, we design a saarning-augment algorithm (i.e.. LOBM) in Algorithm []] which leverages ML prediction &,, 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 guaranteed to be competitive in the worst case while utilizing the potential benefits of MI. predictions.
We describe LOBM in Algorithm as follows. At the beginning, we initialize the dual variables as zero Whenever an online node arrives, the agent receives a ML prediction ε,, indicating the discounting factors for all the offline nodes u E U. Instead of directly using the ML prediction to set the scores and selecting the offline node, LOBM projects the ML prediction Eu, into the competitive space Du, by solving the following for all E U,
2 arg min 12 - Zu,el:
(27)
2ED.,
which 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 žu, out of competitive space Pu,t, such that the selected z,, is the closest to the ML prediction E,,z. Then, the projected value Zu, is used to set the scores sa,t for offline nodes with sufficient budgets for the online arrival i, and the scores for offline nodes with insufficient budgets are set as zero and these offline nodes are appended to Lr The scores based on calibrated ML predictiisn are then used to select the offline node for matching.
As the key design to guarantee the competitive ratio, the competitive space Du. is based on the conditions for dual variables in Lemma and the dual construction by the exponential function class (Corollary 4.2.2). The dual variables are constructed as follows. For the selected note á, and its score $ 82. we update the dual variable az as A,,,1-1 + App
_ E2,,t, where pa = 1 1
with 0 > 0, 2 is the discounting factor when setting the score of at (Line 4 of Algorithm (5). and cxp( (Dw,,.)) - - Brc
Bz, is a variable relying on the bid value Wa., 1. For unselected offline nodes, we keep their dual variables au,t the same as aa,t-1 for u + Iz. The dual variable 3, is set based on the score of the selected offline node, i.c. 3g = Xpe $2,,t Xpp We, 2). By constructing dual variables in this way, when an action x, is selected, the primal objective P. 7,=7, - W,,,r increases by Wz.. and the dual objective D. == E'==1 Bz, Ox + Br increases by B., (Axz, 02,,1.1-11 + 3, = Weec. + Bz, 82,t. When an online arrival is skipped without any matching, both primal and dual objectives remain the same with no updates. Thus, we can always ensure that the primal objective and the dual objective satisfy D: = Xpe Pt + + Ber.ror,, for each t E [7]. 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 dril ratio, leading different competitive ratios.
5 exp(0(11bb...-11)) e--1
Ways
and the remaining budget b2.0-11.
Xpp
Next, we need to ensure that conditions in Lemma D are always satisfied no matter which offline node E U is selected at each round t. Thus, construct the competitive space Du, as below and
19

---

Algorithm 5 Learning-Augmentie OBM (LOBM, w/o FLM)
1: Initialization: Vu U. Bu, Vu E UI On,D B. ... By = O.
2: for t=1 to V, a new request E V arrives do
3: Get the ML prediction t. Vu U
4: Project Ea,t into D,, in (28) and get Zu,t, Vu E U.
5: For all u E U, if bu,t-1 Wh,t 2 O, set score Su,t Wn,e Zu,e): otherwise, set score
Su,t = 0 and append {u bu,t-1 Wa,t 0} into Ut. then
6: if Vu U, Su,
7:
Skip the online arrival & (Ie = mull).
8: else
9:
Select T; = arg max Su,t-
end if
11:
If # mull, update budget ba.tt = bectt-1 Wxr i and Yu o Fz, butt = bu,t-1.
12:
Update dual variables B3 1
Apo
S2..
If 24 * null, update axzed axe.e11 +
ApO Wer Saat + 8za,t-
13:
end for
For u $ u., set aa V,, and for u E U1, set au 1.
project the ML predictions Zu,t into Du,t if they fall outside Du,
Du,t { 2 0
1
Wn,e(1 (1 2) 2 Wu.t Wu,r0ku,--11
Apo
(28)
Wast + su, - App
-1]
au,t-1 +
6 1
Since the dual variable B3 is set as Xps Sm,,t after selecting the offline node with the highest Su, and sufficient budgets, 3e is no less than Xpe Su,t = Xpo (w,,+11 - =u.z) for any u E U. Thus, as long as the first inequality in (28) is satisfied, we always have the dual feasibility 3r 2 Wh,t cw,ra in Lemma T if all the offline nodes have sufficient budgets for the arrival t. For the offline nodes with insufficient budgets for the online arrival f, we ensure the dual feasibility 3g 2 Wa,t Cu, by setting their corresponding dual variable au Algorithm 5)
after the matching process (Line 14 in
The second inequality in (28) sets target for the increment of the dual variables dhet which forces the dual variable ou,, to larger when the remaining budget becomes less. In this way, the score of an offline node with fewer remaining budgets can be set lower to be conservative in consuming budgets. Also, since a,,t is larger when the remaining budget is less, the second inequality in (28) guarantees a large enough dual variable au, when u has insufficient budget for arrival t. This
keeps the additional dual increment after the matching process (Line 14 in Algorithm 5h bounded and further guarantees bounded primal-dual ratio in the second condition of Lemma
As we discussed, if the discounting factor 2,, at each round satisfies the inequalities in 28 the primal variables and the constructed dual variables will satisfy the conditions in Lemma and so competitive ratio for OBM is guaranteed. The size of the set D.., is controlled by the hyper-parameter A: with smaller X, the size of D... becomes larger because the inequalities are easier to be satisfied. We will rigorously prove that Du,, is always non-empty given any E [0, to enable feasible competitive solutions that guarantee the competitive ratio bound in 29 in the robustness analysis of LOBM in Section
ML model training and inference. Given any ML predictions, Algorithm 5 provides guarantee for the competitive ratio. Nonetheless, the average performance Egg [(( 9)] depends on the ML model that yields the ML prediction. Here, we briefly discuss how to achieve high average performance by training the MI model in an environment that aware of the design of Algorithm Note first that the projection operation is differentiable while the discrete matching decision is not differentiable. Thus, we apply policy gradient to train the MI. model. Once the MI. model is trained offline, can be applied online to provide Zu,t advice for scoring and matching by LOBM (Line 3 in Algorithm 5
20

---

C.2 Analysis
Now, we provide a robustness analysis LOBM and formally show that LOBM always guarantees the competitive ratio.
algorithm is robust 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 R [0, 1] and the slackness parameter À [0, 1]. with any ML predictions, LOBM in Algorithm 3 achieves a competitive ratio of
X(1 1
i(())
(29)
1+1 X
L-e-te + (1
where [z] = x if and [z]+ 0f S 0.
Theorem C.I shows that LOBM can guarantee competitiveness ratio of fi(x) regardless of the ML prediction quality for any slackness parameter E [0. 1]. The parameter E [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 imequalities in the competitive space 28 always hold, and LOBM reduces to pure ML-based algorithm with no competitive ratio guarantee. On the other hand, when À = 1, LOBM achieves the highest competitive ratio. When flexibly chosen between the competitive solution space also varies from whole solution space (with X = 0) to the smallest competitive solution space (with = 1) in (8)). Thus, LOBM achieves a flexible trade-off between the competitive guarantee and average performance by varying the levels of trust in ML predictions.
C.3 Proof of Theorem C.1 (Theorem 5.1
the main text)
Proof. The sequence of dual variables constructed by Algorithm 5 We prove three claims leading to Theorem C.I
The dual feasibility is satisfied,i.e. Vu E u, [V], Wn, + Be 2 Wh,t-
The primal-dual ratio guaranteed, i.e. P nD.
The solution of projection (28) always exists, i.e. the feasible set of (28) not empty for each round.
First, we prove the feasibility of dual variables (The first condition in Lemma If 3: for round E [2']. we have either wu,s = 0 or Wa,t >> 0 and a, = au,V v 2 1 holds for a slot u E U by Wa.t a.) holds for the dual construction. On the other hand, 3 holds for round t E [T]. then the score Sa., must be calculated based on the projected 2,, Thus,
Line 14 so Br
we have 3/ = Xpo s 2 1 Su, = 1 W., 2n,t) 2 Wu, - aa,z) 2 We,,((1 a.) where
Xpo
Xpp
Pa - ااك and the second inequality holds by the first inequality of the set (88) This proves the feasibility the dual variables
Next, we prove the primal-dual ratio (the second condition in Lemma I is satisfied. At round t, no vertex selected for a vertex the primal objective P and dual objective D do increase. Otherwise, the primal objective increases by Wx..t and dual objective increases by Bz. (azz..
az.-1,1-1) 3 W By Line 14 at the end of Algorithm the dual variable au,V increases to aa by A, au Qu.V.
Ane Bu, where 6z,t = exp(@(1-b,..)) (1b((_(,,../BB,.)) (exp( Owee. ) B,,
Wass))
e--1
Ba
Thus, the dual objective can be written D and further we have
1 EV= Wxat EV Brg S + EnEul BrAns
Xoo
P
Wast X(1
1 )0)
D Σ ByAu E Ba, Bendeet
(30)
uEtro
21

---

To bound the geght-aan-ssiee we have
e e- 0m
E LuEuo Bu
Σ
BB
Σ Bu
- -1
6
P
ueu
wEl
(31)
e (1 c P
Ewerp By
6
1 - -
P.
e
Eneu: (1 Bx
e (1 k)
For each u E Ut we sum Bu and get
V
exp(O(1-bu.t-) bun.e BB)) (Bu exp(
Owant Bu
Bz Sa,t =
Σ
- Bu - Ww.e))
Am mu
V
exp(O(1 - -bn,o-1/Bu)) Wa,t
Bu
Awn.
Bi -1
Σ
expl
e 1
Wa,t
Bu
Wa,
1=,,,,=
exp(O(1 - -b,,t-//B
Watt
T
By
e
Bu
K
El,,,=u
exp(0
Cu.V
-
8n
< By
B.
8(e0 -1)
K
ni
1
ex
S Ca.V 0
K
(32)
where the first inequality holds because 0z 1 an increasing function for x
E
1]. [0,1], the second inequality holds since ΣV Et exp(0(1 b
B..
V
El exp(0 Bu B. Cu.V
S S2z0 exp(Or)dæ = (exp(0 B. - 1), and the last inequality exp(# Sw.V )-1
holds because B By summing up all bidders in U, we get
@6 1-1
0ie0 1) V.V. S Cu.V 4.
By
Σ B2, Σ Σ
BRg Oent S p.
1
Ox
(33)
1
K
K
uell 1
Continuing with inequality 30
have
(
(D-
e
c
1
9n
+
P P)
P2 A(1
-1
(1 k)
0
K
K
-
(34)
Thus, by moving terms, we have
X(1 3
P>
(35)
1 1+X
I-e-tk
+(1 - 1
I-K
N
This proves the second condition in Theorem
Finally, we prove that the solution of the projection into (8) always exists, i.c. the feasible set of (28 not empty for each round. To do this, we prove by induction that
Aipo exp(O(1 - b IBB)) AA E [A,
(36)
(e" -1
is always feasible for the set
28
For the first round, the initialized dual variable 0a,0 0, the
initialized remaining budget b = B,, so we have
exp(A(
00, + Wu,t 2t + du,1 2
(37)
Apg
e
22

---

Online node
Online node
Mag!
Romaining budget Bty
Score
Features
Projection
Euys
Rays Projection
Remaining budget of
Score
Featumes
I-
Pext
Remaiingg budget of Ity.
Score of My
Features of
Pey!
Projection
Rey
MetaAd
(b) LOBM
Figure 3: Illustration of the scoring strategies in MetaAd and LOBM. The example has 3 offline nodes
(11, U2 uz). The algorithms select the offline node with the largest score.
where the inequality holds because A 2 X, so the second inequality of 288 holds for / = 1.
Also, it holds that
1
Wu,1 (1 - 21,1) Wa,1
c²
A1 A(e
Wa,1
Wa,1 Wu,1 au,o);
Ape
M(e0 11)
1)
(38)
where the first inequality holds since À < and the second inequality holds since A < 1. Thus, we can prove the first inequality of (28) holds for initialization.
Then if the constraints are satisfied for the round before arrival 6, then we have au,t-1 2
exp(9(1 -b. bo..)/B..) and thus we have
0u,t-1 + Wu.t z + du,t
Apg
(39)
exp(O(1 - b,., 1)/ Bu)
Owvlt Bu
exp(0(1 (bw,t-1 w.)
exp(
e
where the inequality holds because t 2 A.
Thus the second inequality of 28 holds.
Then, since Cuat-1 2 exp(0(1 (a1(00(1-,,,-111 b-..)/ we have
Wu,t (1-2 za.t)
Xpe
cB N(e0
d exp(((( - - A(e -1
(40)
2 Wu, au,t-1),
where the inequality holds since < and A < 1. Thus we prove the first inequality of In conclusion, can always find feasible dual variable update 2 in the projection set
28 holds.
28
D Empirical Results
To complement the theoretical analysis, we validate the empirical benefits proposed algorithms by conducting numerical experiments for online movie matching application.
D.1
Online Movie Matching
We evaluate the performances of our algorithms on the online movie matching application based on the MovieLens Dataset [12]
D.1.1
Setup
In the application online movie matching, each movie (i.e., an offline node) has a maximum budget
set by advertisers. Once online query arrives, the bid values of the query for all the movies
23

---

Algorithms w/o ML Predictions
ML-based
Algorithms
Greedy
PrimalDual
MetaAd
LOBM-0.8
LOBK-0.5
LOBK-0.3
Worst-case 0.7941
0.8429
0.8524
0.7903
0.8538
0.8324
0,8113
Average
0.9329
0.9340
0.9344
0.9355
0.9372
0.9371
0.9343
Table 2: Worst-case and and average normalized reward on the MovieLens dataset. The best results among algorithms w/o ML predictiso and the best results among ML-based algorithms are highlighted in bold font.
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 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 movie is more relevant 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 real dataset of MovieLens 122. The Moviel.ens 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 the Moviel.ens 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 each edge between the offline node and the online node. The total budget for each offline node is sampled from normal distribution with a mean of and standard deviation of 0.1, and the maximum bid value is 0.1 (i.e., K 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 ietttributionadderrssaee testing dataset and randomly removing edges and/or rescaling the weights.
examples, we also create examples by modifying 10% examples in the
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
2 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 special case of MetaAd with 0 + co.
PrimalDual PrimalDual [23 calculates the scores of each bidder for each online node based 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 0 +
ML: policy-gradient algorithm that solves the OBM problem I. 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 (rr)) 6 - and LOBM in
Algorithm 5| The illustration of MetaAd for round t is shown in Figure 3(a) LOBM-X is LOBM with the slackness parameter À in the competitive solution space (28). The illustration of LOBM for round is given in Figure 3(b) The The optimal parameter 0 governing the level of conservativeness in MetaAd tuned based on the validation dataset. We also evaluate the performance of MetaAd under different choices of f. and evaluate LOBM with ML predictions under different choices of the syper-parameter À in Da, in (28). For fair
[0. and use LOBM-À to represent LOBM with the comparison, we use the same neural architecture 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 laptop takes around hour, while the inference process over each instance takes less than one second.
D.1.2 Results
The empirical worst-case and average reward (normalized by the optimal reward) based on the Moviel.ens dataset are shown in Table[]] In this table, the parameter of MetaAd 0.7 by default which is obtained by tuning validation dataset. We find that MetaAd can achieve higher
24

---

Parformance
Mait Gat
Worst Case
0.90
LOBM [0
LOBM (6-
LOOM (5-25)
Avarage
LOBM
0.90
0.85
0.94
0.85
110
0.80
0.93
0.75
3.0
0.4
Parameter
Parameter
Worst-case/average reward of (b) Worst-case reward of LOBM
Average reward of LOBM
MetaAd
Figure 4: (a) Worst-case and average reward of MetaAd with different choices of 8. (b) Worst-case reward of LOBM with different choices of 0 and X. (c)aver reward of LOBM with different choices of 0 and X.
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-distributtin testing examples, ML has 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 because the projection of MI. predictions onto the competitive solution space in 28 corrects low-quality MI. predictions. Interestingly, LOBM with À 0.8 achieves the best empirical worst- case and average performance, demonstrating the superiority of LOBM despite that its competitive ratio 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 lower worst-case reward.
The effects of in MetaAd, To validate the effects of the hyper-parameter 0 on the performance of
MetaAd with (xx) __=_ T we give more details of the performances of MetaAd under different
choices of 0 in Fig. 4(a) We give both the empirical worst-case and average reward of MetaAd with different choices
The results show that the average reward of Metadd not significantly affected by the choice of 0, but 0 has large effect the empirical worst-case reward. This is because controls the conservativeness of MetaAd and hence is crucial for the worst-case competitive ratio when * O discussed in Section 4.2, More specifically, larger worst-case reward can be obtained with a smaller for the MovieLens dataset. The reason is that a higher level conservativeness is needed when the maximum bid-budget ratio K. is not zero.
The effects of and À in LOBM. The empirical worst-case and average rewards of LOBM with different choices of 0 and À are provided in Fig. 4(b and Fig. 4(c) respectively. Different choices of 0 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 A as shown in Theorem C.I These theoretical findings are validated by our numerical results.
As we can see from Fig. 4(b) and Fig 4(c) when X = 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 A= 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 well trained. When lies between O and 1, we can find that for some choices of 6, LOBM can achieve an even better average reward than ML. This improvement comes from the fact that the competitive solution space (28) can correct some low-quality MI. predictions on certain problem instances. Also, for certain choices of 0, LOBM can empirically achieve better worst-case reward than MetaAd,
Reward ratio
0.88
0.84
ML
LOBMO Metadd (Exp)
LOBMLA 0.8)
0.80
LOSMLA 0.4)
Percentlle
Figure 5: Reward (normalized by the of- fline optimal reward) at high percentiles (95% 100%). 0 is chosen 1.
25

---

because LOBM can perform well due to ML predictions 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-of distribution instances, we show in Fig. [ 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 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 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 MI. 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.
D.2
Online VM Placement
D.2.1
Problem setting
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 VM request, the cloud operator needs to select 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, 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 at round t, I V has a computing load in the number of computing units denoted as Each server u E l has limited capacity of the computing units (e.g.. virtual cores) denoted as B' If the VM request v is placed on server u, the manager receives a utility proportional to the computing load Waat Ta 2 where Tu is the utility of one computing unit on server u. Denoting Zu,t E {0, 1} as the decision on whether to place request on server u, the objective of the VM placement problem can be formulated as an OBM:
max P=
Σ
t=1 MEN
(41)
s.t. Vu E U, Σ Lw. S Bu, VL IV],
Σ Ru,t S 1, E U, 2V, Zu, 2 0, KEM
where Wa,t = - and B, = r By, In this OBM, the VM request is not divisible, which means fractional matching not allowed at any time and FLMM does not apply.
D.2.2 Experiment setting
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 Binomial distribution BUU Z./U) where d, 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', is sampled from a uniform distribution on the range [20, 40). The computing load of VM request is sampled from uniform distribution on the range [1, 4f. The utility per
computing unit r, 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
26

---

Algorithms w/o ML Predictions
ML-based
Algorithms
Greedy
PrimalDual
MetaAd
ML
LOBM-0.8
LOBK-0.5
LOBK-0.3
Worst-case 0.6528
0.7937
0.8027
0,8005
0.8432
0,8253
0,8277
Average 0.6950
0.8343
0.8449
0.9626
0.934
0.9619
0.9610
Table 3: Worst-case and average rewards different algorithms for VM placement. The worst case and average rewards are normalized by optimal rewards. We compare MetaAd with the algorithms without using ML (Greedy and PrimalDual introduced in Section D.I.I). Additionally, we compare our with the MI. algorithm. LOBK-À means LOBM with slackness parameter À in Eqn. (28).
algorithm LOBM
2 We randomly generate 20k, 1k, and Ik 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 obtained using Gurobi [[]] for each graph instance.
Greedy: The greedy algorithm (33 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 special case of MetaAd with - co.
PrimalDuae Dual: PrimalDual 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 special case of MetaAd with 0 - 1.
22 calculates the scores of each bidder for each online node
ML: A policy-gradient algorithm that solves the OBM problem M. 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- 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 learning rate of 10-3 3 for 50 epochs. Likewise, we use LOBM-À to refer to LOBM with a hyper-parametet À governing the competitiveness requirement in 28
D.2.3 Results
We first show Worst-case and average rewards of different algorithms for VM placement in Table 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 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 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 worst- case reward ratio 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 the table. Importantly,
find that LOBM achieve high average performance while guaranteeing worst-case competitive ratio theoretically as shown in Theorem [5.]] 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 X. Next, we give the ablation study of MetaAd and LOBM for different choices of parameters 0 and À in Fig. 6 The parameter 0 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 0 in Fig. 6(a) We can find that compared with PrimalDual (i.e., 0 = 1), MetaAd can further improve the worst-case performance for the general bid settings by decreasing 0 which is consistent with the competitive analysis in Corollary4.2.22
Moreover, we provide the worst-case and average rewards for LOBM under different 0 and X 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 ML. The worst-case performance can
27

---

0.38
0.85
1012
Warst Case
0.80
020
Average
0.70
0.75
30
0.80
0.86
LOBM 10-0..)
LOBM [8=
0.65
2+4 0.0
0:75
0.2
0.4
0.6
0.8
1.0
0.82
0.0
0.2
0.4
0.6
0.8
1.0
0.5
0
0+1
Parameter
Parameter
(a) MetaAd with exponential func-
(b) Worst-case reward of LOBM
(c) Average reward of LOBM
tion class
Figure 6: (a) Worst-case and average rewards of MetaAd with the exponential function class (a) Worst-case reward of LOBM. (b)Average reward of LOBM. The worst-case and average rewards are normalized by optimal
rewards and calculated empirically based testing dataset with 1000 samples.
be improved by increasing since LOBM with larger has higher competitive ratio guarantee according to Theorem C.1 However, the average performance can be affected when À becomes larger, because a larger results in 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.
28

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] " or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
The abstract and introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
29

---

Justification:
The limitations are discussed in the conclusion section which are mainly about the open question about the best choice of the discounting function.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" " section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Our paper summarizes the assumptions listed in Section The proofs of our theorems are given in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The paper has provided detailed settings of the experiments in Section
Guidelines:
30

---

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 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 specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, 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 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification:
We will open source the codes upon the publication of the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
pablic/guidess/odeettnmi sosoodeeessbiisssssoooooooocc for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//wpss.cc/pulli//uui.
CodeeSumiiiie issiissiino ssiospolicyyyiiiic for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
31

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
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 the core the paper to 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, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports the high percentile performance in Figure D.1.2
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, confi- dence 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.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 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 out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experiments can be reproduced by a personal computer with CPU.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
32

---

The paper should provide the amount of compute required for each of the individual experimental runs as well 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics attpss//neuripp:: httpg//ggt///////roso.o./ooo////
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations 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 socictal impacts or the need of safeguards due to the theoretical nature of our work.
Guidelines:
The answer NA means that there 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., deploymenn 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 tied to particular applications, let alone deployments. However, if there is 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 unintentional) misuse of the technology.
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).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (c.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.
33

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All original sources of the datasets used in the paper are cited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, papprssi tcoodee com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
34

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS 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.
35


Reviews:
[{"review_id": "VzjvjbXryM", "reviewer": "Reviewer_JnBx", "summary": "**Problem Studied**\n\nThis 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.\n\n**Main Results/Contributions**\n\nAdwords 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:\n1. An upper bound on the competitive ratio of any deterministic algorithm parameterized by the bid-budget ratio, and\n2. 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.", "questions": "1. Why is it interesting to study the setting with general bids and no FLM? (see above)\n2. 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": "Yes.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 1, "strengths": "This paper is generally well-written and easy to understand. I believe the main results of the paper to be correct, although the only proof I checked in detail is the proof of the upper bound for deterministic algorithms.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your questions.  We answer them as below.\n\n**`Why is it interesting to study the setting with general bids and no FLM?`**\n\nOBM with general bids covers a wide range of online bipartite matching problems [1], so it models many applications where FLM does not hold. Two examples are given below.\n\n+ **Cloud resource management [2,3].**  In this problem, the cloud manager needs to allocate virtual machines (VMs, online nodes) to different physical servers (offline nodes).  Each server $u$ has a computing resource capacity of $B_u'$. Whenever a VM request $v$ arrives, the manager observes its computing load, denoted as $z_{v}$. If the VM request is placed on a server $u$, the manager receives a utility proportional to the computing load $w_{u,v}= r_u\\cdot z_{v}$ given the heterogeneity of servers.  Denoting $x_{u,v}\\in$ { 0,1}  as whether to place $v$ to VM $u$, the goal is to maximize the total utility $\\sum_{v=1}^V\\sum_{u=1}^U w_{u,v}x_{u,v}$ subject to the computing resource constraint for each server $u$:  $\\sum_{v=1}^V z_v x_{u,v}\\leq B_u'$ which can also be written as $\\sum_{v=1}^V w_{u,v} x_{u,v}\\leq B_u$ with $B_u=B_u'\\cdot r_u$. In this OBM problem, the VM request is not divisible, i.e., fractional matching is not allowed at any time.\n\n+ **Inventory management with indivisible goods.** In this problem, a manager needs to match several indivisible goods (which arrive at different times) to different resource nodes each with limited capacity (e.g., matching parcels to mail trucks, matching food orders to delivery vehicles/bikes). Each good can only be matched to one node without splitting. A good $v$ can take up a percentage of $w_{u,v}$ for resource node $u$. The target is to maximize the total utilization $\\sum_{v=1}^V\\sum_{u=1}^U w_{u,v}x_{u,v}$ subject to the capacity constraint at each node $\\sum_{v=1}^V w_{u,v} x_{u,v}\\leq 1$.\n\nBy studying OBM with general bids and no FLM, we provide provable algorithms for broader applications beyond online advertising (whether FLM holds in online advertising depends on the specific policies of the advertising platforms).\n\nAdditionally, we also extend MetaAd to OBM with general bids and FLM (see **`Appendix B`**). The algorithm and analysis are adjusted to exploit the benefits of FLM assumption. By assigning the discounting function with an exponential function class, MetaAd gives high enough competitive ratios for any bid-to-budget ratios compared to existing deterministic algorithms. Thus, for the FLM setting, our MetaAd is still effective in building competitive algorithms for general bids.\n\n**`Clarify where [10] needs the assumption of FLM`**\n\nIn the first paragraph of the Introduction section in [10], the authors claim the use of the FLM assumption: The platform selects an advertiser for an online impression and pays either its bid or its remaining budget, whichever is smaller. \n\nFLM assumption is necessary in [10]. First, the algorithms and analysis in [10] rely on the reformulation of OBM as a Configuration Linear Program. The objective of Configuration LP depends on the budget-additive payment which means each advertiser pays the sum of the bids for all the online nodes assigned to it or up to its total budget, whichever is smaller. Thus, when the sum of the assigned bids is larger than the available budget for an advertiser, the matching is fractional. \nBesides, whenever an online node arrives,  the basic algorithm (Algorithm 1) of [10] assigns an offline node to an online node no matter whether the offline node has a sufficient remaining budget or not. In this algorithm, the FLM assumption is necessary to make sure the total payment of each advertiser does not exceed the initial budget. \n\nMoreover, [10] provides a randomized algorithm, which assigns offline nodes to online nodes with randomness. By contrast, we focus on deterministic algorithms and make novel contributions to OBM by considering general bids for settings both with and without FLM.\n\n**`Reference`**\n\n[1] Mehta, A., 2013. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science, 8(4), pp.265-368.\n\n[2] Grandl, R., Ananthanarayanan, G., Kandula, S., Rao, S. and Akella, A., 2014. Multi-resource packing for cluster schedulers. ACM SIGCOMM Computer Communication Review, 44(4), pp.455-466.\n\n[3] Speitkamp, B. and Bichler, M., 2010. A mathematical programming approach for server consolidation problems in virtualized data centers. IEEE Transactions on services computing, 3(4), pp.266-278.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "O46b0iQ9Eg", "reviewer": "Reviewer_vF5Z", "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..", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The novel design of the meta algorithms for OBM, MetaAd, is interesting and inspiring. \n2. Concrete theoretical proofs for all the results.\n3. Well-organized presentation.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your question regarding the motivation of general `non-small` bids. \n\nRelaxing the small bid assumption is crucial to providing provable algorithms for many useful online bipartite matching (OBM) scenarios. We explain the significance from both application and theory sides.\n\n+ **Applications to broader scenarios.** Although in some scenarios the bid-to-budget ratio is small enough to justify the previous small-bid assumption, many applications have \"medium bids\", where the bid-to-budget ratios are neither negligible nor as large as 1. Take cloud virtual machine (VM) allocation as an example: One VM request can commonly take up a non-negligible fraction (e.g., 1/10 to 1/2) of the total computing units in a server, which is equivalent to a non-small bid setting.  \n\n+ **Bridge the gap in theory.** The small-bid assumption is restrictive in the sense that it assumes the bid-budget-ratio is infinitesimally small ($\\kappa \\rightarrow 0$) and only models a limited set of online bipartite matching problems.  By relaxing the small bid assumption, OBM with general bids covers a broader set of online matching problems, including the vertex-weighted online bipartite matching [1]. Thus, compared to the small-bid setting, our study provides provable algorithms for more generalized online bipartite matching problems.\n\nIn fact, some recent works have highlighted the importance of generalizing OBM from small-bid to general-bid settings [1,2]. Some of them provide provable algorithms for settings with the fractional last matching (FLM) assumption [2]. Importantly, we design meta algorithms for settings both with and without the FLM assumption.\n\n\n**`Reference`**\n\n[1] Mehta, A., 2013. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science, 8(4), pp.265-368. \n\n[2] Huang, Z., Zhang, Q. and Zhang, Y., 2020, November. Adwords in a panorama. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) (pp. 1416-1426). IEEE.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Br7T0YIWWb", "reviewer": "Reviewer_CTTb", "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.", "questions": "See weakness.", "limitations": "See weakness.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The theoretical results of this paper appear sound. \n- I appreciate that the authors take efforts in presenting their results in a unified framework, establishing connection with the competitive analysis for small-bid setting, as well as prior works such as BJN2007.\n- The authors provided a good summary of prior works studying the same problem (under other assumptions).", "weaknesses": "1. My main concern for this work lies in its contribution. More specifically,\n- 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.\n- 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.\n- Since the main proof techniques come from primal-dual analysis, I also wonder whether the proof also contains technical novelty.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the questions. \n\n**`How to choose a discounting function $\\phi$?`**\n\nOur results (**Theorem 4.2 and 4.3** ) are instrumental to design a discounting function $\\phi$. Specifically, Theorem 4.2 and 4.3 enable us to identify appropriate $\\phi$ by maximizing the derived competitive ratios. In this work, we focus on two important function classes -- exponential function class and quadratic function class --- and solve the best $\\phi$ within the two function classes. We find that even the simple exponential function class can offer appealing results: It recovers the optimal competitive ratio of $1-1/e$ in the small-bid setting, gets close to the upper bound of the competitive ratio for large bids $\\kappa$ without FLM (**Figure 1**), and matches or approaches the best-known competitive ratios of deterministic algorithms ( [BJN2007] for small enough bids and Greedy for large bids ) with FLM (**Figure 2**). \n\nAdditionally, our results provide a foundational guide for more complex designs in OBM. Specifically, our learning-augmented design LOBM in **Section 5** is a successful example of applying our theoretical results to improve average performance while offering competitive ratio guarantees. In this example, we use an ML model to explore a discounting function and make sure it lies in a discounting function space defined by our competitive analysis. In the future, it’s interesting to search for discounting functions over more complex function classes, either analytically or by AI techniques based on our theoretical analysis.\n\n**`Why use the exponential function forms and how to determine the constants?`**\n\nAs our analysis shows, the discounting function $\\phi(x)$ must be a positive decreasing function of the remaining budget because:\n+ Intuitively, the decreasing discount function reduces the chance of selecting the offline nodes with less remaining budget, due to the scarcity of the remaining budget.\n+ Theoretically, a positive decreasing function  $\\phi(x)$  is required to satisfy the dual feasibility (Lemma 1).\n\nWe consider $\\varphi(x)=1-\\phi(1-x)$ with the exponential class $C(e^{\\theta x}-1)$ or quadratic class $Cx^2$ as examples. Given a bid-to-budget ratio $\\kappa$, the constants can be easily determined by maximizing the competitive ratios (Eqn. (5) for exponential class or Eqn. (6) for quadratic class). \n\n**`Technical novelty`**\n\nDue to our novel and generalized settings, our proof uses several novel techniques as summarized below.\n\n+ **Upper bound the competitive ratio for general bids with no FLM (Proposition 4.1)**.  OBM with general bids with no FLM has many key applications (e.g. cloud resource management) but is not well studied theoretically. By a difficult example, we upper bound the competitive ratio for the first time and show the difficulty of this problem theoretically.\n+ **Dual construction for general bids**. With small bids, the remaining budget is almost zero when an offline node has insufficient budget to match a query, but the remaining budget can be large when budget insufficiency happens for general bids.  This presents new challenges in guaranteeing the dual feasibility. We give a new dual construction (*Algorithm 2* for non-FLM, and *Algorithm 4* for FLM) where dual variables are set based on the remaining budget and adjusted at the end of the algorithm to satisfy the dual feasibility with small enough dual increment. \n+ **Techniques to bound the primal-dual ratio for general bids with no FLM (Theorem 4.2)**. It is a key step to bound the primal-dual ratio which translates to the competitive ratio by Lemma 1. The challenges come from the unspecified discounting function $\\phi$ and the absence of small-bid and FLM assumptions.   Without specific forms of $\\phi$, we derive a sufficient condition of guaranteeing a primal-dual ratio and the condition gives us the primal-dual ratio bound. To get the condition, we bound the discrete sum of dual variables with general bids by an integral (Eqn.(15)). Besides, we bound the dual increment due to dual feasibility for non-FLM setting (Eqn. (19)).\n+ **Techniques to bound the primal-dual ratio for general bids with FLM (Theorem 4.3)**. With the FLM assumption, the dual adjustment to satisfy the dual feasibility is different from the non-FLM setting. Thus, we extend our techniques to FLM by bounding the dual increment due to dual feasibility (Eqn. (26)).\n+ **Robustness analysis for learning-augmented OBM (Theorem 5.1).**  Different from the existing learning-augmented OBM [1,2] that relies on an existing competitive baseline, we design a discounting function space (Eqn. (28)) based on our competitive analysis. This leads to LOBM which guarantees a competitive ratio given any ML model without a baseline as input.\n\n**`Practicality of such an algorithm in real-world systems`**\n+ **Choice of discounting function**. As stated in responses above, the exponential function with optimal constants can give us very good competitive guarantees (best-known for general bids with no FLM). To further improve the average performance under the competitive guarantee, we can apply LOBM in Section 5. The empirical results in Section D.1.2 and rebuttal PDF show the superiority of our algorithms in both average and worst-case performance.\n+ **Scalability**. For both MetaAd (Algorithm 1) and LOBM (Algorithm 5), whenever an online node arrives, the scores for offline nodes can be calculated efficiently in parallel by each offline node, and then the maximally scored offline node is matched subject to budget availability. Therefore, like the prior OBM algorithms, our algorithms can easily scale with the size of the offline node set.\n\n**`Reference`**\n\n[1] Choo, D., Gouleakis, T., Ling, C.K. and Bhattacharyya, A., 2024. Online bipartite matching with imperfect advice. In ICML.\n\n[2] Li, P., Yang, J. and Ren, S., 2023, July. Learning for edge-weighted online bipartite matching with robustness guarantees. In ICML.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mdFMfqsdpo", "reviewer": "Reviewer_3oQ3", "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.", "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?\n2. 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?\n3. 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.\n4. 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.\n5. 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 κ?\n6. 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?\n7. 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?\n8. 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": "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.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Originality\nThe paper stands out for its originality by addressing the Online Budgeted Matching (OBM) problem without relying on traditional assumptions like the small bid-to-budget ratio and the Fractional Last Matching (FLM) assumption. The introduction of the MetaAd algorithm is novel, offering a framework that adjusts to various bid-to-budget ratios while achieving provable competitive ratios. The extension of MetaAd to the FLM setting and the development of the learning-augmented algorithm, LOBM, further underscore its innovative contributions. The authors have done a commendable job of citing related work, clearly situating their contributions within the broader research landscape.\n\nQuality\nThe submission is technically robust, featuring rigorous theoretical analysis and comprehensive proofs that establish the competitive ratios of the proposed algorithms. The authors provide clear upper bounds and validate MetaAd through detailed numerical experiments. Additionally, the empirical validation of the learning-augmented algorithm in an online movie matching scenario is well-executed, offering practical evidence to support the theoretical claims. The methods employed are well-suited to the problem, and the paper presents a complete and polished piece of work. The authors have been thorough and honest in evaluating both the strengths and limitations of their research.\n\nClarity\nThe paper is well-written and clearly organized, with a logical flow of ideas that is easy to follow. The introduction sets the stage effectively, and the related work section provides a comprehensive overview of prior research. The descriptions of the MetaAd algorithm and its extensions are detailed and precise, though some complex concepts could benefit from more intuitive explanations or visual aids. Overall, the writing style is concise and effective, ensuring that the reader is well-informed.\n\nSignificance\nThe findings are significant, addressing a critical problem in online budgeted matching. The proposed algorithms have direct applications in online advertising, resource allocation, and revenue management, making the results highly valuable for researchers and practitioners. By providing flexible and competitive algorithms that remove limiting assumptions, the paper advances the state of the art with substantial practical and theoretical improvements. The insights and methodologies are likely to inspire further research and development in this field.", "weaknesses": "Originality\nWhile 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.\n\nQuality\nThe 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.\n\nClarity\nAlthough 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.\n\nSignificance\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the questions.\n\n**`How does the contribution fundamentally differ from prior work?`**\n\nBeyond the removal of the small-bid and FLM assumptions, we present a novel meta algorithm (MetaAd) for general discounting functions. MetaAd can reduce to different competitive algorithms by choosing different discounting functions based on the meta competitive analysis (**Theorems 4.2 and 4.3**).  This lays a foundation for designing more complex scoring strategies for OBM with general bids. Additionally, our proof that uses several novel techniques (e.g., bounding primal-dual ratios and dual updates) and our learning-augmented algorithm design based on the competitive analysis also add to the literature and can be of independent interest.\n\n**`Experiments for other applications.`**\n\nWe further validate our algorithms based on cloud resource management. The setup and results are available in our general rebuttal PDF. The results show that MetaAd achieves higher total utility than existing algorithms (Greedy and Primal Dual [1]). Also, with ML predictions, LOBM in Section 5 achieves a high average utility as well as a much better worst-case utility than a pure ML method without a competitive ratio guarantee.\n\n**`Q1 MetaAd’s performance and approach vs. existing algorithms`**\n\nPrimal Dual [1] (equivalent to MSVV [2]) is an existing algorithm that uses a fixed exponential function as the discounting function. Greedy [1] is an existing algorithm that selects the offline node with the largest bid. By contrast, MetaAd selects different discounting function parameters for different general bid-budget ratios to maximize the competitive ratios. Our empirical results also demonstrate the practical advantage of MetaAd over these algorithms in various applications.\n\n**`Q2 How to construct $\\phi(x)$ and why is it efficient in maintaining a competitive ratio`**\n\nGiven any discounting function $\\phi(x)$, we establish a competitive ratio for MetaAd in Theorem 4.2.  Thus, $\\phi(x)$ is constructed to maximize the derived competitive ratio in Theorem 4.2 for different bid-budget ratios $\\kappa$. To make this process tractable, we consider $\\phi(x)$ within concrete parameterized function classes (e.g., exponential function class and quadratic function class) and optimize the competitive ratios by adjusting the parameters of the function class. In this way, MetaAd achieves a high competitive ratio by using different parameterized discounting functions for different $\\kappa$. We observe that MetaAd with exponential function class is appealing to maintain a high competitive ratio (best-known without FLM).\n\n**`Q3 How to deal with fractional bids?`**\n\nMetaAd with FLM is given in Algorithm 3. The key adjustment is the scoring strategy for the offline nodes with insufficient budgets. Without FLM, MetaAd scores the offline nodes with insufficient budget as zero to avoid selecting them. Differently, FLM sill allows to match a query to an offline node with an insufficient budget, and the matched offline node pays the remaining budget $b_{u,t-1}$ up to the bid value. Thus, we score the offline nodes with insufficient budgets according to the remaining budget $b_{u,t-1}$ instead of scoring them as zero. In this way, the scoring is based on the true payment in the FLM setting. This contributes to a higher competitive ratio than the non-FLM setting. \n\n**`Q4 Results from a secondary domain`**\n\nWe provide another set of empirical results on cloud resource management in the rebuttal PDF and further validate the benefits of our algorithms. The budget constraints in this application are very different from those in online movie matching in terms of the range of the initial budgets and bid values. \n\n**`Q5 A figure to show the impact $\\kappa$?`**\n\nOn Pages 7 & 8, we have figures showing the competitive ratios varying with $\\kappa$. (Figure 1 is for non-FLM and Figure 2 is for FLM). \n\n**`Q6 A detailed case study showing MetaAd’s implementation...`**\n\nWe have provided a detailed case study on online movie matching in Section D.1. Additionally, we implement MetaAd on cloud resource management with results given in the rebuttal PDF. The case studies both validate the superior performance of MetaAd compared with existing deterministic algorithms [1,2]. We’ll also include other applications (e.g., network routing per the reviewer’s suggestion) in the final version.\n\n**`Q7 Sensitivity analysis for the impact of key parameters`**\n\nIn cloud resource management in the rebuttal PDF, the range of initial budget and the bid distribution are different from those in movie matching in Section D.1.  MetaAd achieves the best performance among the competitive algorithms (Greedy and Primal Dua [1]). Additionally in the rebuttal PDF, we give the sensitivity study showing the performance of MetaAd varying with $\\theta$ in the discounting function and the performance of LOBM varying with $\\lambda$. The same sensitivity study is included in Fig. 3 in Section D.1.2.\n\n**`Q8 A diagram to illustrate the algorithm’s workflow?`**\n\nThanks for the suggestion. We’ll include a diagram illustrating the algorithm's workflow in the appendix in our revision.\n\n**`Potential negative societal impacts`**\n\nThanks for the suggestion. For online advertising, if there is a large disparity of the initial budgets among advertisers, those with a larger initial budget may be matched with a larger chance due to their smaller bid-budget ratios. This fairness issue exists in prior algorithms [1,2] and warrants further discussions. We’ll discuss this societal impact in the revision.\n\n**`Reference`**\n\n[1] Mehta, A., 2013. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science, 8(4), pp.265-368.\n\n[2] Mehta, A., Saberi, A., Vazirani, U. and Vazirani, V., 2007. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5), pp.22-es.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their valuable comments and questions. We've included results for a new set of experiments based on cloud resource management. The results are available in the attached PDF.

**`Experiment setup`**

In the experiment, the cloud manager allocates 100 virtual machines (VMs, online nodes) to 10 different physical servers (offline nodes).  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. We randomly generate graphs by Barabási–Albert method [1] with the average degree of online nodes chosen from 4, 2, and 0.5.  We consider a setting where the limited resource is the computing units (e.g., virtual cores) [2]. Each server $u$ has a capacity of $B_u'$ computing units and $B_u'$ is sampled from a normal distribution with a mean of 40.  The computing load of a VM request $v$ is the number of the requested computing units, denoted as $z_{v}$, which is sampled from a uniform distribution on the range 1 to 8.  If the VM request is placed on a server $u$, the manager receives a utility proportional to the computing load, $w_{u,v}= r_u\cdot z_{v}$ with $r_u$ being the price of each computing unit of server $u$. We choose the price $r_u$ (in dollars) in the range [0.08,0.12] according to the prices of the compute-optimized instances on Amazon EC2 (a large cloud service provider). 

Denoting $x_{u,v}\in $ { 0,1}  as whether to place $v$ to VM $u$, the goal is to maximize the total utility $\sum_{v=1}^V\sum_{u=1}^U w_{u,v}x_{u,v}$ subject to the computing resource constraint for each server $u$:  $\sum_{v=1}^V z_v x_{u,v}\leq B_u'$ which can also be written as $\sum_{v=1}^V w_{u,v} x_{u,v}\leq B_u$ with $B_u=B_u'\cdot r_u$.  We randomly generate 10k, 1k and 1k graph samples for training, validation and testing, respectively. We use a neural network as the ML model in ML-based algorithms. The neural networks in different ML algorithms have two layers, each with 200 hidden neurons for fair comparison. The neural networks are trained by Adam optimizer with a learning rate of 0.001 for 50 epochs.

**`Reference`**

[1] Borodin, A., Karavasilis, C. and Pankratov, D., 2020. An experimental study of algorithms for online bipartite matching. Journal of Experimental Algorithmics (JEA), 25, pp.1-37.

[2] Grandl, R., Ananthanarayanan, G., Kandula, S., Rao, S. and Akella, A., 2014. Multi-resource packing for cluster schedulers. ACM SIGCOMM Computer Communication Review, 44(4), pp.455-466.

Meta-review: 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.
Decision: Accept (poster)