
## 5.1 Linearization Of F(X): Step 1

The simple idea in linearizing a nonlinear function is to use a variable for each nonlinear term that appears in the function. In the case of f(x), the nonlinear terms are, for each joint-sequence q of length κ,Qn i=1 xi[qi]. Therefore, to replace the nonlinear terms in f(x), we need to use a variable for every joint-sequence q of length κ. Let y[q] ≥ 0 be the variable for q and let,

$$f(\overline{{{y}}})\equiv\sum_{q\in{\mathcal{S}}^{\kappa}}\nu(q)\overline{{{y}}}[q]$$
$$(17)$$
ν(q)y[q] (17)
So the first step in linearizing f(x) is to change the objective in MP-Dec to f(y) and introduce the |Sκ|-vector y ≥ 0 of variables in it. We denote this modified MP by MP1-Dec.

## 5.2 Linearization Of F(X): Step 2

Once the objective is changed to f(y), we need to relate the variables representing joint-sequences (y) to those representing agents' sequences (the xi vectors). In other words, we need to add the following constraints to MP1-Dec,

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

But the constraints (18) are *nonconvex*. So, if they are added to MP1-Dec, it would amount to maximizing a linear function under nonconvex, nonlinear constraints, and again we would not have any guarantee of finding the globally optimal solution. We therefore must also linearize these constraints. We shall do this in this step and the next.

Suppose that (x1, x2, **. . .**, xn) is a solution to MP1-Dec. Then, for each joint-sequence q of length κ,Qn i=1 xi[qi] takes a value in [0,1]. In other words, it can take an infinite number of values. We can limit the values it can take by requiring that the vectors xi be vectors of *binary* variables, 0 or 1. Moreover, since we want Qn i=1 xi[qi] to equal y[q], but want to avoid the constraints (18), we should also require that each y variable be a binary variable. Thus, the second step in linearizing f(x) is to add the following constraints to MP1-Dec:

$$\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}$$

Note that with these constraints in MP1-Dec, xi would represent a deterministic κpolicy of the ith agent. Constraints (19)-(20) are called *integer constraints*. We denote the MP formed by adding integer constraints to MP1-Dec by MP2-Dec.

## 5.3 Linearization Of F(X): Step 3

This is key step in the linearization. The number of sequences of length κ in a κ-policy of the ith agent is τi = |Ωi| κ−1. Hence the number of joint-sequences of length κ

$$(19)$$
