Preference Reasoning Under Partial Alternatives

Abstract

Selecting a single alternative among many is a key cognitive task. Many formal approaches for solving this problem have been explored, but these approaches consider having, or eliciting, complete preference information. As a natural extension, work has also been done to consider situations where complete preference information is unknown. What has not been studied is the effect of incomplete information wrt the alternatives an agent may select from. This work focuses on the computational problems that arise when preference information is known, but alternatives are only partially specified, such as when one is searching online classified ads. We both define these problems and specify some general computational complexity results. While the complexity of the defined problems are not tightly bound, we do provide a case study which demonstrates how partial alternatives affect different preference representations differently.