Designing queues for overloaded waiting lists, by Jacob Leshno

 Here's a paper by Jacob Leshno, with a really creative new contribution to the (venerable) queuing literature. 

Leshno, Jacob D. 2022. "Dynamic Matching in Overloaded Waiting Lists." American Economic Review, December, 112 (12): 3876-3910. DOI: 10.1257/aer.20201111 (ungated working paper link here)

"Abstract: This paper introduces a stylized model to capture distinctive features of waiting list allocation mechanisms. First, agents choose among items with associated expected wait times. Waiting times serve a similar role to that of monetary prices in directing agents' choices and rationing items. Second, the expected wait for an item is endogenously determined and randomly fluctuates over time. We evaluate welfare under these endogenously determined waiting times and find that waiting time fluctuations lead to misallocation and welfare loss. A simple randomized assignment policy can reduce misallocation and increase welfare."

"A practical recommendation is the simple service-in-random order (SIRO) queuing policy. A SIRO buffer-queue mechanism has a simple description: agents who decline an item are allowed to join a priority pool for their preferred item, and agents in each priority pool have an equal probability of receiving an arriving item. We characterize the SIRO buffer-queue mechanism as the robustly optimal mechanism. This simple randomization does not fully equalize the expected wait across states, but it lessens the expected wait fluctuations and therefore reduces the misallocation probability and achieves higher welfare in equilibrium than FCFS." [FCFS= first come first served.]

"In summary, this paper offers two messages for the practical design of allocation through waiting lists. First, although many public-housing authorities have waiting list policies that discourage applicants from declining items, the analysis suggests agents should be encouraged to decline mismatched items. When the system is overloaded, an agent who declines a mismatched item allows the system to search further and assign the item to a matching agent. Furthermore, such an agent reduces the waiting costs of others by allowing them to be assigned before him. Second, equalizing the expected wait agents face when making their choice can improve welfare. This can be achieved by the SIRO buffer-queue mechanism or by partial information mechanisms. Both are practical mechanisms that offer agents more equal options at the time they make their choice, and thus reduce misallocation and improve welfare."

Returning to your place in the queue following a failed kidney transplant

 Here's a forthcoming paper that proposes that rejections of marginal kidneys could be reduced if recipients were guaranteed a shorter waiting time for a subsequent transplant if a marginal kidney that they accepted failed.

Tunç, Sait, Burhaneddin Sandıkçı, and Bekir Tanrıöver. "A Simple Incentive Mechanism to Alleviate the Burden of Organ Wastage in Transplantation." Management Science (2022).

Abstract: Despite efforts to increase the supply of donated organs for transplantation, organ shortages persist. We study the problem of organ wastage in a queueing-theoretic framework. We establish that self-interested individuals set their utilization levels more conservatively in equilibrium than the socially efficient level. To reduce the resulting gap, we offer an incentive mechanism that recompenses candidates returning to the waitlist for retransplantation, who have accepted a predefined set of organs, for giving up their position in the waitlist and show that it increases the equilibrium utilization of organs whilealso improving social welfare. Furthermore, the degree of improvement increases monotonically with the level of this nonmonetary compensation provided by the mechanism. In practice, this mechanism can be implemented by preserving some fraction of the waiting time previously accumulated by returning candidates. A detailed numerical study for the U.S. renal transplant system suggests that such an incentive helps significantly reduce the kidney discard rate (baseline: 17.4%). Depending on the strength of the population’s response to the mechanism, the discard rate can be as low as 6.2% (strong response), 12.4%(moderate response), or 15.1% (weak response), which translates to 1,630, 724, or 338 more  transplants per year, respectively. Although the average quality of transplanted kidneys deteriorates slightly, the resulting graft survival one-year post transplant remains stable around 94.8% versus 95.0% for the baseline. We find that the optimal Kidney Donor Profile Index score cutoff, defining the set of incentivized kidneys, is around 85%, which coincides with the generally accepted definition of marginal kidneys in the medical community."

Queuing for ridesharing and organ allocation

 Queues for ridesharing drivers at airports (where some trips are much better than others) lead to lots of rejected trips by those at the head of the line, while they wait for a good one.  This is of course something that also occurs in deceased donor waiting lists.

Here's a paper that tackles the ridesharing problem:

Randomized FIFO Mechanisms by Francisco Castro, Hongyao Ma, Hamid Nazerzadeh, Chiwei Yan

