New Heuristic Algorithms to Solve Tough Problems in Sharing Resources

Researchers at the University of Guelph, led by Dr. Monica Cojocaru, Roie Fields, Benjamin Benteke and Kira Tarasuk, have developed heuristic algorithms that can help industries and governments tackle complex decision-making challenges related to resource sharing. The challenge of resource sharing arises when multiple groups or individuals—called “players” in game theory—have to share the same resources. Whether it is managing access to clean water, dividing up land, or planning energy use, each player’s actions impact everyone else’s, making it difficult to find solutions that work for all involved.

The Challenge of Shared Resources

Imagine a community park where each family wants to use a part of the space for different activities. If everyone acts independently without coordination, it could lead to overcrowding and chaos. But with cooperation, everyone can enjoy the park. Now, imagine this situation on a much larger scale, where businesses, governments, or even countries must make decisions about shared resources. This is where game theory—mathematics that studies cooperation and competition—comes into play. But finding a fair balance can be extremely complex.

Researchers have designed two new heuristic algorithms that help model and solve these complex “game theory” problems, where each player’s decisions affect others. These algorithms do more than seek solutions (specifically called equilibria)—they assist stakeholders in finding the optimal balance. They’re also geared towards those that don’t come from a technical mathematical background.

Smarter Tools for Smarter Decisions

The team created two methods, both using algorithms (step-by-step problem-solving processes) to tackle these decision-making issues. The first method, called an “evolutionary-inspired algorithm” (EIA), works a bit like natural selection. It tests multiple possible solutions, keeping the ones that work best and improving on them with each step, similar to selecting the best genes in evolution.

The second method is based on “stochastic gradient descent,” or SGD. Think of SGD as a search process where the algorithm tries out different ideas, keeping track of how close each one is to the best possible outcome. This approach works well in real-life situations where a single perfect solution may not exist, but rather a range of good options.

Making Resource Sharing Easier

Fields and Benteke’s AI-driven tools could make a difference in various areas, from environmental policy to smart city planning. For instance, they could help cities decide how to best use limited energy supplies, reducing waste and costs. These tools might also assist in water management by helping regions or industries share water resources fairly.

“Our algorithms simplify some of the most complex decisions in real-time resource sharing,” says Benteke. “This means faster and more effective solutions, which could help communities and industries make the most of what they have.”

By developing tools that make it easier to find fair solutions, the University of Guelph team is bringing game theory out of the classroom and into real-world applications that could benefit everyone.

This story was written by Mojtaba Safdari as part of the Science Communicators: Research @ CEPS initiative. Mojtaba is a PhD candidate in the School of Engineering under Dr. Amir A. Aliabadi.  

Benjamin Benteke, Monica Gabriela Cojocaru, Roie Fields, Mihai Nica, and Kira Tarasuk. Two Heuristic Methods for Solving Generalized Nash Equilibrium Problems Using a Novel Penalty Function. World Scientific. 2024. doi: 10.1142/9789811267048_0004