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)

Additional URL

https://doi.org/10.1109/THMS.2015.2429573

Share

COinS