Algorithmic problems of nontransitive (SSB) utilities

Abstract

The standard utility theory is based on several natural axioms including transitivity of preference; however, real preference is often not transitive. To describe such preferences, Fishburn (1988) introduced a new formalism (SSB-utilities), in which preference is described by a skew-symmetric function F:M x M - R, where M is the set of all alternatives. He also showed that it is in principle possible to reconstruct this function F by asking the person to compare different alternatives and lotteries. In the present paper we propose a new algorithm for reconstructing F that is asymptotically optimal in the sense that the number of binary (yes-no) questions that one has to ask to determine the values of F with given precision is of minimal possible order.