  We present a method for solving service allocation problems in which a set of
services must be allocated to a set of agents so as to maximize a global
utility. The method is completely distributed so it can scale to any number of
services without degradation. We first formalize the service allocation problem
and then present a simple hill-climbing, a global hill-climbing, and a
bidding-protocol algorithm for solving it. We analyze the expected performance
of these algorithms as a function of various problem parameters such as the
branching factor and the number of agents. Finally, we use the sensor
allocation problem, an instance of a service allocation problem, to show the
bidding protocol at work. The simulations also show that phase transition on
the expected quality of the solution exists as the amount of communication
between agents increases.
