Auctions in Exchange Trading Systems: Modeling Techniques and Algorithms
Tradable items are, for instance, company shares, futures contracts, electricity, or natural gas. The most basic combinatorial order is the fill-or-kill order in stock exchanges. This order is either executed entirely or not executed at all. Combinatorial orders are also available in electricity exchanges and in futures exchanges. An exchange usually determines a single price for each class of tradable items. In the absence of combinatorial orders, these prices can be determined separately. However, if there are combinatorial orders that comprise several item classes, then the prices must be determined simultaneously. This is necessary in order to make the prices for combinatorial orders consistent with the ones of the underlying item classes.
The first part of this work presents general modeling techniques and algorithms. For instance, we present a framework model for auctions in which the prices for several classes of items are determined simultaneously. Roughly speaking, we perform several auctions in parallel and integrate the combinatorial orders in such a way that they couple the parallel auctions among each other. For a certain class of combinatorial auctions this work provides model formulations that are solvable in polynomial time. For the general case, where the problem is NP-hard, we provide model formulations and algorithms which are fast enough such that they can be used in practice.
In the second part of this work, we present specific auction models for futures opening auctions, European day-ahead electricity auctions, and European natural gas auctions. Thereby we apply our general models and algorithms, go into problem specific details, and perform numerical tests on real-world instances.