Improved EGT-based robustness analysis of negotiation strategies in multiagent systems via model checking
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 hav...
Saved in:
Main Authors: | , , , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2016
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/4971 https://ink.library.smu.edu.sg/context/sis_research/article/5974/viewcontent/thms.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-5974 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-59742020-03-12T07:26:29Z Improved EGT-based robustness analysis of negotiation strategies in multiagent systems via model checking SONG, Songzheng HAO, Jianye LIU, Yang SUN, Jun LEUNG, Ho-fung ZHANG, Jie 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. 2016-01-02T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/4971 info:doi/10.1109/THMS.2015.2429573 https://ink.library.smu.edu.sg/context/sis_research/article/5974/viewcontent/thms.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Automated Negotiation Robustness Analysis Empirical Game Theory Model Checking Software Engineering Theory and Algorithms |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Automated Negotiation Robustness Analysis Empirical Game Theory Model Checking Software Engineering Theory and Algorithms |
spellingShingle |
Automated Negotiation Robustness Analysis Empirical Game Theory Model Checking Software Engineering Theory and Algorithms SONG, Songzheng HAO, Jianye LIU, Yang SUN, Jun LEUNG, Ho-fung ZHANG, Jie Improved EGT-based robustness analysis of negotiation strategies in multiagent systems via model checking |
description |
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. |
format |
text |
author |
SONG, Songzheng HAO, Jianye LIU, Yang SUN, Jun LEUNG, Ho-fung ZHANG, Jie |
author_facet |
SONG, Songzheng HAO, Jianye LIU, Yang SUN, Jun LEUNG, Ho-fung ZHANG, Jie |
author_sort |
SONG, Songzheng |
title |
Improved EGT-based robustness analysis of negotiation strategies in multiagent systems via model checking |
title_short |
Improved EGT-based robustness analysis of negotiation strategies in multiagent systems via model checking |
title_full |
Improved EGT-based robustness analysis of negotiation strategies in multiagent systems via model checking |
title_fullStr |
Improved EGT-based robustness analysis of negotiation strategies in multiagent systems via model checking |
title_full_unstemmed |
Improved EGT-based robustness analysis of negotiation strategies in multiagent systems via model checking |
title_sort |
improved egt-based robustness analysis of negotiation strategies in multiagent systems via model checking |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2016 |
url |
https://ink.library.smu.edu.sg/sis_research/4971 https://ink.library.smu.edu.sg/context/sis_research/article/5974/viewcontent/thms.pdf |
_version_ |
1770575162860634112 |