New algorithm improves bipartite matching by mimicking nervous system

When you ask a rideshare app to find you a car, the company’s computers get to work. They know you want to reach your destination quickly. They know you’re not the only user who needs a ride. And they know drivers want to minimize idle time by picking up someone nearby. The computer’s job, says Cold Spring Harbor Laboratory Associate Professor Saket Navlakha, is to pair drivers with riders in a way that maximizes everyone’s happiness.

Computer scientists like Navlakha call this bipartite matching. It’s the same task handled by systems pairing organ donors with transplant candidates, medical students with residency programs, and advertisers with ad slots. As such, it’s the subject of intense study.

“This is probably one of the 10 most famous problems in computer science,” says Navlakha.

Now, he’s found a way to do it better by taking a cue from biology. Navlakha recognized a bipartite matching problem in the wiring of the nervous system. In adult animals, each of the body’s muscle fibers is paired with exactly one neuron that controls its movement. However, early in life, every fiber is targeted by many neurons. To get an animal moving efficiently, excess connections must be pruned. So, which matches are made to last?

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

Navlakha devised a way to implement this matching strategy outside the nervous system. “It’s a simple algorithm,” he says. “It’s only two equations. One is the competition between neurons connected to the same fiber, and two is the reallocation of resources.” The work has been published in Proceedings of the National Academy of Sciences .

Tested against the best bipartite matching programs out there, the neuroscience-inspired algorithm performs very well. It creates near-optimal pairings and leaves fewer parties unmatched. In everyday applications, that 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 bipartite matching systems require that pertinent information be relayed to a central server for processing. But in many cases—from online auctions to donor organ matching—a distributed approach may be preferred. With countless potential applications, Navlakha hopes others will adapt the new algorithm for tools of their own.

“It’s a great example of how studying neural circuits can reveal new algorithms for important AI problems,” he adds.

When you ask a rideshare app to find you a car, the company’s computers get to work. They know you want to reach your destination quickly. They know you’re not the only user who needs a ride. And they know drivers want to minimize idle time by picking up someone nearby. The computer’s job, says Cold Spring Harbor Laboratory Associate Professor Saket Navlakha, is to pair drivers with riders in a way that maximizes everyone’s happiness.

Computer scientists like Navlakha call this bipartite matching. It’s the same task handled by systems pairing organ donors with transplant candidates, medical students with residency programs, and advertisers with ad slots. As such, it’s the subject of intense study.

“This is probably one of the 10 most famous problems in computer science,” says Navlakha.

Now, he’s found a way to do it better by taking a cue from biology. Navlakha recognized a bipartite matching problem in the wiring of the nervous system. In adult animals, each of the body’s muscle fibers is paired with exactly one neuron that controls its movement. However, early in life, every fiber is targeted by many neurons. To get an animal moving efficiently, excess connections must be pruned. So, which matches are made to last?

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

Navlakha devised a way to implement this matching strategy outside the nervous system. “It’s a simple algorithm,” he says. “It’s only two equations. One is the competition between neurons connected to the same fiber, and two is the reallocation of resources.” The work has been published in Proceedings of the National Academy of Sciences .

Tested against the best bipartite matching programs out there, the neuroscience-inspired algorithm performs very well. It creates near-optimal pairings and leaves fewer parties unmatched. In everyday applications, that 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 bipartite matching systems require that pertinent information be relayed to a central server for processing. But in many cases—from online auctions to donor organ matching—a distributed approach may be preferred. With countless potential applications, Navlakha hopes others will adapt the new algorithm for tools of their own.

“It’s a great example of how studying neural circuits can reveal new algorithms for important AI problems,” he adds.