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 trade volume 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 products have uniform cost or when the products 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 suppliers that a buyer must use to satisfy a given product need is
minimized.

We present results on the empirical evaluation of our
algorithms on test problems and simulations. Experiments show that our algorithm (MCC
+ stochastic rounding) runs in a fraction of the time of a commercial mixed
integer programming (MIP) package while producing solutions that are always
within 0.7% of the MIP solution.

We evaluate the effectiveness of our algorithm on maintaining balance and on stimulating trade using two different simulation techniques, both based on transaction history data from a trade exchange. The simulation results support 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.