Lorentz Center - MAO - Multi-Agent Organisation from 19 Dec 2011 through 23 Dec 2011
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    MAO - Multi-Agent Organisation
    from 19 Dec 2011 through 23 Dec 2011




Wil van der Aalst

Process Mining Manifesto                                                                             


The growing interest in log-based process analysis motivated the establishment of the IEEE Task Force on Process Mining. The goal of this task force is to promote the research, development, education, and understanding of process mining. Members of the task force include representatives of more than a dozen commercial software vendors (e.g., Pallas Athena, Software AG, Futura Process Intelligence, HP, IBM, Fujitsu, Infosys, and Fluxicon), ten consultancy firms (e.g., Gartner and Deloitte) and over twenty universities. The task force recently released a manifesto describing guiding principles and challenges. Process mining aims to discover, monitor and improve real processes by extracting knowledge from event logs readily available in today's information systems. The manifesto aims to increase the visibility of process mining as a new tool to improve the (re)design, control, and support of operational business processes. It is intended to guide software developers, scientists, consultants, and end-users. In his talk prof. Wil van der Aalst will introduce process mining as an enabling technology for analyzing the behavior of agents.



Farhad Arbab
Exogenous Coordination of Multi-Agent Organizations

For a multi-agent system to act as an organization, the rules and the structures that characterize that organization need to be identified and incorporated within the mechanism that coordinates the interaction of the agents in that system.  The traditional mechanisms used in multi-agent systems for their coordination rely on direct communication actions performed by individual agents.  Expressing coordination protocols as collections of direct communication actions embedded within a set of agents reflects an endogenous model of coordination and interaction that obfuscates the organization rules and structures that give rise to these protocols.  In this talk, we describe an exogenous coordination language, called Reo, based on an alternative model of concurrency wherein interaction, as opposed to action, is the only first-class concept.

We show how exogenous coordination in Reo allows specification of coordination protocols as explicit, concrete, tangible (software) constructs that can be specified, verified, composed, and reused, independently of the actors that they may engage.  Formally represented as relational constraints on the actions of the agents in an organization, Reo coordination protocols represent a crisp, explicit incarnation of the rules and the structures that characterize an organization.


Matteo Baldoni

An Interaction-oriented Framework for Social Computing


We propose an interaction-oriented framework and the related support infrastructure, that reifies commitment-based interaction protocols into programmable environments and artifacts. The use of commitments gives a normative characterization to coordination artifacts, while the use of artifacts enables the application of software engineering methodologies to protocols.



Nils Bulling

Verifying Normative Behaviour via Normative Mechanism Design

(joint work with Mehdi Dastani)


The environment is an essential component of multi-agent systems and is often used to coordinate the behaviour of individual agents. Recently many languages have been proposed to specify and implement multi-agent environments in terms of social and normative concepts. In this talk, we first introduce a formal setting of multi-agent environment which abstracts from concrete specification languages. We extend this formal setting with norms and sanctions and show how concepts from mechanism design can be used to formally analyse and verify whether specific normative behaviours can be enforced (or implemented) if agents follow their subjective preferences.

We also consider complexity issues of associated problems.



Marc Esteva
Electronic Institutions

Electronic institutions define the rules of the game in agent societies, by fixing what agents
are permitted and forbidden to do and under what circumstances. In this talk I will present first
the notion of electronic institutions and its different components. Later on, I will briefly present
the Electronic Institutions Development Environment, giving special attention to their
execution. Finally, I will present recent work on opening electronic institutions to humans
by means of connecting them to virtual worlds.


Davide Grossi

A note on procedural rules in argument games


In my talk I will look at abstract argument games as a source of interesting intuitions concerning the notion of procedural rule.

I will be concerned, in particular, with the problem of the rationale or justification of procedural rules as appropriate means to achieve a given end---in the case of argument games, the end being the adequacy with respect to a given Dung semantics. I will report on some of my recent work on the topic, and point at a number of research directions. 



Paul Harrenstein
Pareto Optimality in Coalition Formation
(Joint work with Haris Aziz and Felix Brand)


A minimal requirement on allocative efficiency in the social sciences is Pareto optimality. In this paper, we identify a far-reaching structural connection between Pareto optimality and perfection that has various algorithmic consequences for coalition formation. Based on this insight, we formulate the Preference Refinement Algorithm (PRA) which computes an individually rational and Pareto optimal outcome in hedonic coalition formation games or any other discrete allocation setting. Our approach also leads to various results for specific classes of hedonic games. In particular, we show that computing and verifying Pareto optimal partitions in general hedonic games, anonymous games, three-cyclic games, room-roommate games and B-hedonic games is intractable while both problems are tractable for roommate games, W-hedonic games, and house allocation with existing tenants.


Andreas Herzig
"A dynamic logic of normative systems"

(joint work with Emiliano Lorini, Frédéric Moisan, Nicolas Troquard)


