Kevi Enikő

Eniko Kevi

Kim Nguyễn

Kim-Thang Thắng

Nguyen

Shipra Agrawal

Francesco Orabona

N K Thắng

on Algorithmic Learning Theory

Keywords: online algorithm, predictions, matching problems, primal-dual 1. except in relaxed models such as disposal-free, etc

Matching problems have been widely studied in the research community, especially Ad-Auctions with many applications ranging from network design to advertising. Following the various advancements in machine learning, one natural question is whether classical algorithms can benefit from machine learning and obtain better-quality solutions. Even a small percentage of performance improvement in matching problems could result in significant gains for the studied use cases. For example, the network throughput or the revenue of Ad-Auctions can increase remarkably. This paper presents algorithms with machine learning predictions for the Online Bounded Allocation and the Online Ad-Auctions problems. We constructed primal-dual algorithms that achieve competitive performance depending on the quality of the predictions. When the predictions are accurate, the algorithms' performance surpasses previous performance bounds, while when the predictions are misleading, the algorithms maintain standard worst-case performance guarantees. We provide supporting experiments on generated data for our theoretical findings.

Introduction

The matching problem is fundamental in combinatorial optimization and operations research with wide applications from student admission to colleges through kidney exchange to Ad-Auctions. Motivated by different markets, for example, advertising and labor markets, online bipartite matching has been intensively studied. Online bipartite matching revolves around matching a set of items (impressions) to a set of agents (advertisers). Online items arrive over time, and at the arrival of an item, one needs to make an irrevocable decision on the assignment of the item to an agent. For unweighted bipartite graphs, [START_REF] Richard M Karp | An optimal algorithm for on-line bipartite matching[END_REF] gave an elegant algorithm -the RANKING algorithm -which always outputs a matching of size at least (1 -1/e) times that of the optimal solution [START_REF] Richard M Karp | An optimal algorithm for on-line bipartite matching[END_REF][START_REF] Birnbaum | On-line bipartite matching made simple[END_REF]. The ratio of (1 -1/e) is the best achievable competitive ratio in the worst-case paradigm. Besides, for online matchings in edge-weighted bipartite graphs, no online algorithm is competitive 1 to maximize the total (edge-) weight of the output matching, even though this problem is well-motivated by advertising and AdWords markets (see, for example, [START_REF] Fahrbach | Edge-weighted online bipartite matching[END_REF]).

To circumvent the limitations of the worst-case paradigm, several models have been proposed [START_REF] Roughgarden | Beyond worst-case analysis[END_REF][START_REF] Roughgarden | Beyond the Worst-Case Analysis of Algorithms[END_REF]. The motivation for one of these models is the spectacular advance of machine learning (ML). In particular, the capability of ML methods to predict patterns of future requests could provide valuable information for online algorithms. [START_REF] Lykouris | Competitive caching with machine learned advice[END_REF] formally introduces a general framework to incorporate ML predictions into algorithms to improve the worst-case performance guarantees. Other researchers followed their work, studying online algorithms with predictions [START_REF] Mitzenmacher | Beyond the Worst-Case Analysis of Algorithms, chapter Algorithms with Predictions[END_REF] in a large spectrum of problems, such as scheduling [START_REF] Lattanzi | Online scheduling via learned weights[END_REF][START_REF] Mitzenmacher | Scheduling with predictions and the price of misprediction[END_REF], caching (paging) [START_REF] Lykouris | Competitive caching with machine learned advice[END_REF][START_REF] Rohatgi | Near-optimal bounds for online caching with machine learned advice[END_REF][START_REF] Antoniadis | Online metric algorithms with untrusted predictions[END_REF] and ski rental [START_REF] Gollapudi | Online algorithms for rent-or-buy with expert advice[END_REF][START_REF] Kumar | Improving online algorithms via ML predictions[END_REF][START_REF] Angelopoulos | Online Computation with Untrusted Advice[END_REF]. In this paper, we study the design of algorithms with predictions for variants of online edge-weighted matching problems.

Model and Problems

We consider a model (formally stated in [START_REF] Bamas | The primal-dual method for learning augmented algorithms[END_REF]) in which, whenever a request is released, an algorithm receives some predictions and can use these predictions to make decisions. The designed algorithms aim to outperform the best-known algorithms when the predictions are correct, but maintain close worst-case guarantees when the predictions are incorrect. Specifically, we study the following problems in this model.

Online Bounded Allocation.

In this problem, there are n buyers, each buyer 1 ≤ i ≤ n has a budget B i . Items arrive over time; upon the arrival of item j, the price b j of the item as well as the set of buyers S j ⊆ {1, 2, . . . , n} who are interested in purchasing j are revealed. In the standard online setting, one needs to irrevocably sell item j to some buyer in S j (or sell it to no one) while respecting the budget constraints of all buyers. In a learning-enhanced model with predictions, each item has a predicted buyer to whom the item should be sold. This additional information may come from a learning procedure based on the data analysis of buyers and items. We consider the learning procedure as a black box and treat the predictions as outputs of an oracle. Concretely, at the arrival of item j, the oracle provides a predicted buyer pred(j) to whom the item j should be sold (conventionally, pred(j) = 0 if the item should not be sold according to the prediction). The objective is to maximize the revenue, which is the total price of sold items.

