in a κ-joint-policy τ =Qn i=1 τi. Let, τ−i =
τ τi

. Now suppose (x1, x2, **. . .**, xn) is a solution to MP2-Dec. Each xiis a κ-step deterministic policy of the ith agent. The κ-joint-policy formed by them is also deterministic. If for a sequence p of length κ, xi[p**] = 1**, then it implies that for exactly τ−ijoint-sequences q of length κ in which the sequence of the ith agent is p,Qn i=1 xi[q**] = 1**. On the other hand, if xi[p**] = 0**, then for each joint-sequence q in which the sequence of the i agent is p,Qn i=1 xi[q**] = 0**.

This can be represented mathematically as,

$$\sum_{q\in{\mathcal{S}}^{\kappa}:q_{i}=p}\prod_{j=1}^{n}{\overline{{x}}}_{j}[q_{j}]=\tau_{-i}{\overline{{x}}}_{i}[p],\quad\forall\;i\in N,\forall\;p\in{\mathcal{S}}_{i}^{\kappa}$$
i(21)
$$(21)$$

The set of equations (21)is true for every κ-step deterministic joint-policy, and it allows us to linearize the constraints (18). All we have to do is to add the following set of linear constraints to MP2-Dec,

$$\sum_{q\in{\mathcal{S}}^{\kappa}:q_{i}=p}{\overline{{y}}}[q]=\tau_{-i}{\overline{{x}}}_{i}[p],\quad\ \forall\ i\in N,\,\forall\ p\in{\mathcal{S}}_{i}^{\kappa}$$

If these constraints are added to MP2-Dec then the following holds,

$$(22)$$
$$\prod_{j=1}^{n}\overline{{{x}}}_{j}[q_{j}]=\overline{{{y}}}[q],\quad\ \forall\,q\in{\mathcal{S}}^{\kappa}$$
$$(23)$$

xj [qj ] = y[q], ∀ q ∈ Sκ(23)
because the r.h.s. of their corresponding equations are equal. Thus, we have achieved the linearization of the constraints (18) and therefore of f(x). We shall call the constraints (22) as the *joint-policy constraints*. The MP obtained on adding the jointpolicy constraints to MP2-Dec gives us the integer linear program ILP-Dec, on which the mixed ILP (MILP), the main contribution of this paper, is based We give ILP-Dec below for the sake of completeness.

## 5.4 Integer Linear Program Ilp-Dec

1. Variables:
(a) A |Sκ|-vector of variables, y.

(b) For each agent i ∈ N, an |Si|-vector of variables, xi.

2. Objective:

$$\mathrm{maximize}\qquad f({\overline{{y}}})\equiv\sum_{q\in{\mathcal{S}}^{\kappa}}\nu(q){\overline{{y}}}[q]$$
ν(q)y[q] (24)
 * 3. Constraints: for each agent $i\in N$. 
$${\mathrm{(a)~Policy~constraints}}\colon$$

$$\sum_{a_{i}\in A_{i}}\overline{{{x}}}_{i}[a_{i}]=1$$

$$(24)$$
$$(25)$$
$$11$$
