Exchange market for complex goods: Search for optimal matches

Eugene Fink, Jinali Gong, and Josh Johnson

Journal of Experimental and Theoretical Artificial Intelligence, 19(2), pages 91-117, 2007.


The Internet has led to the development of on-line markets, and computer scientists have designed various auction algorithms, as well as automated exchanges for standardized commodities; however, they have done little work on exchanges for complex nonstandard goods.

We present an exchange system for trading complex goods, such as used cars or nonstandard financial securities. The system allows traders to represent their buy and sell orders by multiple attributes; for example, a car buyer can specify a model, options, color, and other desirable features. Traders can also provide complex price constraints, along with preferences among acceptable trades; for instance, a car buyer can specify dependency of an acceptable price on the model, year of production, and mileage.

We describe the representation and indexing of orders, and give algorithms for fast identification of matches between buy and sell orders. The system identifies the most preferable matches, which maximize trader satisfaction; it allows control over the trade-off between speed and optimality of matching. It supports markets with up to 300,000 orders, and processes hundreds of new orders per second.