Online Ad-Auctions. This problem is the generalization of Online Bounded Allocation. In this setting, items do not have a fixed price; instead, at the arrival of item j, each buyer i proposes a price (or bid) b ij for each item j. (Buyers can decline to buy an item by bidding 0 value.) We assume that the bids are significantly smaller than the buyers' budgets, so b ij ≪ B i ∀i, j. Similarly, at the arrival of item j, the algorithm receives the prediction pred(j) and decides to whom to sell the item. The objective is again to maximize the revenue, which is the total price of sold items.

Learning augmented algorithms.

We aim to design algorithms that incorporate predictions to achieve performance beyond the worst-case bounds. The predictions in our paper can be learned efficiently in practice. Ad-Auctions (or Ad-words) are routinely run a hundred times per day by different search engine companies. At the end of a period (a day, a week, a month), such companies can infer a good matching from their data that better matches the items to the buyers to increase their revenue. In other words, they can leverage large amounts of data to build machine learning models to predict the best buyer for an advertisement slot based on previous transactions. Such predictions can be used in our algorithms.

The learning augmentation depends on the algorithm's confidence in the prediction oracle. We represent the algorithm's doubt in the prediction by a parameter η ∈ [0, 1] and assume that η is fixed during the algorithm's execution. Large η values mean high doubt, while small η values show good confidence.

Let A(I) be the objective value of the solution produced by algorithm A on an instance I. Similarly, let P(I) and O(I) be the objective values of the prediction oracle and the optimal solution, respectively. When the prediction oracle provides an infeasible solution, P(I) = 0. Given a confidence parameter η ∈ [0, 1], we say that an algorithm A is c(η)-consistent and r(η)-robust if for every instance I,

A(I) ≥ max{c(η) • P(I), r(η) • O(I)}.
Ideally, we would like c(η) to tend to 1 when η approaches 0, meaning that with high confidence, the algorithm performs at least as well as the prediction. Additionally, we would like r(η) to tend to the best guarantee as in the standard online setting (without predictions) when η approaches 1.

Our Approach and Contributions

Given an algorithm A that blindly follows the predictions and another algorithm B, for example, the best-known algorithm without predictions, a natural question is whether we can derive a new and more efficient algorithm C by taking the linear combination of the two original algorithms. Due to the linear combination, algorithm C can only maintain a consistency of O(1 -η) for Online Bounded Allocation (or Ad-Auctions), if the robustness is Ω(η) times the worst-case guarantee of algorithm B. In this paper, we aim for more substantial and non-trivial guarantees.

We rely on the primal-dual approach to design learning augmented algorithms for both studied problems. The primal-dual method is an elegant and powerful algorithm design technique [START_REF] David | The design of approximation algorithms[END_REF], especially for online algorithms (Buchbinder and Naor, 2009a). To unify previous ad-hoc approaches, [START_REF] Bamas | The primal-dual method for learning augmented algorithms[END_REF] presented a primal-dual framework to design online algorithms with predictions for covering problems with linear objective functions. However, their approach is not applicable for problems with packing constraints, particularly matching problems and their variants. In this paper, we present learning augmented online algorithms with predictions for the Online Bounded Allocation and the Online Ad-Auctions problems, answering some open questions raised by [START_REF] Bamas | The primal-dual method for learning augmented algorithms[END_REF].

Specifically, in Section 2, we provide an algorithm which is (1 -η)-consistent and

e-1 e • 1 1+(1-η)(1-e η-1
) -robust for the Online Bounded Allocation problem. In Section 3, we give a (1 -η)-consistent and (1 -e -η )-robust algorithm for the Online Ad-Auctions problem. Similarly to [START_REF] Bamas | The primal-dual method for learning augmented algorithms[END_REF], we provide algorithms that produce fractional solutions for the studied problems. When the algorithms have high confidence in the prediction (meaning that η is closed to 0), the algorithms achieve a similar objective value as the prediction; and when the confidence is low (η is close to 1), the algorithms guarantee the best worst-case bound, (e -1)/e. This robustness guarantee holds by our algorithms even if the predictions give an infeasible solution (realized during the execution).

Related work

