Inductive Characterizations of Finite Interval Orders and Semiorders

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.     

The dimension of semiorders

The structure of semiorders and interval orders is investigated and various characterizations are given. These ideas are then applied to prove that the dimension of a semiorder is at most 3, to characterize semiorders of dimension 3 and height 2, and to prove Hiraguchi's Theorem.     

Biorders with Frontier

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.     

Linear orders and semiorders close to an interval order

The purpose of this paper is to study the properties of the linear orders and semiorders at minimum symmetric difference distance from a given interval order on a finite set.     

NP-hardness results for the aggregation of linear orders into median orders

Given a collection Π of individual preferences defined on a same finite set of candidates, we consider the problem of aggregating them into a collective preference minimizing the number of disagreements with respect to Π and verifying some structural properties. We study the complexity of this problem when the individual preferences belong to any set containing linear orders and when the collective preference must verify different properties, for instance transitivity. We show that the considered aggregation problems are NP-hard for different types of collective preferences (including linear orders, acyclic relations, complete preorders, interval orders, semiorders, quasi-orders or weak orders), if the number of individual preferences is sufficiently large.     

The recognition of indifference digraphs and generalized semiorders

A digraph is an interval digraph if each vertex can be assigned a source interval and a sink interval on the real line such that there is an edge from u to v if and only if the source interval for u intersects the sink interval for v. A digraph is an indifference digraph or unit interval digraph if and only if such a representation can be constructed in which every source and sink interval has unit length. We present a new characterization and an efficient recognition algorithm for indifference digraphs and generalized semiorders. © 1996 John Wiley & Sons, Inc.     

Counting Split Semiorders

A poset P=(X,) is a split semiorder if a unit interval and a distinguished point in that interval can be assigned to each xX so that xy 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 Genesis of Interval Orders and Semiorders: Transitive NaP-preferences

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.     

Dimensions of Split Semiorders

A poset P=(X,P) is a split semiorder when there exists a function I thatassigns to each x X a closed interval of the real line R and a set of real numbers, with , suchthat x<y in P if and only if and in R. Every semiorder is a split semiorder, and thereare split semiorders which are not interval orders. It is well known thatthe dimension of a semiorder is at most 3. We prove that the dimension of asplit semiorder is at most 6. We note also that some split semiorders havesemiorder dimension at least 3, and that every split semiorder has intervaldimension at most 2.     

Fractional weak discrepancy and split semiorders

The fractional weak discrepancywd_F(P) of a poset P=(V,?) was introduced in Shuchat et al. (2007) [6] as the minimum nonnegative k for which there exists a function f:V→R satisfying (i) if a?b then f(a)+1≤f(b) and (ii) if a∥b then |f(a)−f(b)|≤k. In this paper we generalize results in Shuchat et al. (2006, 2009) [5] and [7] on the range of wd_F for semiorders to the larger class of split semiorders. In particular, we prove that for such posets the range is the set of rationals that can be represented as r/s for which 0≤s−1≤r<2s.     

The Gold Partition Conjecture

We present the Gold Partition Conjecture which immediately implies the – Conjecture and tight upper bound for sorting. We prove the Gold Partition Conjecture for posets of width two, semiorders and posets containing at most elements. We prove that the fraction of partial orders on an -element set satisfying our conjecture converges to when approaches infinity. We discuss properties of a hypothetical counterexample.     

The Borda rule and Pareto stability: a further comment

In their paper “The Borda rule and Pareto stability: a comment” published in 1979 by Econometrica, Farkas and Nitzan revealed the “intimate relationship” between the Borda rule and the Pareto criterion. The idea was the following: in a profile of total orders, when there is a candidate who obviously wins under unanimous agreement of the voters, that candidate should be in the choice set. In a profile where there is no obvious winner, the candidates that are the closest to unanimity should be chosen. According to this principle, they defined a choice rule called “closeness to unanimity” and they showed that it is equivalent to the Borda rule. In our paper, we give an equivalent result for a ranking rule. Then we try to obtain similar results when aggregating profiles of tournaments, weak orders, semiorders, fuzzy relations, … and we show that the definition of an obvious winner is no more obvious.     

A Characterization of Partially Ordered Sets with Linear Discrepancy Equal to 2

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x)–h _L (y)|≤k, where h _L (x) is the height of x in L. Tanenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem of characterizing the posets of linear discrepancy 2. We show that this problem is equivalent to finding the posets with linear discrepancy equal to 3 having the property that the deletion of any point results in a reduction in the linear discrepancy. Howard determined that there are infinitely many such posets of width 2. We complete the forbidden subposet characterization of posets with linear discrepancy equal to 2 by finding the minimal posets of width 3 with linear discrepancy equal to 3. We do so by showing that, with a small number of exceptions, they can all be derived from the list for width 2 by the removal of specific comparisons. The first and second authors were supported during this research by National Science Foundation VIGRE grant DMS-0135290.     

