Design of electronic exchanges through decomposition

Abstract

Decomposition-Based Approaches for Clearing Electronic Exchanges Electronic marketplaces have emerged in recent times as the backbone of important e-commerce and e-business applications to create efficient markets for businesses and consumers. To improve the efficiency of markets in terms of a variety of objectives ranging from pure profit maximization to guaranteeing a target market liquidity, there is a need to design innovative mechanisms and algorithms. In this thesis, we consider electronic exchanges, where buyers place bids and sellers specify asks, and it is required to clear the exchange. The clearance of the exchange involves solving:

Trade determination problem (matching sellers with buyers) Pricing problem (determining payments to be made by buyers and payments to be made to sellers)

Even with many restrictions on the bids and asks submitted by the buyers and sellers, both the above problems often turn out to be intractable. Motivated by this, in this thesis, we propose and explore the idea of decomposition to originate a computationally efficient approach for clearing electronic exchanges.

Multi-Unit Electronic Exchange First, we propose an efficient decomposition-based approach to clear a multi-unit electronic exchange for homogeneous goods, where the buying and selling agents specify marginal-decreasing piecewise constant price curves. Our decomposition method enables the overall exchange problem to be solved in two separate phases:

E-selling (forward auction) E-procurement (reverse auction)

The e-selling and e-procurement problems turn out to be generalized knapsack problems, which we solve using fully polynomial-time approximation schemes (FPTAS). The success of our decomposition approach depends critically on determining the right quantity of goods to be traded by the exchange, and we propose two efficient heuristics to determine this quantity. Our experimentation shows that the proposed decomposition approach produces high-quality, if not optimal, solutions to the exchange clearing problem.

Combinatorial Exchange Next, we propose an efficient decomposition-based approach to clear a combinatorial exchange, where the buying and selling agents specify their preferences in terms of bundles.

In the case of single-unit combinatorial exchanges, we first solve the allocation problem exactly to get the optimal trading vector. We use this allocation vector subsequently in the forward and reverse auctions. We solve the forward auction problem using a known approximate greedy allocation and greedy payment scheme, and we solve the reverse auction problem using another known approximate greedy allocation and a payment scheme proposed by us.

We then show that the decomposition approach can be applied in the case of multi-unit combinatorial exchanges as well.

Conclusion The thesis establishes decomposition as an attractive approach to clear electronic exchanges.