The specification of a decision making problem includes the agent’s preferences on the available alternatives. The choice of a
of preferences (
, utility functions or binary relations) does not say how preferences should be
). A naive idea would consist in writing them
, simply by enumerating all possible alternatives together with their utility (in the case of cardinal preferences) or the list of all pairs of alternatives contained in the relation (in the case of ordinal preferences). This is feasible in practice only when the number of alternatives is small enough with respect to the available computational resources. This assumption is often unrealistic, in particular when the set of alternatives has a combinatorial (or multiattribute) structure,
, when each alternative consists of a tuple of values, one for each of a given set of
): in this case, the set of alternatives is the Cartesian product of the value domains, and its cardinality grows exponentially with the number of variables.