Search

In 2010, Bousquet-M\'elou et al. defined sequences of nonnegative integers called ascent sequences and showed that the ascent sequences of length $n$ are in one-to-one correspondence with the interval orders, i.e., the posets not containing the poset $\mathbf{2}+\mathbf{2}$. Through the use of generating functions, this provided an answer to the longstanding open question of enumerating the (unlabeled) interval orders. A semiorder is an interval order having a representation in which all intervals have the same length. In terms of forbidden subposets, the semiorders exclude $\mathbf{2}+\mathbf{2}$ and $\mathbf{1}+\mathbf{3}$. The number of unlabeled semiorders on $n$ points has long been known to be the $n$-th Catalan number. However, describing the ascent sequences that correspond to the semiorders under the bijection of Bousquet-M\'elou et al. has proved difficult. In this paper, we discuss a major part of the difficulty in this area: the ascent sequence corresponding to a semiorder may have an initial subsequence that corresponds to an interval order that is not a semiorder. We define the hereditary semiorders to be those corresponding to an ascent sequence for which every initial subsequence also corresponds to a semiorder. We provide a structural result that characterizes the hereditary semiorders and use this characterization to determine the ordinary generating function for hereditary semiorders. We also use our characterization of hereditary semiorders and the characterization of semiorders of dimension 3 given by Rabinovitch to provide a structural description of the semiorders of dimension at most 2. From this description, we are able to determine the ordinary generating for the semiorders of dimension at most 2., Comment: 27 pages, 19 figures, 1 table

A NaP-preference (necessary and possible preference) is a pair of nested reflexive relations on a set such that the smaller is transitive, the larger is complete, and the two components jointly satisfy natural forms of mixed completeness and transitive coherence. A NaP-preference is normalized if its smaller component is a partial order. We show that normalized NaP-preferences on a finite set are well-graded in the sense of Doignon and Falmagne (1997).

