Matching Algorithms for Blood Donation

on YouTube ↗48m

" summary

Facebook’s donation product connects 35 million registered donors to hospitals and drives via push notifications and models donor-to-recipient matching with a per-user notification cooldown K, static donors, and time-varying recipients. An LP upper bound guides a simulation-based online algorithm that achieves a proven 0.5 competitive ratio in theory; practical heuristics (random, round‑robin, greedy) are tested in city simulations where greedy approaches near offline optimal but sacrifices fairness. The biggest real-world bottleneck is reliably estimating conversion probability from notifications.

AI-written summary · about

" chapters (26)

1. 0:00Intro
2. 0:43(Safe) Blood is a Scarce Resource
3. 5:23Scarce and Safe and Regularly-Supplied Blood
4. 6:15Blood Supply Chain
5. 8:44Blood Donation at Facebook
6. 13:10Problem Description: Matching Supply & Demand
7. 15:10Problem Formulation
8. 16:41Objectives
9. 17:54Example Matching Problem
10. 25:05Solving for the Omniscient aka "Optimal" Policy For a foved horizon, if we know the full set of edges across all time periods (i.e., know the arrivals and departures of recipient vertices) ...
11. 25:32Complexity
12. 27:21Connections to Standard Online Matching
13. 30:52Online Matching with (Offline) Reusable Resources
14. 34:07A Different View: Stochastic Online Scheduling
15. 35:14A Benchmark: Competitive Ratio
16. 35:39Two-Phase Approach to Designing ALG
17. 36:30E[OPT] Benchmark LP Value
18. 38:02A Simulation-based (Non-Adaptive) ALG
19. 40:04Relation to a Very Recent Working Paper
20. 41:02Challenges Adapting this Model to Blood Donation
21. 42:37For now: Heuristic Policies
22. 44:21Simulations: Setup
23. 44:41Simulations: Results
24. 45:23Complementary Issue: Learning Model Parameters
25. 46:17Conclusions
26. 46:48Open Problems for Simons Participants (1)