Abstract: "We study the matching of jobs to workers in a queue, e.g. a ridesharing platform dispatching drivers to pick up riders at an airport. Under FIFO dispatching, the heterogeneity in trip earnings incentivizes drivers to cherry-pick, increasing riders' waiting time for a match and resulting in a loss of efficiency and reliability. We first present the direct FIFO mechanism, which offers lower-earning trips to drivers further down the queue. The option to skip the rest of the line incentivizes drivers to accept all dispatches, but the mechanism would be considered unfair since drivers closer to the head of the queue may have lower priority for trips to certain destinations. To avoid the use of unfair dispatch rules, we introduce a family of randomized FIFO mechanisms, which send declined trips gradually down the queue in a randomized manner. We prove that a randomized FIFO mechanism achieves the first best throughput and the second best revenue in equilibrium. Extensive counterfactual simulations using data from the City of Chicago demonstrate substantial improvements of revenue and throughput, highlighting the effectiveness of using waiting times to align incentives and reduce the variability in driver earnings."

"Many ridesharing platforms now maintain virtual queues at airports for drivers who are waiting in  designated  areas,  and  dispatch  drivers  from  the  queue  in  a  first-in-first-out  (FIFO)  manner.4 This resolves the congestion issues and is also considered more fair by many since drivers who havewaited the longest in the queue are now the first in line to receive trip offers.  At major U.S. airports,however, a driver at the head of the queue will receive the next trip offer in a few seconds under FIFO dispatching, if she declines an offer from the platform (see Figure 12).  As we shall see, thislowered cost of cherry-picking substantially exacerbates existing problems on incentive alignment.

...

"During busy hours, instead of accepting an average trip, drivers who are close to the head of the queue are better off declining most trip offers and waiting for only the highest earning trips.  Riders, however, have finite patience, despite being willing to wait for some time for a match.  When each driver decline takes an average of 10 seconds, 2 minutes had passed after a trip with low or moderate earnings (e.g.  trips to downtown Chicago) was offered to and declined by the top 12 drivers in the queue.5 At this point, it is very likely that the rider cancels her trip request, not knowing when a driver will be assigned, if at all.

...

"To  achieve  optimal  throughput  and  revenue  without  the  use  of  an  unfair  dispatch  rule,  weintroduce a family ofrandomized FIFO mechanisms.  A randomized FIFO mechanism is specifiedby a set of “bins” in the queue (e.g., the top 10 positions, the 10th to 20th positions, and so on).Each trip request is first offered to a driver in the first bin uniformly at random.  After each decline, the mechanism then offers the trip to a random driver in the next bin.  By sending trips gradually down the queue in this randomized manner, the randomized FIFO mechanisms appropriately align incentives using waiting times,  achieving the first best throughput and second best net revenue: the option to skip the rest of the line incentivizes drivers further down the queue to accept trips with  lower  earnings;  randomizing  each  dispatch  among  a  small  group  of  drivers  increases  each individual driver’s waiting time for the next dispatch, thereby allowing the mechanism to prioritize drivers closer to the head of the queue for trips to every destination without creating incentives for excessive cherry-picking."

Market clearing by queuing, by Ashlagi, Leshno, Qian and Saberi

Queue Lengths as Constantly Adapting Prices: Allocative Efficiency Under Random Dynamics
Itai Ashlagi, Jacob Leshno, Pengyu Qian, and Amin Saberi
EC '20: Proceedings of the 21st ACM Conference on Economics and Computation July 2020 Pages 317–318 https://doi.org/10.1145/3391403.3399539

ABSTRACT
"Waiting lists are common mechanisms for allocating scarce items without monetary transfers. Examples include the allocation of cadaver organs to patients in need of a transplant, public housing apartments to applicants, health care services to patients, and even spots at childcare centers to parents. In all these markets waiting times play the role of prices in guiding the allocation and rationing items. But while prices are set by the designer, waiting times are endogenously determined by the number of agents waiting. Moreover, waiting times are not fixed, and continuously adjust as items arrive or agents join. When agents and items arrive stochastically over time, waiting times stochastically adjust over time.

"The stochastic adaptation of waiting times adversely impacts the allocative efficiency. If utility is quasi-linear in waiting time, standard competitive equilibrium (CE) arguments show that fixed waiting times can serve as market clearing prices and yield the optimal allocative efficiency. But even if one may expect the endogenously generated waiting times to tend towards market clearing prices, the waiting times keep fluctuating and never converge. Agents may arrive when waiting times are far from the market clearing prices, and their assignment can be inefficient.

"This paper evaluates the allocative efficiency loss due to the random fluctuations. We consider a standard waiting list mechanism, which holds a separate First Come First Served (FCFS) queue for each of finitely many items. Items arrive over time according to a Poisson process, and are assigned to the first agent in the respective queue. Agents arrive over time according to a Poisson process, observe the length of each queue, and then choose a queue to join or leave the system. An agent who joins a queue must wait there until he receives the item. Agents have heterogeneous private values over the items, and their utility is quasi-linear in waiting costs. That is, all agents have the same waiting costs. We interpret the expected waiting costs at each queue as prices that stochastically adjust as items arrive or agents join the queues.

