Multiagent Organizations - Multiagent Systems, MIT Press, 2013
Multiagent OrganizationsChapter 2 in G. Weiss (Ed.), Multiagent Systems, MIT Press,2nd edition, 2012Virginia Dignum and Julian PadgetMay 7, 2012
ContentsIntroductionMultiagent OrganizationsInstitutionsAgents in OrganizationsEvolution of Organizations
ContentIntroductionMultiagent OrganizationsInstitutionsAgents in OrganizationsEvolution of Organizations
Definitions of OrganizationIIIIIAn organization is a group of people working together withone or more shared goals.An instrument of purpose, that is, seen as coordinated byintentions and goals.A social system existing in physical and social environmentsover time.An arrangement of relationships between components orindividuals which produces a unit, or system, endowed withqualities not apprehended at the level of the components orindividuals.[Morin, 1977]An arrangement of relationships between components orindividuals which produces a unit, or system, endowed withqualities not apprehended at the level of the components orindividuals.[Olmstead, 2002]
Need for OrganizationIDo agents need organizations?IIDo agents need to know/reason about the organization?Do MAS need organizations?IIIInteraction in MAS cannot be based in communication aloneMAS engineering require high-level agent independentabstractionsNeed for explicit social concepts defining the society whereagents live
Characteristics of Complex OrganizationsIIOperate in a changing environmentDistributed activityIIILocal management, knowledge and dataIndividual interests and operationGlobal strategyIIProcess integrationCulture integrationIGlobal goals vs. individual goalsIBalance control and independence
Relevance (1)IFrom the agents perspective, organizations:IIIInsure a better integration of the agents in the systemin order to better adapt themselves to changeDelegation of tasks/beliefs between the agentsIIThat is, (organizational) structures that need to berepresented or exploitedsuch as coalitions, teams, alliances.
Relevance (2)IFrom MAS perspective, organizationsIinsure global behavior at the MAS levelIIIIn terms of cooperation, collaboration, .To be sure that the global goals of the system or collectiveinstance are achievedrepresent observed patterns of interaction
Regulation versus AutonomyIRegulated, or directed, behaviorIPre-determined behavior, external to agent:IIIIleads to lack of agilityDo not consider differences in individual capabilitiesStrict obedience to rules often does not get work doneAutonomous behaviorIIIAbility to make decisions about own activityIndividual rationality is insufficient to deal with social behavior(helpfulness, greater good, )(Informal) structures are necessary for coordinating processesand stability
Regulation and AutonomyICan we have the best of both?ICombination of individual rationality with laws of socialinteraction
Regulation with AutonomyIInternal autonomy requirement: Specify organizationindependently from the internal design of the agentIIIEnables open systemsheterogeneous participationCollaboration autonomy requirement: Specify organizationswithout fixing a priori all structures, interactions and protocolsIIEnables evolving societiesBalances organizational needs and agent autonomy
ContentIntroductionMultiagent OrganizationsInstitutionsAgents in OrganizationsEvolution of Organizations
Components of organizationsIEntities (roles, positions, people, groups, components, )IRelationships (networks, interactions, coordination )IGoals (purpose, intention, shared, )INorms (culture, rules, )IEnvironment (physical, social, open, dynamic, restrictive)
Characteristics of entitiesIThe entities to be organized are heterogeneousIThe entities to be organized are expected to be rational,cognitive[Olmstead, 2002]: “The people in this definition are physicalorganisms and psychological processes [.] [whose] influence isa function of both his or her psychological properties and theproperties of the coordination and decision making rolesassigned to him or her.”
Characteristics of relationshipsIThe organization should create order among entities.IRelationships enable results that cannot be accomplished byany one the individuals alone[Morin, 1977]: “Endowed with qualities not apprehended atthe level of the components or individuals.”IThe organization is responsible for the achievement of theoverall goal of the system.IThe organization should create a coherence of the whole.Possible relations between entities are:IIIIIIIDelegation of tasksTransfer of informationObligation and normsSynchronization of actionsResponsibility between agentsAccess to resources and services
Characteristics of goalsIOrganizational goals are not necessarily goals of any of theindividualsICombined activity is needed to achieve organizational goalsIGlobal strategy but local decision
Characteristics of normsIIDescribe desired organizational statesNorms as ConstraintsIINorms as RegulationsIICannot be violated: guaranteed fulfilmentCan be violated: agent decidesBalance between CONTROL and EFFICIENCY
Characteristics of environmentsIIOrganizations need to perceive, reason, and act in relation tothe surrounding environmentContingent:IIDynamic:IIIImatch among (business) strategy, organizational structure, andthe characteristics of the environment is necessary for highperformanceAgents can migrate, behaviour can evolve.Organizational structures change, disappear or growOrganizational objectives changeOpen:IIDistributed management, knowledge and dataComponents are not controlled by one entity
Ontology
Requirements of Organization ModelsIReflect and Support Organizational DesignIIISpecify interaction independently from the internal design ofthe agent (internal autonomy requirement)IIIIIStructure: roles, norms, interactionGlobal goals and requirementsInteraction structures are not completely fixed in advanceEnables open systemsHeterogeneous participationin OperA: separation between agent and roleBalance organizational design and agent autonomy(collaboration autonomy requirement)IIIIIExplicit agreements concerning individual performanceExplicit agreements concerning interactionEnables evolving societiesBalances organizational needs and agent autonomyin OperA: landmarks
Example Organization Model: OperAIOrganizational ModelIIISocial ModelIIIrepresents organizational aims and requirementsroles, interaction structures, scene scripts, normsrepresents agreements concerning participation of individualagents (‘job’ contracts for agents)REA role enacting agentInteraction ModelIrepresents agreements concerning interaction between theagents themselves (‘trade’ contracts between REAs)
Opera developmentdesignagentsorganizationmodeldynamic instantiationsocial modelruntime deploymentinteractionmodel
OperA Organizational ModelISocial StructureIIInteraction StructureIIscene scripts, connections, transitionsNormative StructureIIroles, groups, dependenciesrole, scene and transition normsCommunication StructureIcommunicative acts, domain ontology
Social StructureIRole specificationIdObjectivesSub-objectivesRightsNorms &RulesPC memberpaper reviewed(Paper,Report){read(P), report written(P, Rep),review received(Org, P, Rep)}access confmanagement system(me)PC member OBLIGED understand englishPC member OBLIGED review paper BEFORE deadlineIF paper by colleague THEN PC memberFORBIDDEN review paperTable: PC member role description.
Roles and dependenciesConferencesocietypaper submittedconference organizedorganizerrolepaper reviewedPCmemberroleauthorrolesession organizedsessionchairrolepaper presentedpresenterrole
Interaction StructureIScene specificationSceneRolesResultsInteraction PatternNorms & RulesReview ProcessProgram-Chair (1), PC-member(2)r1 P Papers: reviews done(P, rev1, rev2)PATTERN(r1 ): see figure ?Program-Chair PERMITTED assign papersIF paper assigned THEN PC memberOBLIGED review paper BEFORE deadlineTable: Script for the Review Process scene.
C2end
Interaction ScenesSend Call forParticipationReviewProcessForm onsConferenceonsiteregistrationendNSend Callfor PapersPaperSubmissionWorkshops
Normative structureIAbstract normsIIIIStatutes, vision and mission of the organizationValues that direct the fulfilling of organization objectivesContextConcrete normsIIIProtocols and Rules : enable agents to comply withorganizational normsConstraints: cannot be violatedRegulations: agent can decide
Communication structureIAbstract levelIGeneric TermsIModel OntologyIIIIIncontextual conceptsconcepts of the framework itselfe.g. norm, rule, role, group, violation, landmarkConcrete levelIIConcrete domain ontologyGeneric communication acts
ContentIntroductionMultiagent OrganizationsInstitutionsAgents in OrganizationsEvolution of Organizations
InstitutionsIInstitutions facilitate and enforce the normative character oforganizationsIDescribe exchange mechanismsISpecify coordination structuresIDetermine interaction and communication forms within theorganizationIConnect organizational and individual perspectivesIMake explicit the social norms governing behaviour, externalto the agents
What is an Institution?IA set of rules:IIIIIIcapable of describing correctand incorrect action,obligations acquired through correct actionand sanctions levied for incorrect actionwhile maintaining a record through its internal state.An institution is a set of rules that interprets some but notnecessarily all of an agent’s actions as correct or incorrectwithin that context: the norm-regulated RONMENT
Origins of InstitutionsIEconomics [North, 1991]“the rules of the game in a society, or more formally, thehumanly devised constraints that shape social interaction.”ISocial science [Harré and Secord, 1972]“that part of the act-action structure produced by the subsetof the rules followed by a particular category of individual.”“Role is a normative concept, focusing on what is proper for aperson in a particular category to do”Ialso [Ostrom, 1990]“the prescriptions that humans use to organize all forms ofrepetitive and structured interaction. at all scales”“individuals. face choices regarding the actions andstrategies they take, leading to consequences for themselvesand for others.”
OrganizationsIOrganizations derive from [Mintzberg, 1993]:IIIIOrganizational structure,management andbusinessContend that: institutions underpin organizationsInstitution An established law, custom, usage,practice, organization, or other element in thepolitical or social life of a people; a regulativeprinciple or convention subservient to the needs ofan organized community or the general ends ofcivilization.[Oxford English Dictionary, WWW]
Institutions, norms and organizationsIInstitutional rules are called normsIA norms is an informal or formal constraint on actionNorm A standard or pattern of social behaviourthat is accepted in or expected of agroup.[Oxford English Dictionary, WWW]characterizeNORMSestablishchosen byINSTITUTIONS[a set of rules](partial)groundingsynthesize ORGANIZATIONS agents goal(s)/state(s) performance role(s)/action(s) membershipclone
An informal modelTo satisfy the statement of requirements, that:IIAn institution is a set of rules that interprets some but notnecessarily all of an agent’s actions as correct or incorrectwithin that context: the norm-regulated agent.We identifyIIIIIIA (partially) observable environmentwhere agents actions are events: eithat cause environmental state transitionsbut some events map to institutional events: ej0that cause institutional state transitionsby adding/deleting institutional facts
Conventional generationInterpreting a physical action as an institutional action is calledconventional generation (see speech acts [Searle, 1969], actiontheory [Goldman, 1970] and [Davis, 1984])I NSTITUTIONs01s00f act1f act1f act2f act3e00s0e0s11 e0e0e2E NVIRONMENTe01e00 s02e1s2e2s3e3s4f act1f act3
TracesA simple formalization uses traces to capture sequences of actions:ILet si S denote a state of a system (model)ILet ei E denote an event that affects a system (model)ILet τ : S E 2S , denote a state transformer functionIHence, an actor interacting with a system generates a trace:eee012s0 s1 s2 s3 . . . sn TIAnd induces a corresponding institutional trace:e0e0e0012s00 s10 s20 s30 . . . sm TNow need to define:IHow to express constraints on institutional behaviourIHow to map external actions to institutional actions
Constraints on actionIIOne convenient way is through the combination ofObligation, whereIIIPermission, thatIIIan actor must take actions resulting in a particular institutionalstate that satisfies the obligationsuch as a reviewer submitting a review by the end of thereview periodindicates whether some action is permitted for some actor inthe current state of the institutionsuch as the program committee chair closing submission ofpapersPower, thatIIindicates whether some action by some actor has an effect onthe institutional state [Jones and Sergot, 1996]such as only the program chair being able to extend the papersubmission deadline
Event mapping and state changingISome external events are related to institutional events:ei ej0IDefined by the generation relation GIThe institutional state is a set of facts: FWhen there is an institutional event:IIIadd facts to, ordelete facts fromthe institutional stateIDefined by the consequence relation CIHence, the institutional state transformer function:τ : S E 2Smay be realized by C TC(G), where TC denotes thetransitive closure
A formal modelNormative systemEvents, comprising exogenous,(normative) actions and(normative) violationsNormative facts (fluents): power,permission, obligations anddomain-specific factsGeneration relation: maps stateand event to a set of eventsState formula: the set of positiveand negative fluents comprisingthe current normative stateConsequence relation: maps stateand event to a pair (additions,deletions) of sets of fluentsThe initial set of fluentsN : hE, F, G, C, iE Eex Einst withEinst Eact EviolF W P O DG : X E 2EinstX 2F FC : X E 2F 2F whereC (X , e) (C (φ, e), C (φ, e))where C (φ, e) initiates a fluent,and C (φ, e) terminates a fluent
The conference scenarioIEntities: person, paperIRoles: reviewer, chair, authorIProperties: listed author, is in EnglishIExternal events: submit paper, open submission, closesubmission, open review, close reviewIInstitutional events: corresponding to aboveTwo scenarios:IIIopening of submissionreview assignment
Conference scenario: entities, roles and eventsThese are some of the objects that appear inthe model. This is a simple monomorphictype systemtype Person;type (Paper,Person);isInEnglish(Paper);initially eventAssociates a Person with a particular roleAssociates a Person and a PaperUses the above to set up some rolesSome of the events that identify key transitionpoints in the iew(Paper,Person,Review);Some of the actors are identified:IFrank is PC chairIGerhard is a reviewerThese are institutional facts. As is the power and the permissionfrom Frank to declare submission is open.
Conference scenario: submissions opensexogenous eventopenSubmission(Person);inst event iopenSubmission;openSubmission(A) generatesiopenSubmission(A)if isChair(A);iopenSubmission(A) ssion(A));iopenSubmission(A) sion(A)),External event is recognized, generating institutional event, iff A is the PC chair. This ispart of the G relationThe institutional event causes the addition ofsome powers and permissions to the institutional state so that papers can be submittedand submission can be closed. This is part ofthe C relation.and the deletion of powers and permissionsassociated with opening submission. This isalso part of the C relation.ISubmission opens, which adds the facts that Frank ispermitted and empowered to close submissionIAt the same time, the permission and power to opensubmission are deleted: it cannot be done twice
Conference scenario: reviewer assignmentassignReviewer(P,R,A) generatesiassignReviewer(P,R)if isChair(A),isReviewer(R),not listedAuthor(P,R);iassignReviewer(P,R) (P,R,Report));IIThe institutional event is only generated if theprincipal is the PC chair, if R is on the PCand not an author of the paper.The assignment establishes an obligation forreviewer R to deliver the review by the closeof the review period, or the violation eventbadRev occurs.Review delivery now permitted and empoweredA reviewer can be assigned to a paper, as long as the roles arecorrect and the reviewer is not listed as an author on the paperThe corresponding institutional event addsIIAn obligation on the reviewer to produce a review by the endof the review periodThe permission and the power for the reviewer to send a review
A possible traceIdentified events are:IPerson: virginia registers Paper: paper01IPerson: virginia uploads Paper: paper01IPerson: frank closes submissionIPerson: frank assigns reviewer Paper: paper01, Person:gerhardIPerson: gerhard sends review Paper: paper01These events cause changes in the institutional state (next slide):IThe addition and deletion of various powers and permissionsIThe creation of obligations at ik and im
Conference scenario traceij 1registerPaper(paper01, virginia)iregisterP aper(paper01, virginia)ijsubmitPaper(paper01, virginia)isubmitP aper(paper01, virginia)isChair(f ubmission(f or(paper01, virginia)listedAuthor(paper01, julian)perm(sendPaper(virginia))perm(sendP aper(julian))pow(sendPaper(virginia))pow(sendP n(f rank)ilassignReviewer(paper01, gerhard, frank)iassignReviewer(paper01, gerhard)isChair(f (julian)listedAuthor(paper01, virginia)listedAuthor(paper01, ir(f ubmission(f or(paper01, virginia)listedAuthor(paper01, julian)perm(sendP aper(virginia))perm(sendP aper(julian))pow(sendP aper(virginia))pow(sendP aper(julian))isInEnglish(paper01)obl(notif y(virginia),icloseSubmission,badChair)obl(notif er01, gerhard, review02)isendReview(paper01, gerhard, review02)isChair(f (julian)listedAuthor(paper01, virginia)listedAuthor(paper01, julian)reviewOpenperm(icloseReview(f rank))pow(icloseReview(f rank))obl(isendReview(paper01, gerhard, Review),icloseReview,badRev)ikim 1
Multiple InstitutionsIA single institution can capture the full normative behaviour,but a monolithic structure may be undesirable:IISingle institutions with a limited range of interaction can beanalysed and re-used more easily — institution librariesInstitutions are situated in a social and legal framework withwhose norms they must interoperate, so institutional workflowsare unavoidableIInstitutional composition is a different process in which asingle internally consistent institution is synthesized fromseveral institutional specifications.IA multi-i
Chapter 2 in G. Weiss (Ed.), Multiagent Systems, MIT Press, 2nd edition, 2012 Virginia Dignum and Julian Padget May 7, 2012. Contents Introduction Multiagent Organizations Institutions Agents in Organizations Evolution of Organizations. Content Introduction Multiagent Organizations Institutions Agents in Organizations
of multiagent systems, multiagent principles which are used in the optimization method, and the previous multiagent approaches in engineering design and optimization. Multiagent learning Multiagent systems are systems in which multiple agents autono-mously interact with each other and the environment (Stone and Veloso, 2000; Weiss, 2013).
2 Multiagent Organizations 51 Virginia Dignum and Julian Padget 1 Introduction 51 2 Background 53 2.1 From Intelligent Agents to Multiagent Systems 53 2.2 From Multiagent Systems to Multiagent Organizations . . 55 2.3 Sources of Inspiration 56 2.3.1 Organization as Structure 56 2.3.2 Organization as Institution 58 2.3.3 Organization as Agent 59
works on multiagent learning systems can be found in the literature—see, for example, the surveys works of [6,39]. However, most multiagent RL research focuses on problems in which the state-space is typically finite and not too large,1 and only a few works on multiagent learning address prob-lems with very large/infinite state-spaces.
Outline 1 Multiagent Problems in General 2 Dynamic Programming Formulation 3 Agent-by-Agent Policy Improvement 4 Approximate Policy Iteration - Use of Value and/or Policy Networks 5 Autonomous Multiagent Rollout with Signaling Policies 6 Multirobot Repair - A Large-Scale Multiagent POMDP Problem Bertsekas Reinforcement Learning 3 / 29
We first discuss multiagent POMDPs and previous work on Monte Carlo tree search and Bayesian reinforcement learning (BRL) for POMDPs. 2.1 Multiagent POMDPs An MPOMDP (Messias, Spaan, and Lima, 2011) is a multiagent planning model that unfolds over a number of steps. At every stage, agents take individual actions and receive individual .
Multiagent Systems B. Nebel, C. Becker-Asano, S. Wöl General information Agents (once again) Abstract Architectures for Agents Summary General information Recommended reading: Wooldridge, An Introduction to MultiAgent Systems - Second Edition, Wiley & Sons, 2009. Russell & Norvig, Arti cial Intelligence: A Modern Approach, third edition .
Multiagent Systems I Prof. Dr. Jürgen Dix Department of Informatics Clausthal University of Technology SS 2012 Prof. Dr. Jürgen Dix Department of Informatics, TUC Multiagent Systems I, SS 2012 1
The American Revolution, 1763-1783 By Pauline Maier This essay excerpt is provided courtesy of the Gilder Lehrman Institute of American History. INDEPENDENCE The Seven Years’ War had left Great Britain with a huge debt by the standards of the day. Moreover, thanks in part to Pontiac’s Rebellion, a massive American Indian uprising in the territories won from France, the British decided to .
