Surplus optimization in combinatorial double auctions

Although combinatorial double auctions can improve the efficiency of trading goods between buyers and sellers, several issues of combinatorial double auctions are not addressed. For example, an auction mediator usually charges transaction costs to the winners of combinatorial double auctions. Furthermore, a seller may submit multiple bids, but all the winning bids submitted by a seller cannot exceed the available items. These factors are not taken into account in existing literature. In this paper, we study combinatorial double auction problem with transaction costs and supply constraints. We formulate the combinatorial double auction problem and propose an algorithm for finding near optimal solutions. Combinatorial double auctions are notoriously difficult to solve from a computational point of view. To reduce computational complexity, we propose an efficient method by decomposing the combinatorial double auction problem into several buyers' subproblems and sellers' subproblems and applying the subgradient algorithm to iteratively adjust the shadow prices and a heuristic algorithm to find a near-optimal solution. The effectiveness of the proposed algorithm is also demonstrated by a numerical example.