"Our key technical observation is that the waiting list's random price adaptation process is equivalent to that of a stochastic gradient descent algorithm (SGD). While each arrival randomly adjusts prices, the expected price adjustment from each arrival moves waiting times towards market clearing prices. However, waiting times never converge. Standard usage of SGD optimization algorithms requires reducing the step size to zero as the algorithm gets closer to the optimal solution. In contrast, the step-size for the waiting list mechanism is determined by the granularity of waiting costs C>0, which is the maximal price impact (i.e., increase in expected waiting costs) of adding one agent to a queue.

"Our first result states that the allocative efficiency loss from the random price fluctuations is O(C), and this bound is tight. We further show that, if there are finitely many agent types and the optimal static assignment problem has a unique dual solution (which generically holds), then the allocative efficiency loss becomes exponentially small as C -> 0."

Professional line sitters: Giving the gift of time

Have an urgent need to shop Black Friday bargains, but don't like waiting on lines in the cold and dark?  There's a business that will take care of that for you...

Professional Line Sitters Make Up to $35 an Hour — And This Is Their Busiest Time of the Year

Some links if you're too busy to read the story:
Skip the line (STL) inWashington DC
Same Ole Line Dudes in New York City
InLine4You an app for both sides of the market

"The Supreme Court website says security starts admitting people to oral argument sessions at 9:30 a.m., but “visitors may begin lining up on the Front Plaza as early as they feel comfortable” — which sometimes means four days in advance. The average SCOTUS wait time Goff gets tapped for runs about five hours (she charges $35 per hour), with occasional overnight requests for big cases like the travel ban and Masterpiece Cakeshop v. Colorado Civil Rights Commission."

The politics (and incentives) of liver transplants

From the LA Times: California has long wait lists for liver transplants, but not for the reasons you think

"About 7,000 people get a liver transplant each year in the United States, while 17,000 remain on waiting lists at transplant centers. Who should get a lifesaving transplant has always been a complex calculation. But it has blown up into a vicious political struggle that played out most recently at a meeting of the organization governing the nation’s transplant network.

"The benefits of liver transplants are astounding. Patients just weeks from death can have their lives extended significantly, even indefinitely. Given the limited number of donor livers, in 2000 Congress established what’s called “the Final Rule” to guide the medical community in how to allocate them fairly. The Final Rule compels the transplant community to allocate donor organs based on best medical judgment, best use of the organs and avoidance of futile transplants. It also notes that a patient’s chance of getting a transplant should not be affected by where he or she lives.

"Balancing these various guidelines has always been tricky. But what has emerged — and is now the point of contention — is a marked geographic disparity in how sick a patient must be before rising to the top of a transplant list. For example, waiting lists at California transplant centers are significantly longer (and therefore patients in California get a lot sicker before possibly receiving transplants) compared with waiting lists in Oregon. That’s unfair to the Californians who need liver transplants, right?

"Acting on this assumption, the national board of the Organ Procurement and Transplantation Network / United Network for Organ Sharing, or OPTN/UNOS, proposed new boundaries for the nation’s transplant regions. The aim was to have regions with shorter, less-sick waiting lists share the limited supply of donor livers with regions that have longer, more-sick waiting lists. The new map was recently offered for public comment and a regional advisory vote.

"Eight of the 11 regions came out against it — because longer waitlists aren’t necessarily a sign of greater need.

The divide is deep. Antagonists have split into camps (“Liver Alliance” versus “Coalition for Organ Distribution Equity”), hired lobbyists and collected their congressional representatives. Given the uproar, it was not surprising that the OPTN/UNOS board of directors declined to vote on the controversial proposal at its national meeting in St. Louis last week. Nevertheleess, there’s a feeling of urgency that something must be done, so it’s entirely possible the board will soon enact the redistribution proposal — perhaps with minor modifications — despite present objections.
...
"Transplant waiting lists also get distorted by intense competition in populous regions where there are more liver transplant centers — a largely ignored issue. With money and prestige at stake, centers are motivated to perform more liver transplants. The simplest way to accomplish that is to put very ill patients on the transplant list, because when a donor organ becomes available, the center with the sickest listed patient in that region gets the organ.

Unfortunately, this encourages centers to list sicker patients over those who have the best chance of long, high-quality lives post-transplant.
...
"Rates of organ donation, by the way, do not explain the wait-list problem: California has some of the highest donation rates in the country, while New York persistently ranks at the bottom. Everyone agrees on the need to increase donations — but just redistributing livers will not significantly change the number of transplants or lives saved.

"Still, the disparity between the wait lists causes endless teeth-grinding in the transplant community.

"There is no question that wait lists are abhorrently long in some places, but OPTN/UNOS’ redistribution proposal misses the larger point: What is it about our transplant system that has created this situation? How can we make changes to keep the wait lists at more reasonable levels?

