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...

Full description

Saved in:
Bibliographic Details
Main Authors: SONG, Songzheng, HAO, Jianye, LIU, Yang, SUN, Jun, LEUNG, Ho-fung, ZHANG, Jie
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