Multiagent systems can play a prominent role in modeling and controlling complex systems. Complex systems are structured in several heterogeneous subsystems and their global behavior depends on the interactions of these subsystems. Multiagent systems provide a paradigm that appears "natural" for modeling complex systems. Controlling a complex system implies the determination of a set of coordinated control actions, one for each subsystem. The control actions influence the system's behavior in order to reach the desired effect. Multiagent systems provide an effective technique to tackle this task: cooperative negotiation. Indeed, controlling complex systems can be viewed as a decentralized multiobjective optimization problem that can be solved by cooperative negotiation, where the control actions are produced as the agreement between negotiating agents. Cooperative negotiation is effective in controlling complex systems because usually it is robust with respect to the composition of the subsystems' network, that can change dynamically. Notwithstanding its promising role to control complex systems, multiagent cooperative negotiation lacks a satisfactory and comprehensive theory. Some crucial questions are still open: the stability of the negotiation, its optimality, its real-time convergence, and its adaptation both to different applications and to changing conditions in a given application. We have provided the following contributions:
We have provided a formal framework to employ to develop cooperative negotiation settings. The framework defines the protocol the agents must follow to negotiate and provides a criterion for the connective stability of the negotiations. Connective stability is a form of stability studied in dynamical systems that naturally adapts to multiagent negotiations, since it studies the stability of dynamical systems that can undergo structural modifications, as in the case of open multiagent systems when agents connect and disconnect. To the best of our knowledge, ours is the first attempt to apply connective stability to multiagent negotiation.
Nicola Gatti, Francesco Amigoni: A Cooperative Negotiation Protocol for Physiological Model Combination. In Proceedings of the 3rd ACM International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS); pages 656-667, New York, USA, July 19-23, 2004. PDF Slides BibTex
Nicola Gatti: A Connective Stability Analysis of Complex System Simulation and Control via Multiagent Systems. In Proceedings of the 2nd European Starting AI Researcher Symposium (STAIRS) in the 16th European Conference on Artificial Intelligence (ECAI); pages 26-37, Valencia, Spain, August 23-24, 2004. Outstanding Paper Award. PDF Slides Award BibTex
Francesco Amigoni, Nicola Gatti: A Formal Framework for Connective Stability of Highly Decentralized Cooperative Negotiations. Autonomous Agents and Multi-Agent Systems. Forthcoming 2007, Springer. PDF BibTex
Once we have defined a framework for stable cooperative negotiations, we have focused our attention on the optimality of the outcome of a cooperative negotiation. Precisely, we have study the Pareto optimality of the outcome in presence of two agents. We have proposed a class of negotiation function able to produce approximate Pareto optimal outcomes.
Nicola Gatti, Francesco Amigoni: A Decentralized Bargaining Protocol on Dependent Continuous Multi-Issue for Approximate Pareto Optimal Outcomes. In Proceedings of the 4th ACM International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS); pages 1213-1214. Utrecht, The Netherlands, July 27-29, 2005. PDF BibTex
Nicola Gatti, Francesco Amigoni: An Approximate Pareto Optimal Cooperative Negotiation Model for Multiple Continuous Dependent Issues". In Proceedings of the 1st ACM/IEEE International Joint Conference on Web Intelligence and Agent Intelligent Technologies (WIIAT); Volume IAT, pages 565-571. Compiegne, France, September 19-22, 2005. PDF Slides BibTex
We have applied cooperative negotiation techniques in two different settings concerning the integration of partial physiological models. In the first contribution, partial models, describing the insulin response to food ingestion and to physical activity, are embedded in agents that are autonomous computational entities behaving as decision makers. The global model emerges from the interaction of these agents in a distributed decision process. More specifically, the agents perform a cooperative negotiation in order to find an agreement on the values of the variables that are "shared" among the models they embed.
Francesco Amigoni, Nicola Gatti: On the Simulation of Multiagent-Based Regulators for Physiological Processes. In Proceedings of 2nd Workshop on Multiagent Based Simulation (MABS) in the 1st ACM International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS); pages 1-10, Bologna, Italy, July 15, 2002. PDF BibTex
Francesco Amigoni, Nicola Gatti, Marco Somalvico: A Multiagent Interaction Paradigm for Physiological Process Control. In Proceedings of the 1st ACM International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS); Volume 1, pages 215-216, Bologna, Italy, July 17-19, 2002 PDF BibTex
Francesco Amigoni, Nicola Gatti: On the Simulation of Multiagent-Based Regulators for Physiological Processes. In "Multi-Agent Based Simulation II (MABS)"; pages 142-154, Springer-Verlag, Berlin, Germany, 2003. PDF BibTex
Francesco Amigoni, Marco Dini, Nicola Gatti, Marco Somalvico: Anthropic Agency: a Multiagent System for Physiological Processes. Artificial Intelligence in Medicine: Volume 27, Issue 3, pages 305-334, March 2003, Elsevier. Special Issue on Agents in Healthcare. PDF BibTex
In the second contribution, we apply the cooperative negotiation techniques to adaptive cardiac pacing setting. This application is important because of the partiality of the available models of heart rate regulation. A desirable solution would be to combine the partial models in a way that each one prevails just when it provides a good emulation of the normal sinus activity. The cooperative negotiation mechanism presented in this paper is an effective and flexible approximation of such solution.
Alessandro Beda, Nicola Gatti, Francesco Amigoni: Heart-Rate Pacing Simulation and Control via Multiagent Systems. In Proceedings of the 2nd Workshop on Agents Applied in Health Care in the 16th European Conference on Artificial Intelligence (ECAI); pages 22-30, Valencia, Spain, August 23-24, 2004. PDF Slides BibTex
Francesco Amigoni, Alessandro Beda, Nicola Gatti: Multiagent Systems for Cardiac Pacing Simulation and Control. AI Communications: Volume 18, Issue 3, pages 217-228, September 2005. Special Issue on Agents Applied in Healthcare, IOS Press. PDF BibTex
Francesco Amigoni, Alessandro Beda, Nicola Gatti: Combining Multi-Sensor Rate-Adaptive Pacing Algorithms via Multiagent Negotiation. IEEE Transactions on Information Technology in Biomedicine: Volume 10, Issue 1, pages 11-18, January 2006, IEEE Press. PDF BibTex
The theory of negotiation is employed in artificial intelligence to address the challenge of automatizing some typically human negotiations, such as commercial negotiations. In this domain intelligent self-interested software agents negotiate with other intelligent agents on behalf of users for buying and selling services and goods. This automation, apart from saving labor time of human negotiators, can lead to more effective negotiations because software agents can enumerate and evaluate potential outcomes faster than humans and are more prone than humans to follow game-theoretic prescriptions.
Among the negotiation settings for commercial transactions, a very common one is bargaining: a buyer and a seller, who are carrying out a transaction, try to agree on the values of the parameters of the transaction. The best known and perhaps most elegant protocol for bilateral bargaining is the alternating-offers protocol, which comes in many variations. Basically, a player starts by offering a value for the parameter of the bargaining to her opponent. The opponent can accept the offer or exit the negotiation or make a counteroffer. If a counteroffer is made, the process is repeated until one of the players accepts or exits the negotiation. Although much economics and computer science literature studies the alternating-offers protocol, several problems are still to be addressed before it can be usefully employed in automated negotiations. The two main open problems concern incomplete information and multi-issue bargaining for rational agents. Easy and general solutions are available only when every pertinent information is common knowledge between the two players and the bargaining is only on one issue. Both assumptions are unrealistic or restrictive; e.g., it is very unlikely that one knows the other player's reservation price or her possible timeout; and it is very likely that one negotiates not only on the price of a good or service but also on its quantity or quality. We have provided contributions for both these problems. We showed that the problem of bargaining multiple issues in-bundle is tractable, being a problem of linear programming.
Francesco Di Giunta, Nicola Gatti: Bargaining in-Bundle over Multiple Issues in Finite-Horizon Alternating-Offers Protocol. In Proceedings of the 9th International Symposium on Artificial Intelligence and Mathematics (AIMATH). Fort Lauderdale, USA, January 4-6 2006. PDF Slides BibTex
Francesco Di Giunta, Nicola Gatti: Bargaining over Multiple Issues in Finite Horizon Alternating-Offers Protocol. Annals of Mathematics in Artificial Intelligence: Volume 47, Issue 3-4, pages 251-271, August 2006. Springer. PDF BibTex
Nicola Gatti, Alessandro Lazaric, Marcello Restelli: Towards Automated Bargaining in Electronic Markets: a Partially Two-Sided Competition Model. In Proceedings of the 10th Workshop on Agent-Mediated Electronic Commerce (AMEC) in the 7th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS); Lisboa, Portugal, May, 2008. PDF BibTex
We showed that bargaining under uncertain deadlines requires the use of mixed strategies, not existing any equilibrium strategy in pure strategy for a non-null measure subset of the space of the parameters
Francesco Di Giunta, Nicola Gatti: Alternating-Offers Bargaining under One-Sided Uncertainty on Deadlines. In Proceedings of the 17th European Conference on Artificial Intelligence (ECAI); pages 225-229. Riva del Garda, Italy, August 28 - September 1 2006. PDF Slides BibTex
Nicola Gatti, Francesco Di Giunta, Stefano Marino: Alternating-Offers Bargaining with One-Sided Uncertain Deadlines: an Efficient Algorithm. Artificial Intelligence: Volume 172, Issue 8-9, pages 1119-1157, May 2008. Elsevier. PDF BibTex
In several multi-agent applications (e-commerce, politic negotiations, board and card games, just to mention a few) agents take their moves sequentially according to an order fixed by an interaction protocol. The "natural" analysis of such situations is provided by game theory. Specifically, game theory models such situations as extensive form games and provides predictions about how the game should be played by perfectly rational agents in presence of a common prior. When at least one of the these two assumptions on the basis of game theory, i.e. perfectly rationality and common prior, drops, alternative techniques to the game theory are needed. It is in these situations that learning approaches enter the picture. Multi-agent learning emerges from artificial intelligence to reason on the interaction between multiple agents perceiving, reasoning, and acting in a common dynamical environment. Multi-agent learning approaches can be split into two main categories: those that build beliefs about the future behavior of other agents and then act accordingly, and those that exclusively consider their own expected utility and try to maximize it. The methods in the first category are commonly addressed as fictitious-play methods, while the others are Reinforcement Learning (RL) methods. In this work we address learning methods belonging to the latter category. We apply RL techniques in bargaining with incomplete information.
Alessandro Lazaric, Enrique Munoz, Nicola Gatti, Marcello Restelli: Reinforcement Learning in Extensive Form Games with Incomplete Information: the Bargaining Case Study. In Proceedings of the 6th ACM International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS); pages 216-218. Honolulu, USA, May 14-18 2007. PDF BibTex
Francesco Amigoni, Nicola Gatti: Sistemi ad Agenti per Applicazioni Domotiche. Casa Futura; pages 29-32, Junuary/February 2008. Invited paper. PDF BibTex
Francesco Amigoni, Nicola Gatti, Carlo Pinciroli, Manuel Roveri: What Planner for Ambient Intelligence Applications?. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans: Volume 35, Issue 1, pages 7-21, January 2005, IEEE Press. Special Issue on Ambient Intelligence. PDF BibTex
Francesco Amigoni, Nicola Gatti: An Environmental Multiagent Architecture for Health Management. In Proceedings of the Workshop on Ambient Intelligence in the 8th AI*IA National Conference; pages 58-69, September 23-26, 2003, Pisa, Italy. PDF Slides BibTex
Nicola Gatti, Matteo Matteucci: CABA2L a Bliss Predictive Composition Assistant for AAC Communication Software. In Proceedings of the 6th ACM/AAAI International Conference on Enterprise Information Systems (ICEIS); Volume 5, pages 89-96, Porto, Portugal, April 14-17, 2004. PDF Slides BibTex
Nicola Gatti, Matteo Matteucci, Licia Sbattella: An ICT Aid for Verbal Impaired People: Bliss2003. In Proceedings of the International Conference on Helping Handicap People (ICHHP); pages 983-990, Paris, France, July 7-9, 2004. PDF BibTex
Nicola Gatti, Matteo Matteucci: CABA2L a Bliss Predictive Composition Assistant for AAC Communication Software". In "Enterprise Information Systems VI"; pages 277-284, Spinger, Berlin, Germany, 2006. PDF BibTex
Nicola Gatti, Matteo Matteucci, Licia Sbattella: User Linguistic Model Adaptivity for Prediction in AAC Message Composition. In Proceedings of the 11th International Conference on Human-Computer Interaction (HCII); Las Vegas, USA, July 22-27, 2005. PDF Slides BibTex
Nicola Gatti: Automazione e Robotica per Disabili. Magazine of the Italian Electric and Electronic Association (AEI), Dossier on Robotics and Disability; Volume 90, pages 26-31, July/August 2003. Invited paper. PDF BibTex
Francesco Amigoni, Nicola Gatti, Viola Schiaffonati: Marco Somalvico's Legacy on Multiagent Systems. AI*IA Notizie, Italian Association for Artificial Intelligence (AI*IA), Volume 16, Issue 3, pages 78-81, September 2003. Invited paper. PDF BibTex
Nicola Gatti: Il Ruolo dell'Agenzia Antropica nella Scoperta Scientifica. In La Cultura Politecnica, Marisa Bertoldini editor; pages 186-187, Bruno Mondadori, Milano, Italy, 2004. PDF BibTex
Luca Mainardi, Nicola Gatti, Matteo Matteucci: On Predicting the Spontaneous Termination of Atrial Fibrillation Episodes Using Linear and Non-Linear Parameters of ECG Signal and RR Series. In Proceedings of the IEEE International Conference on Computers in Cardiology; page 147, Chicago, USA, September 22, 2004. BibTex