Now or Never : Negotiating Efficiently with Unknown or Untrusted Counterparts

• Autorzy: Mancini T.

Identyfikatory

DOI

10.3233/FI-2016-1443

• Konferencja: Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (22; 22.09.2015; Ferrara; Italy)
• Języki publikacji: EN

Abstrakty

EN

We define a new protocol rule, Now or Never (NoN), for bilateral negotiation processes which allows self-motivated competitive agents to efficiently carry out multi-variable negotiations with remote untrusted parties, where privacy is a major concern and agents know nothing about their opponent. By building on the geometric concepts of convexity and convex hull, NoN ensures a continuous progress of the negotiation, thus neutralising malicious or inefficient opponents. In particular, NoN allows an agent to derive in a finite number of steps, and independently of the behaviour of the opponent, that there is no hope to find an agreement. To be able to make such an inference, the interested agent may rely on herself only, still keeping the highest freedom in the choice of her strategy. We also propose an actual NoN-compliant strategy for an automated agent and evaluate the computational feasibility of the overall approach on both random negotiation scenarios and case studies of practical size.

Słowa kluczowe

EN

automated negotiation; rational selfish agents; unmediated agent negotiation

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 149, nr 1/2
• Strony: 61--100
• Opis fizyczny: Bibliogr. 50 poz., rys., tab., wykr.

Twórcy

autor

Mancini T.

• Computer Science Department, Sapienza University of Rome, Italy

Bibliografia

