Sequential Optimality and Coordination in Multiagent Systems

1 Introduction

The problem of coordination in multiagent systems (MASs) is of crucial importance in AI and game theory. Given a col­ lection of agents charged with the achievement of various ob­ jectives, often the optimal course of action for one agent de­ pends on that selected by another. If the agents fail to coordi­ nate the outcome could be disastrous. Consider, for instance, two agents that each want to cross a bridge that can support the weight of only one of them. If they both start to cross, the bridge will collapse; coordination requires that they each "agree" which one of them should go first.

Coordination problems often arise in fully cooperative MASs, in which each agent shares the same utility function or common interests. This type of system is appropriate for modeling a team of agents acting on behalf of a single indi­ vidual (each tries to maximize that individual's utility). In the bridge example above, it may be that neither agent cares whether it crosses first, so long as they both cross and pur­ sue their objectives. In such a setting, coordination problems generally arise in situations where there is some flexibility regarding the "roles" into which agents fall. If the abilities of the agents are such that it makes little difference if agent al pursues objective ol and a2 pursues o2, or vice versa, the agents run the risk of both pursuing the same objective-with consequences ranging from simple delay in goal achievement to more drastic outcomes-unless they coordinate. This is­ sue arises in many team activities ranging from logistics plan­ ning to robotic soccer.

Unfortunately, none of these approaches explicitly con­ siders the impact of coordination problems in the context of larger sequential decision problems. If the agents run the risk of miscoordination at a certain state in a decision problem, how should this impact their policy decisions at other states? Specifically, what is the long-term (or sequential) value of be­ ing in a state at which coordination is a potential problem? Such a valuation is needed in order for agents to make ratio­ nal decisions about whether to even put themselves in the po­ sition to face a coordination problem.

Unfortunately, there are no clear-cut definitions of sequen­ tial optimality for multiagent sequential decision processes in the general case. Most theoretical work on coordina­ tion problems assumes that a simple repeated game is be­ ing played and studies methods for attaining equilibrium in the stage game. In this paper, we argue that optimal sequen­ tial decision making requires that agents be able to reason about the specific coordination mechanisms they adopt to resolve coordination problems. With this ability, they can make optimal decisions by considering the tradeoffs involv­ ing probability of (eventual) coordination, the consequences of miscoordination, the benefits of coordination, the alter­ native courses of action available, and so on. We develop a dynamic programming algorithm for computing optimal policies that accounts not only for the underlying system state, but also the state of the coordination mechanism be­ ing adopted. Specifically, we show how the underlying state space can be expanded minimally and dynamically to ac­ count for specific coordination protocol being used.

With this definition of state value given a coordination mechanism, one can tackle the problem of defining good co­ ordination mechanisms for specific decision problems that offer good expected value (we but will make a few remarks near the end of the paper on this point). Our framework there­ fore provides a useful tool for the design of conventional, communication and learning protocols [15].

We focus on fully cooperative MASs, assuming that a common coordination mechanism can be put in place, and that agents have no reason to deliberate strategically. How­ ever, we expect most of our conclusions to apply mutatis mu­ tandis to more general settings. We introduce Markov deci­ sion processes (MOPs) and multiagent MDPs (MMDPs) in Section 2. We define coordination problems and discuss sev­ eral coordination mechanisms in Section 3. In Section 4 we describe the impact of coordination problems on sequential optimality criteria, show how to expand the state space of the MMDP to reason about the state of the specific mechanisms or protocols used by the agents to coordinate, and develop a version of value iteration that incorporates such consider­ ations. We illustrate the ability of generalization techniques to enhance the power of coordination protocols in Section 5, and conclude with some remarks on future research direc­ tions in Section 6.

2 Multiagent MDPs

2.1 Markov Decision Processes

We begin by presenting standard (single-agent) Markov deci­ sion processes (MOPs) and describe their multiagent exten­ sions below (see [3, 13] for further details on MOPs). A fully observable MOP M = (S, A, Pr , R) comprises the follow­ ing components. S is a finite set of states of the system be­ ing controlled. The agent has a finite set of actions A with which to influence the system state. Dynamics are given by Pr : S x A x S --+ [0, 1]; here Pr(s; , a, Sj) denotes the probability that action a, when executed at states;, induces a transition to Sj. R : S --+ 3i is a real-valued, bounded reward function. The process is fully observable: though agents can­ not predict with certainty the state that will be reached when an action is taken, they can observe the state precisely once it is reached.

An agent finding itself in state st at timet must choose an action at. The expected value of a course of action rr depends on the specific objectives. A finite horizon decision problem with horizon T measures the value of rr as E('L,~=O R(st) lrr) (where expectation is taken w.r.t. Pr ). A discounted, infinite horizon problem measures value as E('L::o (Jt R(st)lrr). Here 0 ~ (3 < 1 is a discount factor that ensures the infi­ nite sum is bounded.

For a finite horizon problem with horizon T, a nonstation­ ary policy rr : S x { 1, · · · , T} --+ A associates with each state s and stage-to-got ~ Tan action rr( s, t) to be executed at s with t stages remaining. An optimal nonstationary policy is one with maximum expected value at each state-stage pair. A stationary policy rr : S --+ A for an infinite horizon problem associates actions rr( s) with states alone.

A simple algorithm for constructing optimal policies (in both the finite and infinite horizon cases) is value iteration [13]. Define the t-stage-to-go value function Vt by setting

For a finite horizon problem with horizon T, we set (3 = 1 (no discounting) and during these calculations set rr( s;, t) to the action a maximizing the right-hand term, terminating the it­ eration at t = T. For infinite horizon problems, the sequence of value functions vt produced by value iteration converges to the optimal value function v·. For some finite t, the ac­ tions a that maximize the right-hand side of Equation I form an optimal policy, and vt approximates its value.

2.2 The Multiagent Extension

We now assume that a collection of agents is controlling the process. The individual actions of agents interact in that the effect of one agent's actions may depend on the actions taken by others. We take the agents to be acting on behalf of some individual; therefore, each has the same utility or reward function R. The system is fully observable to each agent.

We model this formally as a multiagent Markov deci­ sion process (MMDP). MMDPs are much like MOPs with the exception that actions (and possibly decisions) are "dis­ tributed" among multiple agents. An MMDP M (a, {A;};Ea, S, Pr , R) consists of five components. The set a is a finite collection of n agents, with each agent i E a having at its disposal a finite set A; of individual actions. An element (a 1 , · · · , an) of the joint action space, A = x A;, represents the concurrent execution of the actions a; by each agent i . The components S, Pr and Rare as in an MOP, ex­ cept that Pr now refers to joint actions (a1 , ···,an)·

Taking the joint action space to be the set of basic ac­ tions, an MMDP can be viewed as a standard (single-agent) MOP. Specifically, since there is a single reward function, the agents do not have competing interests; so any course of action is equally good (or bad) for all. We define opti­ mal joint policies to be optimal policies over the joint action space: these can be computed by solving the (standard) MOP (A, S, Pr, R) using an algorithm like value iteration.

Example An example MMDP is illustrated in Figure I. The MMDP consists of two agents a 1 and a2, each with two ac­ tions a and b that can be performed at any of the six states. All transitions are deterministic and are labeled by the joint actions that induce that transition. The joint action (a, b) refers to a1 performing a and a2 performing b, and others similarly (with * referring to any action taken by the cor­ responding agent). At the "source" state 8 1 , a1 alone de­ cides whether the system moves to 82 (using a) or 83 (us­ ing b). At 83 , the agents are guaranteed a move to 86 and a reward of 5 no matter what joint action is executed. At 82 both agents must choose action a or both must choose bin order to move to 84 and gain a reward of 10; choosing opposite actions results in a transition to 85 and a reward of -10. The set of optimal joint policies are those where a1 chooses a at 8 1 (a2 can choose a or b), and al and a2 choose either (a , a) or (b, b) at 82 .

The value function determined by solving the MMDP for the optimal joint policy is the optimal joint value function and is denoted V. In the example above, an infinite horizon prob­ lem with a discount rate of 0.9 has V(8!) = 29.9, while for a finite horizon problem, V 1 ( 81) is given by 10 l £¥ J.

MMDPs, while a natural extension of MDPs to cooper­ ative multiagent settings, can also be viewed as a type of stochastic game as formulated by Shapley [14] . Stochastic games were originally formulated for zero-sum games only (and as we will see, the zero-sum assumption alleviates cer­ tain difficulties), whereas we focus on the (equally special) case of cooperative games.

3 Coordination Problems and Coordination Mechanisms

The example MMDP above has an obvious optimal joint pol­ icy. Unfortunately, if agents a1 and a2 make their decisions independently, this policy may not be implementable. There are two optimal joint action choices at 82 : (a , a) and (b , b). If, say, a1 decides to implement the former and a2 the latter, the resulting joint action (a , b) is far from optimal. This is a classic coordination problem: there is more than one optimal joint action from which to choose, but the optimal choices of at least two agents are mutually dependent (we define this formally below). Notice that the uncertainty about how the agents will "play 8 2" makes a1 's decision at 8 1 rather diffi­ cult: without having a good prediction of the expected value at 82, agent al is unable to determine the relative values of performing a orb at 8 1 (more in this in Section 4).

In the absence of a central controller that selects a single joint policy to be provided to each agent, ensuring coordi­ nated action choice among independent decision makers re­ quires some coordination mechanism. Such a mechanism re­ stricts an agent's choices among the potentially individually optimal actions, perhaps based on the agent's history. We de­ scribe some of these below, including learning, conventional and communication techniques.

In the remainder of this section, we focus on repeated games, returning to general MMDPs in the next section. An identical-interest repeated game can be viewed as an MMDP with only one state-joint actions are played at that state re­ peatedly. An immediate reward R( a) is associated with each joint action. Our aim is to have the individual actions selected by each agent constitute an optimal joint action. Formally, a stage game G comprises action sets A; for each agent i , joint action space A, and reward function R. The stage game is played repeatedly.

Definition Joint action a E A is optimal in stage game G if R(a) 2: R(a') for all a' E A. Action a; E A; is poten­ tially individually optimal (PIO) for agent i if some opti­ mal joint action contains a;. We denote by P/0; the set of such actions for agent i.

Definition Stage game G = (o: , {A;};E,, R) induces a co­ ordination problem (CP) iff there exist actions a; E P/0; , 1 :S i :S n, such that (a1 , ···,an) is not optimal.

Intuitively, a CP arises if there is a chance that each agent se­ lects a PIO-action, yet the resulting joint action is suboptimal.

CPs in repeated games can often be "reduced" by eliminat­ ing certain PIO-actions due to considerations such as domi­ nance, risk (e.g., see the notions of risk-dominance and trac­ ing used by Harsanyi and Selten to select equilibria [7]), or focusing on certain PIO-actions due to certain asymmetries. These reductions, if embodied in protocols commonly known by all agents, can limit choices making the CP "smaller" (thus potentially more easily solved), and sometimes result in a single "obvious" action for each agent. We do not con­ sider such reductions here, but these can easily be incorpo­ rated into the model presented below.

A coordination mechanism is a protocol by which agents restrict their attention to a subset of their PIO-actions in a CP. A mechanism has a state, which summarizes relevant aspects of the agent's history and a decision rule for selecting actions as a function of the mechanism state. While such rules often select actions (perhaps randomly) from among PIO-actions, there are circumstances where non-PIO-actions may be se­ lected (e.g., if the consequences of uncoordinated action are severe). Mechanisms may guarantee immediate coordina­ tion, eventual coordination, or provide no such assurances. To illustrate, we list some simple (and commonly used) co­ ordination methods below. In Section 4, we will focus pri­ marily on randomization techniques with learning. However, communication and conventional methods can be understood within the framework developed below as well .

Randomization with Learning This is a learning mecha­ nism requiring that agents select a PIO-action randomly un­ til coordination is achieved (i .e., an optimal joint action is selected by the group). At that point, the agents play that optimal joint action forever. We assume that actions are se­ lected according to a uniform distribution. 1 The mechanism has k + 1 states, where k is the number of optimal joint ac­ tions: k states each denote coordination on one of the opti­ mal actions, and one denotes lack of coordination. The state changes from the uncoordinated state to a coordinated state as soon as an optimal action is played. This requires that agents be able to observe actions or action outcomes.

We can model this protocol as a finite-state machine (FSM). The FSM for the CP at 82 in Figure 1 is illustrated in Figure 2. When the agents are uncoordinated (state U), they each choose action a and b randomly. If the observed joint action is not coordinated, the remain in state U; but if they coordinate, they move to the appropriate state (A or B) and stay there (executing the corresponding action).

1 In this and other mechanisms, reduction methods can be used to reduce the number of actions considered by each agent.

For many problems, we can view the mechanism as having only two states: coordinated (C) and uncoordinated (U). If C, we simply require that the agent memorize the action on which the group coordinated. For the purposes of comput­ ing expected value below, we often need only distinguish be­ tween C and U states (without regard to the actual action cho­ sen). We note that randomization works quite well if there is a small group of agents with few actions to choose from; but as these sets grow larger, the probability of transitioning from U to C gets exponentially smaller. Randomization en­ sures eventual coordination, at a rate dictated by the number of agents and number of choices available to them.

Fictitious play (FP) is a related learning technique com­ monly studied in game theory [4, 6] where each agent i ob­ serves the actions played in the past by other agents and plays a best response given the empirical distribution observed. We refer to [6] for details, but note that the state of the mecha­ nism consists of "counts" of th~ PIG-actions played by other agents; thus FP has an infinite number of states. For fully cooperative games, FP converges to an optimal joint action if attention is restricted to PIG-actions and agents randomize over tied best responses [2, 12]. 2 It also has the property that once a coordinated action is played, it is played forever. Un­ like randomization, FP tends to lead to faster coordination as the number of agents and actions increase [2] .

Lexicographic Conventions Conventions or social laws (e.g., driving on the right-hand side of the road) are often used to ensure coordination [9, 15]. Lexicographic conventions can be applied to virtually any CP. Given some commonly­ known total ordering of both agents and individual actions, the set of optimal actions can be totally ordered in several dif­ ferent ways. Lexicographic conventions ensure immediate coordination, but can have substantial overhead due to there­ quirement that each agent have knowledge of these orderings of both agents and actions. This may be reasonable in a fixed setting, but may be harder to ensure over a variety of decision problems (e.g., involving different collections of agents). In contrast, the learning models described above can be viewed as "meta-protocols" that can be embodied in an agent once and applied across multiple decision problems .

2 Hence, it might best be described as a learning technique with randomization, rather than a randomization technique with learning.

Communication Finally, a natural means of ensuring co­ ordination is through some form of communication. For ex­ ample, one agent may convey its intention to perform a spe­ cific PIG-action to another, allowing the other agent to se­ lect a matching PIG-action. There are a number of well­ known difficulties with devising communication and negoti­ ation protocols, involving issues as varied as synchronization and noisy channels. We do not delve into such issues here. We assume that some agreed upon negotiation protocol is in place. Realistically, we must assume that communication has some cost, some risk of failure or misinterpretation, and de­ lays the achievement of goals. As such, we model commu­ nication as actions in an MMDP which have effects not on the underlying system state, but on the "mental state" of the agents involved. Rather abstractly, we can say that the state of a communicative coordination mechanism for an agent i is its estimate of the "mental state" of other agents. For exam­ ple, after negotiation, agent al may believe that a2 is com­ mitted to performing action b. The "mental state" of other agents will generally only be partially observable, and the state of the mechanism will be estimated by each agent.

4 Dynamic Programming with Coordination 4.1 Sequential Optimality and State Value

CPs arise at specific states of the MMDP, but must be con­ sidered in the context of the sequential decision problem as a whole. It is not hard to see that CPs like the one at s2 in Fig­ ure 1 make the joint value function misleading. For example, V 1 (s2 ) = 10 and V 1 (sa) = 5, suggesting that al should take action a at s1 with 2 stages-to-go. But V 1 (s2) assumes that the agents will select an optimal, coordinated joint ac­ tion at s2 · As discussed above, this policy may not be imple­ mentable. Generally, the optimal joint value function V will overestimate the value of states at which coordination is re­ quired, and thus overestimate the value of actions and states that lead to them.

A more realistic estimate V 1 ( s2 ) of this value would ac­ count for the means available for coordination. For instance, if a l~xicographic convention were in place, the agents are assured of optimal action choice, whereas if they randomly choose PIG-actions, they have a 50% chance of acting opti­ mally (with value 10) and a 50% chance of miscoordinating (with value -1 0). Under the randomization protocol , we have V 1 ( s2 ) = 0 and V 1 (sa) = 5, making the optimal decision at s1 , with two stages to go, "opting out of the CP:" al should choose action b and move to sa .

Unfortunately, pursuing this line of reasoning (assuming a randomization mechanism for coordination) will lead the al to always choose bat s1 , no matter how many stages remain. If we categorically assert that V 1 (s2 ) = 0, we must have that vt (sa) > vt ( S2) for any stage t ~ 1. This ignores the fact that the coordination mechanism in question does notre­ quire the agents to randomize at each interaction: once they have coordinated at 82, they can choose the same (optimal) joint action at all future encounters at 82 . Clearly, the V 1 (82 ) depends on the state of the coordination mechanism. If the agents have coordinated in the past, then V 1 ( 82) = 10, since they are assured coordination at this final stage· otherwise 1 , V ( 82) = 0. By the same token, Vt ( 82) depends on the state of the mechanism for arbitrary t 2:: 1, as does the value of other states.

The optimal value function V is not a function of the sys­ tem state alone, but also depends on the state of the mecha­ nism. By expanding the state space of the original MMDP to account for this, we recover the usual value function def­ inition. In this example, we define the expanded MMDP to have states of the form (8, c), where 8 is some system state and c is the state of the randomization mechanism. We use C and U to refer to coordinated and uncoordinated states of the mechanism, respectively (with C standing for either A or B in the FSM of Figure 2). Transitions induced by actions are clear: each action causes a system state transition as in the MMDP, while the coordination state changes from U to Conly if the agents choose action (a, a) or (b, b) at 82 (and never reverts to U). The coordination protocol also restricts the policies the agents are allowed to use at 82 · If they find themselves at (expanded) state (82, U), they must random­ ize over actions a and b. As such, the transition probabilities can be computed easily: (82, U) moves to both (84, C) and (8s , U) with probability 0.5. 3

The expanded MMDP can be viewed a combination of the original MMDP and the partially specified controller shown in Figure 2. The state space of the expanded MMDP is given by _the cross-product of the MMDP and FSM state spaces, while the FSM restricts the choices that can be made when the agents are at state 82 (for each state A, B or U of the FSM). Generally speaking, the protocol restricts action choices at the state where the CP arose, while optimal choices should ~e made ~t all other states. Notice that these choices are op­ timal subject to the constraints imposed by the protocol (or finite-state controller).

With this expanded state space, we can trace value iteration on our running example to illustrate how the agents reason about sequential optimality in a way that accounts for the CP and the coordination mechanism. We assume a finite horizon problem without discounting.

Example For all stages t > 0, obviously Vt(82 , C) > Vt(83, C); so if the agents are in a state of coordination, a1 ~hould choose action a at 81 and "opt in" to the CP by mov­ mg to 82. Matters are more complex if the agents are unco­ ordin_ated. For all stages t < 8, Vt(82 , U) < Vt(83 , U). So With 8 or fewer stages remaining, a1 should choose to "opt out" (choose b) at (81, U). For all stages t > 10, how­ ever, Vt(82, U) > Vt(83, U) (e.g., V 11 (82 , U) = 22.5 while V 11 (83, U) = 20.) 4 Thus, a1 should "opt in" to the CP at (8t, U) if there are 12 or more stages remaining.

. 3 M ore pr_e~isely, (s2, U) transitions to states (s4, A) and (s4, B) wtth probabtlity 0.25 each.

4 The values V 1 (s2, U) and V 1 (s3, U) are equal for8 $ t $ 10.

This example shows how knowledge of the state of the co­ ordination mechanism allows the agents to make informed judgments about the (long term) benefits of coordination, the costs of miscoordination, and the odds of (immediate or eventual) coordination. Because of the cost of miscoordina­ tion (and its 50% chance of occurrence), the agents avoid 82 with fewer than eight stages to go. The safe course of action is deemed correct. However, with eight or more stages re­ maining, they move from ( 8 1 , U) to ( 8 2 , U): the 50% chance of coordination not only provides the agents with a 50% chance at the reward of I 0, but also with a 50% chance at least two more passes through 84 . The long term benefits of coor­ dination (with a sufficient horizon) make the risk worthwhile when compared to the safe alternative.

It is important to note that the state of the coordination mechanism must be taken into account at each (system) state of the MMDP. For instance, though the state of the mecha­ nism can have no influence on what the agents do at state 83 (there is only one "choice"), it is relevant to determining the value of being at state 83 .

In general, reasoning with coordination mechanisms al­ lows one to account for the factors mentioned above. Natu­ rally, the tradeoffs involving long term consequences depend on the decision problem horizon or discount factor. The key factor allowing computation of value in this case is an un­ derstanding of the coordination mechanism used to (stochas­ tically) select joint actions in the presence of multiple equi­ libria, and the ability to associate a value with any state of the MMDP (given the state of the mechanism). Shapley's stochastic games [14] provide a related sequential multiagent decision model with a a well-defined value for game states. This value, however, is a consequence of the zero-sum as­ sumption, which removes the reliance of state value on the selection of a (stage game) equilibrium. In particular, it does not apply to fully cooperative settings where CPs arise.

4.2 Value Iteration with State Expansion

Value iteration can be revised to construct an optimal value function and policy based on any given coordination mecha­ nism. A straightforward version is specified in Figure 3. We discuss several optimizations below.

A list CP of state-game CPs and associated mechanisms i~ kep~ ~ the~ are discovered. A CP exists if the set of op­ tJm~ J_mnt actiOns a~ a state/stage pair (the Q-values in step 3(a)I) mduces a CP m the sense defined earlier. Notice that CPs are defined using the value function vt, not immediate reward. We assume that each CP is associated with a state and the collection of actions involved in the optimal joint ac­ t~ons._Any stat~ 8; with a CP will have the availability of ac­ tions mvolved m the CP restricted by the state of the mech­ a~ism. The set PA( s;) is the set of actions permitted at s; given the mechanism state-this may include randomization actions as well (if 8; has no CP, this set is just A); and agents can only use permitted actions (step 3(a)i). If a CP is discov­ ered among the maximizing (permitted) actions at 8;, a new mechanism Cis introduced and the state is split and replaced by all pairs of states (s;, c) (where cis some state of C).

1. Let V 0 ( ·) = R(· ) for all· E S.
2. Sett=O;S 1 =S 0 =S;CP=0.
3. While t < T do:

(a) For each ·; E s<+l

1. For each a E PA(·;). compute Q'+'(·;, a)= R(·;) + {~ , Pr(·;,a, ·i)V'(·i)} w.;es
2. Let Opt 1 + 1 (·;) be the set of actions with max Q-value
3. If Opt 1 + 1 (·;) inducesanewCP at · ;, introduce mechanism C: (a) add C to CP; (b) replace ·; in S' + 1 with states ( ·; , c) , where c ranges over states of C; (c) Recompute Q'+ 1 ((·;, c) , a) for each new state (according to rules of C); (d) return to step ii. to check for new CPs.
4. Let v·+ 1 (· ; ) = max. Q'+' (·;, a) and 1r 1 + 1 (·;) be any maximizing action (if ·; was split, do this for all ( ·; , c)).
5. (b) t = t + 1; 8 1 + 1 = S x CP.

Figure 3: Value Iteration with State Expansion

To illustrate, suppose the value function vt induces the following choices at s;:

If randomization is used to coordinate on a/ b, expected value is 5 (and the mechanism requires agents to randomize over their PIO-actions). In contrast, the Q-value of (c, c) is better than that of attempting to coordinate, thus the value of s; is defined as 7 if the agents are uncoordinated (and 10 if they are coordinated). Notice that new CPs may be introduced at the same state and the process can be iterated. 5 In this prob­ lem, each states is split into three states: (s, A) (agents have coordinated on joint action (a, a) at s; ), (s, B) (coordinated on (b, b)), and (s , U) (have not coordinated w.r.t. a and b).

If a mechanism has been introduced for the same state and actions at an earlier stage, a new mechanism is not generated. Value (and policy choice) is defined by comparing the value of actions not involved in the CP and the value of behaving according to the rules of the mechanism (step 3(a)iv). At the next iteration all states are split according all mechanisms in­ troduced, since this may be required to predict the value of reaching state s;. If multiple CPs exist, each underlying sys­ tem state is expanded many times in this (naive) algorithm.

Implicit in this discussion is that assumption that the tran­ sitions induced by a coordination protocol over the expanded state space are well defined: this will generally involve ex­ tending the underlying system dynamics by rules involving mechanism state evolution. The mechanism designer must provide such rules (as discussed in Section 3.2).

An important optimization is to have the algorithm only expand states with mechanisms whose state is required to predict value. This can be effected rather easily. If system StateS; transitions tO State Sj, and Sj has been split in St tO in­ volve some mechanism in CP, s; must be split in state st+l. But if s; moves only to states that are unaffected by some (or all) CPs, s; need not be split using the state of those CPs. This allows one to only refer to the state of a mechanism when it is necessary for predicting value: the state space need not be split uniformly.

5 However, the splitting must eventually terminate.

Other optimizations of the algorithm are possible. For ex­ ample, one can "cluster" together states of the coordination mechanism together that provide for the same optimal action and value at a given state. For instance, though FP has an infi­ nite number of distinct states, for any finite number of stages­ to-go, only a finite number of distinction are relevant (much like state abstraction methods used in MDPs and reinforce­ ment learning [1 , 3]). Finally, we note that modeling com­ muncation protocols requires introducing communication ac­ tions, in addition to the state-splitting mechanism above.

4.3 Examples

We describe the results of applying the algorithm to several small test problems in this section. We focus here on the use of the simple randomization mechanism described above.

Testing a finite horizon version of the problem in Figure 1 shows that a single CP exists (at state s2). The state space is eventually expanded so that each state is split into two (re­ ferring to coordination or lack of it at s2). The optimal de­ cision at (s1 , U) is to "opt out" with fewer than eight stages to go and "opt in" with eight or more stages remaining. The infinite horizon version of this problem gives rise to station­ ary policies. When the discount rate f3 = 0.9 (or higher), al "opts in" at (s1, U); but for f3 = 0.85 (or lower), al "opts out" and avoids the CP-because of discounting, the delay in expected payoff of coordination ensures that "opting in" is not worth the cost. With {3 = 0.9, the value of opting in is 17.14 and opting out is 16.54 (assuming the agents act opti­ mally thereafter), while with f3 = 0.85, the value of opting in is 8,62 and opting out is 9.36 (within tolerance 0.001).

A more complex example is illustrated in Figure 4. Two agents have independent tasks. Agent al moves box bland a2 moves b2 to the goal state repeatedly. Once a box is dropped at the goal, a reward is received and a new box ap­ pears in the original location (so the problem is a continuous, infinite horizon MMDP). While the objectives are indepen­ dent, both agents are rewarded with the same constant reward whenever either of their boxes is delivered. The optimal poli­ cies are not independent however. The dark shaded region at the bottom is "risky:" if both agents are in the region, a large (variable) penalty is given. They must coordinate their moves to ensure that no more than one agent is in the risky region at any time. The agents' actions are stochastic: they can move in any (feasible) compass direction but with proba­ bility 0.1 they fail to move (they can also stay in place inten­ tionally). Complicating the problem is the fact that the light shaded region is "sticky:" the agents' moves are more prone to failure (with varying probability). If stickiness is low, the optimal policy is for both agents to traverse the top of the grid repeatedly. But if stickiness is relatively high (or the problem is heavily discounted, making speedy delivery more impor­ tant), one or both agents will want to traverse the risky area, in which case coordination is needed. The problem has 900 nominal states (though a number of these are not reachable) and 25 joint actions.

We give a brief summary of the results in this domain with the following specific parameter settings: a reward of 5 is given for each box delivered; a penalty of -20 is given when­ ever both agents are in the risky area; stickiness (the prob­ ability of not moving) is 0.7 in the sticky region; and f3 = 0.95. With these settings, the optimal joint policy (roughly) requires that one agent move across the top of the grid and one move across the bottom. 6 Generally, if an agent is closer to the top it will move across the top; but if both agents are close (and equally close) to the bottom, they must coordinate (since either could move to the top).

CPs arise at eight states of the MMDP. Thus there are eight coordination mechanisms needed to solve this problem, ex­ panding the state space by a factor of 256 (no distinctions need be made among coordinated choices, so each mecha­ nism has only two states). We focus on two MMDP states where CPs arise and their interaction: 84 ,4 = (h1, h2, 4, 4), where both agents are located at grid cell 4 each holding boxes, and 86 ,6 = (h1 , h2, 6, 6), which is similar, but with both agents at location 6. The optimal joint policy at 84,4 re­ quires one agent to move up (to traverse the sticky region) and the other to move down (to traverse the risky region) on the way to the goal. The optimal policy at 86 ,6 is similar: one agent should move up, the other right. The optimal joint value function has V(84 ,4 ) = 11.54 and V(86 ,6 ) = 11.83.

If the agents have coordinated at all other states where CPs arise, we have the following optimal values for the four states of the expanded MMDP corresponding to each of 84,4 and 86,6 (here we use u4 to denote that the agents have not coor­ dinated at 84,4, and c4 to denote that they have coordinated at 84 ,4; similarly for 86 ,6):

In both states (84 ,4 or 8 6 ,6), if the agents are uncoordinated, the optimal policy requires them to randomize, regardless of the state of the other coordination mechanism. Notice that the values for most of the expanded states where the agents are uncoordinated are less than the corresponding values for the optimal joint policy (which is identical to the expected values at the states where c4c6 holds), as expected. The one exception is at 84 ,4 : when c 4 holds, expected value is iden­ tical whether or not c6 holds, since the optimal policy will never take the agents from 84 ,4 to 86,6 · In contrast, when u4 holds, the status of c6 has a dramatic impact on expected value: if the agents are uncoordinated at 84 ,4 they will ran­ domize and with probability 0.25 both choose to move down (hence to 86,6). Their state of coordination at 86 ,6 is thus im­ portant to predicting expected value. Being uncoordinated at 86,6 has very low value, since randomization has a good chance of moving both agents to the risky area-the risk is worthwhile, however, so randomization is the optimal choice at 86 ,6. 7 Also when the agents are coordinated at 86 ,6 , the sta­ tus of c4 has a rather small effect on value. Because coordi­ nation at 86,6 ensures that one agent takes the "sticky" route to the goal region, the agents get "out of synch" and the odds of them both reaching the pickup location (cell 4) at the same time (within a reasonable time frame) is quite small . Hence, whether or not the agents are coordinated at 84 ,4 has little im­ pact on expected value at 86,6 ·

6 If the penalty is negligible or if the stickiness is even higher, the agents will both tend to move across the bottom, perhaps with one waiting for the other. If the stickiness is negligible, then both agents will traverse the top of the grid.

Randomization is an important aspect of this problem. If the agents were to choose from among their PIO actions inde­ pendently, but deterministically, without reasoning about the consequences of miscoordination, they can end up in cycles that never reach the goal state . .

5 Generalization of Coordination Decisions

One difficulty with the algorithm above is the potential for uninhibited state expansion, and the corresponding compu­ tational cost. In the simple experimental domain with two agents collecting boxes in a grid world, eight CPs occurred across the 900 problem states, requiring the state space to be increased by a factor of 256 (to 230,400 states). Fortunately, in many circumstances we can introduce a single coordina­ tion mechanism to deal with multiple, related CPs. In the grid problem, for example, once the agents coordinate at a state by one agent moving up and the other down, they can maintain these "roles" at other states exhibiting similar CPs.

We do not propose a method for constructing such gen­ eralizations automatically-this could use, say, generaliza­ tion techniques from reinforcement learning [1]-but we il­ lustrate potential benefits with the simple example shown in Figure 5. It is similar to the MMDP in Figure 1 except that miscoordination at 8 2 has a larger penalty, and an analogous "low cost" CP has been added. If a single mechanism is used for both CPs (at 82 and 87 ), once coordination is attained at 87, it is automatic at 82 . As in the original MMDP, with fewer than 12 stages-to-go, the optimal action at (51, U) is to "opt out" and take the sure reward 5. With 12 or more stages remaining, the optimal action at (51, U) is (a, a): the agents move to the low risk CP and try to coordinate there. Never do the agents move to 8 2 in an uncoordinated state. Even though there is no immediate benefit to moving to 8 7 , it gives the agents an opportunity to "train," or learn to coordi­ nate with minimal risk. Once they coordinate, they immedi­ ately exploit this learned protocol and choose (a, b) at (51, C) (thereby moving to ( 8 2 , C)). Reasoning about the long term prospects of coordination and its costs, the agents realize that risk-free training is worthwhile.

7 Though with higher penalties, it is not.

If we retain the original penalty of -10 at s5 , this reasoning fails: there is essentially less risk involved in training at the high stakes CP, so the agents will never move to S7 to train.

The infinite horizon problem is similar. With a discount rate of 0. 95, the optimal policy requires the agents to move to s7 until they coordinate, at which point they repeatedly move to s2 . Interestingly, adding the "training states" increases the expected reward accrued by the agents. Without the training states, V ( (s1 , U)) = 46.68 since the agents accept the risk of getting several -20 rewards to ensure coordination. With the training states, they can learn to coordinate without the severe penalties, and V((s1,U)) = 49.57.

6 Concluding Remarks

We have introduced a novel method of defining value func­ tions (and consequently, optimal policies) for multiagent de­ cision problems that accounts for specific means of coordina­ tion. We also defined a value iteration algorithm for comput­ ing optimal policies that recognizes and reasons about CPs.

Further experimentation is needed with other coordination mechanisms and their impact on policy value. We have de­ scribed experiments in this paper using randomization, and have begun to investigate communication methods, and hope to explore other models like FP. We intend to introduce eco­ nomic models (such as auctions) so that agents may integrate reasoning about their activity in markets into their decision processes. We must explore automated generalization meth­ ods further; it has the potential to substantially reduce there­ quired number of mechanisms, alleviate computational diffi­ culties, and increase objective policy value.

We would also like address the problem of designing ro­ bust, computationally effective and value-increasing coordi­ nation protocols in the framework. In a certain sense, such an undertaking can be viewed as one of designing social laws [ 15]. It is also related to the issues faced in the design of pro­ tocols for distributed systems and the distributed control of discrete-event systems [ 1 0] . But rather than designing proto­ cols for specific situations, metaprotocols that increase value over a wide variety of CPs would be the target. The frame­ work developed here can also help decide whether sophisti­ cated protocols are worthwhile. For instance, a lexicographic protocol induces immediate coordination with a measurable (in our model) increase in expected value over (say) a ran­ domization method. This increase can then be used to de­ cide whether the overhead of incorporating a lexicographic convention (e.g., ensuring agents have common orderings) is worthwhile. Similar remarks can be applied to the design of agents (e.g., is communicative ability worthwile given the class of decision problems they will face).

Acknowledgements

This research was supported by the DARPA Co-ABS pro­ gram (through Stanford University contract F30602-98-C0214), NSERC Research Grant OGP0121843, and IRIS Phase-III Project BAC. Thanks to Ron en Brafman for discus­ sion of these issues.