The domain of algorithms with predictions [START_REF] Mitzenmacher | Beyond the Worst-Case Analysis of Algorithms, chapter Algorithms with Predictions[END_REF] -or learning augmented algorithms -has recently emerged and rapidly grown at the intersection of (discrete) algorithm design and machine learning (ML). Its main concept is to incorporate learning predictions and ML techniques in the algorithm design to achieve performance guarantees beyond the worstcase analysis and provide tailored solutions to different problems. Recent studies showed interesting results over a large spectrum of problems, such as scheduling [START_REF] Lattanzi | Online scheduling via learned weights[END_REF][START_REF] Mitzenmacher | Scheduling with predictions and the price of misprediction[END_REF], caching (paging) [START_REF] Lykouris | Competitive caching with machine learned advice[END_REF][START_REF] Rohatgi | Near-optimal bounds for online caching with machine learned advice[END_REF][START_REF] Antoniadis | Online metric algorithms with untrusted predictions[END_REF], ski rental [START_REF] Gollapudi | Online algorithms for rent-or-buy with expert advice[END_REF][START_REF] Kumar | Improving online algorithms via ML predictions[END_REF][START_REF] Angelopoulos | Online Computation with Untrusted Advice[END_REF], counting sketches [START_REF] Hsu | Learning-based frequency estimation algorithms[END_REF] and bloom filters [START_REF] Kraska | The case for learned index structures[END_REF][START_REF] Mitzenmacher | A model for learned bloom filters, and optimizing by sandwiching[END_REF]. [START_REF] Bamas | The primal-dual method for learning augmented algorithms[END_REF] recently proposed a primal-dual approach to design online algorithms with predictions for linear problems with covering constraints. They raised an open question to extend their approach to packing constraints, which we answer in this paper.

The online matching and Ad-Auctions problems have been widely studied (see Mehta ( 2013) and references therein). [START_REF] Mehta | Adwords and generalized online matching[END_REF] introduced the Online Ad-Auctions problem and gave an optimal (1 -1/e) competitive ratio when R max = max i,j {b ij /B i } is small. [START_REF] Buchbinder | Online primal-dual algorithms for maximizing ad-auctions revenue[END_REF] simplified their work by a primal-dual analysis. In the same paper, the authors gave an algorithm with a refined competitive ratio for the Online Bounded Allocation problem assuming an upper bound on the maximum degree of the vertices in the matching. [START_REF] Aggarwal | Online vertex-weighted bipartite matching and single-bid budgeted allocations[END_REF] studied another particular case of Ad-Auctions, in which for each i the bids (b ij ) are the same for every j. They obtained the optimal (1 -1/e) competitive ratio with the generalization of the RANKING algorithm [START_REF] Richard M Karp | An optimal algorithm for on-line bipartite matching[END_REF]. In the Ad-Auctions problem (without any assumptions), the existence of an (1 -1/e)-competitive algorithm has been conjectured, but remained an open problem. [START_REF] Huang | Adwords in a panorama[END_REF] recently presented a 0.5016-competitive algorithm for this problem.

Motivated by internet advertising applications, several works considered the Ad-Auctions problem in various settings where forecasts or predictions are available or learnable. [START_REF] Esfandiari | Allocation with traffic spikes: Mixing adversarial and stochastic models[END_REF] proposed a model in which the input is stochastic, and the model gets a forecast for future items. Intuitively, we can measure the forecast accuracy by the optimal solution's fraction one can obtain from the stochastic input. They provide algorithms with provable bounds in this setting. [START_REF] Schild | Semi-online bipartite matching[END_REF] introduced a semi-online model in which the unknown future has a predicted and an adversarial part. They gave algorithms with competitive ratios depending on the fraction of the adversarial part in the input. Closely related to our work is the model by [START_REF] Mahdian | Online optimization with uncertain information[END_REF] in which, given two algorithms, one needs to design a (new) algorithm that is robust to both given algorithms. They derived an algorithm for the Ad-Auctions problem that achieves a fraction of the maximum revenue of the given algorithms. The main difference compared to our model is that their algorithm is not robust if one of the given algorithms provides infeasible solutions (which could happen with predictions), whereas our algorithm is.

An Algorithm with Predictions for Online Bounded Allocation

Recall that in this problem there are n buyers and each buyer 1 ≤ i ≤ n has a budget B i . Upon the arrival of item j, the algorithm discovers the item's fixed price b j and the subset of buyers S j interested in purchasing the item. Additionally, the algorithm gets a predicted buyer pred(j) to whom item j should be sold (pred(j) = 0 if the item should not be sold according to the prediction). We are interested in fractional solutions as in [START_REF] Bamas | The primal-dual method for learning augmented algorithms[END_REF], so we consider the items to be splittable. Before the arrival of the next item, the algorithm needs to make an irrevocable decision and sell the current item in some fractions to some buyers. The objective is to gain maximum revenue from selling items to buyers.

Formulation. Let x ij be the fraction of item j sold to buyer i. The problem can be cast to the following primal linear program in Figure 1 (in which we also show its dual program).

Primal:

max m j=1 i∈S j b j x ij j:i∈S j b j x ij ≤ B i ∀ i (y i ) i∈S j x ij ≤ 1 ∀ j (z j ) x ij ≥ 0 ∀ i, j
Dual: Algorithm. [START_REF] Buchbinder | Online primal-dual algorithms for maximizing ad-auctions revenue[END_REF] proposes an algorithm for the Online Bounded Allocation problem without predictions. They define buyer levels based on the fraction of the buyers' spent budget. Their algorithm splits each arriving item j equally among its interested buyers i ∈ S j who are on the lowest level. Intuitively, this algorithm corresponds to water-filling the buyer levels.

