Efficient algorithm for estimation of qualitative expected utility in possibilistic case-based reasoning
This incremental improvement addresses computational bottlenecks for decision-making in multi-attribute negotiation systems, such as partner selection.
The paper tackles the computational inefficiency of estimating qualitative expected utility in possibilistic case-based reasoning, where traditional methods scale exponentially with attributes, and presents an algorithm with proven linear complexity.
We propose an efficient algorithm for estimation of possibility based qualitative expected utility. It is useful for decision making mechanisms where each possible decision is assigned a multi-attribute possibility distribution. The computational complexity of ordinary methods calculating the expected utility based on discretization is growing exponentially with the number of attributes, and may become infeasible with a high number of these attributes. We present series of theorems and lemmas proving the correctness of our algorithm that exibits a linear computational complexity. Our algorithm has been applied in the context of selecting the most prospective partners in multi-party multi-attribute negotiation, and can also be used in making decisions about potential offers during the negotiation as other similar problems.