Author
Listed:
- BORISLAV HADZHIEV
(School of Engineering and Science, Jacobs University Bremen, Campus Ring 1, D-28759 Bremen, Germany)
- KATJA WINDT
(School of Engineering and Science, Jacobs University Bremen, Campus Ring 1, D-28759 Bremen, Germany)
- WERNER BERGHOLZ
(School of Engineering and Science, Jacobs University Bremen, Campus Ring 1, D-28759 Bremen, Germany)
- MARC-THORSTEN HÜTT
(School of Engineering and Science, Jacobs University Bremen, Campus Ring 1, D-28759 Bremen, Germany)
Abstract
Recently, Kearnset al.[Kearns, M., Suri, S. and Montfort, N., An experimental study of the coloring problem on human subject networks,Science313(2006) 824–827] studied the topology dependence of graph coloring dynamics. In their empirical study, the authors analyze, how a network of human subjects acting as autonomous agents performs in solving a conflict-avoidance task (the graph coloring problem) for different network architectures. A surprising result was that the run-time of theempiricaldynamics decreases with the number of shortcuts in a Watts–Strogatz small-world graph. In a simulation of the dynamics based on randomly selecting color conflicts for update, they observe a strong increase of the run-time with the number of shortcuts. Here, we propose classes of strategies, which are capable of explaining the decrease in run-time with an increasing number of shortcuts. We show that the agent's strategy, the graph topology, and the complexity of the problem (essentially given by the graph's chromatic number) interact nontrivially yielding unexpected insights into the problem-solving capacity of organizational structures.
Suggested Citation
Borislav Hadzhiev & Katja Windt & Werner Bergholz & Marc-Thorsten Hütt, 2009.
"A Model Of Graph Coloring Dynamics With Attention Waves And Strategic Waiting,"
Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 12(06), pages 549-564.
Handle:
RePEc:wsi:acsxxx:v:12:y:2009:i:06:n:s0219525909002386
DOI: 10.1142/S0219525909002386
Download full text from publisher
As the access to this document is restricted, you may want to
for a different version of it.
Corrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wsi:acsxxx:v:12:y:2009:i:06:n:s0219525909002386. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
We have no bibliographic references for this item. You can help adding them by using this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/acs/acs.shtml .
Please note that corrections may take a couple of weeks to filter through
the various RePEc services.