Towards a framework for the analysis of provenance-aware norms in complex networks?

Abstract

Systemic analysis of dynamics in complex networks has allured interest from different fields. Norms are a mechanism that can be useful to govern or guide the behavior of agents in such scenarios. Such effects of norms can be analyzed in different terms, such as emergence, spread, equilibrium oscillations and stability. In this paper, we present an analysis of the life-cycle of deontic norms in scale-free networks, with special focus on the long-term effects of different agents' personalities and their structural properties. Our approach combines provenance-aware monitoring traces and the analysis of the dynamics emerged in the relations between agents by means of complex network representations.

Keywords

• provenance
• normative systems
• complex networks
• monitoring

1 Introduction

Public goods is a subject that has been largely studied and discussed, concretely recent in-depth research by Hardin [ 1 ] and Ostrom [ 5 ] discusses the rationality behind the ‘tragedy of the commons’. We understand such scenario as a situation where a set of agents use a public finite good. If agents only seek to maximize their own benefit, they will eventually exhaust it once the population surpasses the public good’s renewal capacity. This applies to different situations – politics, energy, pollution. This paper proposes a framework that combines a multi-agent system (MAS) approach with provenance of events to identify behavioural patterns w.r.t. the set of norms that drive the agents. Additionally, we model the agents’ social structure by means of complex networks. With such framework we pursue modelling behavioural patterns to resemble a ‘tragedy of the commons’ scenario where different dynamics can be studied.

Relevant related work

Multi-agent systems and norms are commonly used to model societies and how its individuals coordinate among them. A suitable approach to model these norms is by means of deontic logic, which allows studying norm dynamics in terms of how changes may induce behavioural changes [ 2 ]. Agents react and interact according to events occurring in the system and following the norms specified in that society. These events and interactions can be tracked by a provenance mechanism, such as directed acyclic graphbased [ 4 ], where nodes represent events and edges the causal relation between them. These relations can be analysed to extract causal patterns between nodes [ 3 ]. Finally, the use of complex networks allows analysing group structures [ 7 ] in terms of dynamic changes. For instance, Villatoro [ 6 ] shows how different structures are more prone to internalize external norms and how this affects norms dynamics. 3

Proposal

We propose a framework to model a ‘tragedy of the commons’ scenario by means of a MAS and a set of norms that drive agents behaviour. The events and actions of the MAS are stored in a provenance mechanism and the agents’ social structure is represented by means of complex networks. This framework allows performing retrodiction analyses to detect what past events have concurred to produce current situations thus effectively allowing to prevent/promote certain behaviours to generate similar situations. The usage of complex networks allows analysing the influence of social structures in the stability of norms as well as behaviour spreadness. Furthermore, it also allows knowing when these norms stabilize and discover how certain social structures and agents’ personality distribution affect the stability of the scenario mentioned before and norms in general. 4

Conclusions

This paper proposes a framework that combines MAS, a set of norms to drive their behaviour along a provenance mechanism of their actions as well as a complex network representing their social structure. Other uses of this framework may include: – Monitoring when a norm is about to be violated – Proposing norm or structural changes to avoid a ‘tragedy of the commons’ scenario – Analyse how agents’ personalities and their distribution affect behavioural patterns – Adding semantics to the events provenance to refine and improve pattern detection – Design different approaches for pattern detection, such as sequence alignment

References

1. Hardin , G. : The tragedy of the commons . Science 162 ( 3859 ), 1243 - 1248 ( 1968 )

2. Ku¨bler, D.: On the regulation of social norms . Journal of Law, Economics and Organization 17 ( 2 ), 449 - 76 ( 2001 )

3. Miles , S. , Groth , P. , Munroe , S. , Jiang , S. , Assandri , T. , Moreau , L. : Extracting causal graphs from an open provenance data model . Concurrency and Computation: Practice and Experience 20 ( 5 ), 577 - 586 ( 2008 )

4. Moreau , L. : The foundations for provenance on the web . Foundations and Trends in Web Science 2 ( 2-3 ), 99 - 241 ( November 2010 )

5. Ostrom , E.: Governing the Commons: The Evolution of Institutions for Collective Action (Political Economy of Institutions and Decisions) . Cambridge University Press ( Nov 1990 )

6. Villatoro , D. : Social norms for self-policing multi-agent systems and virtual societies . Ph.D. Thesis ( 2011 )

7. Wasserman , S. , Faust , K. : Social Network Analysis: Methods and Applications . No. 8 in Structural analysis in the social sciences , Cambridge University Press, 1 edn . ( 1994 )