min n i=1 B i y i + m j=1 z j b j y i + z j ≥ b j ∀ j, i ∈ S j (x ij ) y i ≥ 0 ∀ i z j ≥ 0 ∀ j
We propose an algorithm that allocates items using the water-filling strategy of [START_REF] Buchbinder | Online primal-dual algorithms for maximizing ad-auctions revenue[END_REF] and also subtly incorporates predictions. Recall that the parameter η represents the confidence in the predictions. When η is close to 1, our algorithm resembles the water-filling algorithm, while with η close to 0, the prediction has a stronger impact on the algorithm's decision. To do water-filling, our algorithm uses buyer levels as well. At any moment during the execution, a buyer i's level is ℓ, if the fraction of buyer i's spent budget is within the range of ℓ d B i , ℓ+1 d B i . We formally describe the algorithm as follows. Upon the arrival of a new item j, let i * be the predicted buyer (pred(j)) suggested by the oracle. Do the following.

Algorithm 1 Learning Augmented Algorithm for the Online Bounded Allocation Problem.

Stage 1: As long as some interested buyers in S j spend less than η fraction of their budget, the algorithm allocates item j equally to buyers in S j who are on the lowest level.

Stage 2: Once all interested buyers spend at least η fraction of their budgets, the algorithm assigns the remaining fraction of item j to the predicted buyer i * . The prediction assignment ends when one of the two following conditions occurs.

(a) the algorithm assigned to the predicted buyer either (1 -η) fraction or the remaining fraction of j, whichever is smaller (b) buyer i * exhausted its budget Stage 3: If the algorithm does not assign item j completely during Stage 1 and 2 and there exists at least one buyer in S j that does not exhaust its budget, then, similarly to the first step, the algorithm allocates the remaining fraction of item j equally to buyers in S j who are on the lowest level.

Analysis. We first prove the consistency and then the robustness of the algorithm.

Lemma 1 Algorithm 1 is (1 -η)-consistent with the prediction.

Proof Let V be the set of buyers who exhaust their budget at some point during the algorithm's execution. Let U be the set of items whose buyers did not exhaust their budgets, formally, U = {j : pred(j) / ∈ V }. We can formulate the total gain of a feasible prediction as

j pred(j)̸ =∅ b j = j pred(j)∈V b j + j pred(j) / ∈V b j ≤ i∈V B i + j∈U b j (1)
where the inequality holds since any feasible allocation -including the prediction -can allocate items of value at most B i (the total budget) to buyer i.

Let j ∈ U be an arbitrary item. By the construction of the algorithm and the fact that the predicted buyer for item j did not exhaust its budget, the following can occur. The algorithm assigned item j entirely during the limit assignment of Stage 1 (to satisfy the condition of η fraction spent by each interested buyer), or otherwise allocated the remaining fraction of item j to its predicted buyer i up to (1 -η) fraction. We note that the algorithm can always assign the remaining fraction, since buyer i did not exhaust its budget by the end of the execution. In any case, we sell item j in at least (1 -η) fraction, therefore the gain of the algorithm on j is at least (1 -η) b j .

Before the prediction assignment of Stage 2, the total value of items in U sold to buyers in V is at most i∈V ηB i due to the limit assignment rule of Stage 1. As a consequence, each predicted buyer i * where i * / ∈ V gets at least (1 -η) -η i∈V B i /b j fraction of item j. Therefore, the total gain of the algorithm is at least

i∈V B i + j∈U (1 -η) b j -η i∈V B i (2)
where the first term is the gain of the algorithm restricted to buyers in V , the second one is the gain of the algorithm restricted to items in U , and the last term is the upper bound of the total value of items in U sold to buyers in V before the prediction assignment of Stage 2. By (1) and ( 2), the gain of the algorithm is at least (1 -η) that of the prediction.

Let us now establish the robustness of the algorithm. Let d = max{|S j |} be the bound on the number of interested buyers. We characterize the robustness as a function of d. Let us define a piece-wise linear function

f d : [0, 1] → R ≥0 such that f d (1) = 1 and for 0 ≤ u < 1, if ℓ-1 d ≤ u < ℓ d for some 1 ≤ ℓ ≤ d then f d (u) = da ℓ u - ℓ -1 d + da ℓ-1 1 d + da ℓ-2 1 d + . . . + da 1 1 d = da ℓ u - ℓ -1 d + a ℓ-1 + a ℓ-2 + . . . + a 1
where

a 1 = 1 d(1 + 1 d-1 ) d-1 -(d -1)
and

a ℓ = a 1 1 + 1 d -1 ℓ-1 ∀ 2 ≤ ℓ ≤ d.
Informally, f d is linear with coefficient da ℓ on every interval ℓ-1 d , ℓ d for 1 ≤ ℓ ≤ d. Note that the maximum derivative of f d is 1/C(d), where

C(d) = d (1 + 1 d-1 ) d-1 -(d -1) d (1 + 1 d-1 ) d-1 = 1 - d -1 d (1 + 1 d-1 ) d-1 d→∞ -→ e -1 e
and C(d) is always larger than (e -1)/e.

Lemma 2

The robustness of Algorithm 1 is

