Abstract
This paper presents a novel approach to the well-known Knapsack problem, extending it as a bilateral negotiating problem with default information where each of the two agents has a knapsack and there is a set of items distributed between them. The agents can exchange items in order to reach their goal: fill their knapsacks with items without exceeding their capacity with the aim of maximizing their utility function. Initially the agents do not have any information about their counterpart, e.g. the exact weight of their items and their associated values, so that they consider default assignments for them. This default information can change as the negotiation progresses. A sequential negotiation protocol is proposed, along with different strategies of information exchange and the results obtained when the agents negotiate using them. Information transfer efficiency is assessed in terms of the overall usefulness, quantity of information disclosed and negotiation duration.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Rahwan, I., Ramchurn, S.D., Jennings, N.R., Mcburney, P., Parsons, S., Sonenberg, L.: Argumentation-based negotiation. Knowl. Eng. Rev. 18, 343–375 (2003)
Rosenschein, J.S., Zlotkin, G.: Rules of Encounter - Designing Conventions for Automated Negotiation among Computers. MIT Press (1994)
Jennings, N.R., Faratin, P., Lomuscio, A.R., Parsons, S., Sierra, C., Wooldridge, M.: Automated negotiation: Prospects, methods and challenges. International Journal of Group Decision and Negotiation 10(2), 199–215 (2001)
Amgoud, L., Dimopoulos, Y., Moraitis, P.: A unified and general framework for argumentation-based negotiation. In: Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2007 (2007)
Pilotti, P., Casali, A., Chesñevar, C.: A belief revision approach for argumentation-based negotiation with cooperative agents. In: McBurney, P., Parsons, S., Rahwan, I., (eds.) Post-Proceedings of the 9th International Workshop on Argumentation in Multi-Agent Systems (ArgMAS 2013) (2013)
Fisher, R., Ury, W.L.: Getting to Yes: Negotiating Agreement Without Giving, 2nd edn. Penguin (Non-Classics) (December 1991)
Rahwan, I., Pasquier, P., Sonenberg, L., Dignum, F.: On the benefits of exploiting underlying goals in argument-based negotiation. In: Twenty-Second Conference on Artificial Intelligence (AAAI), Vancouver, pp. 116–121 (2007)
Pasquier, P., Hollands, R., Rahwan, I., Dignum, F., Sonenberg, L.: An empirical study of interest-based negotiation. Autonomous Agents and Multi-Agent Systems 22(2), 249–288 (2011)
Jonge, D.D., Sierra, C.: Branch and bound for negotiations in large agreement spaces. In: van der Hoek, W., Padgham, L., Conitzer, V., Winikoff, M., (eds.) AAMAS, IFAAMAS, pp. 1415–1416 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Pilotti, P., Casali, A., Chesñevar, C. (2014). The Double Knapsack Negotiation Problem: Modeling Cooperative Agents and Experimenting Negotiation Strategies. In: Bazzan, A., Pichara, K. (eds) Advances in Artificial Intelligence -- IBERAMIA 2014. IBERAMIA 2014. Lecture Notes in Computer Science(), vol 8864. Springer, Cham. https://doi.org/10.1007/978-3-319-12027-0_44
Download citation
DOI: https://doi.org/10.1007/978-3-319-12027-0_44
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12026-3
Online ISBN: 978-3-319-12027-0
eBook Packages: Computer ScienceComputer Science (R0)