• [1] Mancini T. Now or Never: Negotiating Efficiently with Unknown Counterparts. In: Proceedings of 22nd RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA 2015). vol. 1451. CEUR Workshop Proceedings; 2015. p. 47–61.
• [2] Faratin P, Sierra C, Jennings NR. Using Similarity Criteria to Make Issue Trade-Offs in Automated Negotiations. Artificial Intelligence. 2002;142(2):205–237.
• [3] Lin R, Kraus S, Wilkenfeld J, Barry J. Negotiating with Bounded Rational Agents in Environments with Incomplete Information using an Automated Agent. Artificial Intelligence. 2008;172(6–7):823–851.
• [4] Rosenschein JS, Zlotkin G. Rules of Encounter: Designing Conventions for Automated Negotiations Among Computers. MIT Press; 1994.
• [5] Rubinstein A. Perfect Equilibrium in a Bargaining Model. Econometrica. 1982;50(1):97–109. doi:10.2307/1912531.
• [6] Faratin P, Sierra C, Jennings NR. Negotiation Decision Functions for Autonomous Agents. Robotics and Autonomous Systems. 1998;24(3–4):159–182.
• [7] Mancini T. Negotiation Exploiting Reasoning by Projections. In: Proceedings of 7th International Conference on Practical Applications of Agents and Multi-Agent Systems (PAAMS 2009). Advances in Intelligent Systems and Computing. Springer; 2009. p. 329–338.
• [8] Cadoli M. Proposal-based negotiation in convex regions. In: Proceedings of 7th International Workshop on Cooperative Information Agents (CIA 2003). vol. 2782 of Lecture Notes in Computer Science. Springer; 2003. p. 93–108.
• [9] Costantini S, De Gasperis G, Provetti A, Tsintza P. A Heuristic Approach to Proposal-Based Negotiation: with Applications in Fashion Supply Chain Management. Mathematical Problems in Engineering. 2013;doi:10.1155/2013/896312.
• [10] Lai G, Sycara K. A Generic Framework for Automated Multi-Attribute Negotiation. Group Decision and Negotiation. 2009;18(2):169–187. doi:10.1007/s10726-008-9119-9.
• [11] Schrijver A. Theory of Linear and Integer Programming. John Wiley & Sons; 1998.
• [12] Bagnara R, Hill PM, Zaffanella E. The Parma Polyhedra Library: Toward a Complete Set of Numerical Abstractions for the Analysis and Verification of Hardware and Software Systems. Science of Computer Programming. 2008;72(1–2):3–21.
• [13] Le Berre D, Parrain A. The Sat4j Library, Release 2.2. Journal on Satisfiability, Boolean Modeling and Computation. 2010;7:59–64.
• [14] Della Penna G, Intrigila B, Melatti I, Minichino M, Ciancamerla E, Parisse A, et al. Automatic Verification of a Turbogas Control System with the Murphi Verifier. In: Proceedings of 6th International Workshop on Hybrid Systems: Computation and Control (HSCC 2003). vol. 2623 of Lecture Notes in Computer Science. Springer; 2003. p. 141–155.
• [15] Cesta A, Finzi A, Fratini S, Orlandini A, Tronci E. Validation and Verification Issues in a Timeline-Based Planning System. Knowledge Engineering Review. 2010;25(3):299–318. doi:10.1017/S0269888910000160.
• [16] Mancini T, Mari F, Massini A, Melatti I, Tronci E. System Level Formal Verification via Distributed Multi-Core Hardware in the Loop Simulation. In: Proceedings of 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP 2014). IEEE; 2014. p. 734–742. doi:10.1109/PDP.2014.32.
• [17] Mancini T, Mari F, Massini A, Melatti I, Tronci E. Anytime System Level Verification via Random Exhaustive Hardware In The Loop Simulation. In: Proceedings of 17th Euromicro Conference on Digital System Design (DSD 2014). IEEE; 2014. p. 236–245.
• [18] Cadoli M, Mancini T, Patrizi F. SAT as an Effective Solving Technology for Constraint Problems. In: Proceedings of 16th International Symposium on Foundations of Intelligent Systems (ISMIS 2006). vol. 4203 of Lecture Notes in Computer Science. Springer; 2006. p. 540–549.
• [19] Mancini T, Cadoli M. Detecting and Breaking Symmetries by Reasoning on Problem Specifications. In: Proceedings of 6th International Symposium on Abstraction, Reformulation and Approximation (SARA 2005). vol. 3607 of Lecture Notes in Computer Science. Springer; 2005. p. 165–181.
• [20] Cadoli M, Mancini T. Automated Reformulation of Specifications by Safe Delay of Constraints. Artificial Intelligence. 2006;170(8–9):779–801.
• [21] Cadoli M, Mancini T. Using a Theorem Prover for Reasoning on Constraint Problems. Applied Artificial Intelligence. 2007;21(4&5):383–404. doi:10.1080/08839510701252650.
• [22] Mancini T, Cadoli M, Micaletto D, Patrizi F. Evaluating ASP and Commercial Solvers on the CSPLib. Constraints. 2008;13(4):407–436.
• [23] Bordeaux L, Cadoli M, Mancini T. A Unifying Framework for Structural Properties of CSPs: Definitions, Complexity, Tractability. Journal of Artificial Intelligence Research. 2008;32:607–629. doi:10.1613/jair.2538.
• [24] Mancini T, Cadoli M. Exploiting Functional Dependencies in Declarative Problem Specifications. Artificial Intelligence. 2007;171(16–17):985–1010.
• [25] Molchanov IS, Stoyan D. Statistical Models of Random Polyhedra. CWI, Amsterdam, The Netherlands; 1995. BS-R9510.
• [26] Stoyan D, Stoyan H. Fractals, Random Shapes and Point Fields. John Wiley & Sons; 1994.
• [27] Mancini T. Now or Never: Negotiating Efficiently with Unknown or Untrusted Counterparts (Appendix); 2016. Available from: http://tmancini.di.uniroma1.it.
• [28] Lin R, Kraus S, Baarslag T, Tykhonov D, Hindriks KV, Jonker CM. Genius: an Integrated Environment for Supporting the Design of Generic Automated Negotiators. Computational Intelligence. 2014;30(1):48–70. doi:10.1111/j.1467-8640.2012.00463.x.
• [29] Conry SE, Kuwabara K, Lesser RA V R Meyer. Multistage Negotiation for Distributed Constraint Satisfaction. IEEE Transactions on Systems, Man and Cybernetics. 1991;21(6):462–477.
• [30] Sycara KP, Roth S, Sadeh N, Fox M. Distributed Constrained Heuristic Search. IEEE Transactions on Systems, Man and Cybernetics. 1991;21(6):446–461.
• [31] Jennings NR, Norman TJ, Faratin P, O’Brien P, Odgers B. Autonomous Agents for Business Process Management. Applied Artificial Intelligence. 2000;14(2):145–189.
• [32] Wang Z, Wang L. Adaptive Negotiation Agent for Facilitating Bi-Directional Energy Trading Between Smart Building and Utility Grid. IEEE Transactions on Smart Grid. 2013;4(2):702–710. doi:10.1109/TSG.2013.2237794.
• [33] Vrba P, Marik V, Siano P, Leitao P, Zhabelova G, Vyatkin V, et al. A Review of Agent and Service-Oriented Concepts Applied to Intelligent Energy Systems. IEEE Transactions on Industrial Informatics. 2014;10(3):1890–1903. doi:10.1109/TII.2014.2326411.
• [34] Mancini T, Mari F, Melatti I, Salvo I, Tronci E, Gruber J, et al. Demand-Aware Price Policy Synthesis and Verification Services for Smart Grids. In: Proceedings of 2014 IEEE International Conference on Smart Grid Communications (SmartGridComm 2014). IEEE; 2014. p. 794–799.
• [35] Kraus S. Negotiation and Cooperation in Multi-Agent Environments. Artificial Intelligence. 1997;94(1–2):79–98.
• [36] Yokoo M, Katsutoshi H. Algorithms for Distributed Constraint Satisfaction: A Review. Autonomous Agents and Multi-Agents Systems. 2000;3(2):185–207.
• [37] Jennings NR, Faratin P, Lomuscio AR, Parsons S, Wooldridge M, Sierra C. Automated Negotiation, Prospects, Methods and Challenges. Group Decision and Negotiation. 2001;10:199–215.
• [38] Hemaissia M, El Fallah-Seghrouchni A, Labreuche C, Mattioli J. A multilateral Multi-Issue Negotiation Protocol. In: Proceedings of 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2007). IFAAMAS; 2007. p. 155. doi:10.1145/1329125.1329314.
• [39] Ito T, Klein M, Hattori H. A Multi-Issue Negotiation Protocol among Agents with Nonlinear Utility Functions. Multiagent and Grid Systems. 2008;4(1):67–83. Available from: http://content.iospress.com/articles/multiagent-and-grid-systems/mgs00092.
• [40] Son TC, Pontelli E, Nguyen NH, Sakama C. Formalizing Negotiations Using Logic Programming. ACM Transactions on Computational Logic. 2014;15(2):12:1–12:30. doi:10.1145/2526270.
• [41] Zlotkin G, Rosenschein JS. Mechanism Design for Automated Negotiation, and its Application to Task Oriented Domains. Artificial Intelligence. 1996;86(2):195–244. doi:10.1016/0004-3702(95)00104-2.
• [42] Zlotkin G, Rosenschein JS. Mechanisms for Automated Negotiation in State Oriented Domains. Journal of Artificial Intelligence Research. 1996;5:163–238.
• [43] Fatima SS, Wooldridge M, Jennings NR. Multi-Issue Negotiation with Deadlines. Journal of Artificial Intelligence Research. 2006;27:381–417. doi:10.1613/jair.2056.
• [44] Gottlob G, Greco G, Mancini T. Complexity of Pure Equilibria in Bayesian Games. In: Proceedings of 20th International Joint Conference on Artificial Intelligence (IJCAI 2007); 2007. p. 1294–1299. Available from: http://dl.acm.org/citation.cfm?id=1625275.1625485.
• [45] Chevaleyre Y, Endriss U, Estivie S, Maudet N. Reaching Envy-Free States in Distributed Negotiation Settings. In: Proceedings of 20th International Joint Conference on Artificial Intelligence (IJCAI 2007); 2007. p. 1239–1244. Available from: http://dli.iiit.ac.in/ijcai/IJCAI-2007/PDF/IJCAI07-200.pdf.
• [46] Saha S, Sen S. An Efficient Protocol for Negotiation over Multiple Indivisible Resources. In: Proceedings of 20th International Joint Conference on Artificial Intelligence (IJCAI 2007); 2007. p. 1494–1499. Available from: http://dli.iiit.ac.in/ijcai/IJCAI-2007/PDF/IJCAI07-241.pdf.
• [47] Kraus S, Sycara K, Evenchik A. Reaching Agreements through Argumentation: a Logical Model and Implementation. Artificial Intelligence. 1998;104:1–69. doi:10.1016/S0004-3702(98)00078-2.
• [48] Amgoud L, Dimopoulos Y, Moraitis P. A Unified and General Framework for Argumentation-based Negotiation. In: Proceedings of 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2007). IFAAMAS; 2007. p. 967–974.
• [49] López-Carmona MA, Marsá-Maestre I, de la Hoz E, Velasco JR. A Region-Based Multi-Issue Negotiation Protocol for Nonmonotonic Utility Spaces. Computational Intelligence. 2011;27(2):166–217. doi:10.1111/j.1467-8640.2011.00377.x.
• [50] Williams CR, Robu V, Gerding EH, Jennings NR. Negotiating Concurrently with Unknown Opponents in Complex, Real-Time Domains. In: Proceedings of 20th European Conference on Artificial Intelligence (ECAI 2012). vol. 242 of Frontiers in Artificial Intelligence and Applications. IOS Press; 2012. p. 834–839. doi:10.3233/978-1-61499-098-7-834.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).