1/ 1 C(d) +(1-η)(1-f d (η)) . When d is large enough, f d (η) ≈ 1 + e(e η-1 -1) e-1
and so the robustness is approximatively e-1 e • 1 1+(1-η)(1-e η-1 ) .

Proof We fix an arbitrary item j and bound the ratio of increase of the primal and the dual objective values caused by the arrival of item j. We set the dual variables as

y i = f d j b j x ij B i ∀i, z j = (1 -f d (min i∈S j {ℓ i })) b j
where ℓ i is the level of buyer i at the end of the algorithm's execution. By the definition of the dual variables, y i ≥ f d min i ′ ∈S j {ℓ i ′ } for every i ∈ S j . Therefore, b j y i + z j ≥ b j holds for every i ∈ S j , which indicates that the dual variables are feasible.

Let us assume that item j is not entirely sold during the algorithm's execution. This means that all interested buyers in S j exhausted their budget. Hence, by the definition of the dual variables, ∀ i ∈ S j : y i = 1 and z j = 0. The rate of change of the dual objective value related only to the y-variables is at most:

B i ∂f d ∂x ij ≤ B i • b j B i • f ′ d j b j x ij B i ≤ b j C(d)
where 1/C(d) is the maximum derivative of f d . Meanwhile, the increasing rate of the primal objective value is b j . We obtain that the primal change is at least 1/C(d) that of the dual.

In the remaining part of the proof, we assume that the algorithm sold all items completely. Note that z j can be written as z j = 1 0 (1 -f d (min i∈S j {ℓ i })) b j dy. In other words, one can imagine that during the allocation of item j, z j is increasing at a rate of (1 -f d (min i∈S j {ℓ i })) b j .

There are three stages in the algorithm. In Stage 1 and 3, the algorithm always allocates the fractions of item j equally to buyers in S j on the lowest level. [START_REF] Buchbinder | Online primal-dual algorithms for maximizing ad-auctions revenue[END_REF] showed that during these allocations, the increasing rate of the dual is at most 1/C(d) times the primal. We present our proof in Lemma 3 for completeness, which is similar to the proof of [START_REF] Buchbinder | Online primal-dual algorithms for maximizing ad-auctions revenue[END_REF].

We are now interested in the allocation during Stage 2 of the algorithm. We denote the predicted buyer i * = pred(j). In this stage, the algorithm allocates a part of item j only to the predicted buyer i * . The increasing rate of the dual objective value related only to y i * is

B i * ∂f d ∂x i * j ≤ B i * • b j B i * • f ′ d j b j x i * j B * i ≤ b j C(d) since f ′ d (u) ≤ 1/C(d)
for all 0 ≤ u ≤ 1. We note that every buyer i ∈ S j has spent at least η fraction of its budget before this stage, so z j ≤ (1 -f d (η)) b j . Therefore, the total increasing rate of the dual in this step is at most

B i * ∂f d ∂x i * j + ∂z j ∂x i * j ≤ b j C(d) + (1 -f d (η)) b j .
Combining all the cases, the increasing rate of the dual is at most

b j C(d) + (1 -f d (η)) b j during Stage 2, b j C(d)
during Stage 1 and 3.

We highlight that the algorithm allocates at most (1-η) fraction of item j during Stage 2. Therefore, the total increase of the dual due to the arrival of j is at most:

(1-η) 0 b j C(d) + (1 -f d (η)) b j dy + η 0 b j C(d) dy = 1 C(d) + (1 -η)(1 -f d (η)) b j .
The increase of the primal is b j , so we can deduce that the robustness of the algorithm is

1/ 1 C(d) + (1-η)(1-f d (η)) .
To finish the proof, we compute and estimate the value of f d (η) for large values of d. We have

f d (η) = f d ⌊η • d⌋ d = a 1 d 1 + 1 d -1 ⌊η•d⌋-1 -(d -1) = d(1 + 1 d-1 ) ⌊η•d⌋-1 -(d -1) d(1 + 1 d-1 ) d-1 -(d -1) = 1 + d(1 + 1 d-1 ) ⌊η•d⌋-1 -d(1 + 1 d-1 ) d-1 d(1 + 1 d-1 ) d-1 -(d -1) = 1 + d(1 + 1 d-1 ) ⌊η•d⌋-1 d(1 + 1 d-1 ) d-1 -1 • 1 1 - (d-1) d(1+ 1 d-1 ) d-1 = 1 + 1 C(d) 1 + 1 d -1 ⌊η•d⌋-d -1 d→∞ -→ 1 + e(e η-1 -1) e -1
Lemma 3 Assuming that item j is completely sold by Algorithm 1, during the allocations of Stage 1 and 3, the increasing rate of the dual objective value is at most 1/C(d) times the primal.

Proof The proof follows the proof of Buchbinder and Naor (2009b, Theorem 13.1). We present the details in Appendix A.

Theorem 1 Algorithm 1 is (1 -η)-consistent and 1/ 1 C(d) + (1 -η)(1 -f d (η)) -robust. When d is large enough, f d (η) ≈ 1 + e(e η-1 -1) e-1
and so the robustness is approximately e-1 e • 1 1+(1-η)(1-e η-1 ) . Proof Follows from Lemma 1 and Lemma 2.

