Cooperative Negotiation in Autonomic Systems using Incremental Utility Elicitation

Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5, Canada
email: cebly@cs.toronto.edu

Rajarshi Das, Jeffrey O. Kephart, Gerald Tesauro, William E. Walsh
IBM T. J. Watson Research Center
19 Skyline Dr.
Hawthorne, NY 10532, USA
email: rajarshi,kephart,gtesauro,wwalsh1@us.ibm.com

Abstract
Decentralized resource allocation is a key problem for large-scale autonomic (or self-managing) computing systems. Motivated by a data center scenario, we explore efficient techniques for resolving resource conflicts via cooperative negotiation. Rather than computing in advance the functional dependence of each element's utility upon the amount of resource it receives, which could be prohibitively expensive, each element's utility is elicited incrementally. Such incremental utility elicitation strategies require the evaluation of only a small set of sampled utility function points, yet they find near-optimal allocations with respect to a minimax regret criterion. We describe preliminary computational experiments that illustrate the benefit of our approach.

To appear, UAI 2003

Return to List of Papers