Imagine you sign up for a carpooling service. You open your rideshare app and input your location and desired destination. The app tries to match you with other customers who also want to share a ride. Perhaps right now there aren’t good matches for you, but the longer you can wait, the higher the chances the app can find a better match.

“If you always match customers immediately after they arrive, you won’t  be making too many good matches,” said Yehua Wei, an associate professor of decision sciences at Duke University’s Fuqua School of Business. “But obviously you also don’t want to make the customers wait too long.”

This balancing act — finding better matches by waiting, but not too long — is at the heart of dynamic matching, he said.

Now imagine the same problem applied to higher-stakes settings like kidney exchanges, organizations trying to match kidney donors with recipients who are in urgent need of a transplant.

Sometimes, kidney exchanges don’t just find individual donors willing to donate to anyone in need. They actually match donor/recipient pairs. There may be a family member who is willing to donate the kidney to their son, but the pair is incompatible. In such situations, if the kidney exchange finds another pair with perfect cross-compatibility, two kidney patients have found a donor. For example, let’s say the first donor/recipient couple is called A1/A2, and the second B1/B2. Cross-compatibility would enable A1 to donate to B2, and B1 to A2. 

But things may get even more complicated, Wei said, because you could do the exchange for more than two pairs of donor-patients.

To find the right cross-compatibility, you may have to match more than two pairs, he said. With three pairs, for example, A1 may end up donating to B2, B1 to C2, and C1 to A2.

Such matching problems are called “dynamic” because you don’t have all the donor/patient pairs right away. They also become “multi-way” matching problems, because the chain of cross donations can involve multiple pairs.

In a new working paper, Wei and his Fuqua colleague Jiaming Xu — with Sophie H. Yu of University of Pennsylvania — created a model that achieves the best solution yet to multi-way, dynamic-matching problems, by adding a “price” to the units of these markets — the pairs, in the kidney exchange. The price reflects how valuable a match might be in the future. 

How a “primal-dual” solution improves current solutions

Until now, a standard dynamic matching solution is to make the “optimal” immediate match among all the possible available matches, Wei said.

“A pair comes to the exchange, and if there is another compatible pair available, you do the match,” he said.

However, the researchers found that at any given time, an individual pair has the potential to help the long chain of cross-exchanges.

The researchers’ model shows that perhaps, if you match the pair now, the whole system will miss a link that, if kept available, would have enabled the exchange to help more patients down the road.

In the model, the researchers assign each pair a value — the dynamic “price” the system would be willing to pay — based on its matching potential, determined by the availability of that kind of pair and the “shortage” accumulated through scheduled matches. Through this price,  the system decides whether it’s better to match the pair now or wait for a potentially more valuable match, Wei said.

The researchers call such system a “primal-dual” policy because the price acts as a “dual” solution — estimating the value of each pair — which then informs the “primal” decision of whether to match the pairs or hold off.

“Sometimes, the dynamic price suggests holding off on a match, as it anticipates another pair arriving soon, allowing the system to create more beneficial matches and ultimately save more lives,” Wei said.

In the example of the carpooling service, having a customer wait a bit longer will allow the service to find more suitable riders for the same commute, which would lead to more shared rides.

The researchers write that this “primal-dual” model achieves the best results compared with the previous optimal solution, whether the arrival rates are known or not.

“Many algorithms require precise knowledge of all the parameters,” Wei said, “but our approach performs well even when there’s uncertainty in the parameters.”

An algorithm that is more interpretable for managers

Beyond the technical advantages, this algorithm also offers practical benefits for managers, who often deal with dynamic matching problems to allocate resources efficiently, Wei said. 

One key advantage of this new algorithm is that it’s highly interpretable, he said, because thanks to the price, it becomes easier to understand whether a pair, a customer, or a unit is more or less valuable to the system at any given moment.

Consider for example a typical e-commerce fulfillment problem, where you order a toothbrush, some toothpaste and dental floss, and the platform has to choose which product to send you from which warehouse, Wei said.

“An algorithm decides what is the best match, but the managers want to be able to interpret how the algorithm works,” he said. “With our system, they compute a price for each item at each location. At this warehouse the toothpaste is worth this price for them. At that warehouse, it has a different price. Once you have the price, you can simply pick from the warehouse that has the lowest price. This is more interpretable than using a black-box algorithm.”