A decentralized model for multi-attribute negotiations

ABSTRACT

This paper presents a decentralized model that allows self-interested agents to reach "win-win" agreements in a multi-attribute negotiation. The model is based on an alternating-offer protocol. In each period, the proposing agent is allowed to make a limited number of offers. The responding agent can choose the best offer or reject all of them. In the case of rejection, agents exchange their roles and the negotiation proceeds to the next period. To make counteroffers, an agent first uses the heuristic of choosing, on an indifference curve (or surface), the offer that is closest to the best offer made by the opponent in the previous period, and then taking this offer as the seed, chooses several other offers randomly in a specified neighborhood of this seed offer. Experimental results show that this model can make agents reach near Pareto optimal agreements in general situations where agents have complex preferences on the attributes and incomplete information. Moreover, different from other solutions for multi-attribute negotiations, this model does not require the presence of a mediator.

References

1. A. Mas-Colell, M. D. Whinston and J. R. Green. Microeconomic Theory. Oxford University Press, New York, 1995.
2. M. Bac and H. Raff. Issue-by-issue negotiations: the role of information and time preference. Games and Economic Behavior, 13:125--134, 1996.
3. L.-A. Busch and I. J. Horstmann. Endogenous incomplete contracts: A bargaining approach. Games and Economic Behavior, 19:144--148, 1997.
4. H. Ehtamo, R. Hamalainen, P. Heiskanen, J. Teich, M. Verkama and S. Zionts. Generating pareto solutions in a two-party setting: constraint proposal methods. Management Science, 45:1697--1709, 1999.
5. A. Rubinstein. Perfect equilibrium in a bargaining model. Econometrica, 50(1):97--109, 1982.
6. E. Kalai. Proportional solutions to bargaining situations: Intertemporal utility comparisons. Econometrica, 45(7):1623--1630, 1977.
7. C. Li and G. Tesauro. A strategic decision model for multi-attribute bilateral negotiation with alternating offers. In 4th ACM Conf. on Electronic Commerce, pages 208--209, 2003.
8. C. Li, J. A. Giampapa and K. Sycara. Bilateral Negotiation Decisions with Uncertain Dynamic Outside Options. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Special Issue on Game-theoretic Analysis and Stochastic Simulation of Negotiation Agents, 36(1):1--13, 2006.
9. M. Klein, P. Faratin, H. Sayama and Y. Bar-Yam. Negotiating complex contracts. Group Decision and Negotiation, 12(2):111--125, 2003.
10. J. Nash. The bargaining problem. Econometrica, 18(2):155--162, 1950.
11. P. Faratin, C. Sierra, N. R. Jennings. Using similarity criteria to make negotiation trade-offs. In 4th Int. Conf. on Multi-Agent Systems, pages 119--126, 2000.
12. P. Faratin, C. Sierra and N. R. Jennings. Using similarity criteria to make issue trade-offs in automated negotiations. Artificial Intelligence, 142(2):205--237, 2002.
13. P. Faratin, C. Sierra and N. R. Jennings. Negotiation decision functions for autonomous agents. International Journal of Robotics and Autonomous Systems, 24:159--182, 1998.
14. R. M. Coehoorn and N. R. Jennings. Learning an opponent's preferences to make effective multi-issue negotiation tradeoffs. In 6th Int. Conf. on E-Commerce, pages 59--68, 2004.
15. S. Fatima, M. J. Wooldridge and N. R. Jennings. An agenda-based framework for multi-issue negotiation. Artificial Intelligence, 152(1):1--45, 2004.
16. S. Fatima, M. J. Wooldridge and N. R. Jennings. Optimal negotiation of multiple issues in incomplete information settings. In 3rd Int. Conf. on Autonomous Agents and Multi-Agent Systems, pages 1080--1087, 2004.
17. K. Sycara. Persuasive argumentation in negotiation. Theory and Decision, 28(3):203--242, 1990.
18. K. Sycara. Problem restructuring in negotiation. Management Science, 37(10):1248--1268, 1991.
19. V. Robu, D. Somefun and J. La Poutre. Modeling complex multi-issue negotiations using utility graphs. In 4th Int. Conf. on Autonomous Agents & Multi-Agent Systems, pages 280--287, 2005.
20. C. Jonker and V. Robu. Automated multi-attribute negotiation with efficient use of incomplete preference information. In 3rd Int. Conf. on Autonomous Agents and Multi-Agent Systems, pages 1056--1063, 2004.
21. X. Luo, N. R. Jennings, N. Shadbolt, H. Leung and J. Lee. A fuzzy constraint based model for bilateral multi-issue negotiations in semi-competitive environments. Artificial Intelligence, 148(1-2):53--102, 2003.
22. G. Lai, C. Li, J. Giampapa and K. Sycara. Literature review on multi-attribute negotiations. Tech. Report, Robotics Institute, Carnegie Mellon Univ., December, 2004.
23. D. D. Zeng and K. Sycara. Bayesian learning in negotiation. International Journal of Human-Computer Studies, 48:125--141, 1998.
24. L. Chen and P. Pu. Survey of Preference Elicitation Methods. EPFL Technical Report IC/2004/67, Switzerland, 2004.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Distributed artificial intelligence

      • Multi-agent systems

  • Machine learning

    • Learning settings