fun tions, SE0 i and SE0 i as dened in Equations 5 and 6 to generate b 0t i and b 0t i.

Ea h belief state is a omplete history of observation and ommuni ation pairs for ea h agent. On the other hand, under the omplete ommuni ation of , the state estimator fun tions of Equations 5 and 6 redu e to:

SEi(   0 ; : : : ;  t1   ;  t i ) =   0 ; : : : ;  t1  ;  t i  (9) SEi(   0 ; : : : ;  t1  ;  t i  ; t) =   0 ; : : : ;  t1  ; t  =   0 ; : : : ;  t1  ;  t   (10)

Thus, A is dened over a dierent set of belief states than 0A. In order to determine an equivalent A, we must rst dene a re
ursive mapping, m, that translates the belief states dened by  into those dened by 0:

mi(b t i) =mi  b t1 i ;  t   = mi  b t1 i ;   t i ;  t   = D mi(b t1 i ); D  t i ; 0t EE = * mi(b t1 i ); * j2 0tj ++  t i ; Y = * mi(b t1 i ); * j2 0j(SE0j(mj (b t1 j );  t j ))++ (11)  t i ; Y

Given this mapping, we then spe ify: iA(b t i

) = 0 iA(mi(b t i

)). Exe uting this domainlevel poli y, in onjun tion with the ommuni ation poli y, , results in the identi
al behavior as exe ution of the alternate poli ies, 0 A and 0. Therefore, the team following the poli ies, A and  will a
hieve the same expe
ted value of K, as under 0A and 0
. 2 Given this dominan e of the ompleteommuni ation poli y, we an prove that the problem of onstru ting teams that oordinate optimally is simpler when ommuni ation is free.

Theorem 3 The de ision problem of determining whether there exist poli ies,  and A, for a given COM-MTDP with free 
ommuni
ation under 
olle
tive partial observability, that yield a total reward at least K over some nite horizon T is PSPACE-
omplete.

Proof: To prove that the problem is PSPACE-hard, we redu e the single-agent POMDP to a COM-MTDP. In parti ular, if we are given a POMDP, hS; A; P; 
; O; Ri, we 
an 
onstru
t a COM-MTDP, hS0; A0 1; 0 1; P 0; 0 1; O0 1 ; B0 1; R0i, for a single-agent team (i.e.,  = f1g):

$$S^{\prime}\;=\;S$$

$$A_{1}^{\prime}\;=\;A$$
$$\Sigma_{1}^{\prime}\;=\;\emptyset$$
$$P^{\prime}\!\left(\,s,\left\langle\,a_{1}\,\right\rangle,\,s^{\prime}\,\right)=\ P\!\left(\,s,a_{1},\,s^{\prime}\,\right)$$
$$\Omega_{1}^{\prime}\;=\;\Omega$$
