One-Attribute Sequential Assignment Match Processes in Discrete Time

We consider a sequential matching problem where M offers arrive in a random stream and are to be sequentially assigned to N waiting candidates. Each candidate, as well as each offer, is characterized by a random attribute drawn from a known discrete-valued probability distribution function. An assignment of an offer to a candidate yields a (nominal) reward R > 0 if they match, and a smaller reward r ≤ R if they do not. Future rewards are discounted at a rate 0 ≤ α ≤ 1. We study several cases with various assumptions on the problem parameters and on the assignment regime and derive optimal policies that maximize the total (discounted) reward. The model is related to the problem of donor-recipient assignment in live organ transplants, studied in an earlier work.