Algorithms for combining belief functions

AbstractIn general, combining Dempster-Shafer belief functions over a frame of n elements is a problem with exponential time complexity in n. This is a consequence of an exponential number of focal elements being generated when the focal elements of the belief functions being combined intersect. In order to avoid this undesirable behavior, we must impose some special structure on the focal sets. Our approach is to work with families of subsets that are closed under intersection. Hence, we present four polynomial time algorithms for combining some particular types of belief functions. In the first case, the case of Bayesian belief functions, we exploit the result that if any belief function is Bayesian, then the resulting belief function is also Bayesian. Thus the resulting belief function has no more than n focal elements. In the second case, the special case of polytomic belief functions over the same partition, we exploit the fact that no new focal elements are created. In the case of exact polytomic belief functions, we exploit the fact that the resulting belief function is also exact polytomic, with no more than n focal sets. Finally, in the case of hierarchical belief functions, we exploit the fact that the resulting belief function has the same hierarchy