"Matters of healthcare access, while important, are beyond the control of OPTN/UNOS and the transplant community. Within grasp, however, is a simple solution: Lower the number of patients on transplant lists. Such a move would not affect the number of transplants (every available liver would still be transplanted), but it would reduce the delay and degree of illness for those on the wait lists. This is, of course, simple to say, but difficult to implement given how our current system incentivizes transplant centers to get as many patients on their lists as possible.

"To create a fairer balance between the haves and have-nots, though, both factions in the liver debate need to understand (and agree on) who the haves and have-nots actually are. Without consensus on that, we risk missing the big picture: increasing the health, happiness and well-being of more people with liver disease."

Dr. Willscott E. Naugler is an associate professor and medical director of liver transplantation at Oregon Health & Science University in Portland. He also serves as the Region 6 (Pacific Northwest) regional representative to the UNOS Liver and Intestine Committee."

Gaming the waiting list for a heart transplant

The heart transplant waiting list is game-able, since your place on the list depends on what treatment you are getting. So your doctor can "treat your priority" as well as treat your medical condition.  Here's the story from NPR:
Should Doctors Game The Transplant Wait List To Help Their Patients?
 July 24, MATTHEW MOVSESIAN

And here's an old (2013) editorial on the subject in The Journal of Heart and Lung Transplantation:
The urgent priority for transplantation is to trim the waiting list by Lynne Warner Stevenson:

"Current definitions of priority levels have been based both on medical rationale and the attempt to protect the system from being “gamed.” When the requirements for inotropic therapy for Status IB and pulmonary artery catheters for Status IA were adopted in the USA, it was with optimism that they would be used only when absolutely necessary to prevent imminent death, because continuous inotropic infusions and indwelling pulmonary artery catheters are inconvenient and costly and have been associated with serious complications. Although individual cases trigger heated controversy in regional committees, it is generally agreed that these therapies are being overused in patients awaiting transplantation.

If high priorities defined by therapies are the only route to access donor hearts, we face conflicted incentives as advocates for our patients. This is serious enough with incentives to inflate the description of severity of illness, but even more serious with incentive to impose interventions with complications, such as indwelling pulmonary artery catheters. One of the major conditions currently cited as justification for Status IA exceptions is vascular complications of indwelling catheters that preclude further catheterization. This complication on the list was virtually never seen before pulmonary artery catheters became an index of priority (although arrhythmia device leads have also added to the vascular complication rate).

The strength of inverse incentives in care of our waiting patients is indexed to the concern that they will die before a transplant, or will develop unnecessary risk such as from cachexia before they finally enter into transplant. The priority status will more truly reflect patient illness when the listing physicians have reasonable confidence that patients will receive a heart in a timely manner, a confidence eroded by the lengthening waiting times, which in turn reflect the anasarca of the waiting list."

HT: Marc Melcher

Buying a place in line to hear Supreme Court arguments

Over at the Volokh Conspiracy Dale Carpenter has the story, and the URL is more informative than the headline: http://www.volokh.com/2013/03/30/misbehavior-at-the-court/ 

"There are actually two lines to get into the chamber, which has very limited seating capacity.  One is for the general public, and in high-profile cases it’s quite long.  The other is for lawyers who become members of the Supreme Court bar.  Bar members enjoy a limited number of reserved seats at the front of the audience, right behind the lawyers for the parties in the case.  ...

I joined the Supreme Court bar ($200 one-time fee) in order to get into the marriage arguments. I knew the lines would be long, so I arrived Tuesday morning at about 3:15 a.m., thinking that would be good enough to get me in.  I was about 57th in line at that point for about 100 seats in the bar section.  In front of me were mostly paid line-standers who had been waiting in the 30-degree temperatures all night.  I talked with quite a few of them.  None were members of the bar.  Almost all were impoverished and black.  Many of them slept on the ground, in cold and wet conditions, for several nights.

As daylight approached, a lot of equality advocates arrived to take their premium places in line.  These “clients,” as the line-standers called them, paid about $50 an hour to line-standing-service middlemen organized as businesses (I don’t know what the actual line-standers earn per hour).  For the Prop 8 case,  it cost as much as $6,000 to get to the front of the line and guarantee a seat in the courtroom.  Neither the Supreme Court nor any law-enforcement authorities prohibit this practice.

I don’t categorically object to line-placement capitalism, especially for private functions like buying tickets to a rock concert.  It’s an economic exchange in which the highest bidders get what they want and others sell their services and earn money they wouldn’t otherwise get.  It does seem odd to hold what’s effectively a private-market auction for seats at a public hearing of the country’s highest court.  Many of the buyers who participated in this particular market, given what I know of their other political preferences, would be hard put to defend this system in a public forum. 

