Enabling local computation for partially ordered preferences

Fargier, Hélène; Rollon, Emma; Wilson, Nic

Enabling local computation for partially ordered preferences

Files

Fargier-Rollon-Wilson-2010-version_for_website.pdf(275.86 KB)

Accepted Version

Date

2010-01

Authors

Fargier, Hélène

Rollon, Emma

Wilson, Nic

Publisher

Springer

Published Version

10.1007/s10601-010-9094-z

Abstract

Many computational problems linked to uncertainty and preference management can be expressed in terms of computing the marginal(s) of a combination of a collection of valuation functions. Shenoy and Shafer showed how such a computation can be performed using a local computation scheme. A major strength of this work is that it is based on an algebraic description: what is proved is the correctness of the local computation algorithm under a few axioms on the algebraic structure. The instantiations of the framework in practice make use of totally ordered scales. The present paper focuses on the use of partially ordered scales and examines how such scales can be cast in the Shafer-Shenoy framework and thus benefit from local computation algorithms. It also provides several examples of such scales, thus showing that each of the algebraic structures explored here is of interest.

Keywords

Soft constraints , Dynamic programming , Local computation , Valuation networks/algebra , Constraint satisfaction , Optimization

Citation

Fargier, H,Rollon, E,Wilson, N; (2010) 'Enabling local computation for partially ordered preferences'. Constraints, 15 (4) :516-539. doi: 10.1007/s10601-010-9094-z [untranslated]