Publication - Self-Organization through Bottom-up Coalition Formation
| Authors: | Sims, Mark; Goldman, Claudia; and Lesser, Victor | ||||
| Title: | Self-Organization through Bottom-up Coalition Formation | ||||
| Abstract: | This paper presents a distributed, incremental approach to self-organization through bottom-up coalition formation applied to a distributed sensor network. The agents engage in negotiations that lead to more efficient allocations of resources and better performance when tasks are assigned to the organization as a whole. We take advantage of the cooperativeness of the system by allowing the agents to share information before they allocate resources. We have tested a range of protocols that agents can implement in order to make decisions that will affect the coalition formation. On one extreme these protocols are based on local utility computations, where each agent negotiates based on its own local perspective. From there, due to the cooperative character of the system, there is a continuum of additional protocols that can be studied. These protocols are based on marginal social utility, where each agent bases its decisions on the combination of its marginal utility and that of others. We present a formal framework that allows us to quantify how social an agent can be and how the choice of a certain level affects the decisions made by the agents and the global utility of the organization obtained. Our results show that by implementing more social agents, we obtain an organization with a high global utility even though the agents do not negotiate over complex contracts. Our algorithm is incremental and therefore the organization that evolves can adapt and stabilize even if some of the agents become inactive during task execution. | ||||
| Keywords: | Coalition Formation, Cooperative Negotiation, Distributed Search, Multi-Agent Systems, Negotiation, Organizational Design, Task Distribution | ||||
| Publication: | Proceedings of Second International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2003), pp. 867 - 874 | ||||
| Location: | Melbourne, AUS | ||||
| Publisher: | ACM Press | ||||
| Date: | July 2003 | ||||
| Sources: |
PS: /Documents/msims/aamas03Sims.ps.gz PS: http://mas.cs.umass.edu/~msims/pubs/aamas03Sims.ps.gz PDF: /Documents/aamas03Sims.pdf |
||||
| Notes: | Also sponsored by NSF Grant #DMI0122173 and Air Force Office of Scientific Research grand #F49620-03-1-0090 | ||||
| Reference: | Sims, Mark; Goldman, Claudia; and Lesser, Victor. Self-Organization through Bottom-up Coalition Formation. Proceedings of Second International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2003), ACM Press, pp. 867-874. July 2003. Also sponsored by NSF Grant #DMI0122173 and Air Force Office of Scientific Research grand #F49620-03-1-0090 | ||||
| bibtex: | @inproceedings{Sims-238,
author = "Mark Sims and Claudia Goldman and Victor Lesser",
title = "{Self-Organization through Bottom-up Coalition
Formation}",
booktitle = "Proceedings of Second International Joint
Conference on Autonomous Agents and MultiAgent
Systems (AAMAS 2003)",
publisher = "ACM Press",
pages = "867-874",
month = "July",
year = "2003",
address = "Melbourne, AUS",
url = "http://mas.cs.umass.edu/paper/238",
}
|
||||
