Publication Type
Journal Article
Version
publishedVersion
Publication Date
1-2016
Abstract
Automated negotiations play an important role in various domains modeled as multiagent systems, where agents represent human users and adopt different negotiation strategies. Generally, given a multiagent system, a negotiation strategy should be robust in the sense that most agents in the system have the incentive to choose it rather than other strategies. Empirical game-theoretic (EGT) analysis is a game-theoretic analysis approach to investigate the robustness of different strategies based on a set of empirical results. In this study, we propose that model-checking techniques can be adopted to improve EGT analysis for negotiation strategies. The dynamics of strategy profiles can be modeled as a labeled transition system using the counter abstraction technique. We define single-agent best deviation to represent the strategy deviations during negotiation, which focuses on each agent's best deviation benefit and is different from best single-agent deviation used in previous work. Two interesting properties in EGT analysis, i.e., empirical pure strategy Nash equilibrium and best reply cycle, are automatically verified to investigate the robustness of different strategies. For demonstration, the top-six strategies from the automated negotiating agents competition 2010-2012 are studied in terms of their robustness performance. In addition to identifying the most robust strategies, we supply complete rankings among them in different settings. We show that model checking is applicable and efficient to perform robustness analysis of negotiation strategies.
Keywords
Automated Negotiation, Robustness Analysis, Empirical Game Theory, Model Checking
Discipline
Software Engineering | Theory and Algorithms
Research Areas
Software and Cyber-Physical Systems
Publication
IEEE Transactions on Human-Machine Systems
Volume
46
Issue
2
First Page
197
Last Page
208
ISSN
2168-2291
Identifier
10.1109/THMS.2015.2429573
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Citation
SONG, Songzheng; HAO, Jianye; LIU, Yang; SUN, Jun; LEUNG, Ho-fung; and ZHANG, Jie.
Improved EGT-based robustness analysis of negotiation strategies in multiagent systems via model checking. (2016). IEEE Transactions on Human-Machine Systems. 46, (2), 197-208.
Available at: https://ink.library.smu.edu.sg/sis_research/4971
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/THMS.2015.2429573