Greedy Algorithms for Stationary Dynamic Matching: Part 1

How should a decision-maker form matches in an environment where agents arrive and depart over time?

This video gives an overview of my recent paper with Felipe Simon.

We propose a simple "greedy" matching policy, and show that when departure rates are homogeneous, our policy achieves at least half of the reward earned by an optimal policy with perfect foresight. We conjecture that this conclusion holds even without assumptions on departure rates.

Видео Greedy Algorithms for Stationary Dynamic Matching: Part 1 канала Nick Arnosti