Modeling opponent decision in repeated one-shot negotiations

ABSTRACT

In many negotiation and bargaining scenarios, a particular agent may need to interact repeatedly with another agent. Typically, these interactions take place under incomplete information, i.e., an agent does not know exactly which offers may be acceptable to its opponent or what other outside options are available to that other agent. In such situations, an agent can benefit by learning its opponent's decision model based on its past experience. In particular, being able to accurately predict opponent decisions can enable an agent to generate offers to optimize its own utility. In this paper, we present a learning mechanism using Chebychev's polynomials by which an agent can approximately model the decision function used by the other agent based on the decision history of its opponent. We study a repeated one-shot negotiation model which incorporates uncertainty about opponent's valuation and outside options. We evaluate the proposed modeling mechanism for optimizing agent utility when negotiating with different class of opponents.

References

1. H. H. Bui, D. Kieronska, and S. Venkatesh. Learning other agents' preferences in multiagent negotiation. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, pages 114--119, Menlo Park, CA, 1996. AAAI Press.
2. D. Carmel and S. Markovitch. Incorporating opponent models into adversary search. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, pages 120--125, Menlo Park, CA, 1996. AAAI Press/MIT Press.
3. D. Carmel and S. Markovitch. Learning models of intelligent agents. In Thirteenth National Conference on Artificial Intelligence, pages 62--67, Menlo Park, CA, 1996. AAAI Press/MIT Press.
4. P. O. W. Curtis F. Gerald. Applied Numerical Analysis. Addison-Wesley Publishing Company, Menlo Park, CA, 1992.
5. S. S. Fatima, M. Wooldridge, and N. Jennings. Optimal negotiation strategies for agents with incomplete information. In Intelligent Agents VIII, Lecture Notes in AI, 2333, pages 377--392. Springer-Verlag, March 2002.
6. L. Y. Geronimus. Orthogonal Polynomials. Consultants Bureau, New York, NY, 1961.
7. P.J. Gmytrasiewicz and E. H. Durfee. A rigorous, operational formalization of recursive modeling. In First International Conference on Multiagent Systems, pages 125--132, Menlo Park, CA, 1995. AAAI Press/MIT Press.
8. M. Huber and E. H. Durfee. An initial assessment of plan-recognition-based coordination for multi-agent teams. In Proceedings of the Second International Conference on Multiagent Systems, pages 126--133, Menlo Park, CA, 1996. AAAI Press.
9. N. Jennings, P. Faratin, A. R. L. S. Parsons, C. Sierra, and M. Wooldridge. Automated negotiation: prospects, methods and challenges. International Journal of Group Decision and Negotiation, 10(2):199--215, 2001.
10. S. Kraus, J. Wilkenfeld, and G. Zlotkin. Multiagent negotiation under time constraints. Artificial Intelligence, 75(2):297--345, 1995.
11. C. Li, J. A. Giampapa, and K. Sycara. Bilateral negotiation decisions with uncertain dynamic outside options. In The First IEEE International Workshop on Electronic Contracting, pages 54--61. IEEE Computer Society, July 2004.
12. A. Muthoo. Bargaining theory with applications. Cambridge University Press, New York, NY, USA, 1999.
13. J. Nash. The bargaining problem. Econometrica, 18(2):155--162, 1950.
14. P. Riley and M. Veloso. Planning for distributed execution through use of probabilistic opponent models. In Sixth International Conference on AI Planning and Scheduling, pages 72--81, 2002.
15. T. Sandholm and N. Vulkan. Bargaining with deadlines. In AAAI/IAAI, pages 44--51, 1999.
16. D. Zeng and K. Sycara. Bayesian learning in negotiation. International Journal of Human Computer Studies, 48, 1998.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Distributed artificial intelligence

      • Multi-agent systems

  • Machine learning

    • Learning settings