An Algorithm with Predictions for Ad-Auctions

Recall that in this problem there are n buyers and each buyer 1 ≤ i ≤ n has a budget B i . Upon the arrival of item j, the algorithm discovers the bid2 b ij ≥ 0 of each buyer i, which is the price that buyer i is willing to pay to purchase item j. Additionally, the algorithm gets a predicted buyer pred(j) to whom item j should be sold (pred(j) = 0 if the item should not be sold according to the prediction). We are interested in fractional solutions as in [START_REF] Bamas | The primal-dual method for learning augmented algorithms[END_REF], so we consider the items to be splittable. Before the arrival of the next item, the algorithm needs to make an irrevocable decision and sell the current item in some fractions to some buyers. The objective is to gain maximum revenue from selling items to buyers. In this setting, we assume that b ij ≪ B i ∀i, j.

Formulation. The formulation of the Online Ad-Auctions problem follows that of the Online Bounded Allocation problem. Both the primal and the dual linear programs on Figure 2 now use the buyer-dependent prices, the bids.

Primal:

max n i=1 m j=1 b ij x ij m j=1 b ij x ij ≤ B i ∀ i (y i ) n i=1 x ij ≤ 1 ∀ j (z j ) x ij ≥ 0 ∀ i, j
Dual: Algorithm. We introduce a fictitious buyer with identity 0, such that b 0j = 0 for all item j. When the algorithm does not sell an item, it assigns it to the fictitious buyer 0. The purpose of buyer 0 is to simplify the description of the algorithm. We use a constant C in our algorithm that we define as

min n i=1 B i y i + m j=1 z j b ij y i + z j ≥ b ij ∀ i, j (x ij ) y i ≥ 0 ∀ i z j ≥ 0 ∀ j
C = (1 + R max ) η Rmax where R max = max i,j b ij B i
We present the pseudo-code of our algorithm in Algorithm 2. For each arriving item j, the algorithm considers two buyers: the predicted buyer i * = pred(j) and buyer i who maximizes the product b ij (1 -y j ), where y j is an indicator to know how exhausted the buyer's budget is. We make use of the confidence parameter in the predictions. Our algorithm reserves (1 -η) fraction of each buyer's budget for the prediction assignment. Whenever the bid of buyer i * is greater than the bid of buyer i, the algorithm assigns (1 -η) fraction of item j to i * and η fraction to i.

Intuitively, our proposed algorithm attempts to reserve some fraction of each buyer's budget for future purchases. However, if the predicted buyer's bid is high enough, the algorithm allows assignments to this buyer, even if the budget is close to saturation.

Algorithm 2 Learning Augmented Algorithm for the Online Ad-Auctions Problem. All primal and dual variables are initially set to 0. We maintain two sets N (i) and M (i) for each buyer i for the purpose of analysis only. for each new item j do let i * be the predicted buyer of item j, formally, pred(j) = i * if the prediction is not feasible then i * = 0 // the fictitious buyer

i ← arg max i ′ {b i ′ j (1 -y i ′ )} // weight bids with remaining budget if b ij (1 -y i ) ≤ 0 then i = 0 z j ← max 0, b ij (1 -y i ) if b ij < b i * j then x ij ← η and x i * j ← (1 -η) N (i * ) ← N (i * ) ∪ {j} end else x ij ← 1 // includes the case when pred(j) is infeasible end M (i) = M (i) ∪ {j} y i = y i 1 + b ij B i + b ij B i • 1 C-1 end Lemma 4
During the execution of Algorithm 2 the following always holds for every i

y i ≥ 1 C -1 C j∈M (i) b ij ηB i -1
Proof We adapt the proof of Buchbinder and Naor (2009b) with a slight modification: we prove the dual inequality by induction on the number of processed items. Initially, when no items arrived yet, the inequality is trivially true. Let us assume that the inequality holds right before the arrival of an item j. The inequality remains unchanged for all buyers, except for buyer i, who maximizes b ij (1 -y i ). Let y i denote the value before the update triggered by the arrival of item j and y ′ i its value after the update. We have

y ′ i = y i 1 + b ij B i + b ij B i • 1 C -1 ≥ 1 C -1 C j ′ ∈M (i)\{j} b ij ′ ηB i -1 • 1 + b ij B i + b ij B i • 1 C -1 = 1 C -1 C j ′ ∈M (i)\{j} b ij ′ ηB i • 1 + b ij B i -1 ≥ 1 C -1 C j ′ ∈M (i)\{j} b ij ′ ηB i • C b ij ηB i -1 = 1 C -1 C j∈M (i) b ij ηB i -1
The first inequality holds due to the induction hypothesis. The second inequality holds by the following sequence of transformations. For any y and z where 0 < y ≤ z ≤ 1 we have

ln(1 + y) y ≥ ln(1 + z) z ⇔ ln(1 + y) ≥ ln(1 + z) • y z ⇔ 1 + y ≥ (1 + z) y/z
We apply the above transformation with y = b ij /B i and z = R max at the second inequality. By the definition of C we obtain

