The optimum allocation of limited resources among activities is a classical problem in operations research with many engineering applications. We propose a message-passing paradigm that addresses such problems. This is a conceptual framework where "messages" that reflect the externalities imposed by local decisions are exchanged between individual resource and activity managers. We demonstrate that, like traditional approaches based on shadow prices and convex analysis, message-passing yields optimal allocations when the utility functions are concave and resources are divisible. However, the message-passing approach offers a number of advantages. It extends to cases involving non-concave utility and/or indivisible resources, offering a decentralized and incentive-based framework together with effective heuristic solution algorithms that are amenable to distributed computation. Further, it leads to new analytical tools for the analysis of large scale resource allocation problems.

Joint work with Benjamin Van Roy.
 

About the Speaker

Ciamac C. Moallemi is a PhD student in the Department of Electrical Engineering at Stanford University. He received SB degrees in Electrical Engineering & Computer Science and in Mathematics from the Massachusetts Institute of Technology (1996). He also studied at the University of Cambridge, where he earned a Certificate of Advanced Study in Mathematics, with distinction (1997). Between 1993 and 2003 he was involved in a number of entrepreneurial ventures in finance, biotechnology, and information security.

He has been the recipient of a British Marshall Scholarship (1996-1997) and a Benchmark Stanford Graduate Fellowship (2003-2007). He expects to graduate in 2007.