Subset comparisons for additive linear orders

This paper investigates algebraic and combinatorial properties of the set of linear orders on the algebra of subsets of a finite set that are representable by positive measures. It is motivated by topics in decision theory and the theory of measurement, where an understanding of such properties can facilitate the design of strategies to elicit comparisons between subsets that, for example, determine an individual's preference order over subsets of objects or an individual's qualitative probability order over subsets of states of the world. We introduce a notion of critical pairs of binary comparisons for such orders and prove that (i) each order is uniquely characterized by its set of critical pairs and (ii) the smallest set of binary comparisons that determines an order is a subset of its set of critical pairs. The paper then focuses on the minimum number of on-line binary-comparison queries between subsets that suffice to determine any representable order for a set of given cardinality n. It is observed that, for small n, the minimum is attained by first determining the ordering of singleton subsets. We also consider query procedures with fixed numbers of stages, in each stage of which a number of queries for the next state are formulated.