We propose a logical framework to represent and reason about agent interactions in normative systems. Our starting point is a dynamic logic of propositional assignments. We first show that it embeds Coalition Logic of Propositional Control CL-PC and that various notions of ability and capability can be captured in it. We then extend the logic in order to represent and reason about some important aspects of a theory of institutional action: (1) the distinctions between physical facts and actions and institutional facts and actions; (2) the distinction between causality and ‘counts-as’; (3) the notion of institutional power.

Technically, our contribution consists in extending the dynamic logic of propositional assignments with constructions allowing to express that an agent plays a given role; that a physical action causes another physical action; that a physical action performed by an agent playing a given role counts as an institutional action.



Wojtek Jamroga

Doubtful Deviations and Farsighted Play

(joint work with Matthijs Melissen)


Nash equilibrium is based on the idea that a strategy profile is stable if no player can benefit from a unilateral deviation. We observe that some locally rational deviations in a strategic game may not be profitable anymore if one takes into account the possibility of further deviations by the other players. As a solution, we propose the concept of farsighted pre-equilibrium, which takes into account only deviations that do not lead to a decrease of the player's outcome even if some other deviations follow. While Nash equilibria are assumed to include plays that are certainly rational, our pre-equilibrium is supposed to rule out plays that are _certainly irrational_. We prove that positional strategies are sufficient to define the concept,  we study its computational complexity, and show that pre-equilibria correspond to subgame-perfect Nash equilibria in a meta-game obtained by using the original payoff matrix as arena and the deviations as moves.



Catholijn Jonker

Organisation aware agents: challenges and some first results


Organizational notions such as roles, norms (e.g., obligations and permissions), and services are increasingly viewed as natural concepts to manage the complexity of software development. In particular in the context of multi-agent systems, agents are expected to be organization-aware, i.e., to understand and reason about the structure, work processes, and norms of the agent organization in which they operate. We analyze which kinds of reasoning an agent should be able to do to function in an organization. We categorize these kinds of reasoning with respect to several dimensions and give some examples of the reasoning required.




Brian Logan

Programming Norm-Aware Agents

(joint work with Natasha Alechina and Mehdi Dastani)


We can define a "norm-aware" agent as one that deliberates on its goals, norms and sanctions before deciding which plan to select and execute. Norm-aware agents are able to violate norms (accepting the resulting sanctions) if it is in their overall interests to do so, e.g., if meeting an obligation would result in an important goal of the agent becoming unachievable. Programming norm-aware agents in conventional BDI-based agent programming languages is difficult, as they lack support for deliberating about goals, norms, sanctions and deadlines. In this talk, I will sketch the norm-aware agent programming language N-2APL. N-2APL is based on 2APL and provides support for beliefs, goals, plans, norms, sanctions and deadlines. I will describe how the syntax and  semantics of 2APL were modified to support norm-awareness, and show that N-2APL agents are rational in the sense of committing to a set of plans that will achieve the agent's most important goals and obligations by their deadlines while respecting its most important prohibitions.



Emiliano Lorini

A simple logic for reasoning about institutional actions


We propose a logical framework to represent and reason about some important aspects of a theory of institutional action:
(1) the distinctions between physical facts and actions and institutional facts and actions;
(2) the distinction between causality and ‘counts-as’; (3) the notion of institutional power.
Technically, our contribution consists in extending a dynamic logic of propositional assignments with constructions allowing to express that an agent plays a given role;
that a physical action causes another physical action; that a physical action performed by an agent playing a given role counts as an institutional action.
We show how the logic can be easily extended in order to deal with the strategic aspects of interaction in institutional contexts.


Pablo Noriega

On Co-incidence


Ubiquity, or at least being active in more than one place at a time, is not unusual in conventional social interactions. Contracting within a supply network, trading in investment banking or managing an archaeological  expedition are typical situations where several individuals are involved in simultaneous activities that involve different participants and may have causal and temporal interdependencies. In spite of their natural abundance and their inherent technical interest, such situations have not been thoroughly studied in the context of MAO. In this talk I will explore a notion of "co-incidence" in open multiagent systems. I will first propose a characterization of the notion of activity and then discuss how activities may be interrelated as well as how an agent may be active in more than one activity. Based on those elements I will present a conceptual model to specify and implement MAS with co-incident activities.



Timothy Norman

Goal-Directed Conflict Resolution and Policy Refinement


