Auctions on networks: Efficiency, consensus, passivity, rates of convergence

First, a quantized progressive second price (PSP) auction mechanism called the Unique Limit Quantized - PSP (UQ-PSP) is presented for the allocation of fixed or timevarying quantities of a resource among arbitrary populations of agents. It is shown that (i) the states (i.e. bid prices and quantities) of the corresponding iterative dynamical auction system converge to a unique quantized (Nash) equilibrium with a common limit price for all agents, (ii) the limit price of all system trajectories is independent of the initial data, and (iii) modulo the quantization level, the limiting resource allocation is efficient, that is to say the corresponding social welfare function is optimized. Second, distributed auctions on a twolevel network are developed: each vertex in the higher level network is regarded as a supplier for a uniquely associated lower level network; each such lower level network consists of a set of agents which represent buyers; and each of the lower level networks and their associated suppliers is assumed to constitute a local UQ-PSP auction A_¿. The adjustment of the quantities supplied to any A_¿ is via a consensus-based dynamical system which exchanges quantities depending upon the limit prices of the local auctions in the (nearest neighbour) neighborhood of A_¿ in the higher level network. Convergence is established using a passivity property of UQ-PSP auctions and the system properties on those networks which are scale free random graphs are investigated.