They started letting us into the Court at about 7:30 for the Prop 8 argument on Tuesday.  I got into the main room, third row from the front, not more than 50 feet from the Justices.  Getting there early — and being able to stand in a separate bar-members line – had paid off.

But what happened the next day for the DOMA argument was appalling.  I arrived at 2:15 a.m. when the temperature was a balmy 40 degrees and was headed down.  I was 46th in line, again with a group consisting almost entirely of paid line-standers in front of me.  There were very few bar members personally waiting in line at that time.  The Court had space for fewer bar members that day in order to make room for an extra table for counsel arguing the jurisdictional issues.  But even with more limited seating, #46 was still sure to get in.

As 7 a.m. approached and the lawyers arrived to take their pre-paid places in line, something else happened.  They started inviting their friends to join them at the front of the line, pushing back people who had waited all night to get in.  The lawyer-clients of several of the line-standers near me never arrived to relieve their assigned line-standers, no doubt because they cut in line further up than what they had paid for.  Pretty soon, I was #55 and then #65 and then I lost count. "

Child rearing by queuing

In New York City, many of the good things in life for children are rationed by queue: Born to Wait: 
For City Parents, a Waiting List for Nearly Everything

"The first parent lined up at 4 a.m. on a Sunday..

"Twenty minutes later, other parents showed up and a line began to form down Atlantic Avenue in Brooklyn. One father kept a list so that anyone searching for a thawing hot coffee could do so without losing a place in the line. He abandoned that project as more and more people trickled in and the end of the line was no longer visible from the front...

"If waiting in line in the predawn of a January morning for science camp registration sounds crazy, you do not have a New York City child born after 2004. For those children and their parents, especially in the neighborhoods of brownstone Brooklyn, Lower Manhattan and the Upper West Side, not getting into activities, classes, sports teams — and even local schools — has become a way of life.
...
"Havona Madama’s fear of waiting lists led her to start a database to track her 5-year-old daughter’s favorite classes and their registration deadlines. Two years ago, she decided to leave her law practice to turn her research intoKidKlass.com, a hub of information for brownstone Brooklyn about classes, camps and all-important registration dates. The site is still being developed, but she counts 50 to 100 visitors a day who peruse the listings. Still to come, she said, is an “alert” system to let parents know what deadlines they are about to miss.
...
"Technology has fueled the phenomenon. In 2012, the city moved to online registration for its free summer swim classes at its outdoor pools. The number of applicants jumped to 34,134, from 20,393 in 2011, when officials began to introduce the online application. (That year, four pools still required on-site, in-person registration. Most people got in.) Last summer, only 24,532 applications got spots.

"Often, the activities that fill up fastest are the ones that are most affordable and most accessible, like the swim classes. At the Brooklyn Public Library in Bay Ridge, 25 children can be accommodated at the free story-time sessions. Parents and other caregivers routinely show up when the library opens at 10 a.m. to get a ticket for the 10:30 a.m. story times on Mondays and Wednesdays. On a recent Wednesday, tickets were snatched up within five minutes.

"For children, waiting on a list for soccer or missing story time might not be a tragedy, but for parents, winding up on a list can mean having to put life on pause. In the Brooklyn line for science camp, the parents talked about how getting a spot could determine whether they could go to work on particular days, or whether they would have to spend extra money on a baby sitter.
...
'“It’s just a fact of living in the city,” Ms. Flattery said. She has learned not to discuss classes with her children until it is certain they will get in. She also follows a strategy that may add to the waiting lists. “You fill up every class you can, and you drop if you don’t need it. Everyone overschedules — it’s the only route to choice,” she said.

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.

The regulated market for cemeteries

The NY Times reports, City Cemeteries Face Gridlock.

"More than 50 years have passed since a major cemetery was established within the city, and no new burial grounds are planned. But New Yorkers continue to die, some 60,000 a year.

"Accordingly, per square foot, burial plots in centrally located cemeteries rival the most expensive real estate in the city. A private mausoleum at Woodlawn Cemetery in the Bronx can easily cost more than $1,000 per square foot.

"“We have people who would like to disinter Mom and Dad and sell the graves back to make some money,” said Richard Fishman, the director of the New York State Division of Cemeteries.


"There are state laws limiting the profits on resold graves, but the fact that people would be willing to go to such lengths, Mr. Fishman said, illustrates just how valuable burial plots have become."
...
"Other major urban areas have taken measures to alleviate similar space crunches. London allows people to be buried upright, while cemeteries in Singapore and Sydney, among others, offer “limited tenure,” cemetery-speak for digging up bodies after a certain amount of time so that the plot can be reused."
...
"It might seem that an enterprising developer could find a way to make a lucrative business out of providing burial space.

"But that has not happened.