A norm (or policy) can be defined as a guideline stating what is allowed, what is forbidden and what is obligated for an entity in some situation so that an acceptable outcome is achieved. Policies occur in many contexts, whether they are loose social networks of individuals or highly structured institutions. For example, the NHS (UK National Health Service) state in their Care Record Guarantee that the "NHS is prohibited from sharing any information that identifies the patient for any reason other than providing care". Such a policy provides a high-level guarantee of information privacy to patients, but it is not necessarily clear how this maps to specific clinical care or clinical research protocols. Furthermore, it is a significant challenge for policy authors to specify consistent and coherent policies for systems to support information management and auditing. A thorough understanding of the meanings and implications of policies is important for their effective implementation. Significant effort has been invested in exploring algorithms for evaluating sets of norms or policies for logical consistency. This is, however, only a partial solution. Consistency and coherence evaluation of policies must be context (or more specifically goal) dependent. The authoring and analysis of policies for an institution must focus on both logical and functional conflicts with respect to the goals of the institution. We are exploring reasoning mechanisms to support the authoring an refinement of OWL-POLAR policies within the context of the dot.rural Digital Economy research project, and investigating their application to clinical care information management for the support of patients in rural areas.





Julian Padget
Normative Frameworks: institution and agent perspectives







Jeremy Pitt
The Formal Characterisation of Socio-Economic Principles for Self-Organising Electronic Institutions

We address the problem of deciding resource allocation policies in open embedded systems,
whereby the system components have to form an opportunistic alliance and collectively
agree a policy to distribute resources, that is 'fair', 'robust' and congruent with the state of the
environment This problem  arises in a number of systems and applications, including sensor
networks, cloud computing, and infrastructure management for water, energy, and transport,
We begin by presenting a methodology for the formal characterisation and operationalisation
of social science theories in a computationally tractable framework. We apply the methodology
to Ostrom's socio-economic principles for self-governing institutions, demonstrating how the institutional rules be represented in a framework for specifying dynamic norm-governed systems. We show how six out of eight of Ostrom's principles can be given a formal characterisation through an axiomatisation in the Event Calculus, an action language from artificial intelligence used for representing and reasoning about agency, action and change. We describe the implementation of a testbed and the results of experiments which show whether that these principles are necessary and sufficient
conditions for enduring electronic institutions.



Antonino Rotolo

Arguing about Legal Concepts and Norm Applicability using Theory Revision and Inferences to the Best Theory


This paper moves from the assumption that legal concepts can be fruitfully represented as logical theories of constitutive rules. The interpretation of legal concepts can thus be viewed as a process where we (a) aggregate theories corresponding to the legal and ordinary understandings of concepts, and (b) revise these theories in order to align concepts with the goals of regulative legal rules. The combination of the above two procedures raises the crucial question of how to choose among many possible revision outcomes. This problem can take the form of a dialectical process where the players exchange arguments and counter-arguments to establish which is the best theory. Some criteria are briefly discussed in this regard, such as theory inclusiveness, teleological coherence, simplicity, minimal change, and theory connectedness.


Giovanni Sartor

Compliance with normative systems


I will argue that the cognitive attitudes and operations involved in compliance

with normative systems are usually different from those involved in complying

with isolated social norms. While isolated norms must be stored in the memory of

the agents endorsing them, this does not happen with regard to large normative systems.

In the latter case, the agent adopts a general policy-based intention to comply

with the normative system as a whole, an intention that provides an abstract motivation

for specific acts of compliance, once the agent has established that these

acts are obligatory according the system. I will show how the endorsement of such

a policy can be based on different individual attitudes, ranging from self-interest to

altruistic, social or moral motivations. Finally, I will analyse how a normative system

may both constrain powers and extend them, relying on this abstract motivation

of its addressees.


Marek Sergot

Norms, action and agency


This will be an overview of a `logic of unwitting collective agency', a language combining a transition based account of action with a logic of 'brings it about' or 'sees to it that' expressions. I call it 'unwitting agency' because it makes no attempt to capture deliberative or purposeful action. I want to make no assumptions at all about the reasoning or perceptual capabilities of the agents---they can be human, or computer agents, or simple reactive devices. Actions might be deliberative but could also be unwitting: 'unwitting' can mean both inadvertent and unaware. Somewhat surprisingly perhaps, the logic does bear a strong resemblance to Ingmar P\"orn's (1977) logic of `brings it about' and to `stit' logics, though there are also some important conceptual and technical differences. The account generalises naturally to talking about the collective actions of groups of agents: several different forms of (unwitting) collective agency can be identified. The talk will concentrate on presenting some examples rather than technical details of the language. I will discuss how some illustrative examples can be represented and analysed. On a related but different point, I would also like to make some general remarks about the idea of using norms or `social laws' as a means of coordinating agent interactions in multi-agent systems.




Wamberto Vasconcelos

On group norms


We consider the representation and processing of group norms – these norms address groups of individuals, affecting their joint behaviours. Groups norms arise in many situations;, e.g., an obligation on the sales team to meet once a week, a prohibition on gatherings of more than N people, or a permission for a group visit to a building. We provide a taxonomy of group norms, propose means to represent these, and provide semantics for norm fulfilment and violation. Additionally, we explore mechanisms for agents processing group norms, namely, how agents become aware of group norms, and how their individual behaviours can factor these in (e.g., for joint action/coordination). Finally, we sketch how our representation of group norms formally connects with an organisation algebra, showing how creation and changes affect and are affected by group norms.