Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Giải pháp thương lượng mới cho không gian chào giá hữu hạn
Tóm tắt
Vấn đề thương lượng đề cập đến câu hỏi về việc một đại diện thương lượng nên nhượng bộ đối thủ của mình bao xa. Các giải pháp cổ điển cho vấn đề này, chẳng hạn như giải pháp thương lượng Nash (NBS), dựa trên giả định rằng tập hợp các kết quả thương lượng khả thi tạo thành một không gian liên tục. Gần đây, tuy nhiên, chúng tôi đã đề xuất một giải pháp mới cho vấn đề này cho các tình huống có không gian chào giá hữu hạn, de Jonge và Zhang (Auton Agents Multi-Agent Syst 34(1):1–41, 2020). Ý tưởng của chúng tôi là mô hình hóa vấn đề thương lượng như một trò chơi dạng chuẩn, mà chúng tôi gọi là trò chơi nhượng bộ, và sau đó chọn một trong các điểm cân bằng Nash của nó làm giải pháp. Tuy nhiên, trò chơi này nói chung có nhiều điểm cân bằng Nash và không rõ điểm nào nên được chọn. Trong bài báo này, chúng tôi lấp đầy khoảng trống này bằng cách định nghĩa một giải pháp mới cho vấn đề chung về cách chọn giữa nhiều điểm cân bằng Nash, cho các trò chơi dạng chuẩn 2 người tùy ý. Giải pháp này dựa trên giả định rằng đại diện sẽ chơi một trong hai ‘bên’ của trò chơi (tức là như người chơi hàng hoặc người chơi cột) với tần suất như nhau, hoặc với xác suất bằng nhau. Sau đó, chúng tôi áp dụng điều này vào trò chơi nhượng bộ, điều này kết nối những điểm lỏng lẻo của công trình trước đây của chúng tôi và dẫn đến một giải pháp chính xác, và được định nghĩa rõ ràng cho vấn đề thương lượng. Kết luận nổi bật là, đối với các đại diện hợp lý và hoàn toàn có lợi ích riêng, trong hầu hết các trường hợp, chiến lược tối ưu là đồng ý với thỏa thuận tối đa hóa tổng số tiện ích của các đại diện và không phải là tích của tiện ích của họ như NBS quy định.
Từ khóa
#thương lượng #giải pháp #điểm cân bằng Nash #trò chơi nhượng bộ #lý thuyết trò chơiTài liệu tham khảo
An B, Lesser VR, Irwin DE, et al (2010) Automated negotiation with decommitment for dynamic resource allocation in cloud computing. In: van der Hoek W, Kaminka GA, Lespérance Y, et al (eds) 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), Toronto, Canada, May 10-14, 2010, Volume 1-3. IFAAMAS, pp 981–988, https://dl.acm.org/citation.cfm?id=1838338
Aydogan R, Fujita K, Baarslag T, et al (2019) ANAC 2018: Repeated multilateral negotiation league. In: Ohsawa Y, Yada K, Ito T, et al (eds) Advances in Artificial Intelligence - Selected Papers from the Annual Conference of Japanese Society of Artificial Intelligence (JSAI 2019), Niigata, Japan, 4-7 June 2019, Advances in Intelligent Systems and Computing, vol 1128. Springer, pp 77–89, https://doi.org/10.1007/978-3-030-39878-1_8
Aydogan R, Baarslag T, Fujita K, et al (2020) Research challenges for the automated negotiating agents competition (anac) 2019. In: Multi-Agent Systems and Agreement Technologies. 17th International Conference EUMAS 2020 and 7th International Conference AT 2020. Thessaloniki, Greece September 14-15, 2020. Revised Selected Papers. Springer
Aydoğan R, Baarslag T, Fujita K, et al (2020) Challenges and main results of the automated negotiating agents competition (anac) (2019). In: Bassiliades N, Chalkiadakis G, de Jonge D (eds) Multi-Agent Systems and Agreement Technologies. Springer International Publishing, Cham, pp 366–381
Baarslag T, Fujita K, Gerding EH et al (2013) Evaluating practical negotiating agents: Results and analysis of the 2011 international competition. Artif Intell 198:73–103. https://doi.org/10.1016/j.artint.2012.09.004
Baarslag T, Hendrikx MJC, Hindriks KV et al (2016) Learning about the opponent in automated bilateral negotiation: a comprehensive survey of opponent modeling techniques. Auton Agents Multi Agent Syst 30(5):849–898. https://doi.org/10.1007/s10458-015-9309-1
Bakker J, Hammond A, Bloembergen D, et al (2019) RLBOA: A modular reinforcement learning framework for autonomous negotiating agents. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, Montreal, QC, Canada, May 13-17, 2019, pp 260–268, http://dl.acm.org/citation.cfm?id=3331701
Chakraborty S, Baarslag T, Kaisers M (2018) Energy contract settlements through automated negotiation in residential cooperatives. In: 2018 IEEE International Conference on Communications, Control, and Computing Technologies for Smart Grids, SmartGridComm 2018, Aalborg, Denmark, October 29-31, 2018. IEEE, pp 1–6, https://doi.org/10.1109/SmartGridComm.2018.8587537
Chen S, Weiss G (2012) An efficient and adaptive approach to negotiation in complex environments. In: ECAI 2012 - 20th European Conference on Artificial Intelligence. Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track, Montpellier, France, August 27-31 , 2012, Frontiers in Artificial Intelligence and Applications, vol 242. IOS Press, pp 228–233, https://doi.org/10.3233/978-1-61499-098-7-228
Cheng SF, Reeves DM, Vorobeychik Y, et al (2004) Notes on equilibria in symmetric games. In: Parsons S, Gmytrasiewicz P (eds) Proceedings of the 6th International Workshop On Game Theoretic And Decision Theoretic Agents GTDT, pp 71–78
Conley JP, Wilkie S (1996) An extension of the nash bargaining solution to nonconvex problems. Games Econ Behavi 13(1):26–38
Dreves A (2019) An algorithm for equilibrium selection in generalized nash equilibrium problems. Comput Optim Appl 73(3):821–837
Faratin P, Sierra C, Jennings NR (1998) Negotiation decision functions for autonomous agents. Robot Auton Syst 24(3–4):159–182
Frieder A, Miller G (2013) Value model agent: A novel preference profiler for negotiation with agents. In: Complex Automated Negotiations: Theories, Models, and Software Competitions, Studies in Computational Intelligence, vol 435. Springer, p 199–203, https://doi.org/10.1007/978-3-642-30737-9_12
Fujita K, Aydogan R, Baarslag T, et al (2014) The fifth automated negotiating agents competition (ANAC 2014). In: Fukuta N, Ito T, Zhang M, et al (eds) Recent Advances in Agent-based Complex Automated Negotiation [revised and extended papers from the 7th International Workshop on Agent-based Complex Automated Negotiation, ACAN 2014, Paris, France, May 2014], Studies in Computational Intelligence, vol 638. Springer, pp 211–224, https://doi.org/10.1007/978-3-319-30307-9_13
Harsanyi JC (1995) A new theory of equilibrium selection for games with complete information. Games Econ Behav 8(1):91–122
Harsanyi JC, Selten R (1988) A general theory of equilibrium selection in games. The MIT Press
Herrero MJ (1989) The nash program: non-convex bargaining problems. J Econ Theory 49(2):266–277
Hindriks KV, Tykhonov D (2008) Opponent modelling in automated multi-issue negotiation using bayesian learning. In: 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), Estoril, Portugal, May 12-16, 2008, Volume 1. IFAAMAS, pp 331–338, https://dl.acm.org/citation.cfm?id=1402433
de Jonge D (2022) An analysis of the linear bilateral ANAC domains using the MiCRO benchmark strategy. In: Raedt LD (ed) Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022. ijcai.org, pp 223–229, https://doi.org/10.24963/ijcai.2022/32
de Jonge D, Zhang D (2017) Automated negotiations for general game playing. In: Larson K, Winikoff M, Das S, et al (eds) Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2017, São Paulo, Brazil, May 8-12, 2017. ACM, pp 371–379
de Jonge D, Zhang D (2020) Strategic negotiations for extensive-form games. Auton Agents Multi-Agent Syst 34(1) https://doi.org/10.1007/s10458-019-09424-y
de Jonge D, Bistaffa F, Levy J (2021) A heuristic algorithm for multi-agent vehicle routing with automated negotiation. In: Dignum F, Lomuscio A, Endriss U, et al (eds) AAMAS ’21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021. ACM, pp 404–412, https://dl.acm.org/doi/10.5555/3463952.3464004
Jonge Dd, Bistaffa F, Levy J (2022) Multi-objective vehicle routing with automated negotiation. Appl Intell. https://doi.org/10.1007/s10489-022-03329-2
Kalai E, Smorodinsky M (1975) Other solutions to nash’s bargaining problem. Econometrica 43(3):513–518
Kreindler GE, Young HP (2013) Fast convergence in evolutionary equilibrium selection. Games Econ Behav 80:39–67. https://doi.org/10.1016/j.geb.2013.02.004https://www.sciencedirect.com/science/article/pii/S0899825613000262
van Krimpen T, Looije D, Hajizadeh S (2013) Hardheaded. In: Complex Automated Negotiations: Theories, Models, and Software Competitions, Studies in Computational Intelligence, vol 435. Springer, pp 223–227, https://doi.org/10.1007/978-3-642-30737-9_17
Lampariello L, Neumann C, Ricci JM, et al (2021) Equilibrium selection for multi-portfolio optimization. Eur J Oper Res
Lemke CE, Howson JT Jr (1964) Equilibrium points of bimatrix games. J Soc Ind Appl Math 12(2):413–423
Matsui A, Matsuyama K (1995) An approach to equilibrium selection. J Econ Theory 65(2):415–434
Miękisz J (2005) Equilibrium selection in evolutionary games with random matching of players. J Theor Biol 232(1):47–53 https://doi.org/10.1016/j.jtbi.2004.07.019https://www.sciencedirect.com/science/article/pii/S0022519304003492
Nash J (1950) The bargaining problem. Econometrica 18:155–162
Nash J (1951) Non-cooperative games. Ann Math 54(2):286–295
Nash J (1953) Two-person cooperative games. Econometrica 21:128–140
Osborne MJ, Rubinstein A (1994) A course in game theory. MIT press
Pettigrew R (2016) Accuracy, risk, and the principle of indifference. Philos Phenomenol Res 92(1):35–59
Renting BM, Hoos HH, Jonker CM (2020) Automated configuration of negotiation strategies. In: Seghrouchni AEF, Sukthankar G, An B, et al (eds) Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, Auckland, New Zealand, May 9-13, 2020. International Foundation for Autonomous Agents and Multiagent Systems, pp 1116–1124, https://doi.org/10.5555/3398761.3398891https://dl.acm.org/doi/10.5555/3398761.3398891
Robson AJ, Vega-Redondo F (1996) Efficient equilibrium selection in evolutionary games with random matching. J Econ Theory 70(1):65–92. https://doi.org/10.1006/jeth.1996.0076https://www.sciencedirect.com/science/article/pii/S0022053196900769
Rosenschein JS, Zlotkin G (1994) Rules of Encounter. The MIT Press, Cambridge, USA
Rubinstein A (1982) Perfect equilibrium in a bargaining model. Econometrica: J Econ Soc pp 97–109
Samuelson L (1997) Evolutionary games and equilibrium selection, vol 1. MIT press
Sengupta A, Mohammad Y, Nakadai S (2021) An autonomous negotiating agent framework with reinforcement learning based strategies and adaptive strategy switching mechanism. In: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’21, Online, May 5-7, 2021. International Foundation for Autonomous Agents and Multiagent Systems
Serban LD, Silaghi GC, Litan CM (2012) Agentfsega: Time constrained reasoning model for bilateral multi-issue negotiations. In: New Trends in Agent-Based Complex Automated Negotiations, Studies in Computational Intelligence, vol 383. Springer, pp 159–165, https://doi.org/10.1007/978-3-642-24696-8_11
Williams CR, Robu V, Gerding EH, et al (2011) Using gaussian processes to optimise concession in complex negotiations against unknown opponents. In: IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011. IJCAI/AAAI, pp 432–438, https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-080
Williams CR, Robu V, Gerding EH, et al (2012) Iamhaggler: A negotiation agent for complex environments. In: New Trends in Agent-Based Complex Automated Negotiations, Studies in Computational Intelligence, vol 383. Springer, pp 151–158, https://doi.org/10.1007/978-3-642-24696-8_10
Williams CR, Robu V, Gerding EH, et al (2014) An overview of the results and insights from the third automated negotiating agents competition (ANAC2012). In: Novel Insights in Agent-based Complex Automated Negotiation, Studies in Computational Intelligence, vol 535. Springer, pp 151–162, https://doi.org/10.1007/978-4-431-54758-7_9