1 Introduction

Ordering polytopes have been instrumental to the study of problems from a variety of fields including comparative probability (Anscombe et al. 1963; Chevyrev et al. 2013), computational social choice (Barthelemy and Monjardet 1981; Marley and Regenwetter 2016) and group decision-making (Marti and Reinelt 2011; Yoo and Escobedo 2021; Yoo et al. 2020). The derivation of facet defining inequalities (FDIs) for these polytopes is a focal point owing primarily to their usefulness in tackling challenging combinatorial optimization problems. For example, their implementation via branch-and-cut approaches has been cited as an effective solution methodology (e.g., see Coll et al. 2002; Grötschel and Wakabayashi 1990; Marti and Reinelt 2011). Such polyhedral studies have historically centered on the linear ordering polytope (e.g., see Bolotashvili et al. 1999; Fishburn 1992; Grötschel et al. 1985). In recent years, different classes of FDIs have been introduced for various other ordering polytopes (e.g., see Doignon and Fiorini 2001; Doignon and Rexhep 2016; Müller 1996; Oswald and Reinelt 2003), driven by a fundamental need to consider a broader range of ordinal relationships. For example, the incorporation of non-strict orderings (i.e., possibly containing ties) is regarded as a fundamental form of preference expression in various group decision-making applications (Yoo and Escobedo 2021).

There are many situations in which it is necessary to determine an ordering of all alternatives of a set \(N\,{:}{=}\,\{1,\dots ,n\}\) or, equivalently a complete ranking of n alternatives that best achieves a given objective. For instance, the objective of the consensus ranking problem is to find a ranking \({\varvec{r}}\in N^n\) that minimizes the cumulative distance to a set of input rankings \(\{{\varvec{a}}^k\}_{k=1}^{m}\), the latter of which typically represents a collection of evaluations of the alternatives provided by m sources. It is often prudent, if not necessary, to allow the consensus ranking (as well as the input rankings (Kendall 1945)) to contain ties for a myriad of reasons—e.g., contradictory information in the given evaluations, high cost of obtaining a strict linear ordering when more than a handful of alternatives are involved, etc. However, the universe of complete non-strict rankings is exceedingly large. This underscores the ongoing need to better characterize the weak order polytope, \(P_{\text {WO}}^n\), whose vertices are equivalent to the individual members of this set. Specifically, a weak order on N is defined as a binary relation that is reflexive, transitive, and total.

For the most part, FDIs of \(P_{\text {WO}}^n\) have been either obtained through enumeration approaches with specialized software or derived from known FDIs of other existing polytopes. The complete sets of FDIs for \(P_{\text {WO}}^{4}\) and \(P_{\text {WO}}^{5}\) listed in Fiorini and Fishburn (2004) and Regenwetter and Davis-Stober (2012) respectively, were generated using the Porta program (Christof et al. 1997). Furthermore, in Doignon and Fiorini (2001) certain members of the classes of 2-partition, 2-chorded cycle, 2-chorded path, and 2-chorded wheel FDIs (Grötschel and Wakabayashi 1990) of the partial order polytope \({P_{\text {PA}}^n}\) (also known as the clique partitioning polytope) were lifted into FDIs of \(P_{\text {WO}}^n\). This work introduces a new approach for deriving large classes of FDIs for \(P_{\text {WO}}^n\) from structural insights that are rooted in the connection between weak orders and complete non-strict rankings.

The main contributions of this work are as follows. We derive six large classes of valid inequalities (VIs) of \(P_{\text {WO}}^n\), for \(n\ge 4\). Each VI class is obtained by considering a relatively small number of ordinal relationship combinations, specifically the orderings of only up to two alternatives with one another and with an unspecified number of other alternatives, which are treated as a group. We prove that five of the six new large classes of VIs are FDIs. This is done by characterizing the weak orders that satisfy a VI at equality into a small number of ranking structures and then devising construction procedures that generate expedient sequences of affinely independent points from them. It is important to remark that each fixed value of n provides a VI expression that is not applicable in a dimension lower than n; in other words, the statement about the applicability of these FDI classes to any \(n\ge 4\) is not due to the Lifting Lemma (Fiorini and Fishburn 2004). In fact, we show that a number of FDIs previously obtained through enumeration are special cases of these large classes of FDIs. Lastly, we conjecture how the above contributions may be extended to derive numerous other large classes of VIs, many of which we expect to be FDIs.

The rest of this paper is organized as follows: Sect 2 introduces basic notation and definitions used throughout this work. Section 3 introduces six classes of valid inequalities of the weak order polytope, along with a description of the ranking structures whose members satisfy each inequality at equality. Section 4 introduces novel characteristic vector construction procedures, which are then utilized to demonstrate that five of the six aforementioned large classes of valid inequalities are facet defining for any \(n\ge 4\). Section 5 concludes with additional insights and two conjectures on how the fundamental insights herein presented may induce additional large classes of FDIs.

2 Notation, definitions, and other background concepts

Let \(N\,{:}{=}\,[n]\) be a set of alternatives or objects, where [n] is shorthand for the set \(\{1,\dots ,n\}\), and let \(\mathcal{A}^N\, {:}{=}\, \{(i,j): i,j\in N, i\ne j\}\) be the set of all possible ordered pairings on N. Let \(\mathcal W\) be the family of all weak orders on N. In certain related works, the elements of a weak order \(W\in \mathcal W\) are expressed as \(i\preceq j\) (i is not preferred over j). Without loss of generality, we describe the elements of W as \(i\succeq j\) (alternative i is preferred over or tied with j) and express this preference relation succinctly as the ordered pair (i, j). We do this primarily to help make the description of ranking structures more intuitive. Next, we introduce three different representations of W to be used throughout this paper.

Definition 1

The characteristic vector representation of \(W\in \mathcal W\) is typified by a vector \({\varvec{x}}^W\in \{0,1\}^{{\mathcal {A}}^N}\) whose entry \((i,j)\in {\mathcal {A}}^N\) is given by:

$$\begin{aligned} x^W_{(i,j)} = {\left\{ \begin{array}{ll} 1 &{}\quad \text {if } (i,j)\in W \\ 0 &{}\quad \text {otherwise}. \end{array}\right. } \end{aligned}$$

Definition 2

The (unique) ranking representation of \(W\in \mathcal W\) is typified by a vector \({\varvec{r}}^W\in N^n\) whose entry \(i\in N\) is given by:

$$\begin{aligned} \begin{aligned} r^W_i = n - \sum _{j\in N\backslash \{i\}} \mathbb {I}\left( i\succeq j\in W\right) =n-\sum _{(i,j)\in {\mathcal {A}}^N} x^W_{(i,j)}. \end{aligned} \end{aligned}$$

Definition 3

The alternative-ordering representation of \(W\in \mathcal W\) can be typified by a collection of nonempty subsets \(S_1^W,\dots ,S_p^W\subseteq N\) which forms a preference partition of N of size p, written as \(\{\{S_k^W\}_{k=1}^p\}_{\succeq }\), if:

  1. (a)

    \(S_k^W \cap S_{k'}^W=\emptyset \) for \(k\ne k'\);

  2. (b)

    \(S_1^W\cup S_2^W\cup \dots \cup S_p^W=N\);

  3. (c)

    \(i\approx j\) \(\forall i,j\in S_k^W\); \(i\succ j\) for \(i\in S_k^W, j\in S_{k'}^W \) where \(1\le k < k'\le p\);

where, for a pair of elements \(i,j\in N\), the expression \(``i\approx j''\) indicates that alternative i is tied with alternative j and \(``i\succ j''\) indicates that i is strictly preferred over j. Here, the kth subset of the partition (\(S_k^W\)), contains all alternatives in the kth bucket or equivalence class of W.

Stated otherwise, \(\{\{S_k^{W}\}_{k=1}^p\}_{\succeq }\) is an ordered set of sets. Its kth element, \(S_{k}^W\), contains alternatives that are all tied amongst themselves. An example application of the presented terminology is as follows.

Example 1

Let \(W=\{(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(4,3)\}\). The corresponding ranking is \({\varvec{r}}^W=(1,1,4,3)\); the rank of alternative 3 is \(r^W_3=4\). The corresponding alternative-ordering is \({\{\{S_k^W\}_{k=1}^3\}_{\succeq }}=\{\{1,2\},\{4\},\{3\}\}\); and the contents of bucket 2 are \(S_{2}^{W}=\{4\}\).

For notational convenience, when working with a collection of m weak orders, each \(W^w\in \mathcal W\) may be represented in abbreviated fashion as \({\varvec{x}}^w, {\varvec{r}}^w\), or \({\varvec{\{}}S^{w}{\varvec{\}}}\) for \(w=1,\ldots ,m\), when there is no ambiguity; the number of buckets is evident from the given context or is written as \(|{\varvec{\{}}S^{w}{\varvec{\}}}|\). Additionally, individual elements in the first two representations may be written as \(x^w_{(i,j)}\) and \(r^w_i\), respectively, for \(i,j\in N\), and individual subsets in the third may be written as \(S_{k}^{w}\) for \(k\le |{\varvec{\{}}S^{w}{\varvec{\}}}|\).

Next, we state a few relevant polyhedral theory concepts.

Definition 4

A polyhedron P is a subset of \(\mathbb {R}^n\) that can be described by a finite set of linear constraints as \(P=\{{\varvec{x}}:{\varvec{\pi }}{\varvec{x}}\le \pi _0\}\subseteq \mathbb {R}^n\).

Definition 5

The ordered pair \(({\varvec{\pi }},\pi _0)\) is a valid inequality (VI) for a polyhedron P if \({\varvec{\pi }}{\varvec{x}}\le \pi _0\) holds \(\forall {\varvec{x}}\in P\) or, equivalently, \(\max \{{\varvec{\pi }}{\varvec{x}}:{\varvec{x}}\in P\}\le \pi _0\).

Definition 6

The valid inequality \(({\varvec{\pi }},\pi _0)\) defines a facet of a polyhedron P if \(\emptyset \ne P\cap \{{\varvec{x}}:{\varvec{\pi }}{\varvec{x}}=\pi _0\}\ne P\) and if there exists \(\dim (P)\) affinely independent points in \(P\cap \{{\varvec{x}}:{\varvec{\pi }}{\varvec{x}}=\pi _0\}\), i.e., the dimension of the VI is \(\dim (P){\,-\,}1\).

Since \(P_{\text {WO}}^n\) has dimension \(n(n{\,-\,}1)\) (i.e., the polyhedron is full-dimensional), its facets have dimension \(n(n{\,-\,}1){\,-\,}1\) (Gurgel 1992). The FDIs of \(P_{\text {WO}}^n\) for \(n\ge 3\) that follow directly from the characteristic vector representation and the completeness and transitivity properties of a weak order are (Fiorini and Fishburn 2004):

$$\begin{aligned} x_{ij}&\le 1{} & {} i, j = 1,\ldots ,n;i \ne j \end{aligned}$$
(1a)
$$\begin{aligned} x_{ij} + x_{ji}&\ge 1{} & {} i, j = 1,\ldots ,n; i \ne j \end{aligned}$$
(1b)
$$\begin{aligned} x_{ij} - x_{ik} - x_{kj}&\ge -1{} & {} i, j, k = 1,\ldots ,n; i \ne j \ne k \ne i \end{aligned}$$
(1c)

where \(x_{ij}\) is used in place of \(x^W_{(i,j)}\) for visual simplification.

Later in this work, we refer to the FDIs of \(P_{\text {WO}}^{4}\), as categorized into nine classes \(WO_1\)–\(WO_9\) (Regenwetter and Davis-Stober 2008) in Table 1. For visual clarity, only nonzero coefficients of \(WO_i\) are displayed and the coordinates \((j_k,j_{k'})\) of each VI coefficient-vector \({\varvec{\pi }}\in \mathbb {R}^{4\times 3}\) are abbreviated as \(j_kj_{k'}\), for \((k,k')\in {\mathcal {A}}^4\).

The cardinality of \(WO_i\) in \(P_{\text {WO}}^{4}\), written in the rightmost table column as \(|WO^4_i|\), is obtained by counting the number of ways that the labels \(j_1,j_2,j_3,j_4\in [4]\) can be permuted within each expression. We remark that \(WO_1\)–\(WO_9\) can be reduced into just seven classes (Fiorini 2001; Fiorini and Fishburn 2004) by leveraging symmetries between \(WO_6\) and \(WO_7\) and between \(WO_8\) and \(WO_9\). In the list, \(WO_1\)–\(WO_3\) match Inequalities (1a)–(1c) and are known as the axiomatic inequalities, which comprise the full set of FDIs for \(P_{\text {WO}}^{3}\). They are also FDIs for \(n\ge 4\) due to the Lifting Lemma of Fiorini and Fishburn (2004) restated below for future reference.

Lemma 1

(Lifting Lemma (Fiorini and Fishburn 2004)) Let \(({\varvec{\pi }},\pi _0)\) be an FDI of \(P_{\text {WO}}^n\), and let \(\bar{{\varvec{\pi }}}\in \mathbb {R}^{(n+1)\times n}\) be defined by:

$$\begin{aligned} \bar{\pi }_{jj'} = {\left\{ \begin{array}{ll} \pi _{jj'} &{} \text { if } j,j'\in [n]: j\ne j',\\ 0 &{} \text { if } (j=n {{\, +\, }} 1,j'\in [n]) \text { or } (j\in [n],j'=n {{\, +\, }} 1). \end{array}\right. } \end{aligned}$$

Then, \((\bar{{\varvec{\pi }}},\pi _0)\) is an FDI of \(P_{\text {WO}}^{n+1}\).

Table 1 Facet defining inequalities \(({\varvec{\pi }},\pi _0)\) of \(P_{\text {WO}}^{4}\) and their cardinalities
Full size table

From the Lifting Lemma, \(WO_4\)–\(WO_9\) are FDIs for any \(n\ge 4\). Note that the total number of FDIs that can be generated from \(WO_4\)–\(WO_9\) in higher dimensions is greater than in \(P_{\text {WO}}^{4}\). Expressly, the number of these FDIs that can be generated in \(P_{\text {WO}}^n\) is given by:

$$\begin{aligned} \big |WO^n_i\big |=\left( {\begin{array}{c}n\\ 4\end{array}}\right) |WO^4_i|=\frac{n(n{\,-\,}1)(n{\,-\,}2)(n{\,-\,}3)}{24}\quad \big |WO^4_i\big |, \end{aligned}$$
(2)

where \(4\hspace{-.5mm}\le \hspace{-.5mm}i\hspace{-.5mm}\le \hspace{-.5mm}9\) and \(n\ge 4\). Stated otherwise, \(|WO^4_i|\) distinct FDIs from class \(WO^4_i\) can be generated for every combination of distinct indices \(j_1,j_2,j_3,j_4\in [n]\), each of which can be lifted into any higher dimension.

3 Constructing valid inequalities

This section introduces six new classes of VIs. For fixed dimension \({\hat{n}}\ge 4\), each class defines a set of VIs specific to \(P_{\text {WO}}^{{\hat{n}}}\), that is, no individual member of the specific VIs for dimension \({\hat{n}}\) is applicable in dimension \(n < \hat{n}\). While the VIs defined for \({\hat{n}}\) are also valid for \(n > {\hat{n}}\) owing to the Lifting Lemma, the applicability of the classes to any dimension \(n\ge 4\) is independent of lifting. Hence, the cardinality of each VI class is much larger than those of VIs \(WO_4\)–\(WO_9\), which will be elaborated in Sect. 5; therein, it will also be explained that the latter existing FDIs are in fact special cases of the featured VI classes.

Surprisingly, each of the featured large classes of VIs can be derived by considering only a small number of ordinal relationship combinations. Fig. 1 helps illustrate this insight with digraphs \(G=(N,{\mathcal {A}})\) that represent the left-hand side coefficients \({\varvec{\pi }}\) of each of the six classes of VIs, where \({{\mathcal {A}}}\subseteq {\mathcal {A}}^N\). Each node \(j\in N\) represents an alternative and the format of the arc between nodes \(j,j'\) represents the coefficient of \(x_{jj'}\); expressly, \(\pi _{jj'}=0,1,\) or \({\,-\,}1\) if there is no arc, a solid arc, or a dashed arc, respectively, from j to \(j'\). When \(\pi _{jj'}=\pi _{j'j}\ne 0\), a bidirectional arc of the appropriate kind is drawn between j and \(j'\) to represent arcs \((j,j')\) and \((j',j)\). Furthermore, a light gray node represents a “fixed” alternative \(i_1\in N\); a dark gray node represents a second fixed alternative \(i_2\in N\) (when applicable), with \(i_2\ne i_1\), and blank nodes represent the remaining “unfixed” alternatives \(N\backslash \{i_1\}\) or \(N\backslash \{i_1,i_2\}\), as applicable. Using this characterization, we categorize the featured VI classes as being of Type 1 or Type 2 (T1 or T2 for short) indicating the number of fixed alternatives in each expression; multiple classes of the same type are differentiated accordingly. Henceforth, the fixed alternative set is denoted as \(\hat{N}\), and the unfixed alternative set as \(\hat{N}^c\,{:}{=}\,N\backslash \hat{N}\) (the complement of \(\hat{N}\) in N). Additionally, i-indices are reserved for elements in \(\hat{N}\) while j-indices are used for elements of either \(\hat{N}^c\) or N, depending on the context. As an important note, although the shaded nodes in each digraph represent the actual number (one or two) of fixed alternatives, the six blank nodes represent a variable number of unfixed alternatives that grows with n—more specifically equal to \(n-|\hat{N}|\), for \(n\ge 4\).

Within each digraph depicted in Fig. 1, all arcs belonging to one of the following three sets have a uniform format (all are solid or all are dashed) and a uniform orientation (all point in the same direction or all are bidirectional): \({\mathcal {A}}^{\{i_1,j\}}\,{:}{=}\,\{(i_1,j),(j,i_1): j\in \hat{N}^c\}, {\mathcal {A}}^{\{i_2,j\}}{:}{=} \{(i_2,j),(j,i_2): j\in \hat{N}^c\}\), and \({\mathcal {A}}^{\{j,j'\}}{:}{=}\{(j,j'): j\in \hat{N}^c,j\ne j'\}\). In fact, the characteristics of the arcs belonging to the third set are the same across the six digraphs. In other words, even though each of the digraphs (i.e., VI classes) induces a distinctive mathematical expression for any \(n\ge 4\), their general forms are obtained from a small number of possible uniform-format and uniform-orientation options for \({\mathcal {A}}^{\{i_1,j\}}\) and \({\mathcal {A}}^{\{i_2,j\}}\), combined with the different arc choices between \(i_1\) and \(i_2\). For example, in Fig. 1c all arcs in \({\mathcal {A}}^{\{i_1,j\}}\) are solid and bidirectional, all arcs in \({\mathcal {A}}^{\{i_2,j\}}\) are dashed and directed from \(j\in \hat{N}^c\) to \(i_2\), and arc \((i_1,i_2)\) is solid (with no arc from \(i_2\) to \(i_1\)).

Fig. 1
figure 1

Digraphs representing coefficients \({\varvec{\pi }}\) of the six featured classes of valid inequalities

Full size image

The mathematical expressions and derivations of the T1 and T2 VI classes are given in the ensuing paragraphs. In each VI, all non-zero variable coefficients \(\pi _{jj'}\) are equal to either 1 or \({\,-\,}1\). Hence, the left-hand side of the VI is reexpressed as the difference between the selected positive arcs and the selected negative arcs from G, that is:

$$\begin{aligned} {\big \Vert {\varvec{x}}_+^{W}\big \Vert }-{\big \Vert {\varvec{x}}_{-}^{W}\big \Vert }\,{:}{=}\,\sum _{(j,j')\in {\mathcal {A}}_{+}}{\hspace{1mm}}x_{jj'}-\sum _{(j,j')\in {\mathcal {A}}_{-}}{\hspace{1mm}}x_{jj'}, \end{aligned}$$

where \({\mathcal {A}}_{+}\,{:}{=}\,\{(j,j')\in {\mathcal {A}}:\pi _{jj'}=1\}\), \({\mathcal {A}}_{-}\,{:}{=}\,\{(j,j')\in {\mathcal {A}}:\pi _{jj'}=-1\}\), \({\varvec{x}}_+^W\in \{0,1\}^{|{\mathcal {A}}_{+}|}\), \({\varvec{x}}_-^W\in \{0,1\}^{|{\mathcal {A}}_{-}|}\), and \(||\cdot ||\) is the L1-norm. The derivation of each VI centers on determining the value of \(\max \{\Vert {\varvec{x}}_+^{W}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W}\Vert \}\) in the left-hand side of the given expression, where \({\varvec{x}}_+^W\) and \({\varvec{x}}_-^W\) together must induce a weak ordering on N. The weak orders that achieve this maximum value are described and conveniently grouped into (non-strict) ranking structures. For completeness and clarity, the ranking structures are first described in mathematical notation in tables and then in words within the proof narratives. Each proof begins with an arbitrary weak order W, where the fixed alternatives (\(i_1\) in Theorem 1, and \(i_1\) and \(i_2\) in Theorems 2–6) are tied with a fixed number, \(t\ge 0\), of unfixed alternatives. For each possible value of t, the proof describes modifications to W that lead to one or more of ranking structures listed in the respective ranking structure table. Each set of modifications leads to some weak order \(W'\), i.e., corresponding to the enumerated ranking structures. The proofs then present constructive arguments as to why the value of \(\Vert {\varvec{x}}_+^{W'}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W'}\Vert \) is higher than that achieved by any other weak order. To facilitate understanding, readers are advised to refer to the corresponding digraphs in Fig. 1 while following the proofs.

Due to space limitations, some proofs are located in the “Appendix”. Accompanying examples of the weak order constructions described in the VI proofs are given in the Supplementary Materials.

Theorem 1

(T1 VI) Let \(\hat{N}=\{i_1\}\) be the fixed index set, where \(i_1\in N\), and let \(\hat{N}^c=N\backslash \hat{N}\). The following is a valid inequality for \(\textbf{P}^n_{WO}\), for any \(n\ge 4\):

$$\begin{aligned} \sum _{j\in \hat{N}^c}\left( x_{i_1j}+x_{ji_1}\right) -\hspace{-2mm}\sum _{j,j'\in \hat{N}^c: j\ne j'}\hspace{-2mm}x_{jj'}\le 2 - \frac{(n{\,-\,}2)(n{\,-\,}3)}{2}. \end{aligned}$$
(3)

Proof

The VI is satisfied at equality by the ranking structures listed in Table 2, which are justified as follows. The arc sets \({\mathcal {A}}_{+}\) and \({\mathcal {A}}_{-}\) are given by:

$$\begin{aligned} {\mathcal {A}}_{+}&=\{(i_1,j):j\in \hat{N}^c\} \cup \{(j,i_1):j\in \hat{N}^c\}, \\ {\mathcal {A}}_{-}&=\{(j,j'):j,j'\in \hat{N}^c, j\ne j'\}. \end{aligned}$$

Let W be an arbitrary weak order defined over the set of alternatives N, where alternative \(i_1\) is tied with exactly \(t\ge 0\) unfixed alternatives, \([j_1, j_t]\subseteq \hat{N}^c\), where \([j_1, j_t]\) is used as shorthand for the index set \(\{j_1,j_2,\ldots ,j_t\}\). The structure of the weak orders generated by different values of t can be encapsulated by the following four cases:

Case 1

(\(t=1\)) There are precisely n selected positive arcs, \(\Vert {\varvec{x}}_+^{W}\Vert \) (i.e., from \({\mathcal {A}}_{+}\)): 2 from the tie of \(i_1\) with an unfixed alternative, say \(j_1\), and \((n{\,-\,}2)\) from the strict ordering of \(i_1\) with each \(j\in \hat{N}^c\backslash \{j_1\}\). Now, break the ties (if any) between \(j,j'\in \hat{N}^c\backslash \{j_1\}\), where \(j \ne j'\), by removing either negative arc \((j,j')\) or negative arc \((j',j)\) from W; denote the generated weak order as \(W'\). This gives a total of \((n{\,-\,}1)(n{\,-\,}2)/2\) selected negative arcs (i.e., from \({\mathcal {A}}_{-}\)). Since this removal does not increase the value of \(\Vert {\varvec{x}}_-^{W}\Vert \) and keeps the value of \(\Vert {\varvec{x}}_+^{W}\Vert \) unchanged, we have that \(\Vert {\varvec{x}}_+^{W}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W}\Vert \le \Vert {\varvec{x}}_+^{W'}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W'}\Vert \). For any such weak order, equivalently characterized by ranking structure #1, the value of \(\Vert {\varvec{x}}_+^{W'}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W'}\Vert \) equals the right-hand side of inequality (3). Note that, since there must be at least one arc between every pair of alternatives to induce a total order, further reduction in negative arcs is not possible.

Case 2

(\(t=2\)) This case is addressed using the same arguments as in Case 1 by replacing \(\hat{N}^c\backslash \{j_1\}\) with \(\hat{N}^c\backslash \{j_1, j_2\}\); the generated weak order is defined by ranking structure \(\#2\).

Case 3

(\(t\ge 3\)) First, break the tie between \(\hat{j}\) and \(j_t\) by removing either arc \((\hat{j}, j_t)\) or arc \((j_t, \hat{j})\) from W, for each \(\hat{j}\in [j_1, j_{t{\,-\,}1}] \cup \{i_1\}\); denote the generated weak order as \(W_{t{\,-\,}1}\). Since this removal decreases the value of \(\Vert {\varvec{x}}_-^{W}\Vert \) and \(\Vert {\varvec{x}}_+^{W}\Vert \) by \((t{\,-\,}1)\ge 2\) and 1, respectively, we have that \(\Vert {\varvec{x}}_+^{W}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W}\Vert < \Vert {\varvec{x}}_+^{W_{t-1}}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W_{t-1}}\Vert \). Next, break the ties between each of \(\hat{j}\in [j_1, j_{t{\,-\,}2}]\cup \{i_1\}\) with \(j_{t{\,-\,}1}\) in \(W_{t {\,-\,}1}\) in a similar fashion to obtain a modified weak order, denoted as \(W_{t{\,-\,}2}\). Repeat this process until arriving at a weak order, denoted as \(W_2\), in which \(i_1\) is tied with exactly two unfixed alternatives \(j_1\) and \(j_2\). At this point, apply the results of Case 2 by setting \(W{:}{=}W_2\).

Table 2 List of ranking structures that satisfy T1 VI at equality
Full size table

Case 4

(\(t=0\)) Suppose that the rank of alternative \(i_1\) is fixed as \(r_{i_1}=k>0\). Let \([j_1, j_l]\subseteq \hat{N}^c\) denote those alternatives with rank r equal to \(k{\,-\,}1\) when \(k\ge 2\), or with rank r equal to \(k{\, +\, }1 =2\) when \(k=1\). Add to W arc \((i_1, \hat{j})\) in the former, and add to W arcs \((\hat{j}, i_1)\) in the latter, for each \(\hat{j}\in [j_1, j_l]\); denote the generated weak order in either case as \(W'\). Since these additions keep the value of \(\Vert {\varvec{x}}_-^{W}\Vert \) unchanged and increase the value of \(\Vert {\varvec{x}}_+^{W}\Vert \), we have that \(\Vert {\varvec{x}}_+^{W}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W}\Vert < \Vert {\varvec{x}}_+^{W'}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W'}\Vert \). At this point, apply the results of Cases 1–3 by setting \(W{:}{=}{W'}\). \(\square \)

Theorem 2

(T2-0 VI) Let \(\hat{N}=\{i_1,i_2\}\) be the fixed index set, where \(i_1,i_2\in N\) s.t. \(i_1\ne i_2\), and let \(\hat{N}^c=N\backslash \hat{N}\). The following is a valid inequality of \(\textbf{P}^n_{WO}\), for any \(n\ge 4\):

$$\begin{aligned} x_{i_2i_1}+\sum _{j\in \hat{N}^c}\left( x_{i_1j}+x_{ji_2}\right) -x_{i_1i_2} -\hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-2mm}x_{jj'}\le 2 - \frac{(n{\,-\,}4)(n{\,-\,}5)}{2}. \end{aligned}$$
(4)
Table 3 List of ranking structures that satisfy T2-0 VI at equality
Full size table

Proof

The VI is satisfied at equality by the ranking structures listed in Table 3. Because the VI is only an FDI for \(n=4\) (see Sect. 5), the remainder of the proof is relegated to “Appendix A.1”. \(\square \)

Theorem 3

(T2-1 VI) Let \(\hat{N}=\{i_1,i_2\}\) be the fixed index set, where \(i_1,i_2\in N\) s.t. \(i_1\ne i_2\), and let \(\hat{N}^c=N\backslash \hat{N}\). The following is a valid inequality of \(\textbf{P}^n_{WO}\), for any \(n\ge 4\):

$$\begin{aligned} x_{i_1i_2}+\sum _{j\in \hat{N}^c}\left( x_{i_1j}+x_{ji_1}\right) {\hspace{2mm}}-\hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-2mm}\left( x_{jj'}+x_{ji_2}\right) \le 2 - \frac{(n{\,-\,}3)(n{\,-\,}4)}{2}. \end{aligned}$$
(5)

Proof

The VI is satisfied at equality by the ranking structures listed in Table 4, which are justified as follows. The arc sets \({\mathcal {A}}_{+}\) and \({\mathcal {A}}_{-}\) are given by:

$$\begin{aligned} {\mathcal {A}}_{+}&=\{(i_1,i_2)\}\cup \{(i_1,j):j\in \hat{N}^c\} \cup \{(j,i_1):j\in \hat{N}^c\}, \\ {\mathcal {A}}_{-}&=\{(j,i_2):j\in \hat{N}^c\}\cup \{(j,j'):j,j'\in \hat{N}^c, j\ne j'\}. \end{aligned}$$

Let W be an arbitrary weak order defined over the set of alternatives N, where the fixed alternatives \(i_1\) and \(i_2\) are tied with exactly \(t_1\ge 0\) and \(t_2\ge 0\) unfixed alternatives, respectively, such that \(t_1 + t_2 \le n{\,-\,}2\). Now suppose that the ranks of these alternatives are fixed as \(r_{i_1}=k_1>0\) and \(r_{i_2}=k_2>0\). Additionally, let \(\hat{N}^c_{<k_1}\subseteq \hat{N}^c\) denote the set of unfixed alternatives with rank \(r< r_{i_1}\), and \(\hat{N}^c_{<k_2}\subseteq \hat{N}^c\) denote the set of unfixed alternatives with rank \(r'< r_{i_2}\). Note that, \(\hat{N}^c_{<k_1}\cap \hat{N}^c_{<k_2} =\emptyset \) only when either \(\hat{N}^c_{<k_1} =\emptyset \) or \(\hat{N}^c_{<k_2} =\emptyset \) or both. The structure of the weak orders generated by the different values of \(t_1\) and \(t_2\) can be encapsulated by the following cases:

Case 1

(\(t_1=0, t_2=0\)) For each \(\hat{j}\in \hat{N}^c_{<k_1}\), replace positive arc \((\hat{j},i_1)\) with positive arc \((i_1,\hat{j})\) and for each \(\hat{j'}\in \hat{N}^c_{<k_2}\), replace negative arc \((\hat{j'},i_2)\) with zero arc \((i_2,\hat{j'})\) to obtain a weak order where alternatives \(i_1\) and \(i_2\) are placed in front of all \(j\in \hat{N}^c\). Additionally, if \(k_1 > k_2\), replace zero arc \((i_2, i_1)\) with positive arc \((i_1, i_2)\) to place alternative \(i_1\) in front of \(i_2\). This gives precisely \(n{\,-\,}1\) selected positive arcs: 1 from the relative position of \(i_1\) with \(i_2\) and \(n{\,-\,}2\) from the strict ordering of \(i_1\) with each unfixed alternative. Next, break the ties (if any) between \(j,j'\in \hat{N}^c\), where \(j \ne j'\), by removing either negative arc \((j,j')\) or negative arc \((j',j)\) from W; denote the generated weak order as \(W'\). This gives a total of \((n{\,-\,}3)(n{\,-\,}2)/2\) selected negative arcs. Since all preceding operations neither increase the value of \(\Vert {\varvec{x}}_-^{W}\Vert \) nor decrease the value of \(\Vert {\varvec{x}}_+^{W}\Vert \), we have that \(\Vert {\varvec{x}}_+^{W}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W}\Vert \le \Vert {\varvec{x}}_+^{W'}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W'}\Vert \). For any such weak order, equivalently characterized by either ranking structure #1, if \(k_1 \ne k_2\), or ranking structure #2, if \(k_1 = k_2\), the value of \(\Vert {\varvec{x}}_+^{W'}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W'}\Vert \) equals the right-hand side of inequality (5).

Case 2

(\(t_1=1, t_2=0\)) Let \(j_1\in \hat{N}^c\) denote the unfixed alternative tied with \(i_1\) in rank position \(k_1\). Based on the relative values of \(k_1\) and \(k_2\), the generated weak order can be further divided into the following two sub-cases:

  • Case 2a (\(k_1>k_2\)) For each \(\hat{j'}\in \hat{N}^c_{<k_2}\), replace negative arc \((\hat{j'},i_2)\) with zero arc \((i_2,\hat{j'})\) to obtain a weak order where alternative \(i_2\) is uniquely in first place. Next, break the ties (if any) between \(j,j'\in \hat{N}^c\backslash \{j_1\}\), where \(j \ne j'\), by removing either negative arc \((j,j')\) or negative arc \((j',j)\) from W; denote the generated weak order as \(W'\). Since these removals do not increase the value of \(\Vert {\varvec{x}}_-^{W}\Vert \) and keep the value of \(\Vert {\varvec{x}}_+^{W}\Vert \) unchanged, we have that \(\Vert {\varvec{x}}_+^{W}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W}\Vert \le \Vert {\varvec{x}}_+^{W'}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W'}\Vert \). Here, \(W'\) is a member of ranking structure #5.

  • Case 2b (\(k_1\le k_2\)) For each \(\hat{j}\in \hat{N}^c_{<k_1}\), replace positive arc \((\hat{j}, i_1)\) with positive arc \((i_1, \hat{j})\) and negative arc \((\hat{j}, j_1)\) with negative arc \((j_1, \hat{j})\) in W. Additionally, for each \(\hat{j'}\in \hat{N}^c_{<k_2}\backslash \{j_1\}\), replace negative arc \((\hat{j'},i_2)\) with zero arc \((i_2,\hat{j'})\) to obtain a weak order where alternatives \(i_1\), \(j_1\), and \(i_2\) are placed in front of each \(j\in \hat{N}^c\backslash \{j_1\}\). Next, break the ties (if any) between \(j,j'\in \hat{N}^c\backslash \{j_1\}\), where \(j \ne j'\), by removing either negative arc \((j,j')\) or negative arc \((j',j)\) from W; denote the generated weak order as \(W'\). Since all preceding operations neither increase the value of \(\Vert {\varvec{x}}_-^{W}\Vert \) nor decrease the value of \(\Vert {\varvec{x}}_+^{W}\Vert \), we have that \(\Vert {\varvec{x}}_+^{W}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W}\Vert \le \Vert {\varvec{x}}_+^{W'}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W'}\Vert \). Here, \(W'\) is a member of ranking structure #3, if \(k_1 < k_2\), or #4, if \(k_1 = k_2\).

Table 4 List of ranking structures that satisfy T2-1 VI at equality
Full size table

Case 3

(\(t_1\ge 2, t_2=0\)) Let \([j_1, j_{t_1}]\subseteq \hat{N}^c\) denote the set of unfixed alternatives tied with \(i_1\) in rank position \(k_1\). First, break the tie between \(\hat{j}\) and \(j_{t_1}\) by removing arc \((j_{t_1}, \hat{j})\) from W, for each \(\hat{j}\in \{i_1\}\cup [j_{1}, j_{t_1{\,-\,}1}]\) (if \(k_1=k_2\), \(\hat{j}\in \{i_1, i_2\}\cup [j_{1}, j_{t_1{\,-\,}1}]\)); denote the generated weak order as \(W_{t_1 {\,-\,}1, 0}\). Since this removal decreases the value of \(\Vert {\varvec{x}}_-^{W}\Vert \) and \(\Vert {\varvec{x}}_+^{W}\Vert \) by at least \((t_1{\,-\,}1)\ge 1\) and at most 1, respectively, we have that \(\Vert {\varvec{x}}_+^{W}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W}\Vert \le \Vert {\varvec{x}}_+^{W_{t_1 {\,-\,}1, 0}}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W_{t_1 {\,-\,}1, 0}}\Vert \). Next, break the ties between each of \(\hat{j}\in \{i_1\}\cup [j_{1}, j_{t_1{\,-\,}2}]\) (if \(k_1=k_2\), \(\hat{j}\in \{i_1, i_2\}\cup [j_{1}, j_{t_1{\,-\,}2}]\)) with \(j_{t_1{\,-\,}1}\) in \(W_{t_1 {\,-\,}1, 0}\) in a similar fashion to obtain a modified weak order, denoted as \(W_{t_1 {\,-\,}2, 0}\). Repeat this process until arriving at a weak order, denoted as \(W_{2,0}\), in which \(i_1\) is tied with exactly two unfixed alternatives \(j_1\) and \(j_2\). Afterwards, we consider the following two sub-cases:

  • Case 3a (\(k_1>k_2\)) This case is addressed using the same arguments as in Case 2a by replacing \(\hat{N}^c\backslash \{j_1\}\) with \(\hat{N}^c\backslash \{j_1, j_2\}\); the generated weak order is a member of ranking structure #6.

  • Case 3b (\(k_1\le k_2\)) The ties between each of \(i_1\) and \(j_1\) (if \(k_1=k_2\), between each of \(i_1\), \(i_2\), and \(j_1\)) with \(j_2\) in \(W_{2,0}\) are further broken to obtain a modified weak order, denoted as \(W_{1, 0}\), in which \(i_1\) is tied with exactly one unfixed alternative \(j_1\) (if \(k_1=k_2\), \(i_1\) and \(i_2\) are tied with \(j_1\)). At this point, apply the results of Case 2b by setting \(W{:}{=}W_{1, 0}\).

Case 4

(\(t_2\ge 1\)) Let \([j_1, j_{t_2}]\subseteq \hat{N}^c\) denote the unfixed alternatives tied with \(i_2\) in rank position \(k_2\). This case is addressed using the same arguments as in Case 3 by replacing \(\{i_1\}\cup [j_1, j_{t'{\,-\,}1}]\) with \(\{i_2\}\cup [j_1, j_{t'{\,-\,}1}]\) in each step, where \(t'=t_2, t_2{\,-\,}1,\ldots ,0\). In the generated weak order, denoted as \(W_{t_1,0}\), \(i_2\) is not tied with any unfixed alternatives. At this point, apply the results of Cases 1–3 by setting \(W\,{:}{=}\,W_{t_1,0}\).

\(\square \)

Theorem 4

(T2-2 VI) Let \(\hat{N}=\{i_1,i_2\}\) be the fixed index set, where \(i_1,i_2\in N\) s.t. \(i_1\ne i_2\), and let \(\hat{N}^c=N\backslash \hat{N}\). The following is a valid inequality of \(\textbf{P}^n_{WO}\), for any \(n\ge 4\):

$$\begin{aligned} x_{i_2i_1}+\sum _{j\in \hat{N}^c}\left( x_{i_1j}+x_{ji_1}\right) -\hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-2mm}\left( x_{jj'}+x_{i_2j}\right) \le 2 - \frac{(n{\,-\,}3)(n{\,-\,}4)}{2}. \end{aligned}$$
(6)

Proof

The above inequality is satisfied at equality by six ranking structures that are symmetric images of those listed in Table 4. That is, those alternatives set to the best and second-best available ranking positions in the T2-1  structures are set to the last and second-to-last available positions, respectively, in the T2-2  structures. Alternatives occupying the remaining inferior positions in the T2-1  structures occupy the remaining superior positions in the T2-2  structures. Hence, a string of arguments paralleling the proof of Theorem 3 establishes that these ranking structures achieve a value of \(\max \{\Vert {\varvec{x}}_+^{W'}\Vert \hspace{-.5mm}-\hspace{-.5mm}\Vert {\varvec{x}}_-^{W'}\Vert \}\) equal to the right-hand side of inequality (6) and all others achieve a lower value. \(\square \)

Table 5 List of ranking structures that satisfy T2-3 VI at equality
Full size table

Theorem 5

(T2-3 VI) Let \(\hat{N}=\{i_1,i_2\}\) be the fixed index set, where \(i_1,i_2\in N\) s.t. \(i_1\ne i_2\), and let \(\hat{N}^c=N\backslash \hat{N}\). The following is a valid inequality of \(\textbf{P}^n_{WO}\), for any \(n\ge 4\):

$$\begin{aligned} \sum _{j\in \hat{N}^c}\left( x_{i_1j}+x_{ji_1}+x_{i_2j}\right) -x_{i_2 i_1}-\hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-2mm}x_{jj'}\le 3 - \frac{(n{\,-\,}4)(n{\,-\,}5)}{2}. \end{aligned}$$
(7)

Proof

The VI is satisfied at equality by the ranking structures listed in Table 5. The remainder of the proof can be found in “Appendix A.2”. \(\square \)

Theorem 6

(T2-4 VI) Let \(\hat{N}=\{i_1,i_2\}\) be the fixed index set, where \(i_1,i_2\in N\) s.t. \(i_1\ne i_2\), and let \(\hat{N}^c=N\backslash \hat{N}\). The following is a valid inequality of \(\textbf{P}^n_{WO}\) for any \(n\ge 4\):

$$\begin{aligned} \sum _{j\in \hat{N}^c}\left( x_{i_1j}+x_{ji_1}+x_{ji_2}\right) -x_{i_1 i_2}-\hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-2mm}x_{jj'}\le 3 - \frac{(n{\,-\,}4)(n{\,-\,}5)}{2}. \end{aligned}$$
(8)

Proof

The result can be obtained using a nearly identical line of reasoning as the proof to Theorem 4, with the difference that the T2-4 VI ranking structures are the symmetric images of the T2-3 VI ranking structures (see Table 5). \(\square \)

To conclude this section, it is worth restating that Fig. 1 depicts only a small number of the possible format and orientation choices for \({\mathcal {A}}^{\{i_1,j\}}, {\mathcal {A}}^{\{i_2,j\}}\), and the arcs that join the fixed alternatives. Fig. 1a is only 1 of 7 possible digraphs for the case with \(|\hat{N}|=1\) and Fig. 1b–e are only 5 of 343 possible digraphs for the case with \(|\hat{N}|=2\). While additional T1 and T2 VIs could be constructed for the omitted combinations using similar constructive arguments, these would likely be equivalent to or dominated by one of the featured VIs. Indeed, as Sect. 5 demonstrates, T2-0  is an FDI only for \(n=4\), while T1  and T2-1  to  T2-4  are FDIs for all \(n\ge 4\). It remains an open question whether some of the omitted digraphs represent FDIs for some \(n>4\) even though they are not FDIs for \(n=4\). Moreover, it remains an open question whether expanding the techniques from this section to cases with \(|\hat{N}|\ge 3\) (i.e., T3 VIs, T4 VIs, etc.) can produce FDIs of \(P_{\text {WO}}^n\) for some or all \(n\ge 5\). These inquiries are formalized into conjectures in Sect. 5.

4 Constructing facet defining inequalities

To obtain the dimensionality of the faces induced by the T1 and T2 VIs, we first devise systematic processes for selecting members of their respective ranking structures such that simple patterns of linearly independent characteristic vectors are formed. The key idea is to select these so that consecutive pairs of vectors differ minimally, thereby simplifying the respective proofs.

4.1 Building block procedures

Assume that alternatives \(i\in I\) belong to bucket k of alternative-ordering \({\varvec{\{}}S^{w}{\varvec{\}}}\), that is, \(I\subseteq S_{k}^{w}\), where \(1\le k\le p=|{\varvec{\{}}S^{w}{\varvec{\}}}|\). Additionally, define a step parameter \(q\in \mathbb {Q}\), where \({\,-\,}k< q < p{\,-\,}k{\, +\, }1\), \(q=t/2\), and \(t\in \mathbb {Z}\).

Definition 7

A move of q steps of I in \({\varvec{\{}}S^{w}{\varvec{\}}}\) is an operation that yields an alternative-ordering in which all \(i\in I\) are removed from their current bucket k and either merged with the alternatives in bucket \(k{\, +\, }q\), when \(q\in \mathbb {Z}\), or separated into a new bucket inserted immediately after (before, resp.) bucket \(\lfloor k{\, +\, }q \rfloor \) (\(\lceil k{\, +\, }q \rceil \), resp.), when \(q\notin \mathbb {Z}\) is positive (negative, resp.). The operation is abbreviated as the triple \(\left<I,q,{\varvec{\{}}S^{w}{\varvec{\}}}\right>\).

Example 2

Consider five different move operations and their outputs:

  1. 1.

    \(\left<\{2\},1,\{\{1,2\},\{4\},\{3\}\}\right>\)\(\,=\,\{\{1\},\{2,4\},\{3\}\}\)

  2. 2.

    \(\left<\{2,4\},-1,\{\{1\},\{2,4\},\{3\}\}\right>\)\(\,=\,\{\{1,2,4\},\{3\}\}\)

  3. 3.

    \(\left<\{3\},-2,\{\{1,2\},\{4\},\{3\}\}\right>\)\(\,=\,\{\{1,2,3\},\{4\}\}\)

  4. 4.

    \(\langle \{1,3\},\frac{3}{2},\{\{1,2,3\},\{4\}\}\rangle \)\(\,=\,\{\{2\},\{4\},\{1,3\}\}\)

  5. 5.

    \(\langle \{3\},\frac{-5}{2},\{\{1,2\},\{4\},\{3\}\}\rangle \)\(\,=\,\{\{3\},\{1,2\},\{4\}\}.\)

As the example shows, move operations can be used to change not only the contents of a bucket for a given alternative-ordering, but also the ordering and total number of buckets. For instance, the second move operation merges the entire contents of buckets 1 and 2. Additionally, the output alternative-ordering in the third move operation has one fewer bucket than the input alternative-ordering, since the bucket where alternative 3 resides contains only one alternative and \(q\in \mathbb {Z}\); the reverse holds for the fourth move operation since the bucket where alternatives 1 and 3 reside contains three alternatives and \(q\notin \mathbb {Z}\).

The Merge and Reverse Construction Procedure (M &R), whose pseudocode is given in Algorithm 1, is at the core of the characteristic vector constructions. It begins with an alternative-ordering \({\varvec{\{}}S^{0}{\varvec{\}}}\) with p buckets (associated with a weak ordering \(W^0\in \mathcal W\)), and proceeds to iteratively merge and then reverse adjacent buckets in \({\varvec{\{}}S^{0}{\varvec{\}}}\), generating potential characteristic vectors from each related move operation. To be more precise, the pseudocode displays a shell of the M &R procedure, which can be customized by incorporating optional steps that allow certain alternatives to move more freely between buckets.

Algorithm 1
figure a

Merge and Reverse Construction Procedure (M &R) (Shell)

Full size image

Example 3

Let \({\varvec{\{}}S^{0}{\varvec{\}}}=\{\{1,2\},\{3\},\{4\},\{5\}\}\), \(I^0=\{1\}\) and \({\hat{p}} = 4\); here, \(S_{1}^{0}=\{1,2\}\), \(S_{2}^{0}=\{3\},S_{3}^{0}=\{4\},S_{4}^{0}=\{5\}\), and \(p=4\). Additionally, define the jth optional outer step (pseudocode line 15) for the M &R as:

$$\begin{aligned} {\varvec{\{}}S^{1}{\varvec{\}}} \leftarrow \left<I^0,j{\,-\,}p,{\varvec{\{}}S^{1}{\varvec{\}}}\right> \end{aligned}$$
(9)

Put simply, the optional outer step moves alternative 1 to the first bucket of \({\varvec{\{}}S^{1}{\varvec{\}}}\) after each execution of the inner for-loop. Performing M &R(\({\varvec{\{}}S^{0}{\varvec{\}}}\), \(I^0\), \({\hat{p}}\)) with this optional outer step produces the following sequence of alternative-orderings:

$$\begin{aligned} \begin{aligned} \begin{array}{ll||c|c|c} j &{}{}k &{}{} Merge &{}{}Reverse &{}{}jth{\hspace{1mm}}Outer{\hspace{1mm}}Step\\ \hline 1 &{}{}1 &{}{}\{\{{\textbf {1,2}},3\},\{4\},\{5\}\} &{}{}\{\{3\}\{{\textbf {1,2}}\},\{4\},\{5\}\}&{}{}-\\ 1 &{}{}2 &{}{}\{\{3\}\{{\textbf {1,2}},4\},\{5\}\} &{}{}\{\{3\},\{4\},\{{\textbf {1,2}}\},\{5\}\}&{}{}-\\ 1 &{}{}3 &{}{}\{\{3\},\{4\},\{{\textbf {1,2}},5\}\} &{}{}\{\{3\},\{4\},\{5\},\{{\textbf {1,2}}\}\}&{}{} \{\{1,3\},\{4\},\{5\},\{2\}\} \\ 2 &{}{}1 &{}{}\{\{{\textbf {1,3}},4\},\{5\},\{2\}\} &{}{}\{\{4\},\{{\textbf {1,3}}\},\{5\},\{2\}\}&{}{}-\\ 2 &{}{}2 &{}{}\{\{4\},\{{\textbf {1,3}},5\},\{2\}\} &{}{}\{\{4\},\{5\},\{{\textbf {1,3}}\},\{2\}\} &{}{} \{\{1,4\},\{5\},\{3\},\{2\}\}\\ 3 &{}{}1 &{}{}\{\{{\textbf {1,4}},5\},\{3\},\{2\}\} &{}{}\{\{5\},\{{\textbf {1,4}}\},\{3\},\{2\}\}&{}{}\{\{1,5\},\{4\},\{3\},\{2\}\}\\ \end{array} \end{aligned} \end{aligned}$$

where the numbers in bold are the members of \(I^1\) at iteration j. Here, M &R directly returns 12 characteristic vectors for the weak orders under the “Merge” and “Reverse” columns, which are then appended to matrix X. As a point of emphasis, the optional outer steps serve primarily an auxiliary purpose of setting up \({\varvec{\{}}S^{1}{\varvec{\}}}\) between iterations; characteristic vectors may or may not be stored from their respective weak orders.

Theorem 7

Let \({\varvec{x}}^1,\dots ,{\varvec{x}}^{{\hat{p}}({\hat{p}}{\,-\,}1)}\in \{0,1\}^{n(n{\,-\,}1)}\) denote the \({\hat{p}}({\hat{p}}{\,-\,}1)\) characteristic vectors generated by the non-optional steps of M &R(\({\varvec{\{}}S^{0}{\varvec{\}}}, I^0, {\hat{p}}\)), where \(p=|{\varvec{\{}}S^{0}{\varvec{\}}}|\) and \({\hat{p}}\le p\le n\); let \({\varvec{x}}^0\in \{0,1\}^{n(n{\,-\,}1)}\) denote the corresponding characteristic vector for \({\varvec{\{}}S^{0}{\varvec{\}}}\); and assume that these vectors occupy rows \(1,\dots ,{\hat{p}}({\hat{p}}{\,-\,}1)\) and \({\hat{p}}({\hat{p}}{\,-\,}1){\, +\, }1\), respectively, of \({\varvec{X}}\in \{0,1\}^{m\times n(n{\,-\,}1)}\), with \(m\ge {\hat{p}}({\hat{p}}{\,-\,}1){\, +\, }1\). Additionally, let \(\{j_k\}_{k=1}^{p}\) represent a set of alternative indices, one from each bucket in \({\varvec{\{}}S^{0}{\varvec{\}}}\), which are not permitted to move during the optional outer steps of M &R; that is, \(j_k\in S_{k}^{0}\) with \(j_k\notin I^0\), for \(k\in [p]\). Independent of the optional outer steps performed subject to this restriction, M &R yields at least \({\hat{p}}({\hat{p}}{\,-\,}1){\, +\, }1\) affinely independent characteristic vectors.

Proof

Assume that \({\hat{p}} = p\) in M &R. The proof focuses on the elements \((j,j')\in {\mathcal {A}}^N\) such that \(j,j'\in \{j_k\}_{k=1}^{p}\). Restricted to these elements, each pair of consecutively generated alternative-orderings differs only in that two alternatives that are in the same bucket in one ordering are in separate adjacent buckets in the other ordering. Stated otherwise, in each successive move operation, \((p{\,-\,}2)\) of the alternatives from \(\{j_k\}_{k=1}^{p}\) retain their ordinal relationships. After subtracting \({\varvec{x}}^{i{\,-\,}1}\) from \({\varvec{x}}^i\), for \(i=p(p{\,-\,}1),\dots ,1\), a submatrix \( \bar{X}_{M \& R}\in \{0,{\,-\,}1,1\}^{[p(p{\,-\,}1){\, +\, }1]\times p(p{\,-\,}1)}\) can be extracted from X having the following entry pattern:

(10)

where the 0-row (corresponding to \({\varvec{x}}^0\)) is placed at the bottom to highlight the convenient structure of this submatrix—expressly, the first \( p(p{\,-\,}1)\) rows contain all the possible elementary vectors of size \(p(p{\,-\,}1)\), times \(\pm 1\). Next, add the rows with nonzero even indices to row 0 to yield the all-zeros vector, \({\varvec{0}}\), of size \({p(p{\,-\,}1)}\), and let \( {\varvec{\bar{X}}}_{M \& R}'\) be the resulting submatrix. Now, since the rows of the augmented matrix \( [{\varvec{\bar{X}}}_{M \& R}'{\hspace{1mm}}{\varvec{1}}]\) are linearly independent, where \({\varvec{1}}\) is the all-ones column vector of size \( p(p{\,-\,}1){\, +\, }1\), the characteristic vectors \({\varvec{x}}^0,{\varvec{x}}^1\dots ,{\varvec{x}}^{ p( p{\,-\,}1)}\) are affinely independent. Lastly, when \({\hat{p}} < p\), the resulting matrix \( {\varvec{\bar{X}}}_{M \& R}\) that is extracted from the characteristic vectors generated by subroutine M &R(\({\varvec{\{}}S^{0}{\varvec{\}}}, I^0, {\hat{p}}\)) is contained within the larger matrix obtained with subroutine M &R(\({\varvec{\{}}S^{0}{\varvec{\}}}, I^0, p\)) and, thus, the \({\hat{p}}({\hat{p}}{\,-\,}1){\, +\, }1\) characteristic vectors produced must also be affinely independent. \(\square \)

4.2 Facet constructions and proofs

The presented construction procedures iteratively generate individual characteristic vectors so that they fall into the respective ranking structures of a VI class and differ minimally from preceding vectors (or from other specific reference vectors). These procedures are simplified with the incorporation of M &R subroutines, which are used to generate a large portion of the needed \(n(n{\,-\,}1)\) affinely independent vectors; the remaining vectors are generated to yield other convenient patterns. The respective M &R subroutines differ in their definition of the optional outer step of the jth inner loop; the shorthand statement used to represent a specific M &R variant in the pseudocode is:

$$ \begin{aligned} \text {M} \& \text {R}(S, I, \hat{p}){\hspace{1mm}}{\varvec{\vert }}{\hspace{1mm}}j\text {th optional outer step defined by} (\#) \end{aligned}$$

where (#) denotes a set of algorithmic expressions. The characteristic vectors are stored in a matrix \({\varvec{X}}\in {\mathbb {R}}^{n(n{\,-\,}1)\times n(n{\,-\,}1)}\). Each row of \({\varvec{X}}\) is obtained by converting an alternative-ordering \(\{S\}\) into its characteristic vector, which is represented in the pseudocode by the operation \({\varvec{X}}.append(toBinary(\{S\}))\).

Each FDI proof begins with a difference matrix \(\bar{{\varvec{X}}}\in {\mathbb {R}}^{n(n{\,-\,}1)\times n(n{\,-\,}1)}\) that reflects the dissimilarities between (mostly) consecutively generated vectors in \({\varvec{X}}\); the precise entries of each difference matrix are described in the “Appendix”. Row operations are applied to show that \(\bar{{\varvec{X}}}\) is non-singular or, equivalently, that the characteristic vectors are linearly (and affinely) independent. A salient feature of these proofs is that, by leveraging the characteristic vector patterns devised within each construction procedure, proving the non-singularity of \(\bar{{\varvec{X}}}\) reduces to showing the non-singularity of a symbolic \(4\,\times \,4\) matrix. For the reader’s convenience, numerical examples of the step-by-step matrix operations described within each proof are included in the Supplementary Materials.

The remainder of this subsection will introduce different construction procedures and demonstrate that five of the six featured VI classes are FDIs for any \(n\ge 4\). It will also explain why the remaining class is an FDI only for \(n=4\). Only one of the FDI proofs is shown within the body of the paper. The others are similar in structure and are located in the “Appendix” due to length considerations. Next, the construction procedure used to show that T1 VI is an FDI is presented in Algorithm 2; an example of this procedure is also included.

Example 4

Perform CPT1(5, 1) via Algorithm 2, with \(j_1=2,j_2=3,j_3=4,j_4=5\) (and \(i_1=1\)). With these values, line 2 of Algorithm 2 initializes \({\varvec{\{}}S^{0}{\varvec{\}}}\) to the starting weak order from Example 3, and line 4 yields the 12 characteristic vectors for the weak orders under the “Merge” and “Reverse” columns therein (i.e., these are the direct outputs of the M &R subroutine). Line 5 yields the weak order from the last M &R outer step of Example 3—assigned to \({\varvec{\{}}S^{1}{\varvec{\}}}\) in line 4—as the 13th characteristic vector. Through a sequence of move operations that start from \({\varvec{\{}}S^{1}{\varvec{\}}}\), Lines 6–9 yield the next three characteristic vectors and Lines 10–13 three more after that; finally, line 14 yields the initial weak order as the 20th characteristic vector. These last seven weak orders are as follows:

$$\begin{aligned} \begin{array}{ll} \{\{4\},\{1,5\},\{3\},\{2\}\}, \\ \{\{4\},\{3\},\{1,5\},\{2\}\}, \\ \{\{4\},\{3\},\{2\},\{1,5\}\}, \\ \{\{4\},\{3\},\{1,2\},\{5\}\}, \\ \{\{4\},\{1,3\},\{2\},\{5\}\}, \\ \{\{1,4\},\{3\},\{2\},\{5\}\},\\ \{\{1,2\},\{3\},\{4\},\{5\}\}. \end{array} \end{aligned}$$
Algorithm 2
figure b

Construction Procedure for Type 1 VI (CPT1)

Full size image

Theorem 8

(T1  FDI) T1 VI is an FDI of \(\textbf{P}^n_{WO}\), for any \(n\ge 4\).

Proof

It is straightforward to verify that each row of \({\varvec{X}}\) output by CPT1  belongs to the ranking structures listed in Table 2.

For ease of exposition, fix \(i_1=1\) and \(j_k=k{\, +\, }1\), for \(k=1,\dots ,n{\,-\,}1\) (or assume a corresponding relabeling of the alternatives is performed a priori). To begin, set \(\bar{{\varvec{X}}}\) as the matrix obtained after iteratively subtracting row \(i{\,-\,}1\) from row i, for \(i=n(n{\,-\,}1){\,-\,}1,\dots ,2\), and also subtracting row \(i=n(n{\,-\,}1)\) from row 1 of \({\varvec{X}}\); see “Appendix 2” for a full characterization of \(\bar{{\varvec{X}}}\). To proceed with row operations, define \({\varvec{A}}^0\in {\mathbb {R}}^{n(n{\,-\,}1)\times n(n{\,-\,}1)}\) and set this matrix with the elements of \(\bar{X}\), such that, all comparisons between \(j,j'\in \hat{N}^c=N\backslash \{1\}\) appear in the first \((n{\,-\,}1)(n{\,-\,}2)\) columns, and the elements involving the comparison of alternative 1 with \(j\in \hat{N}^c\) show up in the last \(2(n{\,-\,}1)\) columns. The columns of \(\bar{{\varvec{X}}}\) and \({\varvec{A}}^0\) are further organized as in Eq. (10); that is, odd columns follow a lexicographical ordering of the respective arcs and even columns have the reverse indexing of the preceding odd columns. Next, add the first \((n{\,-\,}1)(n{\,-\,}2)/2\) even-index rows to row \(n(n{\,-\,}1)\) (i.e., the initial weak order) and partition the resulting matrix, \({\varvec{A}}^1\), as follows:

$$\begin{aligned} {\varvec{A}}^1=\left[ \begin{array}{cc} {\varvec{B}}^1 &{}\quad {\varvec{D}}^1 \\ {\varvec{C}}^1 &{}\quad {\varvec{E}}^1 \end{array}\right] \end{aligned}$$
(11)

where \({\varvec{B}}^1\hspace{-1mm}\in \mathbb {Z}^{(n{\,-\,}1)(n{\,-\,}2)\times (n{\,-\,}1)(n{\,-\,}2)}\hspace{-1mm}, {\varvec{C}}^1\hspace{-1mm}\in \mathbb {Z}^{(2n{\,-\,}2)\times (n{\,-\,}1)(n{\,-\,}2)}\hspace{-1mm}, {\varvec{D}}^1\hspace{-1mm}\in \mathbb {Z}^{(n{\,-\,}1)(n{\,-\,}2)\times (2n{\,-\,}2)}\), and \({\varvec{E}}^1\hspace{-1mm}\in \mathbb {Z}^{(2n{\,-\,}2)\times (2n{\,-\,}2)}\). The pertinent entries of the four submatrices are as follows. First, \({\varvec{B}}^1\) consists of all but the last row of the \( {\varvec{\bar{X}}}_{M \& R}\) submatrix [Eq. (10) with \(p=n{\,-\,}1\)], which implies that \(|\det (B^1)|=1\). \({\varvec{C}}^1\) is mostly a zero matrix, with the exception of row i whose values under columns \((n{\,-\,}i{\, +\, }1,n)\) and \((n,n{\,-\,}i{\, +\, }1)\) are 1 and \({\,-\,}1\), respectively, for \(i=2,\dots ,n{\,-\,}1\). Although \({\varvec{D}}^1\) has a more intricate structure than \({\varvec{B}}^1\) and \({\varvec{C}}^1\), it is only necessary to know the contents of a subset of rows aligned with those rows in \({\varvec{B}}^1\) that will be used to turn \({\varvec{C}}^1\) into a zero matrix. Expressly, each nonzero row i of \({\varvec{C}}^1\) is eliminated to yield an all-zero matrix \({\varvec{C}}^2\) by adding to it the two consecutive elementary vectors from \({\varvec{B}}^1\) with the opposite signs under columns \((n{\,-\,}i{\, +\, }1,n)\) and \((n,n{\,-\,}i{\, +\, }1)\); call them k(i) and \(k(i){\, +\, }1\). Rows k(i) and \(k(i){\, +\, }1\) of \({\varvec{D}}^1\) have a 1 under column (n, 1) and a \(-\,1\) under column (1, n) respectively with no other nonzero entries, for \(i=3,\dots ,n{\,-\,}1\). For, \(i=2\), row k(i) of \({\varvec{D}}^1\) has \(-\,1\), 1, and 1 under columns \((n{\,-\,}2,1)\), \((1,n{\,-\,}1)\), and (1, n), respectively, and no other nonzero entries; row \(k(i){\, +\, }1\) of \({\varvec{D}}^1\) has \(-\,1\) under column (1, n) and no other nonzero entries. Finally, \({\varvec{E}}^1\) is comprised primarily of a ‘wraparound staircase’ structure of nonzeros, illustrated as follows:

figure c

\({\varvec{E}}^1\)’s rows align with rows \((n{\,-\,}1)(n{\,-\,}2){\, +\, }1,\dots ,n(n{\,-\,}1)\) of \(\bar{{\varvec{X}}}\), which correspond to the characteristic vectors generated following the M &R subroutine. We remark that in addition to having a 1 under each of its first two columns, row \(2n{\,-\,}2\) of \({\varvec{E}}^1\) has a decreasing sequence of consecutive negative integers under columns (1, j), for \(j=4,\dots ,n\). Based on the above explanations, after eliminating the nonzero elements of \({\varvec{C}}^1\) using the aforementioned rows from \({\varvec{B}}^1\) (and \({\varvec{D}}^1\)), \({\varvec{E}}^1\) changes into \({\varvec{E}}^2\), given by:

figure d

Now, since \({\varvec{C}}^2\) is a zero matrix, \(|\det ({\varvec{A}}^1)|=|\det ({\varvec{B}}^1)\det ({\varvec{E}}^2)|=|\det ({\varvec{E}}^2)|\) and, therefore, we can operate exclusively on \({\varvec{E}}^2\) from this point. First, eliminate the nonzero entries along row \(2n{\,-\,}2\), one by one, from column (1, 2) to column \((n{\,-\,}2,1)\) by adding to row \(2n{\,-\,}2\) a multiple of some row i, where \(3\hspace{-.5mm}\le \hspace{-.5mm}i\hspace{-.5mm}\le \hspace{-.5mm}2n{\,-\,}3\). Specifically, beginning with row \(i=n\), alternate between a row with index \(i\le n\) and a row with index \(i>n\) to select each succeeding pivot row. Note that in each such elimination step, there is only one pivot element available from the designated row-index subset to eliminate the next nonzero entry from row \(2n{\,-\,}2\), whose value may have been modified by the previous elimination steps. For \(4\hspace{-.5mm}\le j\hspace{-.5mm}<\hspace{-.5mm}n\), the sequence value under column (1, j) remains intact until the nonzero under column \((j{\,-\,}1,1)\) (the column immediately to the left of (1, j)) is eliminated; the latter has a value equal to \(1{\,-\,}\sum _{k=1}^{j-3}k\), that is, the sum of the preceding negative integers in the sequence, plus one. Second, subtract row \(2n{\,-\,}3\) (the penultimate row) from row 2 and add rows 3 to \(2n{\,-\,}4\) to row \(2n{\,-\,}3\). Upon completion of these row operations, the resulting matrix \({\varvec{E}}^3\) possesses the following form:

figure e

where

$$\begin{aligned} \alpha= & {} {\,-\,}n{\, +\, }3;\hspace{5mm}\beta =1-\sum _{k=1}^{n-4}k=\frac{-(n{\,-\,}3)^2+n-1}{2};\\ \gamma= & {} -(n{\,-\,}3)-1-\sum _{l=1}^{n{\,-\,}5}\left( 1-\sum _{k=1}^{l}k\right) =\frac{(n{\,-\,}4)^3-13n+46}{6}. \end{aligned}$$

Two further points to remark on the structure of \({\varvec{E}}^3\) are that columns (1, 2) to \((n{\,-\,}2,1)\) do not have nonzeros along rows \(1,2,2n{\,-\,}3,2n{\,-\,}2\) and that the submatrix comprised of these \(2n{\,-\,}6\) columns together with rows 3 to \(2n{\,-\,}4\) forms a basis—indeed, beginning with column \((1,n{\,-\,}1)\), each column can be iteratively added to the left-adjacent column to yield unique elementary columns. Therefore, the first \(2n{\,-\,}6\) columns can be used to eliminate the nonzero entries along rows 3 to \(2n{\,-\,}4\) of columns \((1,n{\,-\,}1),(n{\,-\,}1,1),(1,n),(n,1)\), without impacting the other four rows. Thus, the task of proving the non-singularity of \({\varvec{E}}^3\) reduces to proving the non-singularity of the following \(4\hspace{-.5mm}\times \hspace{-.5mm}4\) submatrix induced from its last four columns and first/last two rows:

$$\begin{aligned} \left[ \begin{array}{cccc} \,\,\,0 &{}\quad {\,-\,}1 &{} \quad 1 &{}\quad 0 \\ {\,-\,}1 &{}\quad 1 &{}\quad 0 &{} \quad 0 \\ \,\,\,1 &{}\quad 0 &{}\quad \alpha &{}\quad {\hspace{1mm}}{\,-\,}\alpha {\,-\,}1\\ \,\,\,\beta &{}\quad 0 &{}\quad \gamma &{}\quad {\hspace{1mm}}\alpha {\,-\,}\gamma {\, +\, }1 \end{array}\right] . \end{aligned}$$

The symbolic determinant of this matrix is \({\,-\,}\alpha ^2{\,-\,}\alpha \beta {\,-\,}2\alpha {\,-\,}\beta {\,-\,}1\), which equals 0 if

$$\begin{aligned} \alpha= & {} {\,-\,}1\Leftrightarrow {\,-\,}n{\, +\, }3={\,-\,}1\Leftrightarrow n=4 \text {, or when}\\ \alpha= & {} {\,-\,}\beta {\,-\,}1\Leftrightarrow {\,-\,}n{\, +\, }3={\,-\,}\frac{n^2{\,-\,}7n+10}{2}{\,-\,}1\Leftrightarrow n=\frac{5}{2}\pm \frac{\sqrt{17}}{2}\notin \mathbb {Z}. \end{aligned}$$

Hence, for \(n\ge 5\), the \(n(n{\,-\,}1)\) characteristic vectors produced by CPT1  are linearly independent, which implies they are also affinely independent. Lastly, it is straightforward to verify that setting \(n=4\) in the T1 VI expression yields \(WO_4\), which was shown to be facet-defining in Fiorini and Fishburn (2004) using the Porta program (Christof et al. 1997). Therefore T1 VI is an FDI for any \(n\ge 4\). \(\square \)

Next, we describe why T2-0 VI is an FDI for \(n=4\) but not \(n\ge 5\). Since \(P_{\text {WO}}^n\) is full dimensional, the rank of the characteristic vectors generated by any construction procedure must be at least \(n(n{\,-\,}1){\,-\,}1\). Because the maximum number of affinely independent weak orders on N that do not contain ties is approximately half of this value, this means that a significant fraction of the generated vectors must contain ties. It can be seen in Table 3, however, that the placement of ties is limited to rankings with a two-way tie with alternative \(i_1\) for first position (#2 & #4) and rankings with a two way-tie with alternative \(i_2\) for last position (#3 & #4). When \(n=4\), enough affinely independent vectors can be drawn from the four T2-0 VI ranking structures to form a facet—in fact, it is straightforward to verify that substituting this value of n in T2-0 VI expression yields \(WO_5\). However, as n becomes larger, they do not add up to a sufficiently large fraction. Through enumeration of the weak orders that satisfy the given ranking structures, we verified for many n that the rank of the resulting matrix is far lower than \(n(n{\,-\,}1)\); for example, for \(n=6\), the rank is 15 (i.e., half the required number). Therefore, T2-0 VI is not an FDI for \(n\ge 5\).

The construction procedure used to generate characteristic vectors for T2-1 VI is given in Algorithm 3, where the jth optional outer step for the respective M &R subroutine is defined as:

$$\begin{aligned}&{\varvec{\{}}S^{1}{\varvec{\}}} \leftarrow \bigl <i_2,\frac{_3}{^2},{\varvec{\{}}S^{1}{\varvec{\}}}\bigr > \end{aligned}$$
(12a)
$$\begin{aligned}&{\varvec{\{}}S^{1}{\varvec{\}}} \leftarrow \left<i_1,j{\,-\,}p,{\varvec{\{}}S^{1}{\varvec{\}}}\right> \end{aligned}$$
(12b)
$$\begin{aligned}&{\varvec{X}}{.{append}({toBinary}}({\varvec{\{}}S^{1}{\varvec{\}}})). \end{aligned}$$
(12c)

Theorem 9

(T2-1 FDI) T2-1 VI is an FDI of \(\textbf{P}^n_{WO}\), for any \(n\ge 4\).

Proof

It is straightforward to verify that all points output by CPT2-1  correspond to the characteristic vectors associated with the six ranking structures that satisfy inequality (5) at equality. The remainder of the proof can be found in “Appendix B.2”. \(\square \)

Theorem 10

(T2-2 FDI) T2-2 VI is an FDI of \(\textbf{P}^n_{WO}\), for any \(n\ge 4\).

Proof

It is evident from the proof of Theorem 4 that the applicable characteristic vectors associated with the ranking structures that satisfy inequality (6) at equality are symmetric images of those output by CPT2-1. Therefore, an almost identical set of arguments used in the proof of Theorem 9 establishes that inequality (6) is an FDI for \(n\ge 4\). \(\square \)

A comparison of Tables 4 and 5 reveals that the only ranking structure from Table 4 that does not satisfy valid inequality T2-3  is #2, in which two fixed alternatives are tied for the first position and the unfixed alternatives are strictly ordered to occupy positions 2 to \(n{\,-\,}1\). The characteristic vector that represents ranking structure #2 from Table 4 is generated by line 7 of the pseudocode(CPT2-1), after which a number of move operations are performed to generate a vector representing structure #3 from the same table. Hence, certain modifications to lines 7–11 are needed to make the construction procedure applicable to the ranking structures associated with T2-3 VI. These modifications are as follows. First, after Line 6, move the second fixed alternative, \(i_2\), one step to the right to generate a ranking representative of structure #2 in Table 5. Second, break the tie between alternatives \(i_2\) and \(j_1\) created by the previous step by first moving \(i_2\) a half step to the right and then shifting \(i_1\) one step to the right to tie it with \(j_1\); this generates a ranking representative of structure #3 in Table 5. The above changes can be encapsulated by replacing lines 7–11 of Algorithm 3 with the following algorithmic expressions:

$$\begin{aligned} \begin{aligned}&\text{ Line } 7'\,\,\,:&{\mathbf {\{}}S^{0}{\mathbf {\}}} \leftarrow \bigl<i_2,1,{\mathbf {\{}}S^{0}{\mathbf {\}}}\bigr> \\ {}&\text{ Line } 8'\,\,\,:&{\textbf{X}}.{{append}({toBinary}}({\mathbf {\{}}S^{0}{\mathbf {\}}})) \\ {}&\text{ Line } 9'\,\,\,:&{\mathbf {\{}}S^{0}{\mathbf {\}}} \leftarrow \bigl<i_2,\frac{_1}{^2},{\mathbf {\{}}S^{0}{\mathbf {\}}}\bigr> \\ {}&\text{ Line } 10':&{\mathbf {\{}}S^{0}{\mathbf {\}}}\leftarrow \bigl <i_1,1,{\mathbf {\{}}S^{0}{\mathbf {\}}}\bigr > \\ {}&\text{ Line } 11':&{\textbf{X}}.{{append}({toBinary}}({\mathbf {\{}}S^{0}{\mathbf {\}}})) \end{aligned} \end{aligned}$$
Algorithm 3
figure f

Construction Procedure for Type 2-1 VI (CPT2-1)

Full size image

Theorem 11

(T2-3 FDI) T2-3 VI is an FDI of \(\textbf{P}^n_{WO}\), for \(n\ge 4\).

Proof

The proof is similar to that of Theorem 9 and can be found in “Appendix B.3”. \(\square \)

Theorem 12

(T2-4 FDI) T2-4 VI is an FDI of \(\textbf{P}^n_{WO}\), for any \(n\ge 4\).

Proof

This theorem is proved by using a string of arguments similar to the proof of Theorem 10, with the difference that the applicable characteristic vectors are symmetric images of those generated by the algorithm used to establish that inequality (7) is facet defining for \(n\ge 4\). \(\square \)

5 Additional insights and conjectures

We begin this section by discussing how the featured VIs yield FDIs \(WO_4\)–\(WO_9\) (see Sect. 2) as a special case. By fixing \(n=4\) in each expression, it is straightforward to verify that VI T1 yields FDI \(WO_4\), while VIs T2-0, T2-1, and T2-2 correspond to FDIs \(WO_5\), \(WO_6\), and \(WO_7\), respectively; finally VI T2-3 induces FDI \(WO_9\) and VI T2-4 induces FDI \(WO_8\). According to this correspondence, \(O(n^4)\) FDIs can be generated from this single variant of each featured VI in a higher dimension n [see Eq. (2)]. On that note, it is important to elaborate on how the featured VI classes provide a distinctive expression for each setting of \(n\ge 4\). To see this, we present the expressions for T1 VI for \(n=4,5\), with \(i_1=1\) as the fixed alternative:

$$\begin{aligned}{} & {} x_{12}+x_{21}+x_{13}+x_{31}+x_{14}+x_{41}-x_{23}-x_{32}-x_{24}-x_{42}-x_{34}-x_{43} \le 1. \nonumber \\ \end{aligned}$$
(13a)
$$\begin{aligned}{} & {} x_{12}+x_{21}+x_{13}+x_{31}+x_{14}+x_{41}-x_{23}-x_{32}-x_{24}-x_{42}-x_{34}-x_{43}\nonumber \\{} & {} \quad +x_{15}+x_{51}-x_{25}-x_{52}-x_{35}-x_{53}-x_{45}-x_{54} \le -1. \end{aligned}$$
(13b)

Although the first 12 terms of the left-hand side of Eq. (13b) mirror the left-hand side of Eq. (13a), neither of the two inequalities dominates the other. Specifically, for a VI \(({\varvec{\pi }}, \pi _0)\) to be dominated by a VI \(({\varvec{\pi '}}, \pi '_0)\), the relationships \({\varvec{\pi '}} \ge \mu {\varvec{\pi }}\) and \(\pi '_0 \le \mu \pi _0\) must hold, for some scalar \(\mu >0\), with at least one of the two inequalities holding in the strict sense. For the two above inequalities, we have that \(\pi '_0=-1< 1=\pi _0\)—choosing \(\mu =1\) since the coefficients of the variables that do not involve alternative index \(j=5\) already match. However, the left-hand side terms related to \(j=5\) are both \({\, +\, }1\) and \({\,-\,}1\) in Eq. (13b), while they are all zero-valued in Eq. (13a), implying that \({\varvec{\pi '}} \not \ge \mu {\varvec{\pi }}\). In general, as n increases, the right-hand side will get smaller. Conversely, on the left-hand side, the coefficients of some newly added variables will become smaller than 0, and the coefficient of other newly added variables will become larger than 0 (hence, the incomparability will hold for any \(\mu >0\)). Similar arguments can be applied to all of the T2 VIs. Therefore, for each of these large VI classes, each fixed value \({\hat{n}}\ge 4\) yields a distinctive VI that does not dominate or is dominated by another member of the same class in a lower dimension.

Since a distinctive set of FDIs can be generated from VIs T1, T2-1, T2-2, T2-3, and T2-4 for any fixed dimension \({\hat{n}}\ge 4\), the number of FDIs that can be generated from these new classes of FDIs is very large. Specifically, the total number of FDIs that can be generated from VI class of Type i in dimension n is given by:

$$\begin{aligned} \big |WO^n_{Ti}\big |=\sum _{\hat{n}=4}^n\big |WO^{{\hat{n}}}_{Ti}\big |=\sum _{\hat{n}=4}^n \left( {\begin{array}{c}n\\ \hat{n}\end{array}}\right) \left( {\begin{array}{c}\hat{n}\\ i\end{array}}\right) i! =n!\sum _{\hat{n}=4}^n \frac{1}{(n-\hat{n})!({\hat{n}}-i)!}. \end{aligned}$$
(14)

That is, each of the five VI classes generates O(n!) FDIs in dimension n.

We conclude the paper by stating two conjectures related to how the insights herein presented may induce many more large classes of FDIs.

Conjecture 13

Let \(\hat{N}=\{i_1,i_2, i_3\}\) be the fixed index set, where \(i_1,i_2, i_3\in N\) s.t. \(i_1\ne i_2\ne i_3\) and let \(\hat{N}^c=N\backslash \hat{N}\). The following are T3 VIs and FDIs of \(\textbf{P}^n_{WO}\), for any \(n\ge 5\):

$$\begin{aligned}{} & {} \begin{aligned}{}&{} x_{i_1i_2} + x_{i_3i_2} + \sum _{j\in \hat{N}^c} ( x_{i_1j} +x_{ji_1} + x_{i_3j} + x_{ji_3} ) - x_{i_1i_3} - x_{i_3i_1} \\{}&{} \hspace{30mm} - \hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-5mm}\left( x_{jj'} + x_{ji_2}\right) \le 4 - \frac{(n{\,-\,}5)(n{\,-\,}6)}{2} \end{aligned} \end{aligned}$$
(15a)
$$\begin{aligned}{} & {} \begin{aligned}{}&{} x_{i_2i_1} + x_{i_2i_3} + \sum _{j\in \hat{N}^c}(x_{i_1j} +x_{ji_1} + x_{i_3j} + x_{ji_3}) - x_{i_1i_3} - x_{i_3i_1} \\{}&{} \hspace{30mm} - \hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-5mm}\left( x_{jj'} + x_{i_2j}\right) \le 4 - \frac{(n{\,-\,}5)(n{\,-\,}6)}{2} \end{aligned} \end{aligned}$$
(15b)
$$\begin{aligned}{} & {} \begin{aligned}{}&{} x_{i_1i_3} + x_{i_2i_3} + \sum _{j\in \hat{N}^c} (x_{i_1j} + x_{ji_1} + x_{i_2j} + x_{ji_2}) - x_{i_1i_2} - x_{i_2i_1} \\{}&{} \hspace{30mm} - \hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-5mm}\left( x_{jj'} + x_{ji_3}\right) \le 4 - \frac{(n{\,-\,}5)(n{\,-\,}6)}{2} \end{aligned} \end{aligned}$$
(15c)
$$\begin{aligned}{} & {} \begin{aligned}{}&{} x_{i_3i_1} + x_{i_3i_2} + \sum _{j\in \hat{N}^c} (x_{i_1j} +x_{ji_1} + x_{i_2j} + x_{ji_2}) - x_{i_1i_2} - x_{i_2i_1} \\{}&{} \hspace{30mm} - \hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-5mm}\left( x_{jj'} + x_{i_3j}\right) \le 4 - \frac{(n{\,-\,}5)(n{\,-\,}6)}{2} \end{aligned} \end{aligned}$$
(15d)
$$\begin{aligned}{} & {} \begin{aligned}{}&{} \sum _{j\in \hat{N}^c}\left( x_{i_1j}+x_{ji_1} +x_{ji_2} + x_{i_3j} + x_{ji_3}\right) - x_{i_1i_2} - x_{i_1i_3} - x_{i_3i_1} - x_{i_3i_2} \\{}&{} \hspace{30mm} - \hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-5mm}x_{jj'} \le 5 - \frac{(n{\,-\,}6)(n{\,-\,}7)}{2} \end{aligned} \end{aligned}$$
(15e)
$$\begin{aligned}{} & {} \begin{aligned}{}&{} \sum _{j\in \hat{N}^c}\left( x_{i_1j}+x_{ji_1} +x_{i_2j} + x_{i_3j} + x_{ji_3}\right) - x_{i_2i_1} - x_{i_1i_3} - x_{i_3i_1} - x_{i_2i_3} \\{}&{} \hspace{30mm} - \hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-5mm}x_{jj'} \le 5 - \frac{(n{\,-\,}6)(n{\,-\,}7)}{2} \end{aligned} \end{aligned}$$
(15f)
$$\begin{aligned}{} & {} \begin{aligned}{}&{} \sum _{j\in \hat{N}^c}(x_{i_1j}+x_{ji_1} + x_{i_2j} + x_{ji_2} + x_{ji_3}) - x_{i_1i_2} - x_{i_2i_1} - x_{i_1i_3} - x_{i_2i_3} \\{}&{} \hspace{30mm} - \hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-5mm}x_{jj'} \le 5 - \frac{(n{\,-\,}6)(n{\,-\,}7)}{2} \end{aligned} \end{aligned}$$
(15g)
$$\begin{aligned}{} & {} \begin{aligned}{}&{} \sum _{j\in \hat{N}^c}(x_{i_1j}+x_{ji_1} + x_{i_2j} + x_{ji_2} + x_{i_3j}) - x_{i_1i_2} - x_{i_2i_1} - x_{i_3i_1} - x_{i_3i_2} \\{}&{} \hspace{30mm} - \hspace{-2mm}\sum _{j,j'\in \hat{N}^c:j\ne j'}\hspace{-5mm}x_{jj'} \le 5 - \frac{(n{\,-\,}6)(n{\,-\,}7)}{2} \end{aligned} \end{aligned}$$
(15h)

This conjecture was conceived as a two-step process. In the first step, the following binary programming problem was solved for all possible format and orientation choices of arcs that join only the fixed alternatives (i.e., \(\{i_1,i_2,i_3\}=\hat{N}\)) combined with the possible format and orientation choices of arc sets \({\mathcal {A}}^{\{i_1,j\}}, {\mathcal {A}}^{\{i_2,j\}}, {\mathcal {A}}^{\{i_3,j\}}\) (where \(j\in \hat{N}^c\) is an unfixed alternative index):

$$\begin{aligned} \text {max } \sum _{(i,j)\in {\mathcal {A}}_{+}}{\hspace{1mm}}x_{ij}-\sum _{(i,j)\in {\mathcal {A}}_{-}}{\hspace{1mm}}x_{ij}&\\ \text {st. }\qquad \qquad \text {Constraints }(1a){-}(1c)&\\ x_{ij} \in \{0,1\}&\qquad \qquad \qquad i,j\in N; i\ne j. \end{aligned}$$

These format and orientation choices determine the contents of the sets \({\mathcal {A}}_{+}\) and \({\mathcal {A}}_{-}\); we remark that the characteristics of the arcs that join only the unfixed alternatives, namely \({\mathcal {A}}^{\{j,j'\}}\,{:}{=}\,\{(j,j'): j\in \hat{N}^c,j\ne j'\}\), were set to the constant format and orientation as the six digraphs given in Fig. 1 (all dashed and bidirectional). In general, the above binary program can be defined for a specific number of fixed alternatives and solved for various values of n so as to deduce a generalizable expression. The objective function provides an algebraic expression for the left-hand side of a VI, while the sequence of numerical objective function values obtained from solving for consecutive values of n are analyzed to derive an algebraic expression for its right-hand side.

The second step to conceive the above conjecture involved verifying that the VIs generated in the first step are FDIs for at least a few values of n. This was done by enumerating all characteristic vectors that satisfy each inequality in (15) at equality and verifying that these vectors induce a matrix of rank \(n(n{\,-\,}1)\), for \(5\le n \le 10\). Hence, the above conjecture is true for at least these values. It remains to show that the result will hold for any \(n\ge 11\). Proving this using the techniques introduced in this work would require introducing new construction procedures for each VI, followed by additional formal proofs (which would likely be even more protracted). Hence, it is left for future work.

Conjecture 14

Let, \(\hat{N}=\{i_1,i_2\ldots i_k\}\) be a subset of \(N=[n]\), where \(k\le n{\,-\,}2\) and \(i_1,i_2\ldots i_k \in N\) s.t. \(i_1\ne i_2\ldots \ne i_k\). By fixing these \(|\hat{N}|\) alternatives, new large classes of FDIs that incorporate at least one variable from each pair of alternatives in N can be obtained using the insights presented in this work.

Verification of Conjecture 14 could lead to the development of new techniques for deriving numerous new large classes of FDIs. Each such class would define a set of FDIs specific to \(P_{\text {WO}}^{{\hat{n}}}\), that is, no individual member of the FDIs specific to dimension \({\hat{n}}\) would be defined in dimension \(q < \hat{n}\). As such, the FDIs would require the involvement of all alternative pairs on \({\hat{N}}\). Conversely, when using the Lifting Lemma to generate FDIs of \(P_{\text {WO}}^{{\hat{n}}}\) from FDIs of \(P_{WO}^{q}\), only the alternative pairs from a smaller set are utilized—for example, from \({\hat{N}}\backslash \{q{\, +\, }1,q{\, +\, }2,\dots ,{\hat{n}}\}\).