"First, by law, cemeteries in New York State must be nonprofit institutions. There are 35 privately owned cemeteries in the city and several dozen with religious affiliations. The closer to Manhattan and major transportation, the more crowded and expensive a burial ground will be. Farther away, particularly in Staten Island and parts of the Bronx, space is available. The indigent of New York City are buried on Hart Island in Long Island Sound.

"Woodlawn, which was part of Westchester County when it was founded in 1863 but was later incorporated into the Bronx, still has burial room. It hopes to be able to offer graves for another 40 to 50 years, but that relative abundance hasn’t kept its prices down.

“We want to have enough saved so that the income from the trust, once we are closed and have nothing left to sell, is enough to maintain the cemetery,” said John P. Toale Jr., the president of Woodlawn.

"While there is a space crunch in the city, there is more space in the suburbs, and cemeteries in upstate New York can barely give away plots, state officials said. Many New Yorkers who struggled and saved to live in the city end up buried elsewhere.

"Even as the broader real estate market languished in the recession, prices for graves in the city continued skyward. The state regulates the fees a cemetery can charge for services like excavation, but graves sell at market price. So burial plots are a cemetery’s revenue-generator.
...
"Now that an end to plot sales is in sight, Green-Wood is seeking to transform its image, according to Richard J. Moylan, its president. The graveyard charges admission for guided tours, giving people a chance to saunter through time among the tombstones of the notable and the notorious. The hope is that it will become much like Père Lachaise cemetery in Paris, a magnet for tourists."

See also this earlier post.

Random allocation, preferences, and welfare: a fish story

Flying from Madrid to Boston on an Airbus with two aisles not long ago, two stewardesses proceeded in parallel down the aisles offering food. I asked for the fish, but the stewardess in my aisle was already out of fish. Speaking to her colleague in the other aisle, she ascertained that her colleague still had some fish. Rather than pass the fish across the (empty) seat between them, “my” stewardess told me that, if her colleague still had fish when she completed her aisle, then I could have it. (I chose the vegetable dish…)

We see similar issues when changes are discussed in how to allocate deceased-donor organs for transplants, or some other policy where there has been a previous decision on an order of allocation to randomly arriving agents. To have passed the fish across to me would have disadvantaged some passenger who, but for the demand for fish on my side of the plane, would have been able to eat fish…

Of course, assuming that on which side of the plane passengers are seated is random, the policy of allowing fish to be passed from side to side and not just from front to back would have the same ex-ante welfare properties. But, once the passengers are seated, any change in policy would likely help some passenger only by hurting another.

This kind of discussion comes up from time to time in the allocation of school places, as well as transplant organs.

A grave problem of supply and demand

Grave sites, once sold and occupied, are intended to be occupied for a very long time, and their sale can't easily be negotiated if more valuable uses turn up. So there is less turnouver than in other kinds of real estate, with predictable consequences, as this Globe article attests: Supply limited, demand eternal, graveyards fill up.


"Provincetown’s shortage, while unusually acute, underscores a broad and burgeoning problem in the crowded Northeast. With land expensive and limited acreage available in large swaths of Eastern Massachusetts, budget-crunched communities are struggling to buy sites for new burial grounds as their existing cemeteries fill up."
...
"In Provincetown, many who have reserved burial plots are relative newcomers to the town, and in response, town officials this week passed a rule restricting burial plots to those who have maintained a principal residence for at least two years. Still, that was a short sojourn, some said, for a chance to spend eternity in a slice of heaven.
Said Lemme, the cemetery supervisor: “We might have to make that a little stricter.’’ "

Reserving spaces in crowded places

It may be possible for vacationing Germans to reserve rental lounge chairs at a crowded beach or pool, but in Saudi Arabia it's a crime to reserve rental prayer mats, the Saudi Gazette reports: 2 held for renting Haram prayer space. It appears that both the reserving and the renting are repugnant.

"MAKKAH – Two persons have been arrested for reserving prayer spaces and renting them out to worshippers at Isha and Taraweeh prayer times...“The practice has diminished a lot this year,” Al-Wabil said. “However, we will show no lenience to anyone caught.”All persons who have been arrested for renting out prayer spaces have been foreigners, Al-Wabil said, adding that culprits are identified through a period of surveillance of individual carpets and persons claiming them beginning half an hour before the start of prayers.Sheikh Saleh Bin Fawzan Al-Fawzan of the Board of Senior Ulema and the Permanent Committee for Ifta ruled last week that reserving prayer spaces at the Grand Mosque in Makkah or the Prophet’s Mosque in Madina was “haraam”, or forbidden.“It is forbidden to reserve places in the mosques, unless the person has left for urgent reasons and intends to return soon, as otherwise it is tantamount to taking something by force,” Al-Fawzan told Okaz newspaper on Thursday. “It is also forbidden to rent a reserved place, and the authorities should put a stop to this vice (munkar).”

HT: Anouar El Haji at U. Amsterdam

