Simple policies in dynamic matching markets

Abstract

This thesis containts two self contained essays.The first essay studies a foundational model of dynamic matching market with abandonment. This model has been studied by Collina et al. (2020) and Aouad and Saritac(2022), and many other papers have considered special cases. The performance of greedy policies – which identify a set of “acceptable” matches up front, and perform these matches as soon as possible – is compared to that of an omniscient benchmark which knows the full arrival and departure sequence. A novel family of linear programs (PLP) is introduced to identify which greedy policy to follow. We show that the value of PLP is a lower bound on the value of the greedy policy that it identifies in two settings of interest: • The case where the everyone has the same departure rate. • The bipartite case where everyone on the same side of the market has the same departure rate. The proofs of these results use a new result (Lemma 1), which relates the probability that at least one agent from a set of types is present in the system to the expected number of such agents. We show that the value of PLP is at least 1/2 of the reward rate earned by the omniscient policy (Proposition 4). Therefore, for both settings above, the identified greedy policy provably earns at least half of the omniscient reward rate. This improves upon the bound of 1/8 from Collina et al. (2020). In both settings the competitive ratio of 1/2 is the best possible: no online policy can provide a better guarantee (Theorem 2). The second essay models the problem facing a policymaker who must allocate rapid rehousing support to people experiencing homelessness and wishes to minimize the steady-state size of the homeless population. Typically, support is given to the most vulnerable applicants, or to applicants most likely to remain housed. Although these approaches can be effective in some cases, in general they may result in a homeless population that is arbitrarily larger than what could be achieved by an optimal policy. We propose an alternative priority queue that is approximately optimal. We then study a family of policies where the policymaker does not differentiate between agents based on their characteristics. Within this family, FIFO queues best target the most vulnerable. If the most vulnerable households benefit most from housing assistance, then a FIFO queue minimizes the expected unhoused population. Conversely, a LIFO queue is optimal if the least vulnerable households benefit most from housing assistance. Finally, we expand our model to allow households to choose among several allocation systems. We show that even in this larger family of policies, if the most vulnerable households are also the ones that most benefit from housing assistance, a FIFO queue minimizes the expected unhoused population.