Design and evaluation of norm-aware agents based on Normative Markov Decision Processes

In this paper, we show how the impact of norms on the sequential decision making of agents can be formally modeled, computationally determined and quantitatively assessed. For this purpose, we put forward the Normative Markov Decision Process (NMDP) framework - an extension of Markov Decision Processes (MDPs). NMDPs provide an explicit declarative representation of obligation and prohibition as penalties associated to states and conditions on the accessibility of states. Furthermore, NMDPs make an explicit representation of the probability that whoever is responsible for enforcing the norms detects a violation, thus modeling enforcement effectiveness and cost. Then, we approach the problem of reasoning with the NMDP framework by proposing two types of agent: norm-compliant and self-interested. Using these agents, this paper shows how this framework may be employed to study the impact of norms on agent behavior by providing a quantitative measure of the cost of norm abidance and, by the same token, to what extent norms affect reasoning complexity. In particular, we illustrate the use of the NMDP framework through experimental analysis in a simulated environment where the chances of norm violation being detected and penalties are varied. (C) 2016 Elsevier Inc. All rights reserved.