Multiagent Netlogo Models

• D. Gale and L. S. Shapley. College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1):9--15, Mathematical Association of America. 1962.

The Top Trading Cycle Algorithm (TTCA) solves this problem using a very simple greedy method. It was first proposed in:

• Lloyd Shapley and Herbert Scarf. On cores and indivisibility. Journal of Mathematical Economics, 1(1):23--37, 1974.

• Ross D. Shachter. Bayes-Ball: The Rational Pastime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams). In Proceedings of the Fourteenth Conference in Uncertainty in Artificial Intelligence, p. 480--487, 1998.

• Jose M. Vidal. Fundamentals of Multiagent Systems: Using NetLogo Models. Unpublished. 2006.

• Peter Cramton and Yoav Shoham and Richard Steinberg. Combinatorial Auctions. MIT Press. 2006.

• Makoto Yokoo and Katsutoshi Hirayama. Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems. In Proceedings of the Second International Conference on Multiagent Systems, p. 401--408, 1996.

• Hari Prasad Thadakamalla, Usha Nandini Raghavan, Soundar Kumara, and Réka Albert,. Survivability of Multiagent-Based Supply Networks: A Topological Perspective. IEEE Intelligent Systems, 19(5):24--31, 2004

• David Willer. Network Exchange Theory. Praeger Publishers, Westport CT. 1999

• Yoav Shoham and Moshe Tennenholtz. On the emergence of social conventions: modeling, analysis, and simulations. Artificial Intelligence, 94 (139--166) 1997.
• Jordi Delgado. Emergence of social conventions in complex networks. Artificial Intelligence, 141. p. 171--185, 2002.

• Dipyaman Banerjee and Sandip Sen. Reaching pareto-optimality in prisoner's dilemma using conditional joint action learning. Autonomous Agents and Multi-Agent Systems, 15(1):91--108, Kluwer Academic Publishers. 2007.

• C. Bessiere, I. Brito, A. Maestre, P. Meseguer. "Asynchronous Backtracking without Adding Links: A New Member in the ABT Family" . Artificial Intelligence, volume 161, pages 7-24. 2005.

• Christian Bessiere, Arnold Maestre, Pedro Meseguer. The ABT family. In Proceedings of JFNP, 2002

• David Wolpert and Kagan Tumer. Optimal Payoff Functions for Members of Collectives. Advances in Complex Systems, 4(2--3):265--279, 2001.

• Onn Shehory and Sarit Kraus. Methods for Task Allocation via Agent Coalition Formation. Artificial Intelligence, May; 101(1-2):165--200, 1998.

• Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, and Makoto Yokoo. An Asynchronous Complete Method for Distributed Constraint Optimization. In Proceedings of Second International Joint Conference on Autonomous Agents and MultiAgent Systems, July; 2003.

The tree is rooted at the top of the screen. All the lines between nodes represent constraints. The light-colored lines (cyan) are also the parent-child links on the tree. The color of the node is, well, the current color of the node. The numbers on each node represent the LB-threshold-UB:ID.

This is only a beta version!

• Makoto Yokoo and Katsutoshi Hirayama. Algorithms for Distributed Constraint Satisfaction: A Review. Autonomous Agents and Multi-Agent Systems, 3(2):185--207, 2000.
• Makoto Yokoo and Katsutoshi Hirayama. Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems. In Proceedings of the Second International Conference on Multiagent Systems, p. 401--408, 1996.

• Makoto Yokoo and Katsutoshi Hirayama. Algorithms for Distributed Constraint Satisfaction: A Review. Autonomous Agents and Multi-Agent Systems, 3(2):185--207, 2000.

• Hong Jiang and Jose M. Vidal. Reducing Redundant Messages in the Asynchronous Backtracking Algorithm. In Proceedings of the Sixth International Workshop on Distributed Constraint Reasoning, 2005.

• Makoto Yokoo and Katsutoshi Hirayama. Algorithms for Distributed Constraint Satisfaction: A Review. Autonomous Agents and Multi-Agent Systems, 3(2):185--207, 2000.

• Sandip Sen. Reciprocity: a foundational principle for promoting cooperative behavior among self-interested agents. In Proceedings of the Second International Conference on Multiagent Systems, p. 322--329, AAAI Press, Menlo Park, CA. 1996.
• Sandip Sen and Partha Sarathi Dutta. The evolution and stability of cooperative traits. I n Proceedings of the First Intenational Joint Conference on Autonomous Agents and Multiagent Systems, pages 1114-1120. ACM Press, NY, NY, 2002.
• Sandip Sen. Believing others: Pros and cons. Artificial Intelligence, 142(2):179-203, December 2002.

• Christopher J. C. H. Watkins and Peter Dayan. Q-Learning. Machine Learning, 8(3-4):279--292, 1992.

• Jimming Cheng, Winston Cheng, and Radhika Nagpal. “Robust and Self-Repairing Formation Control for Swarms of Mobile Agents”. In Proceedings of the Twentieth National Conference on Artificial Intelligence, p. 59--64, AAAI Press. 2005

• If a neighbor reaches a minimum distance the agent repels that neighbor
• If an agent finds itself inside of the desired shape, it will follow the above rules as long as such movement does not take it outside of the shape
• If an agent is inside of the shape, and it determines that its next move will take it outside of the shape, it will instead do one of 2 things: (a) Stay still: 90% probability (b) Move either slightly to the right, left, up, or down: 10% probability