We prove that the order of an ordered group is an interval order if and only if it is a semiorder. Next, we prove that every semiorder is isomorphic to a collection $\mathcal J$ of intervals of some totally ordered abelian group, these intervals being of the form $[x, x+ \alpha[$ for some positive $\alpha$. We describe ordered groups such that the ordering is a semiorder and we introduce threshold groups generalizing totally ordered groups. We show that the free group on finitely many generators and the Thompson group $\mathbb F$ can be equipped with a compatible semiorder which is not a weak order. On another hand, a group introduced by Clifford cannot., Comment: 32 pages, 2 figures

Rationalizability has been a main topic in individual choice theory since the seminal paper of Samuelson (1938). The rationalization of a multi-valued choice is classically obtained by maximizing the binary relation of revealed preference, which is fully informative of the primitive choice as long as suitable axioms of choice consistency hold. In line with this tradition, we give a purely axiomatic treatment of the topic of choice rationalization. In fact, we introduce a new class of properties of choice coherence, called axioms of replacement consistency, which examine how the addition of an item to a menu may cause a substitution in the selected set. These axioms are used to uniformly characterize rationalizable choices such that their revealed preferences are quasi-transitive, Ferrers, semitransitive, and transitive. Further, regardless of rationalizability, we study the relationship of these new axioms with some classical properties of choice consistency, such as standard contraction, standard expansion, and WARP . To complete our analysis of the transitive structure of rationalizable choices, we examine the case of revealed preferences satisfying weak ( m , n ) -Ferrers properties in the sense of Giarlotta and Watson (2014). Originally introduced with the purpose of extending the notions of interval orders and semiorders, these Ferrers properties give a descriptive taxonomy of binary relations displaying a transitive strict preference but an intransitive indifference. Here we suggest a possible economic interpretation of weak ( m , n ) -Ferrers properties, showing that, in a suitable model of transactions, they provide a way of controlling phenomena of money-pump due to the presence of mixed cycles of preference/indifference. Finally, we define ( m , n ) -rationalizable choices as those having a weakly ( m , n ) -Ferrers revealed preference, and characterize these choices by means of additional axioms of replacement consistency.

A poset $P= (X, \prec)$ has an interval representation if each $x \in X$ can be assigned a real interval $I_x$ so that $x \prec y$ in $P$ if and only if $I_x$ lies completely to the left of $I_y$. Such orders are called \emph{interval orders}. Fishburn proved that for any positive integer $k$, an interval order has a representation in which all interval lengths are between $1$ and $k$ if and only if the order does not contain $\mathbf{(k+2)+1}$ as an induced poset. In this paper, we give a simple proof of this result using a digraph model., Comment: 9 pages, 1 figure

The niche graph of a digraph $D$ is the (simple undirected) graph which has the same vertex set as $D$ and has an edge between two distinct vertices $x$ and $y$ if and only if $N^+_D(x) \cap N^+_D(y) \neq \emptyset$ or $N^-_D(x) \cap N^-_D(y) \neq \emptyset$, where $N^+_D(x)$ (resp. $N^-_D(x)$) is the set of out-neighbors (resp. in-neighbors) of $x$ in $D$. A digraph $D=(V,A)$ is called a semiorder (or a unit interval order) if there exist a real-valued function $f:V \to \mathbb{R}$ on the set $V$ and a positive real number $\delta \in \mathbb{R}$ such that $(x,y) \in A$ if and only if $f(x) > f(y) + \delta$. A digraph $D=(V,A)$ is called an interval order if there exists an assignment $J$ of a closed real interval $J(x) \subset \mathbb{R}$ to each vertex $x \in V$ such that $(x,y) \in A$ if and only if $\min J(x) > \max J(y)$. S. -R. Kim and F. S. Roberts characterized the competition graphs of semiorders and interval orders in 2002, and Y. Sano characterized the competition-common enemy graphs of semiorders and interval orders in 2010. In this note, we give characterizations of the niche graphs of semiorders and interval orders., Comment: 7 pages

Traditionally, a preference on a set A of alternatives is modeled by a binary relation R on A satisfying suitable axioms of pseudo-transitivity, such as the Ferrers condition ( a R b and c R d imply a R d or c R b ) or the semitransitivity property ( a R b and b R c imply a R d or d R c ). In this paper we study ( m , n ) -Ferrers properties, which naturally generalize these axioms by requiring that a 1 R … R a m and b 1 R … R b n imply a 1 R b n or b 1 R a m . We identify two versions of ( m , n ) -Ferrers properties: weak, related to a reflexive relation, and strict, related to its asymmetric part. We determine the relationship between these two versions of ( m , n ) -Ferrers properties, which coincide whenever m + n = 4 (i.e., for the classical Ferrers condition and for semitransitivity), otherwise displaying an almost dual behavior. In fact, as m and n increase, weak ( m , n ) -Ferrers properties become stronger and stronger, whereas strict ( m , n ) -Ferrers properties become somehow weaker and weaker (despite failing to display a monotonic behavior). We give a detailed description of the finite poset of weak ( m , n ) -Ferrers properties, ordered by the relation of implication. This poset depicts a discrete evolution of the transitivity of a preference, starting from its absence and ending with its full satisfaction.

Rationalizability has been a main topic in individual choice theory since the seminal paper of Samuelson (1938). The rationalization of a multi-valued choice is classically obtained by maximizing the binary relation of revealed preference, which is fully informative of the primitive choice as long as suitable axioms of choice consistency hold. In line with this tradition, we give a purely axiomatic treatment of the topic of choice rationalization. In fact, we introduce a new class of properties of choice coherence, called axioms of replacement consistency, which examine how the addition of an item to a menu may cause a substitution in the selected set. These axioms are used to uniformly characterize rationalizable choices such that their revealed preferences are quasi-transitive, Ferrers, semitransitive, and transitive. Further, regardless of rationalizability, we study the relationship of these new axioms with some classical properties of choice consistency, such as standard contraction, standard expansion, and WARP. To complete our analysis of the transitive structure of rationalizable choices, we examine the case of revealed preferences satisfying weak (m,n)(m,n)-Ferrers properties in the sense of Giarlotta and Watson (2014). Originally introduced with the purpose of extending the notions of interval orders and semiorders, these Ferrers properties give a descriptive taxonomy of binary relations displaying a transitive strict preference but an intransitive indifference. Here we suggest a possible economic interpretation of weak (m,n)(m,n)-Ferrers properties, showing that, in a suitable model of transactions, they provide a way of controlling phenomena of money-pump due to the presence of mixed cycles of preference/indifference. Finally, we define (m,n)(m,n)-rationalizable choices as those having a weakly (m,n)(m,n)-Ferrers revealed preference, and characterize these choices by means of additional axioms of replacement consistency.

We introduce an inductive definition for two classes of orders. By simple proofs, we show that one corresponds to the interval orders class and that the other is exactly the semiorders class.

A perfect Guttman scale is rarely found in real data. Pairwise dominance relations between items to be scaled, however, often meet the conditions for less simple orders, such as strict partial orders, interval orders, and semiorders. Examples are thus provided for an extension of the Guttman scale to less simple orders in the framework of ordinal theory, or more specifically, the theory of representations with thresholds. The study is methodologically based on ordering theory. Three illustrative constructions of less simple orders demonstrate that they much more strongly account for real data than do Guttman scales, and that some uniqueness in scale values and thresholds is found in semiorders and interval orders.

In this paper, we go further on the problem of the continuous numerical representability of interval orders defined on topological spaces. A new condition of compatibility between the given topology and the indifference associated to the main trace of an interval order is introduced. Provided that this condition is fulfilled, a semiorder has a continuous interval order representation through a pair of continuous real-valued functions. Other necessary and sufficient conditions for the continuous representability of interval orders are also discussed, and, in particular, a characterization is achieved for the particular case of interval orders defined on a topological space of finite support.

Document de travail: Cahier du LAMSADE, n°348 (2013); International audience; This paper studies an extension of bi-semiorders in which a “frontier” is added between the various relations used. This extension is motivated by the study of additive representations of ordered partitions and coverings defined on product sets of two components.

We develop a theory of biased extensive measurement which allows us to prove the existence of a ratio-scale without transitivity of indifference and with a property of homothetic invariance weaker than independence. These representations, which cover the cases of interval orders and of semiorders, reveal a unique biasing function smaller or equal to 1 that distorts extensive measurement and explains departures from its standard axioms. We interpret this biasing function as characterizing the qualitative influence of the underlying measurement process and we show that it induces a proportional indifference threshold.

Binary relations representable by utility functions with multiplicative error are considered. It is proved that if the error is a power of utility then the underlying binary relation is either an interval order, or a semiorder. Moreover, semiorders can be characterized among interval orders by the magnitude of the power of utility that is used in the form of error function.

We present different conditions for the existence of a pair of upper semicontinuous functions representing an interval order on a topological space without imposing any restrictive assumptions neither on the topological space nor on the representing functions. The particular case of second countable topological spaces, which is particularly interesting and frequent in economics, is carefully considered. Some final considerations concerning semiorders finish the paper.

In the framework of the analysis of orderings whose associated indifference relation is not necessarily transitive, we study the structure of an interval order and its representability through a pair of real-valued functions. We obtain a list of characterizations of the existence of a representation, showing that the three main techniques that have been used in the literature to achieve numerical representations of interval orders are indeed equivalent.

A poset P=(X,≺) is a split semiorder if a unit interval and a distinguished point in that interval can be assigned to each x∈X so that x≺y precisely when x's distinguished point precedes y's interval, and y's distinguished point follows x's interval. For each |X|≤10, we count the split semiorders and identify all posets that are minimal forbidden posets for split semiorders.

A classical approach to model a preference on a set A of alternatives uses a reflexive, transitive and complete binary relation, i.e. a total preorder. Since the axioms of a total preorder do not usually hold in many applications, preferences are often modeled by means of weaker binary relations, dropping either completeness (e.g. partial preorders) or transitivity (e.g. interval orders and semiorders). We introduce an alternative approach to preference modeling, which uses two binary relations–the necessary preference ≿ N and the possible preference ≿ P –to fulfill completeness and transitivity in a mixed form. Formally, a NaP-preference (necessary and possible preference) on A is a pair ( ≿ N , ≿ P ) such that ≿ N is a partial preorder on A and ≿ P is an extension of ≿ N satisfying mixed properties of transitivity and completeness. We characterize a NaP-preference ( ≿ N , ≿ P ) by the existence of a nonempty set R of total preorders such that ⋂ R = ≿ N and ⋃ R = ≿ P . In order to analyze the representability of NaP-preferences via families of utility functions, we generalize the notion of a multi-utility representation of a partial preorder by that of a modal utility representation of a pair of binary relations. Further, we give a dynamic view of the family of all NaP-preferences on a fixed set A by endowing it with a relation of partial order, which is defined according to the stability of the information represented by each NaP-preference.

A NaP-preference (necessary and possible preference) on a set A is a pair ${\left(\succsim^{^{_N}}\!,\,\succsim^{^{_P}}\!\right)}$ of binary relations on A such that its necessary component ${\succsim^{^{_N}} \!\!}$ is a partial preorder, its possible component ${\succsim^{^{_P}} \!\!}$ is a completion of ${\succsim^{^{_N}} \!\!}$ , and the two components jointly satisfy natural forms of mixed completeness and mixed transitivity. We study additional mixed transitivity properties of a NaP-preference ${\left(\succsim^{^{_N}}\!,\,\succsim^{^{_P}}\!\right)}$ , which culminate in the full transitivity of its possible component ${\succsim^{^{_P}} \!\!}$ . Interval orders and semiorders are strictly related to these properties, since they are the possible components of suitably transitive NaP-preferences. Further, we introduce strong versions of interval orders and semiorders, which are characterized by enhanced forms of mixed transitivity, and use a geometric approach to compare them to other well known preference relations.

We study poset limits given by sequences of finite interval orders or, as a special case, finite semiorders. In the interval order case, we show that every such limit can be represented by a probability measure on the space of closed subintervals of [0,1], and we define a subset of such measures that yield a unique representation. In the semiorder case, we similarly find unique representations by a class of distribution functions., 18 pages

This paper studies an extension of biorders that has a “frontier” between the relation and the absence of relation. This extension is motivated by a conjoint measurement problem consisting in the additive representation of ordered coverings defined on product sets of two components. We also investigate interval orders and semiorders with frontier.

In this work we are concerned with maximality issues under intransitivity of the indifference. Our approach relies on the analysis of "undominated maximals" (cf., Peris and Subiza, J Math Psychology 2002). Provided that an agent's binary relation is acyclic, this is a selection of its maximal elements that can always be done when the set of alternatives is finite. In the case of semiorders, proceeding in this way is the same as using Luce's selected maximals. We put forward a sufficient condition for the existence of undominated maximals for interval orders without any cardinality restriction. Its application to certain type of continuous semiorders is very intuitive and accommodates the well-known "sugar example" by Luce.