A Message-Passing Paradigm for Decentralized Resource Allocation
<-- Return to the list
Date: 01-25-2007
Start Time:
1:00pm
End Time: 2:00pm
Speaker: Ciamac Moallemi, Stanford (Faculty Candidate)
Location: Uris 332
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 broadly, offering certain optimality guarantees in the general case. It yields a decentralized and incentive-based framework. It provides an efficient algorithm that is amenable to distributed computation, and has empirically demonstrated excellent performance for intractable combinatorial optimization problems. Finally, it allows for new analytical tools for the analysis of complex resource allocation problems.
(Joint work with Benjamin Van Roy)
BIO
More information on Ciamac Moallemi can be found on his website.