The calculation of natural extensions with respect to lower probabilities

The concept of natural extension plays an important role in the theory of imprecise probabilities. It is a nonlinear functional on the class of nonnegative finite measurable functions. The difficulty of its calculation restricts applications of the theory. The paper provides a fast algorithm by which a precise value of the natural extension of a given nonnegative finite function with respect to a given lower probability is computed. Such an algorithm makes the natural extension one of the tools for aggregation in information fusion