Professor Duke’s gig-saving algorithms can help match freelancers and service providers

According to a recent survey, 59 million Americans, more than a third of the entire American workforce, have did freelance work Last year. Many find these gigs through online platforms such as Upwork, TaskRabbit or Fiverr, which help connect customers with independent service providers.

One of the biggest challenges these platforms face is finding the best match between clients and freelancers. Customers often have specific needs that not all workers can adequately meet. This type of problem is one of the many lines of research developed by Jiaming XuAssociate Professor of Decision Science at Duke University Fuqua Business School.

Xu’s main research interest is developing algorithms to infer useful information from network data. “We come across many different types of networks in business applications, engineering, and even the natural sciences,” he says. “The key question is how to extract useful information from these networks to guide downstream decision-making.”

Jiaming Xu (photo Duke University),

These networks, as found in the real world, tend to be very large and complex, sometimes involving millions of nodes and different types of links between them. In addition, the observed data may be noisy or partial. “I’m working on developing scalable algorithms that can run very fast and, at the same time, extract this kind of information even when there’s only a very weak signal in the data,” Xu says.

Dealing with uncertainties

In the case of independent platforms, matching customers and service providers can be particularly difficult due to the inherent uncertainties of the process. First of all, the platform does not know until after a service is performed how effective a given freelancer will be in accomplishing a certain task assigned by a client. In other words, the customer’s gain is unknown.

Another problem is that the customer population is very dynamic. They usually arrive on the platform to meet a certain need, stay for a while, and leave after getting the service. Customer arrival and departure statistics are also unknown in advance. Additionally, every freelancer has a limited ability to provide services, a constraint that must also be considered. “That’s the second uncertainty: how to match clients with freelancers in a way that doesn’t cause congestion in the system,” Xu says.

With his co-authors—Wei-Kang Hsumachine learning algorithm engineer currently at Apple, Xiaojun LinProfessor of Electrical and Computer Engineering at Purdue University, and Mark R. Bellalso Professor of Electrical and Computer Engineering at Purdue University – Xu addressed this issue in the article “Embedded e-learning and adaptive control in queuing systems with uncertain gains”, published by the journal Operational research.

“We investigated this as an online correspondence issue,” he says. “The goal is to find that match and at the same time learn the unknown payouts and make sure the system is stable and uncluttered. Then we can maximize the total payout for the online platform. »

In an ideal scenario, the platform would gradually learn each customer’s preferences from trial and error. In the real world, however, the system cannot afford too many errors. If the client’s needs are not met, they will simply leave the platform after a few attempts, so the learning curve should be quick. “The challenge is that you kind of want to know the customer’s preferences very quickly based on feedback or the outcome of assignments,” Xu says.

In machine learning, this dilemma is known as the explore-exploit trade-off. If you keep exploring new matches, you risk sacrificing customer satisfaction. But if you don’t explore, you may also miss the chance to find the best possible match. “That’s why you want to explore, but not too much because you might lose a lot of the gains or benefits.”

think optimistically

To help solve this dilemma, Xu and his colleagues used the upper confidence limit algorithm, which combines exploration and exploitation to get the best result as quickly as possible.

According to this approach, when the performance of a potential match is unknown, this algorithm optimistically assumes that it is more likely to be a good match. In other words, when the uncertainty is high, the results are “inflated” with optimism. Once you’ve had a chance to observe match performance over and over again, you don’t need to inflate the results so much because there’s greater confidence that you’re observing something close to the performance. actual average of this match.

“You always choose the best match based on inflated results, not actual observed results. This is called the upper confidence limit and is basically how we learn about client preferences while making matches,” Xu explains.

Matching fairly

While finding the best possible match for each customer, the algorithm must also take into account the limited capacity of each service provider and the uncertainty in customer arrivals. A simple greedy match to maximize the current estimated gains turns out to be very suboptimal. “We frame this as an optimization problem. There are capacity constraints for each server and you must ensure that you do not violate them. In addition, each customer is associated with a utility function of the service rate received and you must maximize both the total utilities and the estimated corresponding earnings. The utility function promotes fairness in matching, which is desirable in two ways. First, it has an eye on the future, so we can find the right balance between current and future gains. Second, it also controls the learning processes of all clients equally, so that even clients with low estimated earnings can still receive service and improve their earnings estimates.

To assess the performance of the algorithm, Xu and his colleagues calculated the regret rate, which compares the results of the new algorithm to those of an oracle that knows all customer dynamics and preferences in advance. “We showed that regret is very low and decreases the longer you run the system,” Xu says. Regret also decreases if a particular client assigns multiple tasks. In this case, the system learns the customer’s preferences better and better.

The main contribution of this article is to propose a solution that tackles the uncertainty inherent in these types of platforms. Previous work in the literature assumed a scenario in which the arrival rates of different types of customers on the platform and the corresponding earnings were known in advance. “In our case, we don’t need to know this information. We can dynamically allocate our missions in response to these different arrival rates and the corresponding gains. This is what is interesting in our algorithm and our policy. »

Xu says he is particularly drawn to the study of networks because many systems and platforms with commercial applications can be modeled as networks. One of his lines of research is network data privacy and the ease with which information can be traced back to individual users. “Networks are visually very appealing because you can actually draw the nodes, the edges, and explain them easily to an audience,” he says. “At the same time, there is very deep mathematics behind them.”

(C) Duke University

Note: This story was originally published on:

Sharon D. Cole