2/27/20 | 4:15pm | E51-325
Reception to follow.

Kuang Xu

Associate Professor
Stanford

Abstract: We propose a general framework, dubbed Stochastic Processing under Imperfect Information (SPII), to study the impact of information constraints and memories on dynamic resource allocation. The framework involves a Stochastic Processing Network (SPN) scheduling problem in which the decision maker may access the system state only through a noisy channel, and resource allocation decisions must be carried out through the interaction between an encoding policy (who observes the state) and allocation policy (who chooses the allocation) situated on the two ends of the channel. Applications in the management of large-scale data centers and human-in-the-loop service systems are among our chief motivations. 

We quantify the degree to which information constraints reduce the size of the capacity region in general SPNs, and how such reduction depends on the amount of memories available to the encoding and allocation policies. Using a novel metric, capacity factor, our main theorem characterizes the reduction in capacity region (under “optimal” policies) for all non-degenerate channels, and across almost all combinations of memory sizes. Notably, the theorem demonstrates, in substantial generality, that (1) the presence of a noisy channel always reduce capacity, (2) more memories for the allocation policy always improve capacity, and (3) more memories for the encoding policy have little to no effect on capacity. Finally, all of our positive (achievability) results are established through constructive, implementable policies. 

Our proof program involves the development of a host of new techniques, largely from first principles, by combining ideas from information theory, learning and queueing theory. As a sub-module of one of the policies proposed, we create a simple yet powerful generalization of the Max-Weight policy, in which individual Markov chains are selected dynamically in a manner analogous to how schedules are used in a conventional Max-Weight policy.

Joint work with Yuan Zhong (University of Chicago, Booth School of Business).

Bio: Kuang Xu was born in Suzhou, China. He is an Associate Professor of Operations, Information and Technology at the Stanford Graduate School of Business, Stanford University. He received the B.S. degree in Electrical Engineering (2009) from the University of Illinois at Urbana-Champaign, Urbana, Illinois, USA, and the Ph.D. degree in Electrical Engineering and Computer Science (2014) from the Massachusetts Institute of Technology, Cambridge, Massachusetts, USA. His research interests lie in the fields of applied probability theory, optimization, and operations research, seeking to understand fundamental properties and design principles of large-scale stochastic systems, with applications in queueing networks, healthcare, privacy and learning theory. He has received several awards including a First Place in INFORMS George E. Nicholson Student Paper Competition, a Best Paper Award, as well as a Kenneth C. Sevcik Outstanding Student Paper Award from ACM SIGMETRICS.