Design of multiunit electronic exchanges through decomposition

Dayama, P. ; Narahari, Y. (2007) Design of multiunit electronic exchanges through decomposition IEEE Transactions on Automation Science and Engineering, 4 (1). pp. 67-74. ISSN 1545-5955

PDF - Publisher Version

Official URL:

Related URL:


In this paper, we exploit the idea of decomposition to match buyers and sellers in an electronic exchange for trading large volumes of homogeneous goods, where the buyers and sellers specify marginal-decreasing piecewise constant price curves to capture volume discounts. Such exchanges are relevant for automated trading in many e-business applications. The problem of determining winners and Vickrey prices in such exchanges is known to have a worst-case complexity equal to that of as many as (1+m+n) NP-hard problems, where m is the number of buyers and n is the number of sellers. Our method proposes the overall exchange problem to be solved as two separate and simpler problems: 1) forward auction and 2) reverse auction, which turns out to be generalized knapsack problems. In the proposed approach, we first determine the quantity of units to be traded between the sellers and the buyers using fast heuristics developed by us. Next, we solve a forward auction and a reverse auction using fully polynomial time approximation schemes available in the literature. The proposed approach has worst-case polynomial time complexity and our experimentation shows that the approach produces good quality solutions to the problem.

Item Type:Article
Source:Copyright of this article belongs to Institute of Electrical and Electronic Engineers.
ID Code:30366
Deposited On:22 Dec 2010 10:25
Last Modified:17 May 2016 13:01

Repository Staff Only: item control page