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 less than or equal to R if they do not. Future rewards are discounted at a rate 0 less than or equal to alpha less than or equal to 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 ol gan transplants, studied in an earlier work.