PaperlayerView exact revision on arXiv

Source-linked AI summary

Secretary and Online Matching Problems with Machine Learned Advice

Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, Pavel Kolev

arXiv:2006.01026v2cs.DS

TL;DR

Worst-case analysis can be pessimistic for online selection, while machine-learned predictions can help but may also be arbitrarily inaccurate. The paper augments three online selection problems with predictive advice and designs algorithms that improve competitive ratios for sufficiently accurate predictions while preserving a worst-case guarantee, establishing a trade-off between the two regimes.

  • Problem

    Worst-case analysis may be pessimistic for online inputs, but predictive advice can be arbitrarily inaccurate, creating a need for algorithms robust to both conditions.

  • Method

    The paper augments secretary, online bipartite matching, and graphic matroid secretary algorithms with predictions using a three-phase combination of sampling, prediction exploitation, and prediction disregard.

  • Results

    The algorithms improve competitive ratios when predictions are sufficiently accurate while retaining worst-case guarantees for subpar predictions, with a trade-off between the two ratios.

  • Takeaways & Limitations

    Machine-learned advice can enhance online selection algorithms without requiring reliable predictions in every instance.

  • Takeaways & Limitations

    The optimality of the proposed three-phase results in general remains open, and the prediction error is unknown when selecting trade-off parameters.

Abstract

from arXiv · show

The classical analysis of online algorithms, due to its worst-case nature, can be quite pessimistic when the input instance at hand is far from worst-case. Often this is not an issue with machine learning approaches, which shine in exploiting patterns in past inputs in order to predict the future. However, such predictions, although usually accurate, can be arbitrarily poor. Inspired by a recent line of work, we augment three well-known online settings with machine learned predictions about the future, and develop algorithms that take them into account. In particular, we study the following online selection problems: (i) the classical secretary problem, (ii) online bipartite matching and (iii) the graphic matroid secretary problem. Our algorithms still come with a worst-case performance guarantee in the case that predictions are subpar while obtaining an improved competitive ratio (over the best-known classical online algorithm for each problem) when the predictions are sufficiently accurate. For each algorithm, we establish a trade-off between the competitive ratios obtained in the two respective cases.

1 Introduction

The paper augments online selection algorithms with machine-learned advice, seeking improved guarantees when predictions are accurate without sacrificing too much worst-case performance when they are poor. It develops deterministic approaches for secretary, online bipartite matching, and graphic matroid secretary problems, with trade-offs between accurate-prediction and worst-case competitive ratios.

  • 1 Introduction: Machine-learned advice can improve pessimistic worst-case guarantees for online algorithms when predictions about future inputs are sufficiently accurate.The approach must also account for predictions that may be arbitrarily poor.
  • 1 Introduction: The paper augments secretary, online bipartite matching, and graphic matroid secretary algorithms with predictions while retaining worst-case guarantees when predictions are subpar.The algorithms aim to lose only a constant factor over existing worst-case guarantees.
  • Meta Result: The resulting competitive ratios trade off improved performance for sufficiently accurate predictions against the amount surrendered in the worst case.Greater confidence in predictions permits a better accurate-prediction ratio while weakening the worst-case guarantee.
  • Meta Result: The algorithms use three arrival phases: sampling without selection, a prediction-exploiting policy, and a prediction-ignoring policy.The execution order of the two extreme policies is crucial to showing that they do not obstruct each other excessively.
  • 1 Introduction: The online bipartite matching algorithm can be converted into a truthful mechanism for single-value unit-demand domains, including when predictions are incorporated.The paper also identifies truthfulness for the uniform-edge-weight special case of the classical algorithm.
  • Meta Result: With nearly perfect predictions, online bipartite matching and graphic matroid secretary algorithms can approach a 1/2-approximation.For online bipartite matching, 1/2 is best possible in the corresponding vertex-weighted setting; the graphic matroid guarantee is noted as probably not tight.

2 Preliminaries

The paper formalizes uniformly random-order online selection, competitive performance against an offline optimum, and graph structures used for matching-based problems. It also introduces the Lambert W-function needed later for algorithm design.

  • Online selection: Online selection reveals n objects one at a time in uniformly random order, requiring selection of a best feasible subset.The objective is to maximize total selected value.
  • Competitive analysis: A γ-competitive algorithm achieves expected value at least γ·OPT, where OPT is the offline optimum knowing the full sequence.The expectation covers arrival-order randomness and any internal algorithmic randomness.
  • Graph preliminaries: A bipartite graph partitions vertices into L and R, with edges only between the two parts; matchings use edges incident to at most one edge per node.The notation also includes induced subgraphs and matched-node sets.
  • Graph preliminaries: The paper assumes every subset of L has a perfect matching after adding zero-weight private nodes to R when necessary.This normalization is stated to be without loss of generality.
  • Analytic tool: The Lambert W-function inverts f(w)=we^w and has two real branches, W−1 and W0, on −1/e ≤ x < 0.These branches are later used to specify sampling fractions.

