Schemes to reward winners in combinatorial double auctions based on optimization of surplus

• We propose a model to reward winners in combinatorial double auctions.
• We propose schemes to reward winners based on surplus optimization.
• We formulate the problem to maximize the surplus of auctions.
• We propose an algorithm to solve surplus optimization problem.
• We illustrate the effectiveness of our algorithms.

Although the combinatorial double auction model has been proposed for buyers and sellers to trade goods conveniently for over a decade, it is still not widely adopted. Several factors that hinder the adoption of combinatorial double auction model include the high complexity to determine winning bids and the lack of studies on the schemes to benefit winners in an auction. A relevant challenging research issue is to study how to make this business model acceptable in the real world. Motivated by the deficiency of existing studies on these factors, we will study how to take advantage of the surplus of combinatorial double auctions to benefit the winners based on surplus optimization and schemes to reward winners. The contributions of this study are threefold: (1) we propose a computationally efficient approximate algorithm to tackle the complexity issue in combinatorial double auctions, (2) we propose schemes to reward winners based on the surplus of auctions and (3) our study paves the way for the promotion of combinatorial double auction model. Our main results include (i) a surplus optimization problem formulation that takes transaction cost and supply/demand constraints into account (ii) a divide-and-conquer approach to decomposing the optimization problem into subproblems and a subgradient method to determine shadow price (iii) several schemes to reward winners and (iv) numerical results that indicate that the winners can be better off by applying our schemes.