Heuristics for selecting pair-wise elicitation questions in multiple criteria choice problems

We present a set of heuristic approaches for selecting pair-wise elicitation questions in an interactive process for multiple criteria choice problems. Our heuristics aim at minimizing the number of question-answer iterations leading to the univocal recommendation of the Decision Maker's (DM's) most preferred alternative. To identify the myopically best question at a given stage of interaction, the proposed approaches ask the DM to compare a pair of alternatives that contributes to the greatest reduction of uncertainty, with respect to the indication of the best alternative by all compatible value functions. This uncertainty is measured either in terms of the number of potentially optimal alternatives, or the entropy of first rank acceptabilities, while assuming different a priori unknown probabilities of the DM's answers. We discuss results from the extensive experiments on artificially generated and real-world decision problems. Depending on the complexity of the considered problem instances, we either perform a comprehensive analysis of the question-answer interaction trees constructed by the heuristics, or traverse their paths randomly by simulating a numerous set of decision policies. We demonstrate that the greatest benefits from using our questioning procedures can be observed for problems involving numerous alternatives and few criteria, and when the applied piece-wise linear value functions consist of a small number of characteristic points. The study allows us to identify two approaches that perform well in the average or the least advantageous elicitation scenario.