Balanced Matching of Buyers and Sellers in E-Marketplaces: The Barter Trade Exchange Model

In this paper, we describe the operation of barter trade exchanges by identifying key techniques used by trade brokers to stimulate trade and satisfy member needs, and present algorithms to automate some of these techniques.  In particular, we develop algorithms that emulate the practice of trade brokers by matching buyers and sellers in such a way that the volume of goods traded is maximized while the balance of trade is maintained as much as possible. We show that the buyer/seller matching and trade balance problems can be decoupled, permitting efficient solution as well as numerous options for matching strategies.  We model the trade balance problem as a minimum cost circulation problem (MCC) on a network. When the goods have uniform cost or when the goods can be traded in fractional units, we solve the problem exactly using a simplified version of the minimum mean cycle canceling algorithm. Otherwise, we present a novel stochastic rounding algorithm that takes the fractional optimal solution to the trade balance problem and produces a valid integer solution. We then make use of a greedy heuristic that attempts to match buyers and sellers so that the average number of sellers matched to a buyer of a good is minimized.  Finally, we also present results on the empirical evaluation of our algorithms on test problems and simulations.  The solutions from our stochastic rounding algorithm are always within 0.7% of the solution obtained from a commercial mixed integer programming package. We evaluate the effectiveness of our algorithm on maintaining balance and on stimulating trade using a simulator built using transaction history data from a trade exchange. The simulation results confirm the barter trade exchange rule of thumb that maximizing single-period trade volume while maintaining balance of trade helps to maximize trade volume over the long run.