# Predicting Online Item-Choice Behavior: A Shape-Restricted Regression Approach
## 4 PV Sequence Model
### Partially Ordered Sets  
Let \(U\subseteq\Gamma\) be a subset of PV sequences. The image of each operation is then defined as  
\[\texttt{Up}(U) =\{\texttt{Up}(\mathbf{u},s)\mid\mathbf{u}\in U,\;(\mathbf{u},s)\in\mathcal{ D}_{\mathbb{U}}\},\] \[\texttt{Move}(U) =\{\texttt{Move}(\mathbf{u},s,t)\mid\mathbf{u}\in U,\;(\mathbf{u},s,t)\in \mathcal{D}_{\mathbb{H}}\},\] \[\texttt{Swap}(U) =\{\texttt{Swap}(\mathbf{u},s,t)\mid\mathbf{u}\in U,\;(\mathbf{u},s,t)\in \mathcal{D}_{\mathbb{S}}\}.\]  
We define \(\texttt{UM}(U):=\texttt{Up}(U)\cup\texttt{Move}(U)\) for \(U\subseteq\Gamma\). The following definition states that the binary relation \(\mathbf{u}\prec_{\texttt{UM}}\mathbf{v}\) holds when \(\mathbf{u}\) can be transformed into \(\mathbf{v}\) by the repeated application of Up and Move:  
**Definition 4** (\(\preceq_{\texttt{UM}}\)).: _Suppose \(\mathbf{u},\mathbf{v}\in\Gamma\). We write \(\mathbf{u}\prec_{\texttt{UM}}\mathbf{v}\) if and only if there exists \(k\geq 1\) such that_  
\[\mathbf{v}\in\texttt{UM}^{k}(\{\mathbf{u}\})=\underbrace{\texttt{UM}\circ\cdots\circ \texttt{UM}\circ\texttt{UM}}_{k\text{ compositions}}(\{\mathbf{u}\}).\]  
_We also write \(\mathbf{u}\preceq_{\texttt{UM}}\mathbf{v}\) if \(\mathbf{u}\prec_{\texttt{UM}}\mathbf{v}\) or \(\mathbf{u}=\mathbf{v}\)._  
Similarly, we define \(\texttt{US}(U):=\texttt{Up}(U)\cup\texttt{Swap}(U)\) for \(U\subseteq\Gamma\). Then, the binary relation \(\mathbf{u}\prec_{\texttt{US}}\mathbf{v}\) holds when \(\mathbf{u}\) can be transformed into \(\mathbf{v}\) by the repeated application of Up and Swap.  
**Definition 5** (\(\preceq_{\texttt{US}}\)).: _Suppose \(\mathbf{u},\mathbf{v}\in\Gamma\). We write \(\mathbf{u}\prec_{\texttt{US}}\mathbf{v}\) if and only if there exists \(k\geq 1\), such that_  
\[\mathbf{v}\in\texttt{US}^{k}(\{\mathbf{u}\})=\underbrace{\texttt{US}\circ\cdots\circ \texttt{US}\circ\texttt{US}}_{k\text{ compositions}}(\{\mathbf{u}\}).\]  
_We also write \(\mathbf{u}\preceq_{\texttt{US}}\mathbf{v}\) if \(\mathbf{u}\prec_{\texttt{US}}\mathbf{v}\) or \(\mathbf{u}=\mathbf{v}\)._  
To prove properties of these binary relations, we can use the lexicographic order, which is a well-known linear order [55]:  
**Definition 6** (\(\preceq_{\texttt{lex}}\)).: _Suppose \(\mathbf{u},\mathbf{v}\in\Gamma\). We write \(\mathbf{u}\prec_{\texttt{lex}}\mathbf{v}\) if and only if there exists \(s\in[1,n]\), such that \(u_{s}<v_{s}\) and \(u_{j}=v_{j}\) for \(j\in[1,s-1]\). We also write \(\mathbf{u}\preceq_{\texttt{lex}}\mathbf{v}\) if \(\mathbf{u}\prec_{\texttt{lex}}\mathbf{v}\) or \(\mathbf{u}=\mathbf{v}\)._  
Each application of Up, Move, and Swap makes a PV sequence greater in the lexicographic order. Therefore, we can obtain the following lemma:  
**Lemma 1**.: _Suppose \(\mathbf{u},\mathbf{v}\in\Gamma\). If \(\mathbf{u}\preceq_{\texttt{UM}}\mathbf{v}\) or \(\mathbf{u}\preceq_{\texttt{US}}\mathbf{v}\), then \(\mathbf{u}\preceq_{\texttt{lex}}\mathbf{v}\)._  
The following theorem states that a partial order of PV sequences is derived by operations Up and Move.  
**Theorem 1**.: _The pair \((\Gamma,\preceq_{\texttt{UM}})\) is a poset._  
Proof.: From Definition 4, the relation \(\preceq_{\texttt{UM}}\) is reflexive and transitive. Suppose \(\mathbf{u}\preceq_{\texttt{UM}}\mathbf{v}\) and \(\mathbf{v}\preceq_{\texttt{UM}}\mathbf{u}\). It follows from Lemma 1 that \(\mathbf{u}\preceq_{\texttt{lex}}\mathbf{v}\) and \(\mathbf{v}\preceq_{\texttt{lex}}\mathbf{u}\). Since the relation \(\preceq_{\texttt{lex}}\) is antisymmetric, we have \(\mathbf{u}=\mathbf{v}\), thus proving that the relation \(\preceq_{\texttt{UM}}\) is also antisymmetric.  
We can similarly prove the following theorem for operations Up and Swap:  
**Theorem 2**.: _The pair \((\Gamma,\preceq_{\texttt{US}})\) is a poset._