• A red agent is an agent outside of the desired shape
• A blue agent is an agent inside of the desired shape
• A green agent is an agent that has been displaced

• Jose M. Vidal. An Incentive-Compatible Distributed Recommendation Model. In Proceedings of the Sixth International Workshop on Trust, Privacy, Deception, and Fraud in Agent Societies, p. 84--91, 2003.

• Martha Pollack and Marc Ringuette. Introducing the Tileworld: experimentally evaluating agent architectures. Thomas Dietterich and William Swartout ed.In Proceedings of the Eighth National Conference on Artificial Intelligence, p. 183--189, AAAI Press. 1990.

• Kurt Dresner and Peter Stone. Multiagent Traffic Management: A Reservation-Based Intersection Control Mechanism. In Proceedings of the Third International Joint Conference on Autonomous Agents and MultiAgent Systems, p. 530--537, ACM. 2004. (see also Dresner's original applet)

• Christian Bessiere, Arnold Maestre, Pedro Meseguer. Distributed Dynamic Backtracking (english version). or Distributed Dynamic Backtracking. In Proceedings of the CP00 Workshop on Distributed Constraint Satisfaction Problems, Singapore, Thailand, 2000.

In the constraint graph, constraints are oriented forming a directed acyclic graph, from which an agent hierarchy may be built using heuristic criteria (max-degree, for instance) following the DisAO ordering scheme [Hamadi et al., 1998]. If no heuristic is used, this hierarchy defaults to lexicographic ordering among agents. Considering a generic agent self in the hierarchy, Gama^-(self), it the set of agents constrained with self and appearing at higher levels in the hierarchy. Conversely, Gama⁺(self) is the set of agents constrained with self appearing at lower levels in the hierarchy. This hierarchy induces a partial order among agents, which should be completed to form the total order (using for instance agents identifiers) to ensure completeness.

The DisDB algorithm is executed on each agent, keeping its own agent view and nogood store. The agent view of self is the set of values that it believes to be assigned to agents before self in the total order. The agent view is always consistent with the nogoods in the store. Agents exchange assignments and nogoods. DisDB always accepts new assignments, updating the agent view accordingly. When receiving a nogood, it is accepted if it is consistent with the agent view in Gama ^- (self) and self , otherwise it is discarded due to obsolescence. An accepted nogood is used to update the agent view of agents not in Gama^-(self), and the set of stored nogoods. When all values of an agent are discarded by some nogood, the set of stored nogoods is resolved as in the centralised case, generating a new nogood which is sent to the variable in its right-hand side. This variable plus all variables in the left-hand side of the new nogood that are not in Gama^-(self) are unassigned in the agent view, and nogoods are updated accordingly. The process terminates when achieving quiescence, meaning that a solution has been found, or when the empty nogood is generated, meaning that the problem is unsolvable.

• Christian Bessiere, Arnold Maestre, Pedro Meseguer. Distributed Dynamic Backtracking. C. Bessiere, A. Maestre, and P. Meseguer. In M.C. Silaghi, editor, Proceedings of the IJCAI'01 workshop on Distributed Constraint Reasoning, Seattle WA, pages 9-16.

• Makoto Yokoo, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara. The distributed constraint satisfaction problem: Formalization and algorithms. IEEE Transactions on Knowledge and Data Engineering, 10(5):673-685, 1998.

The queens are prioritized. Queens with a lower 'who' value are of higher priority. The links this program are directed from a queen to all queens of lower priority (for the ok messages) and from each queen to the queen of next higher priority (for the nogood messages) There is no link request required because these are all the links that are needed. An agents current-view consists of the locations of queens of higher priority. The locations are discovered through 'ok' messages.

Nogoods will be handled as follows. If there is no good position based on the positions of higher priority agents, the queen will forward it's current-view to the next higher queen. Upon recieving a no good an agent will first check to see if the nogood is consistent with it's current agent view.. if not the nogood is ignored. Otherwise the agent moves to the next available good position. If the agent's current view is changed the agent discards his nogood and calculates a new one. Each agent maintains a list of positions flagged as either acceptable or unacceptable. When no acceptable position is available a nogood message is passed up containing the agents current-view.

• Jeffrey S. Rosenschein and Gilad Zlotkin. Rules of Encounter. The MIT Press, Cambridge, MA, 1994.

• H. Van Dyke Parunak, Sven Brueckner, and John Sauter. Synthetic pheronome mechanisms for coordination of unmanned vehicles. In Proceedings of the First Intenational Joint Conference on Autonomous Agents and Multiagent Systems, pages 448-450, Bologna, Italy, 2002. ACM Press, New York, NY.

• Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, and Makoto Yokoo. An Asynchronous Complete Method for General Distributed Constraint Optimization. In Proceedings of Autonomous Agents and Multi-Agent Systems Workshop on Distributed Constraint Reasoning, p. 104--118, 2002.

• Chistopher H. Brooks and Edmund H. Durfee. Congregating and market formation. In Proceedings of the 1st International Joint Conference on Autonomous Agents and MultiAgent Systems, pages 96-103, 2002.