The lexicographic complexity of asymmetric binary relations

Vicki Knoblauch

Mathematical Social Sciences, 2022, vol. 117, issue C, 6-12

Abstract: The lexicographic complexity of an asymmetric binary relation on a finite set is defined to be the minimal number of ternary criteria sufficient to construct a 1–1 lexicographic representation of that relation. Lexicographic complexity provides a measure of the degree of non-representability by utility function of an asymmetric binary relation. Tight upper and lower bounds are established for the lexicographic complexity of an asymmetric binary relation on a set of cardinality n. Four examples launch an exploration of the relationships between lexicographic complexity and intransitivity and between lexicographic complexity and incompleteness. Two examples of 1–1 lexicographic representations exhibit a strong lexicographic flavor in that, for each of the two examples, any two distinct reorderings of its coordinate functions result in representations of distinct binary relations.

Keywords: Lexicographic complexity; Asymmetric binary relation; Lexicographic flavor (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165489622000130
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matsoc:v:117:y:2022:i:c:p:6-12

DOI: 10.1016/j.mathsocsci.2022.02.002

Access Statistics for this article

Mathematical Social Sciences is currently edited by J.-F. Laslier

More articles in Mathematical Social Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().