Skip to main content

Subset comparisons for additive linear orders

Publication ,  Journal Article
Fishburn, PC; Pekeč, A; Reeds, JA
Published in: Mathematics of Operations Research
January 1, 2002

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 stage are formulated.

Duke Scholars

Published In

Mathematics of Operations Research

DOI

ISSN

0364-765X

Publication Date

January 1, 2002

Volume

27

Issue

1

Start / End Page

227 / 243

Related Subject Headings

  • Operations Research
  • 4901 Applied mathematics
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics
  • 0102 Applied Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Fishburn, P. C., Pekeč, A., & Reeds, J. A. (2002). Subset comparisons for additive linear orders. Mathematics of Operations Research, 27(1), 227–243. https://doi.org/10.1287/moor.27.1.227.339
Fishburn, P. C., A. Pekeč, and J. A. Reeds. “Subset comparisons for additive linear orders.” Mathematics of Operations Research 27, no. 1 (January 1, 2002): 227–43. https://doi.org/10.1287/moor.27.1.227.339.
Fishburn PC, Pekeč A, Reeds JA. Subset comparisons for additive linear orders. Mathematics of Operations Research. 2002 Jan 1;27(1):227–43.
Fishburn, P. C., et al. “Subset comparisons for additive linear orders.” Mathematics of Operations Research, vol. 27, no. 1, Jan. 2002, pp. 227–43. Scopus, doi:10.1287/moor.27.1.227.339.
Fishburn PC, Pekeč A, Reeds JA. Subset comparisons for additive linear orders. Mathematics of Operations Research. 2002 Jan 1;27(1):227–243.

Published In

Mathematics of Operations Research

DOI

ISSN

0364-765X

Publication Date

January 1, 2002

Volume

27

Issue

1

Start / End Page

227 / 243

Related Subject Headings

  • Operations Research
  • 4901 Applied mathematics
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics
  • 0102 Applied Mathematics