1 + R max 1 Rmax • b ij B i = C b ij ηB i Since R max = max i,j b ij B i
by definition, the induction step is complete and the lemma holds.

Lemma 5

The primal solution is feasible up to a factor of (1 + R max ).

Proof

The first primal constraint requires m j=1 b ij x ij ≤ B i to hold for every i. By Lemma 4, we know that for every i the following holds.

y i ≥ 1 C -1 C j∈M (i) b ij ηB i - 1
Therefore, whenever j∈M (i) b ij ≥ ηB i , we have y i ≥ 1 and the algorithm stops allocating items to buyer i. The set M (i) and the value of y i are updated after the assignments. Therefore, buyer i can receive at most one additional item fraction once its budget is already saturated. We obtain j∈M (i) b ij < ηB i + max j {b ij } and the following formula.

m j=1 b ij x ij = j∈M (i) b ij x ij + j∈N (i) b ij x ij < B i + max j {b ij }
The inequality holds due to the feasibility of N (i), the set of items assigned by the prediction to buyer i. We can bound the prediction assignments as follows.

j∈N (i) b ij x ij ≤ (1 -η) j | pred(j)=i b ij x ij ≤ (1 -η) B i Therefore, m j=1 b ij x ij ≤ B i (1 + R max )
, which means that the first primal constraint is feasible up to a factor of (1 + R max ). The second primal constraint requires i x ij ≤ 1 to hold. During the allocations of Algorithm 2 the values of x ij and x i * j do not exceed 1 by the design of the algorithm. The lemma follows.

Theorem 2 Algorithm 2 is (1 -η)-consistent and 1-1/C 1+Rmax -robust. The robustness tends to 1 -e -η when R max tends to 0.

Proof First, we establish robustness. Upon the arrival of item j, the increase in the primal is

(1 -η) b i * j + η b ij if b ij < b i * j , b ij if b ij ≥ b i * j
which is always larger than or equal to b ij . Meanwhile, the increase in the dual is

B i ∆y i + z j = b ij y i + b ij C -1 + b ij (1 -y i ) = 1 + 1 C -1 b ij = C C -1 b ij
Hence, by Lemma 5, the robustness is C-1 C • 1 1+Rmax . Finally, we straightforwardly establish consistency. Every time the prediction solution gets a profit of b i * j , the algorithm achieves a profit of at least (1 -η) b i * j . The theorem follows.

Experiments

In the following experiments, we evaluate the algorithms' performance with the competitive ratio metric. We calculate the competitive ratio by dividing the objective value of the algorithm, ALGO(I), with the objective value of the optimal fractional offline solution, OPT(I). The competitive ratio is visible on the y-axis of the figures. The x-axis corresponds to the ratio with which the algorithms consider the prediction. We indicate with η = 0 no doubt and η = 1 complete doubt in the prediction. Therefore, the left-hand side of the figures corresponds to a prediction dominated algorithm, while the right-hand side is closer to a classical online algorithm. The different colors on the figures correspond to different prediction error rates. The lines represent the average over several executions, while the colored areas show the 95% confidence intervals.

Online Bounded Allocation

We present here four experiments. Table 1 below summarizes the configurations of the instances. Figure 3 displays the competitive ratio of the algorithm on different instances.

Predictions. We create predictions for the experimental instances by introducing perturbations to the optimal offline integral solution. The perturbation is skipped when |S j | = 1. When |S j \ {i * }| > 1 we choose uniformly at random a remaining buyer to replace the optimal buyer. Manual Instance. Instance 1 corresponds to one of the pathological inputs for the water-filling strategy of Buchbinder and Naor (2009b). We created this instance manually to observe the behavior of Algorithm 1 when this strategy performs poorly. In Instance 1's scenario, each buyer i is interested in each item j when i ≥ j. The optimal solution is to sell each item j to buyer i, where i = j, while the water-filling strategy attempts to allocate each item equally.

Randomized Instances. Instances 2-4 are randomly generated based on their corresponding configuration visible on Table 1. We executed each instance 20 times. The lines on Figure 3 correspond to the average of these executions, and the colored areas correspond to the 95% confidence intervals. Instance 2 and Instance 3 mimic real-life instances, where the general expectation is to have a small bound d on the interested buyers. The average item price over the average budget value across the executions was 6.36% for Instance 2 and 0.98% for Instance 3. Finally, Instance 4 shows an example where the integral solution (and therefore the prediction) is not optimal. While Instance 2 and 3 have no integrality gap, Instance 4 has an average of 17.99% observed integrality gap over the 20 executions. Instance 4 has a large bound on the number of interested buyers, and the items' prices vary greatly. Evaluation. The experiments confirm the water-filling algorithm's benefit from the prediction information. We showed that Algorithm 1 has improved performance on the pathological input of the water-filling strategy even with high prediction error rates. Besides, the algorithm demonstrated firm robustness against elevated prediction error rates in the second instance, where the algorithm performed close to optimality without predictions. Furthermore, we observed improved performance on the third instance, which represents a close to real-life use case. In the fourth instance, we can remark the drawback of the predictions. When the integral solution of the linear program is not optimal -or even far from optimal -the prediction can significantly misguide our algorithm, decreasing the performance towards the standard performance bounds.

