Mechanism design for dynamic double auctions

A mechanism is a specification for the determination of economic decisions based on the information that is known by the individuals within the economy. Mechanism design is the discipline of designing mechanisms that lead to socially desirable outcomes in a context in which individuals are self-interested. Traditionally, mechanism design has focused on static settings in which the individuals (participants) are known to the mechanism prior to any decision being made. However, many real environments are dynamic, such as in a stock exchange where participants are arriving and departing at different times, and existing solutions for static settings are inappropriate. Although mechanism design for dynamic settings has gained the attention of many researchers over the past decade, most of them have focused on one-sided dynamic market models; that is, either the supply or the demand of the market is dynamic, but not both. Online double auctions, in which the dynamics are two-sided, represent the dominant type of exchange market, but only limited studies have been conducted for online double auctions, due to the complexity of the dynamics. In order to address this gap, this thesis attacks the design problem in two types of online double auction: one type is decision-independent, where each trader’s private information (that is, type) is observed independently and therefore cannot be changed by the decisions of the auction, and the other is decision-dependent, where each trader’s private information depends on other traders and also varies in response to the decisions of the auction. For the first type, this thesis studies a model in which each trader participates (or is active) in the market for only one period of time and the trader’s valuation does not change during this period. First, it provides a computationally efficient optimal (offline) solution that is truthful, efficient and individually rational. This optimal solution is one kind of Vickrey-Clarke-Groves (VCG) mechanism, but it is computationally more efficient than the classical VCG mechanism. Apart from serving the online double auction design, this VCG mechanism also provides a dedicated solution for real trading environments such as futures exchanges. Next, it proposes a reduction framework within which to build an online/dynamic double auction by reducing it to an online one-sided auction. This reduction framework is notable because (1) well-studied online one-sided auctions can be easily reused, and (2) the key properties of the reduced online double auction match those of the online one-sided auction, which is very difficult even for static double auctions. In addition, this thesis shows that in this model it is impossible to design a deterministic online double auction that is truthful, individually rational and competitive for efficiency, although it shows that this is possible under certain assumptions. The second type is approached by means of two steps. First, the double auction design problem is studied in an environment in which traders’ valuations vary with respect to the number of units they trade, but without consideration for the dynamic nature of arrivals and departures. This environment can be mapped to the tremendously growing online shopping model, which leverages group buying, and in this thesis it is modelled as a multi-unit double auction. The thesis provides new insights (impossibilities and possibilities) into the design of multi-unit double auctions under group buying. In particular, it demonstrates that there are no budget-balanced, individually rational and truthful allocations that can guarantee a reasonable transaction size. In the second step, a more complex dynamic environment is envisaged, in which traders dynamically arrive and depart and their valuations change over time. This environment can be mapped to real stock exchanges. Since the models of traders in this kind of environment have been well studied in economics, this thesis addresses the auction design problem directly, based on these well-studied models. However, because traders’ types are dependent on each other as well as on the decisions of the auction, a good auction also needs to learn traders’ behaviours in order to make appropriate decisions in different environments. To that end, an auction design framework based on trader behaviours is developed. This framework demonstrates how auctions can be designed to analyse market dynamics (or trader behaviours) and then use trader behaviours to guide market decisions such that desirable resource allocations are achievable by, for example, attracting more good traders to return to the market in the future