3 Secretary problem

The secretary setting predicts the maximum value rather than the winning identity, then combines prediction-driven and prediction-free policies through a confidence parameter. The resulting algorithm improves on 1/e when predictions are sufficiently accurate, while retaining a 1/(ce) guarantee when they are poor.

  • Problem and advice: The value-maximization secretary problem selects one secretary online to maximize expected value, unlike the classical version that maximizes the probability of selecting the best.Any α-approximation for the classical problem also applies to the value-maximization variant.
  • Problem and advice: The advice is a prediction p∗ for the maximum value OPT, with error η = |p∗−v∗|; the algorithm does not know η.The prediction identifies the target value, not which secretary attains it.
  • Algorithm: Algorithm 1 uses three phases: sample without selecting, exploit the prediction using a threshold, then apply a prediction-free threshold policy.The confidence parameter λ controls how closely the prediction is trusted, while c controls the tolerated worst-case loss.
  • Algorithm: Low confidence sets λ close to p∗ and recovers the classical solution; high confidence sets λ close to 0 and can improve the ratio beyond 1/e when η < λ.The parameter c represents the factor accepted in the poor-prediction worst case.
  • Guarantees: 1/(ce) is retained when the prediction is poor, while for 0 ≤ η < λ the guarantee is f(c)(1 − (λ + η)/OPT) when OPT − λ − η ≥ 0.The proof handles separately predictions whose lower threshold exceeds OPT and those whose threshold does not.
  • Guarantees: Figure 1 compares gc,λ(0) with the no-prediction baseline 1/e across λ/p∗ and c, showing improvement below the baseline curve and degradation above it.The axes are chosen as λ/p∗ and c.
  • Limitation: Because η is unknown, the algorithm cannot choose λ and c optimally for every possible prediction error.Different prediction errors require different parameter settings.
  • Guarantees: η + λ = 1/10OPT yields improvement over 1/e for c ≥ 1.185, and large c approaches a 1-competitive ratio when predictions are nearly perfect.The confidence and worst-case-loss parameters are independent, but their choices determine the trade-off between robustness and accuracy.

4 Online bipartite matching with random arrivals

The section augments online bipartite matching with predictions of optimal edge values and develops a deterministic three-phase algorithm. Its guarantee trades performance under prediction error against improved performance when predictions are accurate.

  • Prediction model: The algorithm predicts each offline node’s edge value in a fixed optimal matching, without predicting the specific adjacent edge.These predictions also implicitly estimate the optimal matching value.
  • Prediction model: Perfect predictions yield a 1/2-approximation, even under adversarial arrival order, using a simple deterministic greedy algorithm.The approach is closely related to an earlier greedy algorithm and can operate online.
  • Algorithm: Algorithm 3 combines two sampling-based phases with a threshold-greedy third phase to balance accurate-prediction performance against robustness to poor predictions.The first phases avoid matching too many or too few offline nodes before threshold greedy is applied.
  • Guarantees: Theorem 4.1 establishes an asymptotic gc,d,λ(η)-competitive guarantee for uniformly random arrivals.The analysis provides two lower bounds on the expected matching value, covering prediction-sensitive and worst-case behavior.
  • Guarantees: For small λ, the guarantee is roughly (d−1)/2c when η is small and ln(c/d)/c when η is large.As c/d approaches 1, the small-error bound approaches 1/2, while the large-error guarantee increases accordingly.
  • Mechanism extension: Algorithm 3 can also be transformed into a truthful mechanism for single-value unit-demand domains with the same social-welfare guarantee.The construction exploits flexibility in the algorithm, with formal definitions and proof supplied separately.

5 Deterministic graphic matroid secretary algorithm

