Mechanism Design for Double Auctions with Temporal Constraints
Dengji Zhao, Dongmo Zhang and Laurent Perrussel
This paper examines an extended double auction model where market clearing is restricted by temporal constraints. It is found that the allocation problem in such auction markets can be effectively transformed into a weighted bipartite matching in graph theory. By using the augmentation technique, we propose a double auction mechanism and prove its efficiency and incentive compatibility. We also show that both the algorithms for allocation and payment calculation run in polynomial time. It is expected that the method and the results provided in this paper can be applied to the design and analysis of dynamic double auctions and futures markets.