Resource allocation via message passing
Coauthor(s): Benjamin Van Roy.
Adobe Acrobat PDF
We propose a message-passing paradigm for resource allocation problems. This serves to connect ideas from
the message-passing literature, which has primarily grown out of the communications, statistical physics,
and artificial intelligence communities, with a problem central to operations research. This also provides a new
framework for decentralized management that generalizes price-based systems by allowing incentives to vary
across activities and consumption levels. We demonstrate that message-based incentives, which are characterized
by a new equilibrium concept, lead to system-optimal behavior for convex resource allocation problems yet yield
allocations superior to those from price-based incentives for nonconvex problems. We describe a distributed
and asynchronous message-passing algorithm for computing equilibrium messages and allocations, and we
demonstrate its merits in the context of a network resource allocation problem.
Source: INFORMS Journal on Computing
Moallemi, Ciamac, and Benjamin Van Roy. "Resource allocation via message passing." INFORMS Journal on Computing 23, no. 2 (Spring 2011): 205-219.