This section develops deterministic algorithms for the graphic matroid secretary problem using a bipartite representation of the graph. A baseline algorithm achieves a deterministic (1/4−o(1))-competitive guarantee, while the prediction-augmented algorithm trades accuracy-sensitive performance against a worst-case bound.

  • Problem and representation: The graphic matroid secretary problem selects a maximum-weight forest from graph edges arriving in uniformly random order.Selected edges must remain acyclic.
  • Problem and representation: Predictions assign each graph vertex the maximum weight of an adjacent edge, with prediction error measured from these vertex-level values.The prediction is equivalent to the maximum adjacent edge weight in an optimal greedy solution.
  • Baseline algorithm: The baseline deterministic algorithm represents the graph as a bipartite graph and accepts an edge only when its corresponding matching preserves the forest constraint.Both endpoints being unmatched is sufficient to prevent a cycle, although it is not necessary.
  • Baseline algorithm: Algorithm 4 is a deterministic (1/4−o(1))-competitive algorithm for the graphic matroid secretary problem.It is presented as an improvement over a prior randomized algorithm because it does not require randomness.
  • Prediction-augmented algorithm: Algorithm 5 adds predictions through a three-phase procedure that uses prediction-based thresholds and a fail-safe threshold from the sampling phase.The fail-safe threshold limits selections when predictions are poor, particularly when they are too low.
  • Guarantees: Theorem 5.3 gives an asymptotic gc,d,λ(η)-competitive guarantee in expectation for the prediction-augmented algorithm.The analysis assumes distinct edge weights adjacent to each vertex in its small-error case.
  • Guarantees: For small λ, the guarantee is roughly (1/d−1/c)/2 when η is small and (d−1)/c2 when η is large.When d approaches 1 and c approaches infinity, the accurate-prediction bound approaches 1/2, whereas the poor-prediction bound can become arbitrarily bad.

6 Conclusion

The section frames prediction-augmented online selection as promising while identifying unresolved questions about natural prediction models, worst-case guarantees, and optimality. It also examines randomized variants of the deterministic secretary algorithm and their competitive-ratio trade-offs.

  • The results provide initial evidence that online selection problems are promising settings for machine learned advice.
  • Open questions: Open questions include natural prediction models for general matroid secretary problems and whether the three-phase results are optimal beyond that approach.
  • Randomized algorithms: Randomizing the confidence parameter λ can smooth the deterministic competitive-ratio discontinuity at η = λ.The expected ratio becomes a convex combination of two competitive ratios.
  • Randomized algorithms: A randomized distribution cannot outperform every deterministic choice because η is unknown and matching the deterministic optimum requires the distribution’s center of mass to equal η.

A.2 Comparison between Algorithm 1 and its naive randomization

This section compares Algorithm 1 with a naive randomization that mixes the classical secretary algorithm and a prediction-based threshold rule. With equal worst-case guarantees, Algorithm 1 performs better under sufficiently accurate predictions for suitable parameter values.

  • The naive randomization chooses the classical secretary algorithm with probability γ and a prediction-based threshold procedure with probability 1 − γ.
  • Setting γ = 1/c gives both algorithms a worst-case guarantee of at least 1/(ce)-competitive when predictions are poor.
  • For λ + η = δ ·OPT with small δ, the comparison focuses on accurate predictions while preserving the shared worst-case guarantee.
  • Figure 3 compares the classical 1/e bound, Algorithm 1’s guarantee, and the obvious randomized algorithm’s guarantee.
  • For δ = 0.1, Algorithm 1 is at least 1/e-competitive for c ≥ 1.185 and beats naive randomization for c ≥ 1.605.Its advantage over naive randomization decreases as δ increases.
  • Supporting construction: The comparison uses a perfect bipartite graph construction that adds zero-weight edges connecting corresponding left-side nodes.

C General analysis of the algorithm of Kesselheim et al. [22]

This section analyzes a modified Kesselheim et al. online matching algorithm under uniformly random vertex arrivals. The proof uses optimal matchings on progressively revealed induced subgraphs and a structural lemma for perfect bipartite graphs.

  • The analysis studies a modified Kesselheim et al. algorithm for online matching on perfect bipartite graphs.
  • Algorithm: The algorithm observes an initial sample, then processes later arrivals by computing an optimal matching on the revealed left nodes and accepting the assigned edge when feasible.
  • Additional analysis: The section also establishes a lower-bound analysis for the probability that a right-side node remains unmatched after Phase II.
  • Proof framework: The proof models arrivals as a random permutation and defines the event that the current matching can accept the edge assigned to the arriving node.
  • Proof framework: Lemma C.2 bounds the expected contribution of each processed node, and the section uses it to derive Theorem C.1.

C.2.1 Proof of Theorem C.1

The proof of Theorem C.1 proceeds by applying the bound established in Lemma C.2 and combining the resulting inequalities.

  • Theorem C.1 is derived by applying Lemma C.2 to the algorithm’s expected contribution.
  • The proof section therefore links the per-node estimate from Lemma C.2 to the theorem-level competitive guarantee.
  • The remaining inequalities follow by combining the relevant bounds involving ⌊n/c⌋.

C.2.2 Proof of Lemma C.2

