A modified Gale-Shapley deferred acceptance method for many-to-many supplier-receiver matchings with transfer of divisible goods

We propose a practical solution to the many-to-many matching problem with transfer of divisible goods. The general model considers a set S of suppliers and a set R of receivers. Each supplier has a “stock” and can supply several receivers. Each receiver has “needs” that can be fulfilled by obtaining goods from one or more suppliers. Each receiver (supplier) has a preference list of individual suppliers (receivers) with no ties. The method uses the Gale-Shapley Deferred Acceptance (DA) algorithm in which we introduce the deferred updating of remaining stocks and needs during the transactions. This ensures that the quantities proposed or requested remain consistent between successive turns, thus avoiding a sub-optimal division of goods among several supplier-receiver pairs. <br> The system is represented by a bipartite graph G = (S, R, E). The suppliers of set S and the receivers of set R are the vertices of the graph, and E is the set of edges. Note that the graph is not necessarily complete: a supplier (receiver) may not be connected to all receivers (suppliers). The edges hold "costs" that are values used by the suppliers or the receivers to rank the counterparts they are connected to in order of preference. As in the original GS method, the matching results from an iteration during which one side proposes and the other side rejects or defers its acceptance while updating its decision with better proposals in subsequent turns. The rejected sides make proposals to others down their list of preferences, and the turns continue until the system is stabilized. Unlike for the original GS method, the matching results obtained are identical irrespective of whether the first turn is taken by suppliers or receivers. We illustrate the application of the method using a small dataset composed of 7 suppliers and 15 receivers. In real-world cases the method has successfully been deployed with several thousands of suppliers and receivers, requiring computing time of the order of minutes. <br> The method presented was originally developed for studying biomass exchanges within an insular territory in its transition towards a more circular economy. The motivation is that a more efficient use of agricultural by-products can help reduce the island’s dependency on imported materials, such as chemical fertilisers for crops and concentrates for animal feed.