
$$x_{j}\geq y_{j}+\sum_{i=1}^{j-1}(y_{i}-x_{i})$$

We must satisfy these m constraints with a threshold probability θ =
0.8. This stochastic CSP has a number of solutions including xi =
105 for each i (i.e. always produce as many books as the maximum demand). However, this solution will tend to produce books surplus to demand which is undesirable.

Suppose storing surplus book costs $1 per quarter. We can define a m stage stochastic COP based on this stochastic CSP in which we additionally miminize the expected cost of storing surplus books. As the number of surplus books in the jth quarter is **min(**Pj i=1 xi −
yi, 0), we have a cost function over all quarters of:

$$\sum_{j=1}^{m}\operatorname*{min}(\sum_{i=1}^{j}x_{i}-y_{i},0)$$

Note that a solution to a stochastic CSP or COP defines how to set later decision variables given the values for earlier stochastic and decision variables.

## 4 Semantics

A stochastic constraint satisfaction problem is a 6-tuple h**V, S, D, P, C, θ**i where V is a list of variables, S is the subset of V which are stochastic varibles, D is a mapping from V to domains, P is a mapping from S to probability distributions for the domains, C is a set of constraints over V , and θ is a threshold probability in the interval [0, 1]. Constraints are defined by a set of variables and a relation giving the allowed tuples of values.

Variables are set in the order in which they appear in V . Thus, in an one stage stochastic CSP, V contains the decision variables and then the stochastic variables. In a two stage stochastic CSP, V contains the first set of decision variables, the first set of stochastic variables, then the second set of decision variables, and finally the second set of stochastic variables.

A **policy** is a tree with nodes labelled with variables, starting with the first variable in V labelling the root, and ending with the last variable in V labelling the nodes directly above the leaves. Nodes labelled with decision variables have a single child, whilst nodes labelled with stochastic variables have one child for every possible value. Edges in the tree are labelled with values assigned to the variable labelling the node above. Leaf nodes are labelled with 1 if the assignment of values to variables along the path to the root satisfies all the constraints, and 0 otherwise. Each leaf node corresponds to a possible world and has an associated probability; if si is the ith stochastic variable on a path to the root, di is the value given to si on this path, (i.e. the label of the following edge), and **prob**(si = di) is the probability that si = di, then the probability of this world is simply Qi prob(si = di). We define the **satisfaction** of a policy as the sum of the leaf values weighted by their probabilities. A policy satisfies the constraints iff its satisfaction is at least θ. A stochastic CSP is **satisfiable** iff there is a policy which satisfies the constraints.

The **optimal satisfaction** of a stochastic CSP is the maximum satisfaction of all policies. For a stochastic COP, the **expected value**
of a policy is the sum of the objective valuations of each leaf node weighted by their probabilities. A policy is **optimal** if it satisfies the constraints and maximizes (or, if desired, minimizes) the expected value.

Consider again the production planning problem and a two-quarter policy that sets x1 **= 104** and if y1 > 100 then x2 = y1 + 1 else y1 **= 100** and x2 **= 100**. We can represent this policy by the following (partial) tree:

![0_image_0.png](0_image_0.png)

By definition, each of the leaf nodes in this tree is equally probable. There are 6 2leaf nodes, of which only 7 are labelled 0. Hence, this policy's satisfaction is (36 − 7)/36, and the policy satisfies the constraints as this just exceeds θ = 0.8.

## 5 Complexity

Constraint satisfaction is NP-complete in general. Not surprisingly, stochastic constraint satisfaction moves us up the complexity hierarchy. It may therefore be useful for modelling problems like reasoning under uncertainty which lie in these higher complexity classes.

We show how a number of satisfiability problems in these higher complexity classes reduce to stochastic constraint satisfaction. In each case, the reduction is very immediate. Note that each reduction can be restricted to stochastic CSPs on binary constraints using a hidden variable encoding to map non-binary constraints to binary constraints. The hidden variables are added to the last stage of the stochastic CSP.

PP, or probabilistic polynomial time is characterized by the PPcomplete problem, MAJSAT which decides if at least half the assignments to a set of Boolean variables satisfy a clausal formula. This can be reduced to a one stage stochastic CSP in which there are no decision variables, the stochastic variables are Boolean, the constraints are the clauses, the two truth values for the stochastic variables are equally likely and the threshold probability θ = 0.5. A number of other reasoning problems like plan evaluation in probabilistic domains are PP-complete.

NPPP is the class of problems that can be solved by nondeterministic guessing a solution in polynomial time (NP) and then verifying this in probabilistic polynomial time (PP). Given a clausal formula, E-MAJSAT is the problem of deciding if there exists an assignment for a set of Boolean variables so that, given randomized choices of values for the other variables, the formula is satisfiable with probability at least equal to some threshold θ [LGM98]. This can be reduced very immediately to an one stage stochastic CSP.

A number of other reasoning problems like finding optimal sizebounded plans in uncertain domains are NPPP-complete.

PSPACE is the class of problems that can be solved in polynomial space. Note that NP ⊆ PP ⊆ NPPP ⊆ PSPACE. SSAT, or stochastic satisfiability is an example of a PSPACE-complete problem. In SSAT,
we have a clausal formula with m alternating decision and stochastic variables, and must decide if the formula is satisfiable with probability at least equal to some threshold θ. This can be immediately reduced to a m stage stochastic CSP. A number of other reasoning problems like propositional STRIPS planning are PSPACE-complete.