How to allocate goods when the waiting list is essentially infinite. New queues for overloaded systems, by Jacob Leshno

Matching is about who gets what when allocation isn't entirely by price. And a common means of allocating scarce goods is by waiting lists. But there are special problems to consider when the goods being allocated are so scarce that most of those waiting will never receive an allocation. How should applicants be matched to goods when they become available, and how can applicants be given an incentive to pass on goods that might more efficiently be allocated to someone else, if match quality is private information? In considering these things, Jacob Leshno opens up a new front for market design, and introduces a novel kind of queue and some new ideas to the venerable study of queues.

For example, the city of Chicago caps the waiting list for public housing at 60,000 people. The total supply of public housing that they administer is around 20,000 units, and units only become vacant after being occupied for several years, so it's clear that most people who are eligible for public housing will never get it; the system is simply overloaded.  How should the places be allocated? The whole point of public housing is that we don't want to use price to determine who gets what by pricing the poorest out of the market.

Dynamic Matching in Overloaded Systems by Jacob Leshno
Abstract: "In many assignment problems items arrive stochastically over time. When items are scarce agents form an overloaded waiting list and items are dynamically allocated as they arrive; two examples are public housing and organs for transplant. Even when all the scarce items are allocated, there is the efficiency question of how to assign the right items to the right agents. I develop a model in which impatient agents with heterogeneous preferences wait to be assigned scarce heterogeneous items that arrive stochastically over time. Social welfare is maximized by appropriately matching agents to items, but an individual impatient agent may misreport her preferences to receive an earlier mismatched item. To incentivize an agent to avoid mismatch, the policy needs to provide the agent with a (stochastic) guarantee of future assignment, which I model as putting the agents in a priority buffer-queue. I first consider a standard queue-based allocation policy and derive its welfare properties. To determine the optimal policy, I formulate the dynamic assignment problem as a dynamic mechanism design problem without transfers. The resulting optimal incentive compatible policy uses a buffer-queue of a new queueing policy, the uniform wait queue, to minimize the probability of mismatching agents. Finally, I derive a robustly optimal policy which uses a simple rule: giving equal priority to every agent who declines a mismatched item (a SIRO buffer-queue). This robustly optimal policy has several good properties that make it a compelling market design policy recommendation."

That is, to reduce mismatches, the allocation process has to give some people the incentive to wait when they are offered a space of the “wrong” type for them, e.g. in a wrong location.  It is easy to incentivize the first such person, e.g. you could promise him that if he declines the space currently being offered, he will be the first to get a space in his preferred location when it becomes available. If the anticipated wait is short enough, this could be an attractive proposition. But suppose the next person on line likes the same location as the first person? You couldn’t offer him as good a deal, since he would now have to wait for the second space to become available in his preferred location. So, it could be that, before someone who actually prefers the current location comes to the head of the line (which they have to reveal, since it’s private information), a mismatch would occur when a person decides it’s better to take the wrong location than to wait further for the kth place at the location he prefers. In a simple model with just two locations, Jacob shows (the far from obvious conclusion) that maximizing the number k of people willing to wait for their preferred location is the same as minimizing the steady state probability of mismatches.

But conventional queue disciplines (e.g. FIFO, LIFO, etc.) don’t maximize the number of people willing to wait in this buffer queue of folks who would have been mismatched if they had taken what was first offered to them. In solving the optimization problem, Jacob discovered/invented a new queue discipline that he calls uniform wait. People who choose to wait in the buffer queue for a given location are given different probabilities of being called to the head of the queue as different housing spaces arrive to be allocated, based on how many people have joined the buffer queue so far, so that the expected wait for any of the 1,…k people who might decide to wait is equal at the moment that they have to decide whether to join the buffer queue. That is, if you are the first to join, you will get the location you are waiting for if it arrives before someone else has joined, and after that you will have some probability of getting each apartment-at-the-right-location as one arrives, and that probability will depend on how many other people are also waiting. In this way, the 2^nd through kth people who join can also be given good incentives to wait for a perfect match; they might not have to wait for all the people ahead of them to be served. Everyone faces the same choice; to take the offered apartment (at the wrong location) or to have a fixed (uniform) waiting time for one at the location they prefer, whether they would be the first person in the buffer queue or the kth. Mismatches will now occur only when this buffer queue has so many people that new people prefer to accept a mismatch than to wait.

Jacob also proposes an almost optimal, more robust solution (that doesn't have to be tuned to the particular parameters of the problem) which is to place mismatched applicants into an unordered buffer, from which they are selected at random when an object of the kind they are all waiting for becomes available.

Incidentally, Jacob is a local hero:
"The Martin Award is awarded to HBS doctoral students enrolled in the PhD in Business Economics program who have excelled at conducting outstanding academic research. This year, the faculty have selected one student to receive the Martin Award.
Jacob Leshno – Jacob studies market design, specifically the dynamic allocation of scarce resources through the use of waiting lists."

Jacob is on the job market this year, you could hire him. Here's a link to his papers.