text: 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.
  @cite_7: 1. Conceptual outline of current evolutionary theory PART I: ADAPTATION ON THE EDGE OF CHAOS 2. The structure of rugged fitness landscapes 3. Biological implications of rugged fitness landscapes 4. The structure of adaptive landscapes underlying protein evolution 5. Self organization and adaptation in complex systems 6. Coevolving complex systems PART II: THE CRYSTALLIZATION OF LIFE 7. The origins of life: a new view 8. The origin of a connected metabolism 9. Autocatalytic polynucleotide systems: hypercycles, spin glasses and coding 10. Random grammars PART III: ORDER AND ONTOGENY 11. The architecture of genetic regulatory circuits and its evolution 12. Differentiation: the dynamical behaviors of genetic regulatory networks 13. Selection for gene expression in cell type 14. Morphology, maps and the spatial ordering of integrated tissues
summary: There is ongoing work in the field of complexity that attempts to study they dynamics of complex adaptive systems @cite_7 . Our approach is based on ideas borrowed from the use of NK landscapes for the analysis of co-evolving systems. As such, we are using some of the results from that field. However, complexity theory is more concerned with explaining the dynamic behavior of existing systems, while we are more concerned with the engineering of multiagent systems for distributed service allocation.