Formulation and dynamical analysis of quantized progressive second price auctions.

摘要

The fundamental motivation for the work in this thesis is the study of decentralized dynamical decision systems and their optimization properties. The design of competitive markets to substitute for traditional centralized regulation has been considered in many domains and a key feature of the decentralized decision mechanisms of competitive markets is that, subject to certain hypotheses, they maximize social welfare. Progressive auctions constitute a highly developed form of such market mechanisms and hence in this thesis we construct and analyze them as paradigm examples of decentralized dynamical decision making systems.;First, a so-called Quantized - PSP (Q-PSP) auction algorithm is analyzed where the agents have similar private demand functions and submit bids synchronously. It is shown that the nonlinear dynamics induced by this algorithm are such that the prices bid by the various agents and the quantities allocated to these agents converge in at most five iterations or oscillate indefinitely, with all prices converging to one price for all agents or to a limit cycle on just two prices for all agents. This behaviour is not only independent of the number of agents involved but is also independent of the number of quantization levels.;Second, the Aggressive-Defensive Quantized - PSP (ADQ-PSP) auction algorithm is presented which improves upon the performance of the Q-PSP auction. For the ADQ-PSP auction applied to agent populations with randomly distributed demand functions, it is shown that the states of the corresponding dynamical systems rapidly converge with high probability to a quantized (Nash) equilibrium with a common price for all agents.;Third, the Unique-limit Quantized - PSP (UQ-PSP) auction algorithm is developed as a modification of the ADQ-PSP; for this algorithm, (i) the limit price of all system trajectories is independent of the initial data, and (ii) modulo the quantization level, the limiting resource allocation is efficient (i.e., the corresponding social welfare function, or summed individual valuation functions, is optimal up to a quantized level).;In the work of Lazar and Semret (1999), a so-called Progressive Second Price auction mechanism (PSP) was proposed for both dynamic market-pricing and allocation of variable-size resources. In this thesis, three quantized versions of the PSP auction are developed.;These quantized auction algorithms are, first, extended to supply auctions, that is to say, competitive markets where only sellers are assumed to exist, and then, second, extended to double-sided auctions where auctions are defined between both sellers and buyers separately and which interact in a well defined way.;Finally, network based auctions are considered; this is motivated by the fact that agents in communication networks or social networks may not be able to access the bid information of all other agents or resource information over such networks and hence must make decisions based solely upon local information. In particular, a two-level network-based auction is developed and is formulated as a consensus UQ-PSP auction where suppliers in the upper network recursively follow consensus dynamics to allocate quantities which are the subject of UQ-PSP auctions at each network node. This configuration solves the corresponding discrete-time weighted-average consensus problem, converges to a unique network wide price and achieves social efficiency for the whole network.