Irreducible Width 2 Posets of Linear Discrepancy 3

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x) − h _L (y)| ≤ k, where h _L (x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2. The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290.     

Linear Extensions of Semiorders: II

Let M _n (k) denote the family of posets on n points with k ordered pairs that maximize the number of linear extensions among all such posets. Fishburn and Trotter [2] prove that every poset in M _n (k) is a semiorder and identifies all semiorders in M _n (k) for k n. The present paper specifies M _n (k) for all k 2 n – 3.     

Range of the Fractional Weak Discrepancy Function

In this paper we describe the range of values that can be taken by the fractional weak discrepancy of a poset and characterize semiorders in terms of these values. In [6], we defined the fractional weak discrepancy of a poset to be the minimum nonnegative for which there exists a function satisfying (1) if then and (2) if then . This notion builds on previous work on weak discrepancy in [3, 7, 8]. We prove here that the range of values of the function is the set of rational numbers that are either at least one or equal to for some nonnegative integer . Moreover, is a semiorder if and only if , and the range taken over all semiorders is the set of such fractions .The third author's work was supported in part by a Wellesley College Brachman Hoffman Fellowship.     

Almost Connected Orders

One of the standard axioms for semiorders states that no three-point chain is incomparable to a fourth point. We refer to asymmetric relations satisfying this axiom as almost connected orders or ac-orders. It turns out that any relation lying between two weak orders, one of which covers the other for inclusion, is an ac-order (albeit of a special kind). Every ac-order is bracketed in a natural way by two weak orders, one the maximum in the set of weak orders included in the ac-order, and the other minimal, but not necessarily the minimum, in the set of weak orders that include the ac-order. The family of ac-orders on a finite set with at least five elements is not well graded (in the sense of Doignon and Falmagne, 1997). However, such a family is both upgradable and downgradable, as every nonempty ac-order contains a pair whose deletion defines an ac-order on the same set, and for every ac-order which is not a chain, there is a pair whose addition gives an ac-order.     

Linear extension majority cycles on partial orders

Let P define a partial order on a set X of cardinalityn. A linear extensionL ofP is a linear order withP G L, and is the set of all linear extensions ofP. denotes that subset of withxLy forx, y X. A linear extension majority (LEM) relationM onX is defined byxMy if . Similarly,M is defined byxMy if . An LEM cycle exists if there arex, y, z X withxMyMzMx, and an LEM quasi-cycle exists ifxMyMzMx and the equality part of the definition ofM holds for exactly one pair in the triple. The study shows that no semiorders have LEM cycles or LEM quasi-cycles, and that every interval order has a maximal element under theM relation. LEM cycles and LEM quasi-cycles are also considered for partial orders with specific structures. Simulation is used to determine the relative likelihood with which LEM cycles and LEM quasi-cycles are observed when connected partial orders are generated at random by a specific procedure.Dr. Gehrlein's research was supported through a fellowship from the Center for Advanced Study of the University of Delaware.     

Fractional weak discrepancy and interval orders

The fractional weak discrepancywd_F(P) of a poset P=(V,?) was introduced in [A. Shuchat, R. Shull, A. Trenk, The fractional weak discrepancy of a partially ordered set, Discrete Applied Mathematics 155 (2007) 2227-2235] as the minimum nonnegative k for which there exists a function satisfying (i) if a?b then f(a)+1≤f(b) and (ii) if a∥b then |f(a)−f(b)|≤k. In this paper we generalize results in [A. Shuchat, R. Shull, A. Trenk, Range of the fractional weak discrepancy function, ORDER 23 (2006) 51-63; A. Shuchat, R. Shull, A. Trenk, Fractional weak discrepancy of posets and certain forbidden configurations, in: S.J. Brams, W.V. Gehrlein, F.S. Roberts (Eds.), The Mathematics of Preference, Choice, and Order: Essays in Honor of Peter C. Fishburn, Springer, New York, 2009, pp. 291-302] on the range of the wd_F function for semiorders (interval orders with no induced ) to interval orders with no , where n≥3. In particular, we prove that the range for such posets P is the set of rationals that can be written as r/s, where 0≤s−1≤r<(n−2)s. If wd_F(P)=r/s and P has an optimal forcing cycle C with and , then r≤(n−2)(s−1). Moreover when s≥2, for each r satisfying s−1≤r≤(n−2)(s−1) there is an interval order having such an optimal forcing cycle and containing no.     

Belief structures,weight generating functions and decision-making

We describe the Dempster–Shafer belief structure and provide some of its basic properties. We introduce the plausibility and belief measures associated with a belief structure. We note that these are not the only measures that can be associated with a belief structure. We describe a general approach for generating a class of measures that can be associated with a belief structure using a monotonic function on the unit interval, called a weight generating function. We study a number of these functions and the measures that result. We show how to use weight-generating functions to obtain dual measures from a belief structure. We show the role of belief structures in representing imprecise probability distributions. We describe the use of dual measures, other then plausibility and belief, to provide alternative bounding intervals for the imprecise probabilities associated with a belief structure. We investigate the problem of decision making under belief structure type uncertain. We discuss two approaches to this decision problem. One of which is based on an expected value of the OWA aggregation of the payoffs associated with the focal elements. The second approach is based on using the Choquet integral of a measure generated from the belief structure. We show the equivalence of these approaches.