Online Budgeted Matching with General Bids

We thank the reviewer for the questions.

How does the contribution fundamentally differ from prior work?

Beyond 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.

Experiments for other applications.

We 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.

Q1 MetaAd’s performance and approach vs. existing algorithms

Primal 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.

Q2 How to construct $\phi(x)$ and why is it efficient in maintaining a competitive ratio

Given 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).

Q3 How to deal with fractional bids?

MetaAd 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.

Q4 Results from a secondary domain

We 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.

Q5 A figure to show the impact $\kappa$?

On 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).

Q6 A detailed case study showing MetaAd’s implementation...

We 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.

Q7 Sensitivity analysis for the impact of key parameters

In 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.

Q8 A diagram to illustrate the algorithm’s workflow?

Thanks for the suggestion. We’ll include a diagram illustrating the algorithm's workflow in the appendix in our revision.

Potential negative societal impacts

Thanks 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.

Reference

[1] Mehta, A., 2013. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science, 8(4), pp.265-368.

[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.

We thank the reviewer for the questions.

How to choose a discounting function $\phi$?

Our 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).

Additionally, 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.

Why use the exponential function forms and how to determine the constants?

As our analysis shows, the discounting function $\phi(x)$ must be a positive decreasing function of the remaining budget because:

• 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.
• Theoretically, a positive decreasing function $\phi(x)$ is required to satisfy the dual feasibility (Lemma 1).

We 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).

Technical novelty

Due to our novel and generalized settings, our proof uses several novel techniques as summarized below.

• 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.
• 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.
• 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)).
• 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)).
• 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.

Practicality of such an algorithm in real-world systems

• 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.
• 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.

Reference

[1] Choo, D., Gouleakis, T., Ling, C.K. and Bhattacharyya, A., 2024. Online bipartite matching with imperfect advice. In ICML.

[2] Li, P., Yang, J. and Ren, S., 2023, July. Learning for edge-weighted online bipartite matching with robustness guarantees. In ICML.

Thank you for your question regarding the motivation of general non-small bids.

Relaxing 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.

• 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.

• 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.

In 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.

Reference

[1] Mehta, A., 2013. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science, 8(4), pp.265-368.

[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.

Thank you for your questions. We answer them as below.

Why is it interesting to study the setting with general bids and no FLM?

OBM 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.

• 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.

• 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$.

By 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).

Additionally, 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.

Clarify where [10] needs the assumption of FLM

In 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.

FLM 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. Besides, 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.

Moreover, [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.

Reference

[1] Mehta, A., 2013. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science, 8(4), pp.265-368.

[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.

[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.