Behavioral game theory on the MA Turnpike

A recent story in the Boston Globe sounds like a behavioral economics seminar on transaction costs: why are a third of the tolls on the Massachusetts Turnpike still paid (more slowly and expensively) in cash, rather than using the (now free) transponders?
Some still slow to make the move to Fast Lane: 1 in 3 tollpayers paying at booth
"The Massachusetts Turnpike Authority has made strides in signing people up to use Fast Lane, with 66 percent of tolls now paid electronically, up from 62 percent in January. But the 34 percent who use cash, and pay higher tolls at booths inside Greater Boston to do so, remain a bit of a mystery."
...
"The survey LeBovidge conducted found that the biggest hurdle to signing up more people used to be cost, accounting for about 75 percent of the abstainers. About 7 percent worried about handing personal data to the Turnpike Authority or having their movements tracked. Some remaining drivers - not reflected in the survey - come from out of state and might not have an E-Z Pass account usable in Massachusetts. Other commuters do not have a checking account or credit card.
...
"If they wait in cash lanes enough times, most technophobes get converted. Fast Lane usage at the Allston-Brighton booths rises to 86 percent during morning rush hour into Boston. Massive traffic jams also do the trick: The Easter backup helped drive signups to 45,905 in May, compared with 10,875 during the same month last year."

One reason this is an interesting problem is that it's not just about individual choice, there's an element of behavioral game theory in this kind of slow learning. Cash payers produce congestion--negative reinforcement--for other cash payers. When lines at the toll booths get really long, even the EZ Pass users have to wait on line to get to the toll booths. So slower payers provide a negative externality to everyone on the busiest days.

In a forthcoming paper in the QJE, Amy Finkelstein raises the possibility that those cash payers may also provide a small positive externality by being more politically sensitive to changes in the tolls: EZ-Tax: Tax Salience and Tax Rates.
"Abstract: This paper examines whether the salience of a tax system affects equilibrium tax rates. I analyze how tolls change after toll facilities adopt electronic toll collection (ETC); drivers are substantially less aware of tolls paid electronically. I estimate that, in steady state, tolls are 20 to 40 percent higher than they would have been without ETC. Consistent with a salience-based explanation for this toll increase, I find that under ETC, driving becomes less elastic with respect to the toll and toll setting becomes less sensitive to the electoral calendar. Alternative explanations appear unlikely to be able to explain the findings."

So the next time you are stuck on the Mass Pike behind a long line of drivers waiting to pay their tolls, try to remember that there may be a small benefit to having the toll be so salient.

Where the wait for a parking permit is 8 to 10 years

In Rye, NY, that's apparently how long it takes to get a parking permit at the commuter rail station.

The NY Times reports that the recession has resulted in fewer commuters and empty parking spaces, but has not shortened the wait for a parking permit, since commuters are reluctant to give up their right to park (and cannot sublet them to those still working): Slump Opens Spaces at the Station

"From Ronkonkoma on Long Island to Darien, Conn., riders are doing double takes at the vacancies in the station lot, and the empty spots, in turn, have sparked efforts to free them up for parkers without permits. In Connecticut, there is even a push to let permit holders “rent” their permits.
...
But these empty spaces may be chimerical. It’s “look but don’t touch” for people like Mr. Blake because many permit holders, even if they have lost their jobs and no longer commute regularly, still hold tightly onto their permits. Jeanette DeLeo, an assistant in the city clerk’s office in Rye, said there has been no whittling of the waiting list in her town, and the reason is not hard to fathom.
“With a waiting list of 8 to 10 years, people will not give up their permits,” Ms. DeLeo said."

Queuing to tee up at the Bethpage State Park Black Course

The USGA 2009 US Open golf tournament begins tomorrow, June 18. The host golf course is the Bethpage State Park Black Course. You have to be pretty skilled to qualify ("Entries are open to professional golfers and amateur golfers with an up-to-date men’s Handicap Index® not exceeding 1.4 under the USGA Handicap System™. ")

But if you just want the experience of playing on the same course as the top pros, the Black is a public golf course. You could just sign up for a tee time. Or could you? It turns out not to be quite so easy.

Just as markets can unravel, so can queues. A reliable symptom is people waiting on line overnight, especially if they have to wait for more than one night. Getting a tee time at this particular famous public (i.e. not rationed by price) golf course on Long Island seems to qualify: Parking All Night at Bethpage, Hoping to Drive. Note the well developed rules for regulating the queue, which include a rule meant to prevent the substitution of capital for leisure.