The proof of Lemma C.2 analyzes conditional expectations over random subsets and matching events, deriving probability bounds by decomposing the relevant events and combining intermediate inequalities.

  • Conditional setup: The proof conditions on a fixed subset S of left nodes and the corresponding edge in the optimum matching.The subset event and edge event are fixed before the subsequent probability analysis.
  • Event decomposition: The argument represents a conditional expectation through products of probabilities for events Q_k across successive arrival stages.The product form is stated in equation (17), with conditioning events W_i,t.
  • Probability bounds: For intermediate stages, the proof lower-bounds Pr[Q_t | W_i,t] by upper-bounding the complementary event.This step uses the relation Pr[Q_t | W_i,t] = 1 − Pr[not Q_t | W_i,t].
  • Conclusion: Combining the intermediate inequalities yields a common lower bound for every summand in the conditional expectation.The resulting bound is then used to establish the lemma’s stated conclusion.

C.3 Algorithm 3 (Omitted Proofs)

This section develops supporting bounds for Algorithm 3 and extends the matching analysis to bipartite-matroid graphs, culminating in a lower-bound expression optimized at c = 2.

  • Algorithm 3: The analysis lower-bounds the probability that a right node remains unmatched after Phase II of Algorithm 3.Lemma C.5 states this guarantee for every right node in a perfect bipartite graph.
  • Summation bounds: The section’s proof infrastructure includes summation identities and induction-based derivations used in later bounds.Claims D.1 and D.2 provide the stated closed-form tools.
  • Summation bounds: The lower bound is maximized at c = 2 and yields f(2, n) approximately 1/4.The optimization follows from the behavior of g(x), whose maximum over x > 0 occurs at x = 2.
  • Bipartite-matroid extension: An undirected weighted graph is transformed into a bipartite-matroid graph by representing original edges as left nodes and original vertices as right nodes.Each original edge connects to its two endpoints with equal weights.
  • Bipartite-matroid extension: The matching analysis is extended to bipartite-matroid graphs, producing bounds for selected arrival positions and the resulting matching structure.The extension uses Lemmas D.3 and D.4 and distinguishes matching⋆ from ordinary matching.

D.4 Proof of Theorem 5.2

This section analyzes Phase III of Algorithm 5 to establish a worst-case bound and prove the associated theorem. The proof bounds eligibility and matching events through case distinctions and conditioning arguments.

  • The section analyzes Phase III of Algorithm 5 to prove a worst-case bound of (d −1)/c2.
  • The proof studies when distinct vertex pairs are eligible for matching and lower-bounds the event that adding an edge preserves a matching⋆.
  • The analysis conditions on the set of nodes appearing in Phases I and II and distinguishes cases based on the highest-weight nodes sampled.
  • Lemma E.3 applies the argument to perfect bipartite-matroid graphs and considers separate cases for ℓ=⌊m/d⌋+1 and ℓ∈{⌊m/d⌋+2,...,m}.
  • The final bound combines a union bound with equation (18).

E.3 Proof of Theorem 5.3

The proof of Theorem 5.3 lower-bounds the expected contribution of Phase III by analyzing vertex eligibility and the probability that a selected edge preserves matching⋆ feasibility.

  • Expected contribution: The final expected-contribution bound combines the Phase III guarantee with the earlier eligibility estimate.The proof concludes by combining the first inequality in (22) with Claim E.2.
  • Matching⋆ feasibility: The argument lower-bounds the event that the arriving edge together with the current matching forms a matching⋆.Lemma E.3 gives the corresponding Phase III guarantee for every relevant arrival position.

F Truthful mechanism for unit-demand domain

The section develops a truthful online mechanism for single-value unit-demand domains by modifying the matching procedure with monotone allocation rules and critical-value pricing. It establishes polynomial-time computability and a social-welfare approximation guarantee.

  • Motivation and model: The mechanism targets truthful online allocation in single-value unit-demand domains, where agents value sets of preferred items uniformly.Truthfulness means reporting the true value is always in an agent’s best interest, regardless of other declarations and arrival order.
  • Mechanism phases: Phase I assigns no items and charges zero, while Phase III assigns an eligible preferred item with the lowest prediction-based price threshold.Phase III uses thresholds of the form p∗_r − λ and charges the selected threshold.
  • Mechanism phases: Phase II computes an offline matching on agents seen so far and assigns an edge only when it preserves the current online matching.The assigned agent pays the critical value τ_a associated with the monotone matching algorithm.
  • Truthfulness: Monotonicity requires each agent either to remain unmatched below a critical value or to receive the same neighbor above it.This property supports truthful behavior under the critical-value pricing rule.
  • Guarantee: The resulting deterministic truthful mechanism is a gλ,c,d(η)-approximation for social-welfare maximization, with its alignment and pricing computable in polynomial time.The guarantee uses the function specified in Theorem 4.1 and depends on the mechanism parameters.
  • Matching algorithm: A lexicographically maximum-weight matching algorithm supplies the required monotone matching rule and can be computed in polynomial time using at most O(n^2) calls to an exact algorithm.The resulting lexicographically maximum weighted matching is unique for every input instance.
Loading 2006.01026v2…