Online Ad-Auctions

We present one experiment for the Online Ad-Auctions problem here. Figure 4 displays the competitive ratio of the algorithm.

Predictions. The predictions rely on the optimal offline integral solution, which is a partial mapping from items to buyers. We perturbed the solution as suggested by [START_REF] Bamas | The primal-dual method for learning augmented algorithms[END_REF] and used the error rate parameter as a probability to randomly choose a buyer among the buyers who placed a non-zero bid on the item. However, the perturbation is only possible if the solution remains feasible.

Instance. Our test instance is a randomized instance with 100 buyers and 10, 000 items, adapting the model described in [START_REF] Lavastida | Learnable and instance-robust predictions for online matching, flows and load balancing[END_REF]. For every item j, there are exactly 6 random buyers proposing a bid. The values of the bids follow a lognormal distribution with mean and deviation set to 0.5. By choosing the budget of the bidders, we can tune the hardness of the instance under the constraint that R max remains reasonably small. We set the budget to 0.1 fraction of the total bids, leading to a value of R max ≈ 0.1. The integrality gap of the instance is close to 0. Evaluation. We can observe the algorithm's benefit of the prediction. We note that in the algorithm η can not be 0 since, in this case, the update of y i would require division by 0. The closer η gets to 0, the closer the performance of the algorithm gets to 1. As expected, the performance degrades with increased prediction perturbation. The observed robustness is not monotone in η, unlike the bound shown in this paper. We think that this performance degradation for η around 0.5 is due to the rather simplistic mixture between the primal-dual and the predicted solution.

Conclusion

The presented algorithms in this paper incorporate prediction information and achieve competitive consistency and robustness. However, it remains an open question to determine lower bounds and verify how tight our obtained bounds are. An important research direction for the future is to study matching problems with dynamic confidence parameters, which change over time depending on the quality of the previous predictions. In general, it might be possible to design more complete systems that evolve through the interactions between the algorithms and the learning oracles. The oracles provide useful information (predictions) for the algorithms to improve their performance (as studied in this paper), while the algorithms could give feedback to the oracles to enhance their predictions.

Figure 1 :

 1 Figure 1: Formulation of the Online Bounded Allocation problem

Figure 2 :

 2 Figure 2: Formulation of the Online Ad-Auctions problem

Figure 4 :

 4 Figure 4: Observed competitive ratio

Table 1 :

 1 Properties of the experiment instances

	Name	Type	Buyers	Items d = max{|S j |} Budget range Item price range
	Instance 1 manual	5	5	5	100 -100	100 -100
	Instance 2 random	100	1.000	5	10 -100	0.1 -8
	Instance 3 random	100 10.000	3	10 -1.000	1 -10
	Instance 4 random	80	80	40	10 -100	10 -100

we call the prices bids because of the motivations in the auctions setting

Acknowledgments

This research has been partly supported by the research program on Edge Intelligence at the Multidisciplinary Institute on Artificial Intelligence MIAI in Grenoble (ANR-19-P3IA-0003) and by the french research agency Energumen (ANR-18-CE25-0008).

Appendix A. for the Online Bounded Allocation problem

Lemma 3 Assuming that item j is completely sold by Algorithm 1, during the allocations of Stage 1 and 3, the increasing rate of the dual objective value is at most 1/C(d) times the primal.

Proof

The proof follows the proof of Buchbinder and Naor (2009b, Theorem 13.1). We highlight that this proof considers items that were sold completely. There are two cases.

Case 1: The highest level item j was sold at is ℓ, and at the end of the algorithm, all buyers in S j spent at least ℓ+1 d fraction of their budget. By the definition of the dual variables

, the increasing rate of z j at any time during the allocation of item j is at most

Besides, as the highest level on which item j was sold at is ℓ, the rate of change of the dual value due to the change in y i is:

Therefore, the total change of the dual is at most

Case 2: The highest level on which item j was sold at is ℓ and at the end of the execution at least one buyer in S j spent less than ℓ+1 d fraction of its budget. In this case we have to set z j = (1 -f d (ℓ/d)) b j to satisfy the dual constraint. During any (short) period of time ∆t, the increase of i B i y i over i in the highest level is at most:

where the fraction (d -1)/d comes from the fact that there are at most (d -1) buyers in the highest level. We recall that d is the bound on the size of all S j and at least one buyer did not reach the highest level as of the statement of this case. The increase of i B i y i over i in the lower levels is at most b j d a ℓ (1 -∆t) by the definitions of a ℓ+1 = a ℓ (1 + 1/(d -1)) and a ℓ = ((d -1)/d)a ℓ+1 . Therefore, by adding the terms together we get that the increasing rate of i B i y i is at most b j (d -1) a ℓ+1 . Hence, the increasing rate of the dual is at most: The increasing rate of the dual is at most b j /C(d), while for the primal it is b j . The lemma follows from this conclusion.