"Bethpage has five public golf courses: Black, Red, Blue, Yellow and Green. But the bulk of tee times for the courses, particularly the famed Black, can be hard to get through the phone-reservation system, which has 70,000 registered users. At least one company floods the system each night with hired callers, then resells the times as part of golf packages.
Yet there is one way to ensure a time at Bethpage Black, a major-championship course with $50 fees during the week, $60 on weekends, and double that for non-New Yorkers: get to the parking lot and spend a night. Maybe two. Maybe more."
...
"A sign there explains the complex rules of the “Walk Up Car Line.” Most important is that someone must be at the car for part of every hour. For the Envoy, on this Saturday afternoon, that person was Steve Atieh, 25, from Basking Ridge, N.J., who planned to play the Black course with two brothers and a friend.
They teed off 39 hours after arriving, about 11 hours after their car battery died while the radio broadcast a Yankees game."
...
"Steve Tomasheski was sitting in space No. 3 when someone offered $1,000 for it. He declined, afraid to disappoint his playing partners. Please do not tell his wife."
...
"At 7 p.m., Michael Azzue, an assistant supervisor at Bethpage, arrived in a cart. “Who’s No. 1?” he said, shouting. Azzue attached a plastic bracelet around Atieh’s wrist. At least one person from every car must be present when a supervisor arrives between 6 and 9 p.m. That person must be one of the golfers the next morning, to prevent hiring a nongolfer to do the waiting, which used to happen."

Apparently it is repugnant to pay someone to wait in line for you, although the story suggests that there is some demand for this, and people who arrive a little late (and before the monitoring kicks in) sometimes buy places from early arrivals.

Endnote: "Success has many fathers...", here's a story on a dispute about who really deserves the credit for designing the course. (Credit is a subject worth a discussion in its own right. In my experience, success in complex design projects often does have many fathers, with lots of people contributing in critical ways.)

''Not everything that is immoral has to be illegal'

The quotation in the title of this post is from Romanian Justice Ministry legal expert Valerian Cioclei, and it comes from the NY Times story Romania Weighs Decriminalizing Consensual Incest .

"Three European Union nations -- France, Spain and Portugal -- do not prosecute consenting adults for incest, and Romania is considering following suit.
...
"Incest is defined as sexual intercourse between people too closely related to marry legally. In the United States, all 50 states and the District of Columbia prohibit even consensual incest, although a few states impose no criminal penalties for it..."

Incest is surely one of the prototypical repugnant transactions, namely one that people don't like to have others engage in. Such repugnance is often reflected in law, but by no means always. (E.g. there is no law against going to the front of a long line at the supermarket checkout counter and asking a person near the front to sell you their spot, i.e. to move to the back of the line and let you into their place in return for a cash payment. But here's a story of an economist , Oz Brownlee, who, after trying to do that, decided that the best course of action was to leave the store without buying anything.)

A famous article by Jonathan Haidt (Haidt, J. (2001). The emotional dog and its rational tail: A social intuitionist approach to moral judgment. Psychological Review. 108, 814-834 ) begins with an example of consensual incest.
"Julie and Mark are brother and sister. They are traveling together in France on summer vacation from college. One night they are staying alone in a cabin near the beach. They decide that it would be interesting and fun if they tried making love. At very least it would be a new experience for each of them. Julie was already taking birth control pills, but Mark uses a condom too, just to be safe. They both enjoy making love, but they decide not to do it again. They keep that night as a special secret, which makes
them feel even closer to each other.
What do you think about that, was it OK for them to make love?

"Most people who hear the above story immediately say that it was wrong for the siblings to make love, and they then set about searching for reasons (Haidt, Bjorklund, & Murphy, 2000). They point out the dangers of inbreeding, only to remember that Julie and Mark used two forms of birth control. They argue that Julie and Mark will be hurt, perhaps emotionally, even though the story makes it clear that no harm befell them. Eventually,
many people say something like “I don’t know, I can’t explain it, I just know it’s wrong.” But what model of moral judgment allows a person to know that something was wrong, without knowing why?"

Haidt (and colleagues, particularly Paul Rozin) have studied the emotion of disgust, and think that a lot of moral judgements may be mediated by the disgust reaction (whose initial evolutionary significance is presumably to prevent us from eating spoiled food, etc.). This makes a lot of sense for incest (because evolution should help us avoid inbreeding, with the excessive concentration of recessive genes in offspring).

I suspect that many of the more clearly economic transactions that are or have been regarded as repugnant are less closely tied to hard-wired disgust. That is not to say that, as people who are culturally acclimated to find some kind of transaction repugnant (e.g. charging interest on loans was repugnant for centuries in Europe), we may not be able to recruit our disgust reaction to make sense of things we disapprove of. Just as not every repugnant transaction is against the law, they may not all originate with (or even activate in a secondary manner) feelings of disgust. (See my other posts on repugnant transactions for a variety of examples...)

Update: see an article on disgust and moral judgement in the March 2009 issue of The Jury Expert (a very task oriented journal focused on picking and persuading jurors): Grime and Punishment: How Disgust Influences Moral, Social and Legal judgments