Analysis of Decentralized Quantized Auctions on Cooperative Networks

Peng Jia
McGill University

Monday, October 18, 2010 at 10:30am
Engr IV Maxwell Room 57-124

Abstract

In this talk I will first present a quantized Progressive Second Price (PSP) auction algorithm, called, the Unique-limit Quantized - PSP (UQ-PSP) algorithm for the allocation of fixed or time-varying quantities of a divisible resource among arbitrary populations of agents. It will be 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 (i.e., the corresponding social welfare function, or summed individual valuation functions, is optimal). Second, in this talk, I will develop a distributed auction on a two-level network: each vertex in the higher level network shall be regarded as a supplier for a uniquely associated lower level network; each such lower level network will consist of a set of agents which represent buyers; and each of the lower level networks and their associated suppliers will be assumed to constitute a local UQ-PSP auction A?. The adjustment of the quantities supplied to any A? will be via a consensus-based dynamical system which exchanges quantities depending upon the limit prices of the local auctions in the neighborhood of A? in the higher level network. Such a consensus UQ-PSP system will solve the corresponding discrete-time weighted-average consensus problem with an associated family of time-varying and asymmetric Perron matrices. Convergence will be established using a passivity property of UQ-PSP auctions, and using the primitiveness and SIA (stochastic, indecomposable and aperiodic) property of the family of Perron matrices.

Biography
Peng Jia is currently a Ph.D. candidate in the Department of Electrical and Computer Engineering and the Centre for Intelligent Machines at McGill University. He received his M.S. degree in Mechanical and Automation Engineering from the Chinese University of Hong Kong, Hong Kong, in 2005, and his B.E. degree in Electrical Engineering from Beijing University of Aeronautics and Astronautics, China, in 2001. His research interests include network control and games, large population and large scale stochastic systems and control, and, in particular, dynamical auctions and their potential applications in communication networks and other decentralized systems.