
| Mode l      |                       | o                                |
|-------------|-----------------------|----------------------------------|
| DE C-POMDP  | no communication      | collective partial observability |
| P OIP SG    | no communication      | collective partial observability |
| MMMMM       | no communication      | individual observability         |
| Xuan-Lesser | general communication | collective observability         |

## 2.4.4 Xuan- Lesser  Framework

The COM-MTDP's separation of communication from other actions is similar to previous work on multiagent decision models (Xuan, Lesser, & Zilberstein, 2001), which supported general communication. However, while the Xuan-Lesser model generalizes beyond individually observable environments, it supports only a subset of collectively observable environments. In particular, the Xuan-Lesser framework cannot represent agents who receive local observations of a common world state, where the observations of different agents could potentially be interdependent.

## 3.  Com-Mtdp  Complexity  Analysis

We can use the COM-MTDP model to prove some results about the complexity of constructing optimal agent teams (i.e., teams that coordinate to produce optimal behavior in a problem domain). The problem facing these agents (or the designer of these agents) is how to construct the joint policies, παχ and παλ t so as to maximize their joint reward, as represented by the expected value, V T ( παλ , παχ). In all of the results presented, we assume that all of the values in a model instance (e.g., transition probabilities, rewards) are rational numbers, so that we can express the particular instance as a finite-sized input.

Theorem 1  The decision problem of whether there exist policies, παχ and παλ, for a given COM-MTDP, under general communication and collective partial observability, that yield a total reward at least K over some finite horizon T is NEXP-complete if [a] ≥ 2 (i.e.,
more than one agent).

Proof: To prove that the COM-MTDP decision problem is NEXP-hard, we reduce a DEC- POMDP (Bernstein et al., 2000) to a COM-MTDP with no communication by copying all of the other model features from the given DEC-POMDP. In other words, if we are given a DEC-POMDP, (S, {A'},
(S', {A'}"
S' = S'
A,

$s^{\prime}\,\big)\,=$
= A'
E' = 0 P ′ ( s, ⟨ a 1 , . . . , α m ⟩ , s ′ ) = P ( s ′ | s, α 1 , . . . , α m )

$$a_{1},\,\cdot\,\cdot\,\cdot\,,\,a_{m}\,)$$
