$\forall\;t\in\{1,2,\ldots,\kappa-1\},\forall\;p\in\mathcal{S}_{i}^{t},\forall\;o_{i}\in\Omega_{i},$  $$\overline{x}_{i}[p]-\sum_{a\in A_{i}}\overline{x}_{i}[poa]=0$$

$$(26)$$
$$\sum_{q\in{\mathcal{S}}^{k}:q_{i}=p}{\overline{{y}}}[q]=\tau_{-i}{\overline{{x}}}_{i}[p]$$
$$(27)$$
$$(28)$$
$$4.\ {\mathrm{Integer~constraints}}:$$
$$\begin{array}{l l}{{\overline{{{x}}}_{i}[p]\in\{0,1\},}}&{{\quad\forall\,i\in N,\,\forall\,p\in{\mathcal{S}}_{i}}}\\ {{\overline{{{y}}}[q]\in\{0,1\},}}&{{\quad\forall\,q\in{\mathcal{S}}^{\kappa}}}\end{array}$$

## 5.5 Mixed Integer Linear Program Milp-Dec

We thus have the following result.

Theorem 1 *An optimal solution (*x1, x2, **. . .**, xn*) to* ILP-Dec yields an optimal κ*-jointpolicy for the given Dec-Pomdp.* (Proof is omitted)
An ILP is so called because it is an LP whose variables are constrained to take integer values. In ILP-Dec, each variable can be either 0 or 1. The principle method for solving an integer linear program is *branch and bound*. So when solving ILP-Dec, a tree of LPs is solved in which each LP is identical to the ILP-Dec but in which the integer constraints are replaced by non-negativity constraints (i.e., all the variables are allowed to take real values greater than or equal to 0). In general, the lesser the number of integer variables in an LP, the faster a solution will be obtained. Therefore it is desirable to minimize the number of integer variables in an LP. An LP in which some variables are allowed to take real values while the remaining ones are constrained to be integers is called a mixed ILP (MILP). Thus, an MILP may be solved faster than an ILP of the same size. We say that an MILP is equivalent to an ILP if every solution to the MILP is also a solution to the ILP. An MILP that is equivalent to ILP-Dec can be conceived as follows. Let this MILP be denoted by MILP-Dec. Let MILP-Dec be identical to ILP-Dec in all respects except the following: in each vector xi, only those variables representing sequences of length κ be constrained to take integer values 0 or 1; all the other variables in each xi and all the variables in the vector y be allowed to take real values greater than or equal to 0. Due to the equivalence, we have the following result.

Theorem 2 *An optimal solution (*x1, x2, **. . .**, xn*) to* MILP-Dec yields an optimal κ*joint-policy for the given Dec-Pomdp* The proof of this theorem (and of the claim that MILP-Dec is equivalent to ILP-Dec) is omitted due to lack of space. The discussion henceforth applies to ILP-Dec as well.

(b) Joint-policy $\cos$
(b) Joint-policy constraints: for each p ∈ Sκ

$${\mathfrak{o}}\in S_{i}^{\kappa},$$
