A Message-Passing Paradigm for Resource Allocation

Benjamin Van Roy
Department of Management Science and Engineering and
Department of Electrical Engineering
Stanford University


Wednesday, January 31, 2007
4:30 - 5:30 PM
Terman Engineering Center, Room 453


Abstract:

The optimum allocation of limited resources among activities is a classical problem in operations research. 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.

This is joint work with Ciamac Moallemi.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html