New algorithm improves bipartite matching by mimicking the nervous system

When you ask a ride-hailing app to find you a car, the company’s computers go to work. They know you want to get to your destination quickly. They know you’re not the only user who needs a ride. And they know drivers want to minimize downtime by picking up someone nearby. The computer’s job, says Saket Navlakha, an associate professor at Cold Spring Harbor Laboratory, is to match drivers and passengers in a way that maximizes everyone’s happiness.

Computer scientists like Navlakha call this bipartite matching. It’s the same task performed by systems that match organ donors with transplant candidates, medical students with residency programs, and advertisers with ad space. So it’s the subject of intense study.

“It’s probably one of the ten most famous problems in computer science,” Navlakha says.

Now, he’s found a way to do better by taking inspiration from biology. Navlakha has identified a bipartite correspondence problem in the wiring of the nervous system. In adult animals, each muscle fiber in the body is associated with a single neuron that controls its movement. But early in life, each fiber is targeted by many neurons. For an animal to move efficiently, excess connections must be cleared. So which correspondences are built to last?

The nervous system has an effective solution. Navlakha explains that neurons initially connected to the same muscle fiber compete to maintain their match, using neurotransmitters as “bidding” resources. Neurons that lose this biological auction can take their neurotransmitters and bid on other fibers. In this way, each neuron and fiber eventually ends up with a partner.

Navlakha has come up with a way to implement this matching strategy outside the nervous system. “It’s a simple algorithm,” he explains. “It’s just two equations. The first is competition between neurons connected to the same fiber, and the second is resource reallocation.” The work was published in Proceedings of the National Academy of Sciences .

Tested against the best existing bipartite matching programs, the neuroscience-inspired algorithm performed very well. It creates near-optimal matches and leaves fewer unmatched parties. In everyday applications, this could mean shorter wait times for rideshare passengers and fewer hospitals without medical residents.

Navlakha points out another advantage: The new algorithm preserves privacy. Most two-party matching systems require that relevant information be transmitted to a central server for processing. But in many cases, from online auctions to matching donor organs, a distributed approach may be preferred. With countless potential applications, Navlakha hopes others will adapt the new algorithm to their own tools.

“This is a great example of how studying neural circuits can reveal new algorithms to solve important AI problems,” he adds.