Estimation, Prediction, and Assortment Optimization for Markov Chain Choice Models with Panel Data

# Estimation, Prediction, and Assortment Optimization for Markov Chain Choice Models with Panel Data
Source: [https://arxiv.org/html/2607.09817](https://arxiv.org/html/2607.09817)
Yalcin Akcay, Gerardo Berbeglia11footnotemark:1, Young\-San Lin11footnotemark:1

###### Abstract

We propose a framework for the Markov chain \(MC\) choice model with panel data, including parameter estimation, personalized choice prediction, and personalized assortment optimization\. In contrast to the traditional setting, which assumes that each transaction is independently drawn from a random utility model, our framework accounts for dependencies among transactions for the same customer in historical data, captured by partial\-ordering preference information\. To the best of our knowledge, our framework initiates the study of choice modeling with panel data under MC\. As our primary result, we propose novel expectation\-maximization \(EM\) algorithms for MC parameter estimation by incorporating partial\-ordering\-based customer preference information\. On synthetic datasets and the sushi dataset, our EM algorithms outperform the traditional EM algorithm of Şimşek and Topaloglu \(Operations Research, 66, 2018\) and multinomial\-logit\-based partial\-order benchmarks adapted from Jagabathula and Vulcano \(Management Science, 64, 2018\)\. As our secondary contribution, we present hardness and computational results for conditional choice prediction and assortment optimization problems\. These results complement our estimation framework and clarify the computational landscape of conditional choice and assortment optimization, which may be of independent interest\.

## 1Introduction

Incorporating customer choice behavior into assortment planning is a central problem in revenue management\. A standard roadmap for assortment planning consists of two key steps: choice model estimation and assortment optimization\. In the literature, traditional choice model estimation algorithms typically assume that transactions in historical datasets are independent, while the assortment optimization problem seeks to maximize the expected revenue aggregated over the entire customer population\. A crucial feature of these traditional frameworks is their reliance on unconditional choice probabilities—that is, choice probabilities are assumed to be identical across customers and independent of customer\-specific transaction histories\.

Recent advances in data collection and e\-commerce technologies now allow retailers to observe detailed transaction histories at the individual customer level\. This information, popularly referred to as*panel data*, reveals correlations among transactions made by the same customer, challenging the independence assumptions underlying classical models\. This development naturally motivates the following questions:

*Can customer choice probabilities be estimated more precisely by incorporating individual historical transaction information into a choice model? What is the computational effort needed for this task?*

These questions take the choice model as given and focus on personalization at the level of choice probability estimation\. Specifically, we study how to compute customer\-specific choice probabilities conditional on individual transaction histories, while assuming that the unconditional choice probabilities are governed by an underlying choice model that is common to all customers\.

Intuitively, transaction histories provide additional information about individual preferences, as repeated choices made by the same customer are inherently correlated\. From a broader perspective, this raises a second complementary question\.

*Can the estimation of the choice model for the entire population improve by exploiting individual historical transaction information? When is this approach more beneficial?*

Here, the emphasis shifts from prediction to inference, asking whether exploiting information from repeated customer choice interactions can lead to more accurate estimation of the underlying choice model\.

Motivated by these questions, we develop both theoretical and experimental results on choice model estimation, conditional choice prediction, and assortment optimization with panel data\. Our analysis demonstrates how individual\-level transaction data can be systematically leveraged to enhance both predictive accuracy and decision\-making performance in assortment planning\.

### 1\.1Our Results

To the best of our knowledge, our framework initiates the study of choice modeling with panel data under the Markov chain \(MC\) choice model\. Our results are summarized as follows\.

- •As a motivating question, we investigate for which choice models panel data improve population\-level estimation\. The primary goal is to maximize the*likelihood*of the given data by selecting the best parameters\. Here, likelihood is defined as the probability that the full set of observations occurs independently\. In the traditional setting, each observation is a transaction\. In the setting with panel data, each observation is a customer\-specific partial ordering described by customer\-specific historical transactions\. Under multinomial logit \(MNL\), where the choice probabilities are observed in the population limit, using panel data does not add identification power for the MNL parameters\. In contrast, for MC, customer\-level information can improve model estimation\. This result highlights the gap between MNL and MC regarding how exploiting individual transaction information could facilitate choice model estimation, thereby motivating the use of panel data when estimating an MC\.
- •As our primary result, we present expectation\-maximization \(EM\) algorithms that incorporate customer\-level information to estimate an MC\. The EM algorithmCusassumes that each customer has a strict underlying preference, and aims to maximize the likelihood that each customer has a specific transaction set, which is equivalently captured by a partial\-ordering preferenceJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\); Jagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\)\. The hybrid algorithmHybcombinesCusand the traditional EM algorithmŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\), which provides a practical heuristic for mixing preference\-consistent histories with ordinary independent transactions\. These algorithms outperform the traditional EM algorithm for MC estimationŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\)and the benchmarks based on a partial\-ordering\-based heuristic for MNL estimationJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\)on synthetic datasets and the sushi dataset in a setting similar toBerbegliaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib3)\)\. The improvement is not only in customer\-specific choice predictions but also in population choice predictions\.
- •As our secondary contribution, we present computational hardness and tractability results for conditional choice probability computation and conditional assortment optimization under MNL or MC for a specific customer\. These results complement our estimation framework and clarify the computational landscape of conditional choice and assortment optimization under MNL and MC\. In contrast to the previous workJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\); Jagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\), which considers partial ordering over*all*products, our formulation considers partial ordering over*products selected by the customer*\. This formulation relies heavily on the structure of MNL or MC and could potentially reduce computational burden\.

### 1\.2Related Literature

#### 1\.2\.1EM Algorithms for Choice Model Estimation

One of the most popular measures used for demand or choice model estimation is the likelihood metric\. In some special cases, finding the optimal parameters is computationally tractable due to the concavity of the log\-likelihood objectiveMcFadden \([1974](https://arxiv.org/html/2607.09817#bib.bib22)\); van Ryzin and Vulcano \([2015](https://arxiv.org/html/2607.09817#bib.bib30)\)\. However, the log\-likelihood function is not well\-structured in general\. Standard optimization methods may become computationally intensive\.

A common approach for addressing this computational burden is the EM algorithmDempsteret al\.\([1977](https://arxiv.org/html/2607.09817#bib.bib27)\), widely used in demand censorship of substitutable products or choice model estimationVulcanoet al\.\([2012](https://arxiv.org/html/2607.09817#bib.bib29)\); van Ryzin and Vulcano \([2017](https://arxiv.org/html/2607.09817#bib.bib31)\); Jagabathula and Rusmevichientong \([2017](https://arxiv.org/html/2607.09817#bib.bib32)\); Anupindiet al\.\([1998](https://arxiv.org/html/2607.09817#bib.bib33)\); Talluri and van Ryzin \([2004](https://arxiv.org/html/2607.09817#bib.bib8)\); Kök and Fisher \([2007](https://arxiv.org/html/2607.09817#bib.bib34)\); Conlon and Mortimer \([2013](https://arxiv.org/html/2607.09817#bib.bib35)\); Stefanescu \([2009](https://arxiv.org/html/2607.09817#bib.bib36)\)\. In the scope of choice model estimation,Train \([2008](https://arxiv.org/html/2607.09817#bib.bib28)\)established EM algorithms for latent\-class MNL and a discrete mixture of choice distributions\. The latent\-class MNL EM framework was later adapted to panel data settings inJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\); Jagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\)\.Şimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\)presented the EM algorithm for MC, assuming that each transaction is independent\. Our framework is an extension ofŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\), which utilizes correlations among transactions from the same customer, thus improving the estimation of MC parameters\.

#### 1\.2\.2Choice Modeling and Assortment Planning with Panel Data

Most assortment problems with panel data in the literature are based on the multinomial logit \(MNL\) model, a special case of MC\.Chenet al\.\([2023](https://arxiv.org/html/2607.09817#bib.bib10)\)considered a multi\-period assortment optimization problem under MNL, where the goal is to maximize the expected revenue over all time periods\.Jagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\)initiated the study of partial\-ordering\-based customer preference estimation, later adapted to personalized promotion decision\-makingJagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\)\. This framework estimated choice probabilities conditional on the customer’s historical transactions under MNL and claimed that computing the exact probability is intractable\. We present a formal proof of this statement and derive a closed\-form expression to compute the exact choice probability under MC\. In contrast toJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\); Jagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\), which utilize an efficient heuristic to estimate the choice probability under MNL, we focus on a more fine\-grained computation under MC at a reasonable scale\.

#### 1\.2\.3Other Results for the MC Choice Model

The MC choice model was pioneered inBlanchetet al\.\([2016](https://arxiv.org/html/2607.09817#bib.bib2)\), which presented the first polynomial\-time algorithm for the assortment optimization problem under MC\. Shortly after,Feldman and Topaloglu \([2017](https://arxiv.org/html/2607.09817#bib.bib5)\)investigated the properties of the primal and dual linear programs \(LP\) for the assortment problem and an LP\-based approximation for the network revenue management problem under MC\. The capacitated assortment problem under MC is APX\-hardDésiret al\.\([2020](https://arxiv.org/html/2607.09817#bib.bib19)\), and there is a fully polynomial\-time approximation scheme \(FPTAS\) when the rank of the MC transition matrix is constantDésiret al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib20)\)\.Désiret al\.\([2024](https://arxiv.org/html/2607.09817#bib.bib37)\)developed an efficient algorithm for the robust assortment problem under MC\. The goal is to maximize the worst\-case expected revenue when the MC parameters are uncertain\.Gupta and Hsu \([2020](https://arxiv.org/html/2607.09817#bib.bib39)\)presented an efficient algorithm for the identification of MC parameters under limited\-size assortments and noiseless choice probabilities\.Liet al\.\([2025](https://arxiv.org/html/2607.09817#bib.bib38)\)presented an online learning algorithm for the dynamic assortment selection problem under MC, which simultaneously involves online parameter estimation and sequential assortment decision\-making\.

### 1\.3Organization

In Section[2](https://arxiv.org/html/2607.09817#S2), we present the basic framework of choice modeling with panel data and introduce MC and MNL\. In Section[3](https://arxiv.org/html/2607.09817#S3), we present the likelihood functions and the gap between MNL and MC regarding how exploiting individual transaction information could facilitate choice model estimation\. In Section[4](https://arxiv.org/html/2607.09817#S4), we present our EM algorithms for MC parameter estimation using panel data\. In Section[5](https://arxiv.org/html/2607.09817#S5), we present our experimental results\. We conclude in Section[6](https://arxiv.org/html/2607.09817#S6)\. In Appendix[A](https://arxiv.org/html/2607.09817#A1), we present hardness and computational results for conditional choice prediction and conditional assortment optimization\.

## 2Preliminaries

In Section[2\.1](https://arxiv.org/html/2607.09817#S2.SS1), we provide the background for random utility models \(RUM\) with panel data, including the basic settings, the connection between preference\-based linear extensions and directed acyclic graphs \(DAG\), and the closed\-form expression for conditional choice probability\. In Section[2\.2](https://arxiv.org/html/2607.09817#S2.SS2), we introduce specific choice models: the Markov chain \(MC\) and the multinomial logit \(MNL\)\. We end this section by presenting the closed\-form expression for the probability of observing a specific set of transactions under MC and MNL\.

In a RUM, there arennsubstitutable products, denoted as the set\[n\]=\{1,2,…,n\}\[n\]=\\\{1,2,\.\.\.,n\\\}\. The no\-purchase option is denoted as product 0\. A customer has a random utilityuj∈ℝu\_\{j\}\\in\\mathbb\{R\}for productjj, following an underlying probability distribution\. Depending on the RUM, the random utilities may be independent or not\. LetS⊆\[n\]S\\subseteq\[n\]be a subset of products offered to a customer\. The no\-purchase option is always available to the customer, so we use the notationS\+:=S∪\{0\}S\_\{\+\}:=S\\cup\\\{0\\\}\. The customer purchases the product with the highest utility fromS\+S\_\{\+\}\. That is,jjis chosen fromS\+S\_\{\+\}ifj=arg⁡maxi∈S\+⁡\{ui\}j=\\arg\\max\_\{i\\in S\_\{\+\}\}\\\{u\_\{i\}\\\}\.111We assume that the probability that multiple products have the highest utility is 0\.We useπ​\(j,S\)\\pi\(j,S\)to denote the probability thatjjis chosen fromS\+S\_\{\+\}\.

### 2\.1Choice Modeling with Panel Data

Traditional studies have focused primarily on choice\-probability computation, parameter estimation for a given class of RUM assuming that each transaction is independent, and assortment optimization when the RUM parameters are given\. We propose variants of these problems in which each transaction is associated with a specific customer, potentially capturing correlations between transactions from the same customer\.

Letccdenote a customer and\[C\]=\{1,2,…,C\}\[C\]=\\\{1,2,\.\.\.,C\\\}denote the set of customers\. Letkck\_\{c\}denote the number of observed transactions associated with the customercc\. A tuple\(j,S\)\(j,S\)captures a transaction in which the productj∈S\+j\\in S\_\{\+\}is purchased whenSSis offered\. Let𝒟c:=\{\(jℓc,Sℓc\)∣ℓ∈\[kc\]\}\\mathcal\{D\}^\{c\}:=\\\{\(j^\{c\}\_\{\\ell\},S^\{c\}\_\{\\ell\}\)\\mid\\ell\\in\[k\_\{c\}\]\\\}be the set of observed transactions associated with the customercc\. That is, the productjℓcj^\{c\}\_\{\\ell\}is purchased whenSℓcS^\{c\}\_\{\\ell\}is offered in theℓ\\ell\-th transaction of the customercc\. In practice,SℓcS^\{c\}\_\{\\ell\}can be the same for different labelsℓ\\elland customerscc, capturing the scenario in which different customers visit the same store during the same time period and face the same offer set\. The notation𝒟c\\mathcal\{D\}^\{c\}will be used for different purposes in different sections\. In Sections[3](https://arxiv.org/html/2607.09817#S3),[4](https://arxiv.org/html/2607.09817#S4), and[5](https://arxiv.org/html/2607.09817#S5),𝒟c\\mathcal\{D\}^\{c\}is used as the collection of customer\-specific transactions from different customersccto estimate the parameters of MC\. In Appendix[A](https://arxiv.org/html/2607.09817#A1), we assume that the RUM parameters \(more specifically, MC and MNL\) are known and focus on the purchasing probability of a specific customer, conditional on the customer’s transactions\. In the remainder of this section, we focus on one specific customer by dropping the notationcc\.

Suppose the RUM and the historical transactions𝒟:=\{\(jℓ,Sℓ\)∣ℓ∈\[k\]\}\\mathcal\{D\}:=\\\{\(j\_\{\\ell\},S\_\{\\ell\}\)\\mid\\ell\\in\[k\]\\\}of a specific customer are given\. We assume that the customer has underlying fixed utilities randomly generated according to the RUM\. The customer has a strict ranking for the products in\[n\]\+\[n\]\_\{\+\}\. The seller only has access to𝒟\\mathcal\{D\}as partial information\. The transactions in𝒟\\mathcal\{D\}must be consistent with a strict ranking\. For example, havingS1=\{1,2\}S\_\{1\}=\\\{1,2\\\}andj1=1j\_\{1\}=1would implyu1\>max⁡\{u0,u2\}u\_\{1\}\>\\max\\\{u\_\{0\},u\_\{2\}\\\}, so ifS2=\{1\}S\_\{2\}=\\\{1\\\}, we must havej2=1j\_\{2\}=1\. Without loss of generality, we assume that𝒟=\{\(jℓ,Sℓ\)∣ℓ∈\[k\]\}\\mathcal\{D\}=\\\{\(j\_\{\\ell\},S\_\{\\ell\}\)\\mid\\ell\\in\[k\]\\\}withjℓ≠jℓ′j\_\{\\ell\}\\neq j\_\{\\ell^\{\\prime\}\}for allℓ≠ℓ′\\ell\\neq\\ell^\{\\prime\}\. Otherwise, ifjℓ=jℓ′j\_\{\\ell\}=j\_\{\\ell^\{\\prime\}\},\(jℓ,Sℓ\)\(j\_\{\\ell\},S\_\{\\ell\}\)and\(jℓ′,Sℓ′\)\(j\_\{\\ell^\{\\prime\}\},S\_\{\\ell^\{\\prime\}\}\)can be described as\(jℓ,Sℓ∪Sℓ′\)\(j\_\{\\ell\},S\_\{\\ell\}\\cup S\_\{\\ell^\{\\prime\}\}\)becausejℓj\_\{\\ell\}is the most preferred product whenSℓ∪Sℓ′S\_\{\\ell\}\\cup S\_\{\\ell^\{\\prime\}\}is offered\.

We derive the probability thatjjis chosen fromSS, conditional on the past transactions in𝒟\\mathcal\{D\}\. Letℰ​\(j,S\)\\mathcal\{E\}\(j,S\)denote the event thatjjis chosen fromS\+S\_\{\+\}\. Letℰ𝒟\\mathcal\{E\}\_\{\\mathcal\{D\}\}denote the event thatjℓj\_\{\\ell\}is chosen fromSℓS\_\{\\ell\}for allℓ∈\[k\]\\ell\\in\[k\]\. Letπ𝒟\\pi\_\{\\mathcal\{D\}\}be the probability thatℰ𝒟\\mathcal\{E\}\_\{\\mathcal\{D\}\}occurs\. By definition,

π𝒟=Pr⁡\[ℰ𝒟\]=Pr⁡\[∩ℓ∈\[k\]ℰ​\(jℓ,Sℓ\)\]\.\\pi\_\{\\mathcal\{D\}\}=\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}\}\]=\\Pr\[\\cap\_\{\\ell\\in\[k\]\}\\mathcal\{E\}\(j\_\{\\ell\},S\_\{\\ell\}\)\]\.\(1\)Letπ𝒟​\(j,S\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)denote the probability thatjjis purchased whenS\+S\_\{\+\}is offered, conditional onℰ𝒟\\mathcal\{E\}\_\{\\mathcal\{D\}\}\. By definition,

π𝒟​\(j,S\)=Pr⁡\[ℰ𝒟∩ℰ​\(j,S\)\]π𝒟\.\\pi\_\{\\mathcal\{D\}\}\(j,S\)=\\frac\{\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}\}\\cap\\mathcal\{E\}\(j,S\)\]\}\{\\pi\_\{\\mathcal\{D\}\}\}\.\(2\)
We note that when the set of past transactions𝒟\\mathcal\{D\}is empty, thenπ𝒟=1\\pi\_\{\\mathcal\{D\}\}=1andπ𝒟​\(j,S\)=Pr⁡\[ℰ​\(j,S\)\]=π​\(j,S\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)=\\Pr\[\\mathcal\{E\}\(j,S\)\]=\\pi\(j,S\)\. This captures the unconditional choice probability\.

To compute the conditional probabilityπ𝒟​\(j,S\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)in \([2](https://arxiv.org/html/2607.09817#S2.E2)\), it suffices to calculate the probability of observing a transaction set separately for the numerator and denominator\. The eventℰ𝒟∩ℰ​\(j,S\)\\mathcal\{E\}\_\{\\mathcal\{D\}\}\\cap\\mathcal\{E\}\(j,S\)is equivalent toℰ𝒟′\\mathcal\{E\}\_\{\\mathcal\{D\}^\{\\prime\}\}where𝒟′=𝒟∪\{\(j,S\)\}\\mathcal\{D\}^\{\\prime\}=\\mathcal\{D\}\\cup\\\{\(j,S\)\\\}\. That is, we add transaction\(j,S\)\(j,S\)and compute the probability in the numerator\.

We proceed to introduce the directed acyclic graph \(DAG\) based presentation that is equivalent to the transaction\-based presentation, the notion of complete linear extensions that captures all the possible strict rankings over products, and the conditional assortment optimization problems\.

#### 2\.1\.1A DAG\-based Presentation for Customer Information

An alternative presentation for partial customer information is a DAGJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\); Jagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\)\. A DAGD=\(\[n\]\+,A\)D=\(\[n\]\_\{\+\},A\)has productsj∈\[n\]\+j\\in\[n\]\_\{\+\}representing the vertices and a set of arcsA⊆\[n\]\+×\[n\]\+A\\subseteq\[n\]\_\{\+\}\\times\[n\]\_\{\+\}where\(j,j′\)∈A\(j,j^\{\\prime\}\)\\in Adenotes thatjjis preferred overj′j^\{\\prime\}, that is,uj\>uj′u\_\{j\}\>u\_\{j^\{\\prime\}\}\. We note that transitive arcs can be removed for the sake of presentation\. For example, suppose\(j,j′\)\(j,j^\{\\prime\}\),\(j′,j′′\)\(j^\{\\prime\},j^\{\\prime\\prime\}\), and\(j,j′′\)\(j,j^\{\\prime\\prime\}\)are inAA, then we can remove\(j,j′′\)\(j,j^\{\\prime\\prime\}\)because the other two arcs imply thatuj\>uj′\>uj′′u\_\{j\}\>u\_\{j^\{\\prime\}\}\>u\_\{j^\{\\prime\\prime\}\}\.

The DAG\-based presentation is equivalent to the transaction\-based presentation\. Given a set of historical transactions𝒟=\{\(jℓ,Sℓ\)∣ℓ∈\[k\]\}\\mathcal\{D\}=\\\{\(j\_\{\\ell\},S\_\{\\ell\}\)\\mid\\ell\\in\[k\]\\\}consistent with an underlying strict ranking, an equivalent DAG can be constructed as follows\. For eachℓ∈\[k\]\\ell\\in\[k\]andj∈Sℓ\+∖\{jℓ\}j\\in\{S\_\{\\ell\}\}\_\{\+\}\\setminus\\\{j\_\{\\ell\}\\\}, add\(jℓ,j\)\(j\_\{\\ell\},j\)toAA\. That is, for each transaction, connect the purchased product to each product that was not purchased to capture the customer’s pairwise preference\. On the other hand, given a DAG that captures the customer’s preference, a set of historical transactions can be constructed as follows\. With a specific ordering, letjℓj\_\{\\ell\}denote theℓ\\ell\-th product that has at least one outgoing arc\. For eachjℓj\_\{\\ell\}, define the offer set asSℓ=\(\{jℓ\}∪\{j′∣\(jℓ,j′\)∈A\}\)∖\{0\}S\_\{\\ell\}=\(\\\{j\_\{\\ell\}\\\}\\cup\\\{j^\{\\prime\}\\mid\(j\_\{\\ell\},j^\{\\prime\}\)\\in A\\\}\)\\setminus\\\{0\\\}\.

We note that in empirical applications, customers might purchase and try different products, and update their idiosyncratic preferences from time to time\. Considering the transactions over a time period may introduce cyclic preferences\. In this scenario, cycle\-removal heuristics can be used to find a DAG that best describes the customer’s preferenceJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\); Jagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\)\.

#### 2\.1\.2Complete Linear Extensions

Given a set of transactions𝒟=\{\(jℓ,Sℓ\)∣ℓ∈\[k\]\}\\mathcal\{D\}=\\\{\(j\_\{\\ell\},S\_\{\\ell\}\)\\mid\\ell\\in\[k\]\\\}\(or a DAGD=\(\[n\]\+,A\)D=\(\[n\]\_\{\+\},A\)\), a*complete linear extension*σ:\[n\+1\]→\[n\]\+\\sigma:\[n\+1\]\\to\[n\]\_\{\+\}is a strict preference ranking over\[n\]\+\[n\]\_\{\+\}that is consistent with𝒟\\mathcal\{D\}\(orDD\)\.222A linear extension is also called a topological ordering\.Here,σ​\(s\)\\sigma\(s\)is thess\-th most preferred product among\[n\]\+\[n\]\_\{\+\}\. For clarity, sometimes we use\(σ​\(1\),σ​\(2\),…,σ​\(n\+1\)\)\(\\sigma\(1\),\\sigma\(2\),\.\.\.,\\sigma\(n\+1\)\)to denoteσ\\sigma\. We useσ∼c𝒟\\sigma\\sim\_\{c\}\\mathcal\{D\}to denote that the complete linear extensionσ\\sigmais consistent with𝒟\\mathcal\{D\}\.

Letπσ\\pi\_\{\\sigma\}be the probability that the customer’s strict preference ranking over\[n\]\+\[n\]\_\{\+\}isσ\\sigma\. Then the probability thatℰ𝒟\\mathcal\{E\}\_\{\\mathcal\{D\}\}occurs is

π𝒟=∑σ∼c𝒟πσ\.\\pi\_\{\\mathcal\{D\}\}=\\sum\_\{\\sigma\\sim\_\{c\}\\mathcal\{D\}\}\\pi\_\{\\sigma\}\.\(3\)
Using \([3](https://arxiv.org/html/2607.09817#S2.E3)\) could be computationally intensive\. In Section[2\.2\.3](https://arxiv.org/html/2607.09817#S2.SS2.SSS3), we present a simplified form for \([3](https://arxiv.org/html/2607.09817#S2.E3)\) under MC and MNL, to potentially reduce computation burden\.

###### Example 1\.

Letn=4n=4and𝒟=\{\(j1,S1\),\(j2,S2\),\(j3,S3\)\}\\mathcal\{D\}=\\\{\(j\_\{1\},S\_\{1\}\),\(j\_\{2\},S\_\{2\}\),\(j\_\{3\},S\_\{3\}\)\\\}with\(j1,S1\)=\(1,\{1,3\}\)\(j\_\{1\},S\_\{1\}\)=\(1,\\\{1,3\\\}\),\(j2,S2\)=\(2,\{2,3,4\}\)\(j\_\{2\},S\_\{2\}\)=\(2,\\\{2,3,4\\\}\), and\(j3,S3\)=\(3,\{3,4\}\)\(j\_\{3\},S\_\{3\}\)=\(3,\\\{3,4\\\}\)\. The DAG for𝒟\\mathcal\{D\}is presented in Figure[1](https://arxiv.org/html/2607.09817#S2.F1)\.

Products11and22have higher utilities than product33and no\-purchase\. Product33has a higher utility than product44and no\-purchase\. We do not know whether product 1 is preferred to product 2, and whether product 4 is preferred to no\-purchase\. The possible complete linear extensions are\(1,2,3,4,0\)\(1,2,3,4,0\),\(1,2,3,0,4\)\(1,2,3,0,4\),\(2,1,3,4,0\)\(2,1,3,4,0\), and\(2,1,3,0,4\)\(2,1,3,0,4\), representing the possible rankings for all products\. Suppose that the RUM is such that the complete linear extensions\(1,2,3,4,0\)\(1,2,3,4,0\),\(1,2,3,0,4\)\(1,2,3,0,4\),\(2,1,3,4,0\)\(2,1,3,4,0\), and\(2,1,3,0,4\)\(2,1,3,0,4\)occur with probability0\.20\.2,0\.10\.1,0\.20\.2, and0\.10\.1, respectively\. Thenπ𝒟=0\.6\\pi\_\{\\mathcal\{D\}\}=0\.6by \([3](https://arxiv.org/html/2607.09817#S2.E3)\)\.

011223344Figure 1:The DAG for𝒟\\mathcal\{D\}

#### 2\.1\.3Conditional Assortment Optimization

In assortment problems, each productj∈\[n\]\+j\\in\[n\]\_\{\+\}is associated with a revenuerj∈ℝ≥0r\_\{j\}\\in\\mathbb\{R\}\_\{\\geq 0\}\. In particular, the no\-purchase option has zero revenue, sor0=0r\_\{0\}=0\. We user:=\{rj\}j∈\[n\]\+r:=\\\{r\_\{j\}\\\}\_\{j\\in\[n\]\_\{\+\}\}to denote the revenue vector\. The traditional assortment optimization \(TAO\) problem aims to find an offer setS⊆\[n\]S\\subseteq\[n\]that maximizes the expected revenue:

maxS⊆\[n\]​∑j∈Sπ​\(j,S\)​rj\.\\max\_\{S\\subseteq\[n\]\}\\sum\_\{j\\in S\}\\pi\(j,S\)r\_\{j\}\.\(TAO\)
In the conditional assortment optimization \(CAO\) problem, the seller aims to maximize the expected revenue for a specific customer, conditional on the transactions𝒟\\mathcal\{D\}\. That is,

maxS⊆\[n\]​∑j∈Sπ𝒟​\(j,S\)​rj\.\\max\_\{S\\subseteq\[n\]\}\\sum\_\{j\\in S\}\\pi\_\{\\mathcal\{D\}\}\(j,S\)r\_\{j\}\.\(CAO\)In the*transparent*setting where the seller cannot hide the products presented in the past, it is required to offer a set that includes all products that were purchased\. We useS∼t𝒟S\\sim\_\{t\}\\mathcal\{D\}to denote thatS⊆\[n\]S\\subseteq\[n\]satisfiesjℓ∈S\+j\_\{\\ell\}\\in S\_\{\+\}for allℓ∈\[k\]\\ell\\in\[k\]\. The transparent conditional assortment optimization \(TCAO\) problem is

maxS∼t𝒟​∑j∈Sπ𝒟​\(j,S\)​rj\.\\max\_\{S\\sim\_\{t\}\\mathcal\{D\}\}\\sum\_\{j\\in S\}\\pi\_\{\\mathcal\{D\}\}\(j,S\)r\_\{j\}\.\(TCAO\)

### 2\.2Specific Choice Models

In this section, we introduce the Markov chain \(MC\) choice model and its special case, the multinomial logit \(MNL\) choice model\. Both models are special cases of RUMsBerbeglia \([2016](https://arxiv.org/html/2607.09817#bib.bib26)\)\. We derive simpler closed\-form probabilities in equations \([1](https://arxiv.org/html/2607.09817#S2.E1)\), \([2](https://arxiv.org/html/2607.09817#S2.E2)\), and \([3](https://arxiv.org/html/2607.09817#S2.E3)\) under these two models\.

#### 2\.2\.1Markov Chain Choice Model

Throughout the paper, we primarily consider the Markov chain \(MC\) choice model\. Under MC, each product in\[n\]\+\[n\]\_\{\+\}is associated with a state\. Each statei∈\[n\]\+i\\in\[n\]\_\{\+\}is associated with a given parameterλi\\lambda\_\{i\}which denotes the probability of starting at stateii\. Each statei∈\[n\]i\\in\[n\]has a transition probability to statej∈\[n\]\+j\\in\[n\]\_\{\+\}, denoted asρi​j\\rho\_\{ij\}\. Naturally, we have∑i=0nλi=1\\sum\_\{i=0\}^\{n\}\\lambda\_\{i\}=1and∑j=0nρi​j=1\\sum\_\{j=0\}^\{n\}\\rho\_\{ij\}=1for alli∈\[n\]i\\in\[n\]\. We useλ:=\{λj\}j∈\[n\]\+\\lambda:=\\\{\\lambda\_\{j\}\\\}\_\{j\\in\[n\]\_\{\+\}\}to denote the initial probability vector andρ:=\{ρi​j\}i∈\[n\],j∈\[n\]\+\\rho:=\\\{\\rho\_\{ij\}\\\}\_\{i\\in\[n\],j\\in\[n\]\_\{\+\}\}to denote the transition matrix\. The customer enters the system according to the initial probabilityλ\\lambdaand performs a Markovian random walk according toρ\\rho\. Given an offer setS⊆\[n\]S\\subseteq\[n\]and suppose the customer is at stateii\. Ifi∈S\+i\\in S\_\{\+\}, then the customer selects productiiand leaves the system\. Otherwise, ifi∉S\+i\\notin S\_\{\+\}, the customer transitions to statejjwith probabilityρi​j\\rho\_\{ij\}\. The customer performs this Markovian random walk until it reaches a state inS\+S\_\{\+\}\.

Recall thatπ​\(j,S\)\\pi\(j,S\)denotes the probability that the productjjis chosen fromS\+S\_\{\+\}\. LetS¯:=\[n\]∖S\\overline\{S\}:=\[n\]\\setminus Sdenote the complement of the offer setSS\. InBlanchetet al\.\([2016](https://arxiv.org/html/2607.09817#bib.bib2)\); Feldman and Topaloglu \([2017](https://arxiv.org/html/2607.09817#bib.bib5)\),π​\(j,S\)\\pi\(j,S\)is derived from the following system of linear equations:

π​\(j,S\)=λj\+∑i∈S¯ρi​j​π​\(i,S\)∀j∈\[n\]\+\.\\pi\(j,S\)=\\lambda\_\{j\}\+\\sum\_\{i\\in\\overline\{S\}\}\\rho\_\{ij\}\\pi\(i,S\)\\quad\\forall j\\in\[n\]\_\{\+\}\.\(4\)On the left\-hand side,π​\(j,S\)\\pi\(j,S\)is the expected number of times that a customer visits statejjduring the course of the choice process whenSSis offered\. When a customer visits statejj, it either enters the system directly at statejjor transitions from a stateS¯\\overline\{S\}to statejj\. The former case yields the termλj\\lambda\_\{j\}on the right\-hand side\. In the latter case, the expected number of times that a customer visits a statei∈S¯i\\in\\overline\{S\}isπ​\(i,S\)\\pi\(i,S\)\. In each of these visits, the customer transitions from stateiito statejjwith probabilityρi​j\\rho\_\{ij\}, yielding the term∑i∈S¯ρi​j​π​\(i,S\)\\sum\_\{i\\in\\overline\{S\}\}\\rho\_\{ij\}\\pi\(i,S\)on the right\-hand side\. Whenj∈Sj\\in S, sincejjcan be visited at most once, the expected number of visits tojjis the same as the probability thatjjis chosen fromSS\.

From \([4](https://arxiv.org/html/2607.09817#S2.E4)\), we proceed to derive the closed\-form expression forπ​\(j,S\)\\pi\(j,S\)\. For anyT⊆\[n\]\+T\\subseteq\[n\]\_\{\+\}, letπ​\(T,S\):=\{π​\(j,S\)\}j∈T\\pi\(T,S\):=\\\{\\pi\(j,S\)\\\}\_\{j\\in T\}denote the vector that captures the expected number of times statej∈Tj\\in Tis visited whenSSis offered\. Letλ​\(T\):=\{λj\}j∈T\\lambda\(T\):=\\\{\\lambda\_\{j\}\\\}\_\{j\\in T\}denote a sub\-vector ofλ\\lambdawith coordinates inTT\. For anyT′⊆\[n\]T^\{\\prime\}\\subseteq\[n\]andT⊆\[n\]\+T\\subseteq\[n\]\_\{\+\}, letρ​\(T′,T\):=\{ρi​j\}i∈T′,j∈T\\rho\(T^\{\\prime\},T\):=\\\{\\rho\_\{ij\}\\\}\_\{i\\in T^\{\\prime\},j\\in T\}denote the sub\-matrix ofρ\\rhothat captures a transition from states inT′T^\{\\prime\}to states inTT\. From \([4](https://arxiv.org/html/2607.09817#S2.E4)\), we observe thatπ​\(S¯,S\)=λ​\(S¯\)\+ρ​\(S¯,S¯\)T​π​\(S¯,S\)\\pi\(\\overline\{S\},S\)=\\lambda\(\\overline\{S\}\)\+\\rho\(\\overline\{S\},\\overline\{S\}\)^\{T\}\\pi\(\\overline\{S\},S\), which implies that

π​\(S¯,S\)=\(\(I−ρ​\(S¯,S¯\)\)T\)−1​λ​\(S¯\)=\(\(I−ρ​\(S¯,S¯\)\)−1\)T​λ​\(S¯\)\.\\pi\(\\overline\{S\},S\)=\\left\(\(I\-\\rho\(\\overline\{S\},\\overline\{S\}\)\)^\{T\}\\right\)^\{\-1\}\\lambda\(\\overline\{S\}\)=\\left\(\(I\-\\rho\(\\overline\{S\},\\overline\{S\}\)\)^\{\-1\}\\right\)^\{T\}\\lambda\(\\overline\{S\}\)\.\(5\)To ensure that\(I−ρ​\(S¯,S¯\)\)−1\(I\-\\rho\(\\overline\{S\},\\overline\{S\}\)\)^\{\-1\}is unique and always exists, we assume that∑i∈S¯ρi​j<1\\sum\_\{i\\in\\overline\{S\}\}\\rho\_\{ij\}<1for allS⊆\[n\]S\\subseteq\[n\]Puterman \([2014](https://arxiv.org/html/2607.09817#bib.bib6)\)\.333This assumption is equivalent to having the spectral radius ofρ​\(\[n\],\[n\]\)\\rho\(\[n\],\[n\]\)strictly less than one\.From \([4](https://arxiv.org/html/2607.09817#S2.E4)\) and \([5](https://arxiv.org/html/2607.09817#S2.E5)\), we have that

π​\(S\+,S\)\\displaystyle\\pi\(S\_\{\+\},S\)=λ​\(S\+\)\+ρ​\(S¯,S\+\)T​π​\(S¯,S\)\\displaystyle=\\lambda\(S\_\{\+\}\)\+\\rho\(\\overline\{S\},S\_\{\+\}\)^\{T\}\\pi\(\\overline\{S\},S\)=λ​\(S\+\)\+ρ​\(S¯,S\+\)T​\(\(I−ρ​\(S¯,S¯\)\)−1\)T​λ​\(S¯\)\.\\displaystyle=\\lambda\(S\_\{\+\}\)\+\\rho\(\\overline\{S\},S\_\{\+\}\)^\{T\}\\left\(\(I\-\\rho\(\\overline\{S\},\\overline\{S\}\)\)^\{\-1\}\\right\)^\{T\}\\lambda\(\\overline\{S\}\)\.\(6\)We interpret the right\-hand side of \([6](https://arxiv.org/html/2607.09817#S2.E6)\) as follows\. When a customer enters the system, it either directly enters a state inS\+S\_\{\+\}, or starts from a state inS¯\\overline\{S\}, and transitionsqqadditional times inS¯\\overline\{S\}forq≥0q\\geq 0before reaching a state inS\+S\_\{\+\}\. The former case is captured by the probability vectorλ​\(S\+\)\\lambda\(S\_\{\+\}\)while the latter case is captured byρ​\(S¯,S\+\)T​\(∑q=0∞ρ​\(S¯,S¯\)q\)T​λ​\(S¯\)=ρ​\(S¯,S\+\)T​\(\(I−ρ​\(S¯,S¯\)\)−1\)T​λ​\(S¯\)\\rho\(\\overline\{S\},S\_\{\+\}\)^\{T\}\\left\(\\sum\_\{q=0\}^\{\\infty\}\\rho\(\\overline\{S\},\\overline\{S\}\)^\{q\}\\right\)^\{T\}\\lambda\(\\overline\{S\}\)=\\rho\(\\overline\{S\},S\_\{\+\}\)^\{T\}\\left\(\(I\-\\rho\(\\overline\{S\},\\overline\{S\}\)\)^\{\-1\}\\right\)^\{T\}\\lambda\(\\overline\{S\}\)\.

Under MC, the following linear program \(LP\) introduced inFeldman and Topaloglu \([2017](https://arxiv.org/html/2607.09817#bib.bib5)\)solves \([TAO](https://arxiv.org/html/2607.09817#S2.Ex1)\) in polynomial time\.

ming​∑i∈\[n\]λi​gis\.t\.gi≥ri​and​gi≥∑j∈\[n\]ρi​j​gj∀i∈\[n\]\.\\min\_\{g\}\\sum\_\{i\\in\[n\]\}\\lambda\_\{i\}g\_\{i\}\\quad\\text\{s\.t\.\}\\quad g\_\{i\}\\geq r\_\{i\}\\text\{ and \}g\_\{i\}\\geq\\sum\_\{j\\in\[n\]\}\\rho\_\{ij\}g\_\{j\}\\quad\\forall i\\in\[n\]\.\(7\)Here, the variablegig\_\{i\}denotes the maximum expected revenue obtained while visiting stateii\. The objectiveming​∑i∈\[n\]λi​gi\\min\_\{g\}\\sum\_\{i\\in\[n\]\}\\lambda\_\{i\}g\_\{i\}represents the expected revenue and forcesgi=max⁡\{ri,∑j∈\[n\]ρi​j​gj\}g\_\{i\}=\\max\\\{r\_\{i\},\\sum\_\{j\\in\[n\]\}\\rho\_\{ij\}g\_\{j\}\\\}\. Ifgi=rig\_\{i\}=r\_\{i\}, then offering productiimaximizes the expected revenue while visiting stateii\. Otherwise, ifgi\>rig\_\{i\}\>r\_\{i\}, then not offering productiiforces the customer to transition to another statejj, andgi=∑j∈\[n\]ρi​j​gjg\_\{i\}=\\sum\_\{j\\in\[n\]\}\\rho\_\{ij\}g\_\{j\}maximizes the expected revenue while visiting stateii\. Letg∗g^\{\*\}be the optimal solution to \([7](https://arxiv.org/html/2607.09817#S2.E7)\), then offering\{i∣gi∗=ri\}\\\{i\\mid g^\{\*\}\_\{i\}=r\_\{i\}\\\}maximizes the expected revenue\.

#### 2\.2\.2Multinomial Logit Choice Model

The Multinomial Logit \(MNL\) model is by far the most popular in practiceBradley and Terry \([1952](https://arxiv.org/html/2607.09817#bib.bib21)\); Luce \([1959](https://arxiv.org/html/2607.09817#bib.bib23)\); McFadden \([1974](https://arxiv.org/html/2607.09817#bib.bib22)\); Plackett \([1975](https://arxiv.org/html/2607.09817#bib.bib24)\)\. Under MNL, the utility of productjjtakes the formuj=μj\+εju\_\{j\}=\\mu\_\{j\}\+\\varepsilon\_\{j\}whereμj\\mu\_\{j\}is the mean ofuju\_\{j\}that is fixed andεj\\varepsilon\_\{j\}is a standard Gumbel random variable\. The Gumbel shocksεj\\varepsilon\_\{j\}are independent, so the utilitiesuju\_\{j\}are independent\. Letvj:=exp⁡\(μj\)\>0v\_\{j\}:=\\exp\(\\mu\_\{j\}\)\>0be the attraction value of productjj\. Then the choice probability

π​\(j,S\)=vj∑i∈S\+vi=vjV​\(S\+\)\\pi\(j,S\)=\\frac\{v\_\{j\}\}\{\\sum\_\{i\\in S\_\{\+\}\}v\_\{i\}\}=\\frac\{v\_\{j\}\}\{V\(S\_\{\+\}\)\}\(8\)whereV​\(T\):=∑j∈TvjV\(T\):=\\sum\_\{j\\in T\}v\_\{j\}for ease of notation\. MNL can be represented by MC, where the transition matrixρ\\rhois rank one\. More specifically, an MNL with parameter vectorv:=\{vj\}j∈\[n\]\+v:=\\\{v\_\{j\}\\\}\_\{j\\in\[n\]\_\{\+\}\}can be captured by an MC with parametersλj=vj/V​\(\[n\]\+\)\\lambda\_\{j\}=v\_\{j\}/V\(\[n\]\_\{\+\}\)for allj∈\[n\]\+j\\in\[n\]\_\{\+\}andρi​j=vj/V​\(\[n\]\+\)\\rho\_\{ij\}=v\_\{j\}/V\(\[n\]\_\{\+\}\)for alli∈\[n\],j∈\[n\]\+i\\in\[n\],j\\in\[n\]\_\{\+\}Blanchetet al\.\([2016](https://arxiv.org/html/2607.09817#bib.bib2)\)\.

Under MNL, \([TAO](https://arxiv.org/html/2607.09817#S2.Ex1)\) can be solved in polynomial time by considering revenue\-ordered assortmentsGallegoet al\.\([2004](https://arxiv.org/html/2607.09817#bib.bib7)\); Talluri and van Ryzin \([2004](https://arxiv.org/html/2607.09817#bib.bib8)\)\. An assortmentS⊆\[n\]S\\subseteq\[n\]is revenue\-ordered ifSSincludes the topssrevenue products for somes∈\[n\]s\\in\[n\]\.

#### 2\.2\.3Closed\-form for the Probability of a Set of Transactions under MC or MNL

Given a set of transactions𝒟=\{\(jℓ,Sℓ\)∣ℓ∈\[k\]\}\\mathcal\{D\}=\\\{\(j\_\{\\ell\},S\_\{\\ell\}\)\\mid\\ell\\in\[k\]\\\}, we derive a closed\-form expression forπ𝒟\\pi\_\{\\mathcal\{D\}\}under MC or MNL\. Section[2\.1\.2](https://arxiv.org/html/2607.09817#S2.SS1.SSS2)equation \([3](https://arxiv.org/html/2607.09817#S2.E3)\) takes the summation of the probabilities of having each complete linear extension\. However, this could cause computational burden\. Under MC or MNL, an alternative is to consider*reduced linear extensions*represented as rankings over the subscript indices of the chosen products\{jℓ∣ℓ∈\[k\]\}\\\{j\_\{\\ell\}\\mid\\ell\\in\[k\]\\\}\. Recall that the customer has an underlying strict preference, and we assume thatjℓ≠jℓ′j\_\{\\ell\}\\neq j\_\{\\ell^\{\\prime\}\}for allℓ≠ℓ′\\ell\\neq\\ell^\{\\prime\}\. For anyℓ≠ℓ′\\ell\\neq\\ell^\{\\prime\}where\(jℓ,Sℓ\),\(jℓ′,Sℓ′\)∈𝒟\(j\_\{\\ell\},S\_\{\\ell\}\),\(j\_\{\\ell^\{\\prime\}\},S\_\{\\ell^\{\\prime\}\}\)\\in\\mathcal\{D\}, ifjℓ′∈Sℓj\_\{\\ell^\{\\prime\}\}\\in S\_\{\\ell\}, thenjℓj\_\{\\ell\}is more preferred thanjℓ′j\_\{\\ell^\{\\prime\}\}, so we haveℓ≻ℓ′\\ell\\succ\\ell^\{\\prime\}\. Considering all pairsℓ,ℓ′\\ell,\\ell^\{\\prime\}and transitivity, this defines the partial ordering for\[k\]\[k\]based on𝒟\\mathcal\{D\}\. A reduced linear extensionσ:\[k\]→\[k\]\\sigma:\[k\]\\to\[k\]is a strict preference ranking over\[k\]\[k\]that is consistent with𝒟\\mathcal\{D\}\. Here,jσ​\(s\)j\_\{\\sigma\(s\)\}is thess\-th most preferred product among\{jℓ∣ℓ∈\[k\]\}\\\{j\_\{\\ell\}\\mid\\ell\\in\[k\]\\\}\. We note that ifjℓ′=0j\_\{\\ell^\{\\prime\}\}=0, thenσ​\(k\)=ℓ′\\sigma\(k\)=\\ell^\{\\prime\}, i\.e\., the no\-purchase option is the least preferred among\{jℓ∣ℓ∈\[k\]\}\\\{j\_\{\\ell\}\\mid\\ell\\in\[k\]\\\}\. Since0∈Sℓ\+0\\in\{S\_\{\\ell\}\}\_\{\+\}for allℓ∈\[k\]\\ell\\in\[k\], we do not know the ranking over products less preferred than the no\-purchase option\. For clarity, sometimes we use\(σ​\(1\),σ​\(2\),…,σ​\(k\)\)\(\\sigma\(1\),\\sigma\(2\),\.\.\.,\\sigma\(k\)\)to denoteσ\\sigma\. We useσ∼r𝒟\\sigma\\sim\_\{r\}\\mathcal\{D\}to denote that the reduced linear extensionσ\\sigmais consistent with𝒟\\mathcal\{D\}\.

The partial ordering≻\\succfor\[k\]\[k\]can be presented as a*reduced DAG*, which has\[k\]\[k\]as the set of vertices and arcs that represent the partial ordering≻\\succ\. That is,ℓ≻ℓ′\\ell\\succ\\ell^\{\\prime\}if and only if there is anℓ​⤳​ℓ′\\ell\\leadsto\\ell^\{\\prime\}path in the reduced DAG, capturing the case thatjℓj\_\{\\ell\}is more preferred thanjℓ′j\_\{\\ell^\{\\prime\}\}\.

##### Markov Chain\.

Under MC, the ranking for the chosen products\{jℓ∣ℓ∈\[k\]\}\\\{j\_\{\\ell\}\\mid\\ell\\in\[k\]\\\}is decided by the customer’s random walk, i\.e\., the course of product selection\. The ordering for the first appearance of each product in the random walk defines the customer’s preference\. In other words, if the first visit of stateiiappears before the first visit of statejjin the random walk, then productiiis more preferred than productjj\.

Following this observation, any random walk that is consistent with𝒟\\mathcal\{D\}must be in the form of a reduced linear extensionσ∼r𝒟\\sigma\\sim\_\{r\}\\mathcal\{D\}\. Suppose that the random walk is in the form ofσ\\sigma\. LetU:=∪ℓ∈\[k\]SℓU:=\\cup\_\{\\ell\\in\[k\]\}S\_\{\\ell\}\. Before the first visit ofjσ​\(1\)j\_\{\\sigma\(1\)\}, it is impossible that the random walk has visited a state inU∖\{jσ​\(1\)\}U\\setminus\\\{j\_\{\\sigma\(1\)\}\\\}\. Otherwise, there exists a statej∈\{jℓ∣ℓ∈\[k\]\}∖\{jσ​\(1\)\}j\\in\\\{j\_\{\\ell\}\\mid\\ell\\in\[k\]\\\}\\setminus\\\{j\_\{\\sigma\(1\)\}\\\}that is more preferred thanjσ​\(1\)j\_\{\\sigma\(1\)\}, violating the form ofσ\\sigma\. A random walk that is in the form ofσ\\sigma, up to the first visit ofjσ​\(1\)j\_\{\\sigma\(1\)\}, has the following prefix form: the customer either directly entersjσ​\(1\)j\_\{\\sigma\(1\)\}or enters a state inU¯\\overline\{U\}, traverses states inU¯\\overline\{U\}, and transitions from a state inU¯\\overline\{U\}tojσ​\(1\)j\_\{\\sigma\(1\)\}\. The probability of having this prefix random walk isπ​\(jσ​\(1\),U\)\\pi\(j\_\{\\sigma\(1\)\},U\), the probability thatjσ​\(1\)j\_\{\\sigma\(1\)\}is chosen fromUU\.

The random walk then proceeds from the first visit ofjσ​\(1\)j\_\{\\sigma\(1\)\}to the first visit ofjσ​\(2\)j\_\{\\sigma\(2\)\}, through states in∪ℓ=2kSσ​\(ℓ\)¯=∩ℓ=2kSσ​\(ℓ\)¯\\overline\{\\cup\_\{\\ell=2\}^\{k\}S\_\{\\sigma\(\\ell\)\}\}=\\cap\_\{\\ell=2\}^\{k\}\\overline\{S\_\{\\sigma\(\\ell\)\}\}\. For convenience, letUsσ:=∪ℓ=skSσ​\(ℓ\)U^\{\\sigma\}\_\{s\}:=\\cup\_\{\\ell=s\}^\{k\}S\_\{\\sigma\(\\ell\)\}be the*union of the absorbing sets*with subscript indices fromσ​\(s\)\\sigma\(s\)toσ​\(k\)\\sigma\(k\)andAsσ:=Usσ¯=∪ℓ=skSσ​\(ℓ\)¯=∩ℓ=skSσ​\(ℓ\)¯A^\{\\sigma\}\_\{s\}:=\\overline\{U^\{\\sigma\}\_\{s\}\}=\\overline\{\\cup\_\{\\ell=s\}^\{k\}S\_\{\\sigma\(\\ell\)\}\}=\\cap\_\{\\ell=s\}^\{k\}\\overline\{S\_\{\\sigma\(\\ell\)\}\}be the*admissible set*from the first visit ofσ​\(s−1\)\\sigma\(s\-1\)to the first visit ofσ​\(s\)\\sigma\(s\)fors∈\{2,3,…,k\}s\\in\\\{2,3,\.\.\.,k\\\}\. We denote the event of having a random walk from stateiito statejjthrough states inTTasi​⤳𝑇​ji\\overset\{T\}\{\\leadsto\}j\. Following the same reasoning for \([6](https://arxiv.org/html/2607.09817#S2.E6)\), we have that

Pr⁡\[i​⤳𝑇​j\]:=ρi​j\+ρ​\(T,\{j\}\)T​\(\(I−ρ​\(T,T\)\)−1\)T​ρ​\(\{i\},T\)T=ρi​j\+ρ​\(\{i\},T\)​\(I−ρ​\(T,T\)\)−1​ρ​\(T,\{j\}\)\.\\Pr\[i\{\\overset\{T\}\{\\leadsto\}\}j\]:=\\rho\_\{ij\}\+\\rho\(T,\\\{j\\\}\)^\{T\}\\left\(\\left\(I\-\\rho\(T,T\)\\right\)^\{\-1\}\\right\)^\{T\}\\rho\(\\\{i\\\},T\)^\{T\}=\\rho\_\{ij\}\+\\rho\(\\\{i\\\},T\)\\left\(I\-\\rho\(T,T\)\\right\)^\{\-1\}\\rho\(T,\\\{j\\\}\)\.\(9\)The random walk from the first visit ofjσ​\(1\)j\_\{\\sigma\(1\)\}to the first visit ofjσ​\(2\)j\_\{\\sigma\(2\)\}, through states inA2σA^\{\\sigma\}\_\{2\}, occurs with probabilityPr⁡\[jσ​\(1\)​⤳A2σ​jσ​\(2\)\]\\Pr\[j\_\{\\sigma\(1\)\}\{\\overset\{A^\{\\sigma\}\_\{2\}\}\{\\leadsto\}\}j\_\{\\sigma\(2\)\}\]by \([9](https://arxiv.org/html/2607.09817#S2.E9)\)\. Using analogous arguments, the random walk from the first visit ofjσ​\(s\)j\_\{\\sigma\(s\)\}to the first visit ofjσ​\(s\+1\)j\_\{\\sigma\(s\+1\)\}for eachs∈\[k−1\]s\\in\[k\-1\], through states inAs\+1σA^\{\\sigma\}\_\{s\+1\}, occurs with probabilityPr⁡\[jσ​\(s\)​⤳As\+1σ​jσ​\(s\+1\)\]\\Pr\[j\_\{\\sigma\(s\)\}\{\\overset\{A^\{\\sigma\}\_\{s\+1\}\}\{\\leadsto\}\}j\_\{\\sigma\(s\+1\)\}\]\. When the customer’s random walk is in the form ofσ\\sigma, the likelihood factors over the prefix segment and the subsequent inter\-arrival segments\. We have

πσ𝒟=π​\(jσ​\(1\),U\)​∏s=1k−1Pr⁡\[jσ​\(s\)​⤳As\+1σ​jσ​\(s\+1\)\]\\pi^\{\\mathcal\{D\}\}\_\{\\sigma\}=\\pi\(j\_\{\\sigma\(1\)\},U\)\\prod\_\{s=1\}^\{k\-1\}\\Pr\[j\_\{\\sigma\(s\)\}\{\\overset\{A^\{\\sigma\}\_\{s\+1\}\}\{\\leadsto\}\}j\_\{\\sigma\(s\+1\)\}\]\(10\)whereπσ𝒟\\pi^\{\\mathcal\{D\}\}\_\{\\sigma\}is the probability of having a random walk consistent with the reduced linear extensionσ\\sigmagiven the transaction set𝒟\\mathcal\{D\}\. The probability thatℰ𝒟\\mathcal\{E\}\_\{\\mathcal\{D\}\}occurs is

π𝒟=∑σ∼r𝒟πσ𝒟\.\\pi\_\{\\mathcal\{D\}\}=\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}\}\\pi^\{\\mathcal\{D\}\}\_\{\\sigma\}\.\(11\)We note that \([3](https://arxiv.org/html/2607.09817#S2.E3)\) accounts for the probabilityπσ\\pi\_\{\\sigma\}of having a random walk consistent with a complete linear extensionσ\\sigma, which depends on the RUM and is independent of𝒟\\mathcal\{D\}\. In \([11](https://arxiv.org/html/2607.09817#S2.E11)\), the probabilityπσ𝒟\\pi^\{\\mathcal\{D\}\}\_\{\\sigma\}of having a random walk consistent with a reduced linear extensionσ\\sigmadepends on𝒟\\mathcal\{D\}\.

##### Multinomial Logit\.

Under MNL, when the customer preference is consistent with a reduced linear extensionσ∼r𝒟\\sigma\\sim\_\{r\}\\mathcal\{D\},σ\\sigmamust be in the following form\. First, products ranked beforejσ​\(1\)j\_\{\\sigma\(1\)\}must belong toU¯\\overline\{U\}, sojσ​\(1\)j\_\{\\sigma\(1\)\}is the most preferred amongU\+U\_\{\+\}\. Afterjσ​\(1\)j\_\{\\sigma\(1\)\}, products ranked beforejσ​\(2\)j\_\{\\sigma\(2\)\}must belong toA2σA^\{\\sigma\}\_\{2\}, sojσ​\(2\)j\_\{\\sigma\(2\)\}is the most preferred amongU2σ\+\{U^\{\\sigma\}\_\{2\}\}\_\{\+\}\. Repeating the same argument, for anys∈\[k\]s\\in\[k\],jσ​\(s\)j\_\{\\sigma\(s\)\}is the most preferred amongUsσ\+\{U^\{\\sigma\}\_\{s\}\}\_\{\+\}\. According toBeggset al\.\([1981](https://arxiv.org/html/2607.09817#bib.bib9)\),

πσ𝒟=∏s=1kπ​\(jσ​\(s\),Usσ\)=∏s=1kvjσ​\(s\)V​\(Usσ\+\)\.\\pi^\{\\mathcal\{D\}\}\_\{\\sigma\}=\\prod\_\{s=1\}^\{k\}\\pi\(j\_\{\\sigma\(s\)\},\{U^\{\\sigma\}\_\{s\}\}\)=\\prod\_\{s=1\}^\{k\}\\frac\{v\_\{j\_\{\\sigma\(s\)\}\}\}\{V\\left\(\{\{U^\{\\sigma\}\_\{s\}\}\}\_\{\+\}\\right\)\}\.\(12\)
###### Example 2\.

Recall that in Example[1](https://arxiv.org/html/2607.09817#Thmexample1),n=4n=4and𝒟=\{\(j1,S1\),\(j2,S2\),\(j3,S3\)\}\\mathcal\{D\}=\\\{\(j\_\{1\},S\_\{1\}\),\(j\_\{2\},S\_\{2\}\),\(j\_\{3\},S\_\{3\}\)\\\}with\(j1,S1\)=\(1,\{1,3\}\)\(j\_\{1\},S\_\{1\}\)=\(1,\\\{1,3\\\}\),\(j2,S2\)=\(2,\{2,3,4\}\)\(j\_\{2\},S\_\{2\}\)=\(2,\\\{2,3,4\\\}\), and\(j3,S3\)=\(3,\{3,4\}\)\(j\_\{3\},S\_\{3\}\)=\(3,\\\{3,4\\\}\)\. The partial ordering is defined by1≻31\\succ 3and2≻32\\succ 3, so bothj1j\_\{1\}andj2j\_\{2\}are more preferred thanj3j\_\{3\}\. The possible reduced linear extensionsσ∼r𝒟\\sigma\\sim\_\{r\}\\mathcal\{D\}are\(1,2,3\)\(1,2,3\)and\(2,1,3\)\(2,1,3\)\. The reduced DAG is presented in Figure[2](https://arxiv.org/html/2607.09817#S2.F2)\. Under MC, following \([10](https://arxiv.org/html/2607.09817#S2.E10)\), we have that

π\(1,2,3\)𝒟=π​\(1,\[4\]\)​Pr⁡\[1​⤳\{1\}​2\]​Pr⁡\[2​⤳\{1,2\}​3\]​and​π\(2,1,3\)𝒟=π​\(2,\[4\]\)​Pr⁡\[2​⤳\{2\}​1\]​Pr⁡\[1​⤳\{1,2\}​3\]\.\\displaystyle\\pi^\{\\mathcal\{D\}\}\_\{\(1,2,3\)\}=\\pi\(1,\[4\]\)\\Pr\[1\{\\overset\{\\\{1\\\}\}\{\\leadsto\}\}2\]\\Pr\[2\{\\overset\{\\\{1,2\\\}\}\{\\leadsto\}\}3\]\\text\{ and \}\\pi^\{\\mathcal\{D\}\}\_\{\(2,1,3\)\}=\\pi\(2,\[4\]\)\\Pr\[2\{\\overset\{\\\{2\\\}\}\{\\leadsto\}\}1\]\\Pr\[1\{\\overset\{\\\{1,2\\\}\}\{\\leadsto\}\}3\]\.
Under MNL, following \([12](https://arxiv.org/html/2607.09817#S2.E12)\), we have that

π\(1,2,3\)𝒟=π​\(1,\[4\]\)​π​\(2,\{2,3,4\}\)​π​\(3,\{3,4\}\)​and​π\(2,1,3\)𝒟=π​\(2,\[4\]\)​π​\(1,\{1,3,4\}\)​π​\(3,\{3,4\}\)\.\\displaystyle\\pi^\{\\mathcal\{D\}\}\_\{\(1,2,3\)\}=\\pi\(1,\[4\]\)\\pi\(2,\\\{2,3,4\\\}\)\\pi\(3,\\\{3,4\\\}\)\\text\{ and \}\\pi^\{\\mathcal\{D\}\}\_\{\(2,1,3\)\}=\\pi\(2,\[4\]\)\\pi\(1,\\\{1,3,4\\\}\)\\pi\(3,\\\{3,4\\\}\)\.
112233Figure 2:The reduced DAG for𝒟\\mathcal\{D\}

## 3The Value of Panel Information

In this section, we investigate the value of using panel data while estimating a choice model\. In Section[3\.1](https://arxiv.org/html/2607.09817#S3.SS1), we present the log\-likelihood functions, which measure the performance of choice model parameter estimation\. In Section[3\.2](https://arxiv.org/html/2607.09817#S3.SS2), we provide an example that highlights how exploiting individual transaction information can improve MC parameter estimation\. In Section[3\.3](https://arxiv.org/html/2607.09817#S3.SS3), we show that the MNL parameters can be identified without linking the transactions to specific customers when the choice probability vectors of a few assortments are given\. Sections[3\.2](https://arxiv.org/html/2607.09817#S3.SS2)and[3\.3](https://arxiv.org/html/2607.09817#S3.SS3)highlight the gap between MNL and MC in how exploiting individual transaction information can facilitate choice model estimation\.

### 3\.1The Log\-likelihood Objectives

Suppose we have a set of observable transactions\. Each transaction is associated with a customer identity \(ID\), the offer set, and the product chosen from the offer set\. In the traditional setting, the customer ID is not revealed, and transactions are treated as independent observational units\. In the setting with panel data, the customer ID of each transaction is revealed\. Customers are treated as independent observational units, while transactions from the same customer jointly induce a partial order\.

More specifically, in the traditional setting, we are given a set of transactionsℐ=\{\(jr,Sr\)∣r∈\[I\]\}\\mathcal\{I\}=\\\{\(j\_\{r\},S\_\{r\}\)\\mid r\\in\[I\]\\\}without the customer IDs\. Here,ℐ\\mathcal\{I\}hasIItransactions\(jr,Sr\)\(j\_\{r\},S\_\{r\}\)denoting thatjrj\_\{r\}is chosen from the offer setSrS\_\{r\}in transactionr∈\[I\]r\\in\[I\]\. Each transaction inℐ\\mathcal\{I\}is assumed to be independent\. The likelihood of havingℐ\\mathcal\{I\}is∏r=1Iπ​\(jr,Sr\)\\prod\_\{r=1\}^\{I\}\\pi\(j\_\{r\},S\_\{r\}\), and the log\-likelihood function is

Lt​r​a​d\(\.\)=∑r=1Ilogπ\(jr,Sr\)L^\{trad\}\(\.\)=\\sum\_\{r=1\}^\{I\}\\log\\pi\(j\_\{r\},S\_\{r\}\)\(13\)whereLt​r​a​dL^\{trad\}andπ​\(jr,Sr\)\\pi\(j\_\{r\},S\_\{r\}\)depend on the choice model parameters to be selected\. A choice model estimation algorithm aims to maximize the log\-likelihood objective \([13](https://arxiv.org/html/2607.09817#S3.E13)\) by selecting the best parameters\. The log\-likelihood objective \([13](https://arxiv.org/html/2607.09817#S3.E13)\) for MNL is concave\. For MC, the structure of \([13](https://arxiv.org/html/2607.09817#S3.E13)\) is more complicated and thus requires a more sophisticated algorithm like EMŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\)to find the parameters that achieve a local maximum\.

In the setting with panel data, the customer ID of each transaction is revealed, so each customer is associated with a set of transactions\. Recall that\[C\]\[C\]is the set of customers, and each customerc∈\[C\]c\\in\[C\]has a set of transactions𝒟c:=\{\(jℓc,Sℓc\)∣ℓ∈\[kc\]\}\\mathcal\{D\}^\{c\}:=\\\{\(j^\{c\}\_\{\\ell\},S^\{c\}\_\{\\ell\}\)\\mid\\ell\\in\[k\_\{c\}\]\\\}wherekck\_\{c\}is the number of transactions in𝒟c\\mathcal\{D\}^\{c\}\. Without loss of generality, we assume thatjℓc≠jℓ′cj^\{c\}\_\{\\ell\}\\neq j^\{c\}\_\{\\ell^\{\\prime\}\}for allℓ≠ℓ′\\ell\\neq\\ell^\{\\prime\}\. Each set of transactions𝒟c\\mathcal\{D\}^\{c\}is consistent with at least one strict preference list for\[n\]\+\[n\]\_\{\+\}, that is, there are no cycles induced by𝒟c\\mathcal\{D\}^\{c\}, and a reduced DAG for𝒟c\\mathcal\{D\}^\{c\}can be constructed\. It is assumed that the underlying strict preference of each customer is independently drawn\. Recall thatℰ𝒟c\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\}is the event that customerccselectsjℓcj^\{c\}\_\{\\ell\}fromSℓc\+\{S^\{c\}\_\{\\ell\}\}\_\{\+\}for allℓ∈\[kc\]\\ell\\in\[k\_\{c\}\]andπ𝒟c:=Pr⁡\[ℰ𝒟c\]\\pi\_\{\\mathcal\{D\}^\{c\}\}:=\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\}\]\. The likelihood of having\{𝒟c\}c∈\[C\]\\\{\\mathcal\{D\}^\{c\}\\\}\_\{c\\in\[C\]\}is∏c=1Cπ𝒟c\\prod\_\{c=1\}^\{C\}\\pi\_\{\\mathcal\{D\}^\{c\}\}, and the log\-likelihood function is

Lc​u​s\(\.\)=∑c=1Clogπ𝒟cL^\{cus\}\(\.\)=\\sum\_\{c=1\}^\{C\}\\log\\pi\_\{\\mathcal\{D\}^\{c\}\}\(14\)whereLc​u​sL^\{cus\}andπ𝒟c\\pi\_\{\\mathcal\{D\}^\{c\}\}depend on the choice model parameters to be selected\. A choice model estimation algorithm aims to maximize the log\-likelihood objective \([14](https://arxiv.org/html/2607.09817#S3.E14)\) by selecting the best parameters\. Unlike the traditional setting, for both MNL and MC, the objective \([14](https://arxiv.org/html/2607.09817#S3.E14)\) is not concave, and computingπ𝒟c\\pi\_\{\\mathcal\{D\}^\{c\}\}is \#P\-hard given the choice model parameters, as shown in Theorem[A\.1](https://arxiv.org/html/2607.09817#A1.Thmtheorem1)in the appendix\. For computational efficiency, an approximation for \([14](https://arxiv.org/html/2607.09817#S3.E14)\) under MNL, which is a concave function, is used as a heuristic inJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\)\.

### 3\.2Improving MC Parameter Estimation: An Example

In this section, we present an example showing that using panel data for choice model estimation could be beneficial for MC\.

Parameter identification in MC was studied inGupta and Hsu \([2020](https://arxiv.org/html/2607.09817#bib.bib39)\)\. For anyr∈\{2,3,…,n−1\}r\\in\\\{2,3,\.\.\.,n\-1\\\}, when the choice probability vectorsπ​\(S\+,S\)\\pi\(S\_\{\+\},S\)for allSSof sizerrorr\+1r\+1are given as input, the MC parameters can be perfectly identified\. We present an example where the set of assortments is limited, so that parameter identification becomes challenging in the traditional setting, but linking transactions from the same customer could provide extra information to facilitate MC parameter estimation\.

Let the parameter of the ground truth MC \(expressed with superscriptg​tgt\) withn=2n=2be as follows:λ1g​t=0\.6\\lambda^\{gt\}\_\{1\}=0\.6,λ2g​t=0\.4\\lambda^\{gt\}\_\{2\}=0\.4,ρ10g​t=1\\rho^\{gt\}\_\{10\}=1,ρ20g​t=1\\rho^\{gt\}\_\{20\}=1, and all other parameters are zero\. The goal is to estimate the MC parameters\(λ,ρ\)\(\\lambda,\\rho\)that maximize \([13](https://arxiv.org/html/2607.09817#S3.E13)\) or \([14](https://arxiv.org/html/2607.09817#S3.E14)\)\. Without loss of generality, we assume that there are no self\-cycles in the choice process, i\.e\.,ρ11=ρ22=0\\rho\_\{11\}=\\rho\_\{22\}=0\. Therefore, it is sufficient to estimate four parameters:λ1,λ2,ρ12\\lambda\_\{1\},\\lambda\_\{2\},\\rho\_\{12\}, andρ21\\rho\_\{21\}, so thatλ0=1−λ1−λ2\\lambda\_\{0\}=1\-\\lambda\_\{1\}\-\\lambda\_\{2\},ρ10=1−ρ12\\rho\_\{10\}=1\-\\rho\_\{12\}, andρ20=1−ρ21\\rho\_\{20\}=1\-\\rho\_\{21\}\. The illustration for the ground truth MC and the MC parameters to be determined is presented in Figure[3](https://arxiv.org/html/2607.09817#S3.F3)\.

11220ρ10g​t\\rho^\{gt\}\_\{10\}=1ρ20g​t\\rho^\{gt\}\_\{20\}=1λ1g​t=0\.6\\lambda^\{gt\}\_\{1\}=0\.6λ2g​t=0\.4\\lambda^\{gt\}\_\{2\}=0\.4λ=\[1−λ1−λ2,λ1,λ2\]T\\lambda=\[1\-\\lambda\_\{1\}\-\\lambda\_\{2\},\\lambda\_\{1\},\\lambda\_\{2\}\]^\{T\}ρ=\[1−ρ120ρ121−ρ21ρ210\]\\rho=\\begin\{bmatrix\}1\-\\rho\_\{12\}&0&\\rho\_\{12\}\\\\ 1\-\\rho\_\{21\}&\\rho\_\{21\}&0\\end\{bmatrix\}Figure 3:The ground truth MC and the parameters to be determined\.From Figure[3](https://arxiv.org/html/2607.09817#S3.F3), there are two types of customers with the following strict preferences:1≻0≻21\\succ 0\\succ 2and2≻0≻12\\succ 0\\succ 1, which occur with probability 0\.6 and 0\.4, respectively\. Each customer, randomly and independently drawn from the ground truth MC, is offered\{1\}\\\{1\\\}and\{2\}\\\{2\\\}once each\. WithCCrandomly drawn customers, we haveI=2​CI=2Ctransactions\. The customer choice \(selected product\) from the combination of each customer type and each assortment is presented in Table[1](https://arxiv.org/html/2607.09817#S3.T1)\.

Table 1:Customer choice of each combination\.In the traditional setting, when the number of customersCCbecomes large, the observed choice probabilities converge toπ~​\(0,\{1\}\)=0\.4\\tilde\{\\pi\}\(0,\\\{1\\\}\)=0\.4,π~​\(1,\{1\}\)=0\.6\\tilde\{\\pi\}\(1,\\\{1\\\}\)=0\.6,π~​\(0,\{2\}\)=0\.6\\tilde\{\\pi\}\(0,\\\{2\\\}\)=0\.6, andπ~​\(2,\{2\}\)=0\.4\\tilde\{\\pi\}\(2,\\\{2\\\}\)=0\.4\. Here,π~​\(j,S\)\\tilde\{\\pi\}\(j,S\)is the choice probability thatjjis chosen fromS\+S\_\{\+\}\. Different fromπ​\(j,S\)\\pi\(j,S\), which is the estimated choice probability that depends on the MC parameters,π~​\(j,S\)\\tilde\{\\pi\}\(j,S\)is the given input\. From \([13](https://arxiv.org/html/2607.09817#S3.E13)\), we aim to maximize

π~​\(1,\{1\}\)​log⁡π​\(1,\{1\}\)\+π~​\(0,\{2\}\)​log⁡π​\(0,\{2\}\)\+π~​\(0,\{1\}\)​log⁡π​\(0,\{1\}\)\+π~​\(2,\{2\}\)​log⁡π​\(2,\{2\}\)\\displaystyle\\tilde\{\\pi\}\(1,\\\{1\\\}\)\\log\\pi\(1,\\\{1\\\}\)\+\\tilde\{\\pi\}\(0,\\\{2\\\}\)\\log\\pi\(0,\\\{2\\\}\)\+\\tilde\{\\pi\}\(0,\\\{1\\\}\)\\log\\pi\(0,\\\{1\\\}\)\+\\tilde\{\\pi\}\(2,\\\{2\\\}\)\\log\\pi\(2,\\\{2\\\}\)=\\displaystyle=\\quad0\.6​log⁡\(λ1\+λ2​ρ21\)\+0\.6​log⁡\(λ0\+λ1​ρ10\)\+0\.4​log⁡\(λ0\+λ2​ρ20\)\+0\.4​log⁡\(λ2\+λ1​ρ12\)\\displaystyle 0\.6\\log\(\\lambda\_\{1\}\+\\lambda\_\{2\}\\rho\_\{21\}\)\+0\.6\\log\(\\lambda\_\{0\}\+\\lambda\_\{1\}\\rho\_\{10\}\)\+0\.4\\log\(\\lambda\_\{0\}\+\\lambda\_\{2\}\\rho\_\{20\}\)\+0\.4\\log\(\\lambda\_\{2\}\+\\lambda\_\{1\}\\rho\_\{12\}\)=\\displaystyle=\\quad0\.6​log⁡\(λ1\+λ2​ρ21\)\+0\.6​log⁡\(\(1−λ1−λ2\)\+λ1​\(1−ρ12\)\)\\displaystyle 0\.6\\log\(\\lambda\_\{1\}\+\\lambda\_\{2\}\\rho\_\{21\}\)\+0\.6\\log\(\(1\-\\lambda\_\{1\}\-\\lambda\_\{2\}\)\+\\lambda\_\{1\}\(1\-\\rho\_\{12\}\)\)\+0\.4​log⁡\(\(1−λ1−λ2\)\+λ2​\(1−ρ21\)\)\+0\.4​log⁡\(λ2\+λ1​ρ12\)\\displaystyle\+0\.4\\log\(\(1\-\\lambda\_\{1\}\-\\lambda\_\{2\}\)\+\\lambda\_\{2\}\(1\-\\rho\_\{21\}\)\)\+0\.4\\log\(\\lambda\_\{2\}\+\\lambda\_\{1\}\\rho\_\{12\}\)\(15\)subject toλ1\+λ2≤1\\lambda\_\{1\}\+\\lambda\_\{2\}\\leq 1, andλ1,λ2,ρ12,ρ21∈\[0,1\]\\lambda\_\{1\},\\lambda\_\{2\},\\rho\_\{12\},\\rho\_\{21\}\\in\[0,1\]\. Here, the factorCCis omitted, and we focus on the proportion of the choice outcomes\. We have thatπ​\(1,\{1\}\)=λ1\+λ2​ρ21\\pi\(1,\\\{1\\\}\)=\\lambda\_\{1\}\+\\lambda\_\{2\}\\rho\_\{21\}\. Whenρ11=ρ22=0\\rho\_\{11\}=\\rho\_\{22\}=0, product 1 is chosen from\{0,1\}\\\{0,1\\\}because either the customer starts from state 1 and ends the choice process or starts from state 2, transitions to state 1, then ends the choice process\. The reasoning forπ​\(0,\{1\}\)\\pi\(0,\\\{1\\\}\),π​\(0,\{2\}\)\\pi\(0,\\\{2\\\}\), andπ​\(2,\{2\}\)\\pi\(2,\\\{2\\\}\)follows analogously\.

One can verify that \([15](https://arxiv.org/html/2607.09817#S3.E15)\) is maximized when

π​\(1,\{1\}\)\\displaystyle\\pi\(1,\\\{1\\\}\)=λ1\+λ2​ρ21=0\.6,\\displaystyle=\\lambda\_\{1\}\+\\lambda\_\{2\}\\rho\_\{21\}=0\.6,π​\(0,\{1\}\)\\displaystyle\\pi\(0,\\\{1\\\}\)=\(1−λ1−λ2\)\+λ2​\(1−ρ21\)=0\.4,\\displaystyle=\(1\-\\lambda\_\{1\}\-\\lambda\_\{2\}\)\+\\lambda\_\{2\}\(1\-\\rho\_\{21\}\)=0\.4,π​\(2,\{2\}\)\\displaystyle\\pi\(2,\\\{2\\\}\)=λ2\+λ1​ρ12=0\.4,and\\displaystyle=\\lambda\_\{2\}\+\\lambda\_\{1\}\\rho\_\{12\}=0\.4,\\text\{and\}π​\(0,\{2\}\)\\displaystyle\\pi\(0,\\\{2\\\}\)=\(1−λ1−λ2\)\+λ1​\(1−ρ12\)=0\.6\.\\displaystyle=\(1\-\\lambda\_\{1\}\-\\lambda\_\{2\}\)\+\\lambda\_\{1\}\(1\-\\rho\_\{12\}\)=0\.6\.The optimal solutions are parameterized byλ1\\lambda\_\{1\}andλ2\\lambda\_\{2\}:

ρ12=0\.4−λ2λ1<1​and​ρ21=0\.6−λ1λ2<1,where​λ1∈\(0,0\.6\],λ2∈\(0,0\.4\],\\displaystyle\\rho\_\{12\}=\\frac\{0\.4\-\\lambda\_\{2\}\}\{\\lambda\_\{1\}\}<1\\text\{ and \}\\rho\_\{21\}=\\frac\{0\.6\-\\lambda\_\{1\}\}\{\\lambda\_\{2\}\}<1,\\text\{where \}\\lambda\_\{1\}\\in\(0,0\.6\],\\lambda\_\{2\}\\in\(0,0\.4\],and​λ1\+λ2∈\[0\.6,1\]\.\\displaystyle\\text\{ and \}\\lambda\_\{1\}\+\\lambda\_\{2\}\\in\[0\.6,1\]\.\(16\)The feasible region forλ1\\lambda\_\{1\}andλ2\\lambda\_\{2\}is a 2D polytope, which does not perfectly recover the MC parameters\. Note thatρ12g​t=ρ21g​t=0\\rho^\{gt\}\_\{12\}=\\rho^\{gt\}\_\{21\}=0whileρ12\\rho\_\{12\}andρ21\\rho\_\{21\}can be positive\. The limited number of assortments and the limited information from the choice probability profileπ~\\tilde\{\\pi\}do not capture the following scenarios: no customers will transition from state 1 to state 2 when product 1 is not offered, and no customers will transition from state 2 to state 1 when product 2 is not offered\.

In the setting with panel data, we observe that each customer of type1≻0≻21\\succ 0\\succ 2selects product11from\{0,1\}\\\{0,1\\\}and product0from\{0,2\}\\\{0,2\\\}, so the strict preference1≻0≻21\\succ 0\\succ 2is fully observed\. Similarly, if the customer is of type2≻0≻12\\succ 0\\succ 1, the strict preference is also fully observed\. When the number of customer samplesCCbecomes large, we observe that there are 60 percent of type1≻0≻21\\succ 0\\succ 2customers and 40 percent of type2≻0≻12\\succ 0\\succ 1customers\. From \([10](https://arxiv.org/html/2607.09817#S2.E10)\) and \([14](https://arxiv.org/html/2607.09817#S3.E14)\), we aim to maximize

0\.6​log⁡\(π​\(1,\{1,2\}\)​Pr⁡\[1​⤳\{1\}​0\]\)\+0\.4​log⁡\(π​\(2,\{1,2\}\)​Pr⁡\[2​⤳\{2\}​0\]\)\\displaystyle 0\.6\\log\(\\pi\(1,\\\{1,2\\\}\)\\Pr\[1\{\\overset\{\\\{1\\\}\}\{\\leadsto\}\}0\]\)\+0\.4\\log\(\\pi\(2,\\\{1,2\\\}\)\\Pr\[2\{\\overset\{\\\{2\\\}\}\{\\leadsto\}\}0\]\)=\\displaystyle=\\quad0\.6​log⁡\(λ1​ρ10\)\+0\.4​log⁡\(λ2​ρ20\)=0\.6​log⁡\(λ1​\(1−ρ12\)\)\+0\.4​log⁡\(λ2​\(1−ρ21\)\)\\displaystyle 0\.6\\log\(\\lambda\_\{1\}\\rho\_\{10\}\)\+0\.4\\log\(\\lambda\_\{2\}\\rho\_\{20\}\)=0\.6\\log\(\\lambda\_\{1\}\(1\-\\rho\_\{12\}\)\)\+0\.4\\log\(\\lambda\_\{2\}\(1\-\\rho\_\{21\}\)\)\(17\)subject toλ1\+λ2≤1\\lambda\_\{1\}\+\\lambda\_\{2\}\\leq 1, andλ1,λ2,ρ12,ρ21∈\[0,1\]\\lambda\_\{1\},\\lambda\_\{2\},\\rho\_\{12\},\\rho\_\{21\}\\in\[0,1\]\. Whenρ11=ρ22=0\\rho\_\{11\}=\\rho\_\{22\}=0,π​\(1,\{1,2\}\)​Pr⁡\[1​⤳\{1\}​0\]=λ1​ρ10\\pi\(1,\\\{1,2\\\}\)\\Pr\[1\{\\overset\{\\\{1\\\}\}\{\\leadsto\}\}0\]=\\lambda\_\{1\}\\rho\_\{10\}is the probability of having the strict preference1≻0≻21\\succ 0\\succ 2andπ​\(2,\{1,2\}\)​Pr⁡\[2​⤳\{2\}​0\]=λ2​ρ20\\pi\(2,\\\{1,2\\\}\)\\Pr\[2\{\\overset\{\\\{2\\\}\}\{\\leadsto\}\}0\]=\\lambda\_\{2\}\\rho\_\{20\}is the probability of having the strict preference2≻0≻12\\succ 0\\succ 1\. The optimal solution isρ12=ρ21=0\\rho\_\{12\}=\\rho\_\{21\}=0,λ1=0\.6\\lambda\_\{1\}=0\.6, andλ2=0\.4\\lambda\_\{2\}=0\.4, which recovers the ground truth MC parameters\. Note that this solution is also optimal for \([15](https://arxiv.org/html/2607.09817#S3.E15)\)\.

One might wonder how much the objective \([17](https://arxiv.org/html/2607.09817#S3.E17)\) would deteriorate while using an optimal solution to \([15](https://arxiv.org/html/2607.09817#S3.E15)\)\. Plugging \([16](https://arxiv.org/html/2607.09817#S3.E16)\) into \([17](https://arxiv.org/html/2607.09817#S3.E17)\), we have the log\-likelihood

0\.6​log⁡\(λ1​\(1−ρ12\)\)\+0\.4​log⁡\(λ2​\(1−ρ21\)\)=0\.6​log⁡\(λ1\+λ2−0\.4\)\+0\.4​log⁡\(λ1\+λ2−0\.6\)\.\\displaystyle 0\.6\\log\(\\lambda\_\{1\}\(1\-\\rho\_\{12\}\)\)\+0\.4\\log\(\\lambda\_\{2\}\(1\-\\rho\_\{21\}\)\)=0\.6\\log\(\\lambda\_\{1\}\+\\lambda\_\{2\}\-0\.4\)\+0\.4\\log\(\\lambda\_\{1\}\+\\lambda\_\{2\}\-0\.6\)\.\(18\)Whenλ1\+λ2→0\.6\+\\lambda\_\{1\}\+\\lambda\_\{2\}\\to 0\.6^\{\+\}, \([18](https://arxiv.org/html/2607.09817#S3.E18)\) reaches−∞\-\\infty\. The customer either starts at state 0 with probability 0\.4 and ends the choice process, or starts at state 1 \(or 2\) and transitions from state 1 to state 2 \(respectively, state 2 to state 1\) with high probability\. The estimated MC parameters deviate dramatically from the ground truth\.

### 3\.3Parameter Identification for MNL

In this section, we show that the MNL parameters can be identified in the traditional setting when the choice probability vectors of a few assortments are given\.

We assume that the choice probability follows an underlying MNL\. Suppose a collection of offer sets𝒮=\{Si⊆\[n\]∣i∈\[m\]\}\\mathcal\{S\}=\\\{S\_\{i\}\\subseteq\[n\]\\mid i\\in\[m\]\\\}is given for somem\>0m\>0\. To ensure that we have information about each product, we assume that𝒮\\mathcal\{S\}is*exhaustive*\. That is, all products in\[n\]\[n\]are offered, i\.e\.,∪S∈𝒮S=\[n\]\\cup\_\{S\\in\\mathcal\{S\}\}S=\[n\]\. For eachi∈\[m\]i\\in\[m\], the offer setSiS\_\{i\}is offered with a given probabilitypi\>0p\_\{i\}\>0\.

In the traditional setting, the choice probability vectors\{π~​\(S\+,S\)\}S∈𝒮\\\{\\tilde\{\\pi\}\(S\_\{\+\},S\)\\\}\_\{S\\in\\mathcal\{S\}\}, denoting the probability thatj∈S\+j\\in S\_\{\+\}is chosen fromS\+S\_\{\+\}for allj∈S\+j\\in S\_\{\+\}, is the given input\. Suppose we sampleIIrandom transactions independently, whereSiS\_\{i\}is offered with probabilitypip\_\{i\}, andjjis chosen with probabilityπ~​\(j,Si\)\\tilde\{\\pi\}\(j,S\_\{i\}\)\. WhenIIapproaches infinity, the proportion thatSiS\_\{i\}is offered converges topip\_\{i\}\. WhenSiS\_\{i\}is offered, the proportion thatjjis chosen fromSi\+\{S\_\{i\}\}\_\{\+\}converges toπ~​\(j,Si\)\\tilde\{\\pi\}\(j,S\_\{i\}\)\. Building on \([8](https://arxiv.org/html/2607.09817#S2.E8)\) and \([13](https://arxiv.org/html/2607.09817#S3.E13)\), we aim to solve

max​∑i=1m∑j∈Si\+pi​π~​\(j,Si\)​log⁡\(pi​π​\(j,Si\)\)=maxv​∑i=1m∑j∈Si\+pi​π~​\(j,Si\)​\(log⁡pi\+log⁡vj−log⁡V​\(Si\+\)\)\\max\\sum\_\{i=1\}^\{m\}\\sum\_\{j\\in\{S\_\{i\}\}\_\{\+\}\}p\_\{i\}\\tilde\{\\pi\}\(j,S\_\{i\}\)\\log\(p\_\{i\}\\pi\(j,S\_\{i\}\)\)=\\max\_\{v\}\\sum\_\{i=1\}^\{m\}\\sum\_\{j\\in\{S\_\{i\}\}\_\{\+\}\}p\_\{i\}\\tilde\{\\pi\}\(j,S\_\{i\}\)\(\\log p\_\{i\}\+\\log v\_\{j\}\-\\log V\(\{S\_\{i\}\}\_\{\+\}\)\)\(19\)by selecting the best MNL parameters\. Here,pip\_\{i\}andπ~​\(j,Si\)\\tilde\{\\pi\}\(j,S\_\{i\}\)are the input, and the estimated probabilityπ​\(j,S\)\\pi\(j,S\)depends on the MNL parametersvvto be selected\.

Without loss of generality, we setv0=1v\_\{0\}=1\. For eachi∈\[m\]i\\in\[m\], we solve the system of linear equations

π~​\(j,Si\)​\(1\+∑ℓ∈Sivℓ\)=vj∀j∈Si\\tilde\{\\pi\}\(j,S\_\{i\}\)\(1\+\\sum\_\{\\ell\\in S\_\{i\}\}v\_\{\\ell\}\)=v\_\{j\}\\quad\\forall j\\in S\_\{i\}\(20\)to get the value ofvjv\_\{j\}so that the estimated probability matchesπ~​\(j,Si\)\\tilde\{\\pi\}\(j,S\_\{i\}\)\. \([20](https://arxiv.org/html/2607.09817#S3.E20)\) has a unique solutionvj=π~​\(j,Si\)/π~​\(0,Si\)v\_\{j\}=\\tilde\{\\pi\}\(j,S\_\{i\}\)/\\tilde\{\\pi\}\(0,S\_\{i\}\)for allj∈Sij\\in S\_\{i\}\. We note that ifj∈Sij\\in S\_\{i\}andj∈Si′j\\in S\_\{i^\{\\prime\}\}fori≠i′i\\neq i^\{\\prime\}, thenvjv\_\{j\}is the solution to both the systems of linear equations ofSiS\_\{i\}andSi′S\_\{i^\{\\prime\}\}since the choice probability vectors are consistent with the same underlying MNL\. Because𝒮\\mathcal\{S\}is exhaustive, we obtain the value ofvjv\_\{j\}for allj∈\[n\]j\\in\[n\]\. Combining the system of linear equations \([20](https://arxiv.org/html/2607.09817#S3.E20)\) for alli∈\[m\]i\\in\[m\], we have the following grand system of linear equations

π~​\(j,Si\)​\(1\+∑ℓ∈Sivℓ\)=vj∀j∈Si,∀i∈\[m\]\.\\tilde\{\\pi\}\(j,S\_\{i\}\)\(1\+\\sum\_\{\\ell\\in S\_\{i\}\}v\_\{\\ell\}\)=v\_\{j\}\\quad\\forall j\\in S\_\{i\},\\forall i\\in\[m\]\.\(21\)We show that the solution to \([21](https://arxiv.org/html/2607.09817#S3.E21)\) withv0=1v\_\{0\}=1is optimal for \([19](https://arxiv.org/html/2607.09817#S3.E19)\)\.

###### Proposition 3\.1\.

Given an exhaustive𝒮=\{Si⊆\[n\]∣i∈\[m\]\}\\mathcal\{S\}=\\\{S\_\{i\}\\subseteq\[n\]\\mid i\\in\[m\]\\\}withpi\>0p\_\{i\}\>0for alli∈\[m\]i\\in\[m\]and choice probability vectors that are consistent with the underlying MNL, the solution to \([21](https://arxiv.org/html/2607.09817#S3.E21)\) is the unique optimal solution to \([19](https://arxiv.org/html/2607.09817#S3.E19)\) whenv0v\_\{0\}is fixed to 1\. The unique optimal solution does not depend on thepip\_\{i\}’s\.

###### Proof\.

LetLt​r​a​d​\(v\)=∑i=1m∑j∈Si\+pi​π~​\(j,Si\)​\(log⁡pi\+log⁡vj−log⁡V​\(Si\+\)\)L^\{trad\}\(v\)=\\sum\_\{i=1\}^\{m\}\\sum\_\{j\\in\{S\_\{i\}\}\_\{\+\}\}p\_\{i\}\\tilde\{\\pi\}\(j,S\_\{i\}\)\(\\log p\_\{i\}\+\\log v\_\{j\}\-\\log V\(\{S\_\{i\}\}\_\{\+\}\)\)\. Taking the partial derivative ofLt​r​a​dL^\{trad\}with respect tovjv\_\{j\}, we have

∂Lt​r​a​d∂vj=∑i∈\[m\]:j∈Sipi​\(π~​\(j,Si\)​\(1vj−1V​\(Si\+\)\)−∑ℓ∈Si\+∖\{j\}π~​\(ℓ,Si\)V​\(Si\+\)\)\.\\displaystyle\\frac\{\\partial L^\{trad\}\}\{\\partial v\_\{j\}\}=\\sum\_\{i\\in\[m\]:j\\in S\_\{i\}\}p\_\{i\}\\left\(\\tilde\{\\pi\}\(j,S\_\{i\}\)\\left\(\\frac\{1\}\{v\_\{j\}\}\-\\frac\{1\}\{V\(\{S\_\{i\}\}\_\{\+\}\)\}\\right\)\-\\sum\_\{\\ell\\in\{S\_\{i\}\}\_\{\+\}\\setminus\\\{j\\\}\}\\frac\{\\tilde\{\\pi\}\(\\ell,S\_\{i\}\)\}\{V\(\{S\_\{i\}\}\_\{\+\}\)\}\\right\)\.Letvj′v^\{\\prime\}\_\{j\}be the solution to \([21](https://arxiv.org/html/2607.09817#S3.E21)\)\. LetV′​\(S\)=∑ℓ∈Svℓ′V^\{\\prime\}\(S\)=\\sum\_\{\\ell\\in S\}v^\{\\prime\}\_\{\\ell\}for anyS⊆\[n\]\+S\\subseteq\[n\]\_\{\+\}\. For alli∈\[m\]i\\in\[m\]such thatj∈Sij\\in S\_\{i\}, we haveπ~​\(j,Si\)=vj′/V′​\(Si\+\)\\tilde\{\\pi\}\(j,S\_\{i\}\)=v^\{\\prime\}\_\{j\}/V^\{\\prime\}\(\{S\_\{i\}\}\_\{\+\}\)\. Evaluating the derivative atvj=vj′v\_\{j\}=v^\{\\prime\}\_\{j\}, we have

π~​\(j,Si\)​\(1vj′−1V′​\(Si\+\)\)−∑ℓ∈Si\+∖\{j\}π~​\(ℓ,Si\)V′​\(Si\+\)=\\displaystyle\\tilde\{\\pi\}\(j,S\_\{i\}\)\\left\(\\frac\{1\}\{v^\{\\prime\}\_\{j\}\}\-\\frac\{1\}\{V^\{\\prime\}\(\{S\_\{i\}\}\_\{\+\}\)\}\\right\)\-\\sum\_\{\\ell\\in\{S\_\{i\}\}\_\{\+\}\\setminus\\\{j\\\}\}\\frac\{\\tilde\{\\pi\}\(\\ell,S\_\{i\}\)\}\{V^\{\\prime\}\(\{S\_\{i\}\}\_\{\+\}\)\}=vj′V′​\(Si\+\)​1vj′−∑ℓ∈Si\+vℓ′V′​\(Si\+\)2=1V′​\(Si\+\)−1V′​\(Si\+\)=0\\displaystyle\\frac\{v^\{\\prime\}\_\{j\}\}\{V^\{\\prime\}\(\{S\_\{i\}\}\_\{\+\}\)\}\\frac\{1\}\{v^\{\\prime\}\_\{j\}\}\-\\sum\_\{\\ell\\in\{S\_\{i\}\}\_\{\+\}\}\\frac\{v^\{\\prime\}\_\{\\ell\}\}\{V^\{\\prime\}\(\{S\_\{i\}\}\_\{\+\}\)^\{2\}\}=\\frac\{1\}\{V^\{\\prime\}\(\{S\_\{i\}\}\_\{\+\}\)\}\-\\frac\{1\}\{V^\{\\prime\}\(\{S\_\{i\}\}\_\{\+\}\)\}=0for alli∈\[m\]i\\in\[m\]such thatj∈Sij\\in S\_\{i\}\. This implies that∂Lt​r​a​d/∂vj=0\\partial L^\{trad\}/\\partial v\_\{j\}=0whenvj=vj′v\_\{j\}=v^\{\\prime\}\_\{j\}for allj∈\[n\]j\\in\[n\]\. Writingvj=exp⁡\(μj\)v\_\{j\}=\\exp\(\\mu\_\{j\}\)and fixingμ0=0\\mu\_\{0\}=0,Lt​r​a​dL^\{trad\}is strictly concave inμ\\mu\. Moreover, we have∂Lt​r​a​d/∂μj=0\\partial L^\{trad\}/\\partial\\mu\_\{j\}=0whenvj=vj′v\_\{j\}=v^\{\\prime\}\_\{j\}for allj∈\[n\]j\\in\[n\]since∂Lt​r​a​d/∂μj=vj​∂Lt​r​a​d/∂vj=0\\partial L^\{trad\}/\\partial\\mu\_\{j\}=v\_\{j\}\\partial L^\{trad\}/\\partial v\_\{j\}=0andvj\>0v\_\{j\}\>0\. Since the collection𝒮\\mathcal\{S\}is exhaustive and every assortment includes the no\-purchase option with fixedμ0\\mu\_\{0\}, the solution to \([21](https://arxiv.org/html/2607.09817#S3.E21)\) is the unique optimal solution that maximizesLt​r​a​dL^\{trad\}\. ∎

Proposition[3\.1](https://arxiv.org/html/2607.09817#S3.Thmtheorem1)implies that when the ground truth is an MNL, and the number of transaction samples is sufficient, then it suffices to gather the choice probability information to identify an MNL\. In a scenario where the customer ID is provided for each transaction, ignoring correlations among transactions from the same customer does not hinder recovery of the MNL parameters\.

## 4Markov Chain Model Estimation with Panel Data

In this section, we present EM algorithms for MC parameter estimation with panel data\. Our EM algorithms are adapted from the traditional EM algorithm inŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\)\. In Section[4\.1](https://arxiv.org/html/2607.09817#S4.SS1), we provide the incomplete and complete likelihood functions used in the EM algorithms\. In Section[4\.2](https://arxiv.org/html/2607.09817#S4.SS2), we present the EM algorithmCus, which assumes that each customer has a set of transactions consistent with at least one strict preference, or equivalently, each customer is associated with a reduced DAG\. This setting captures the DAG\-based partial customer preference information used inJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\)\. In practice, however, individual transactions might not be consistent with any strict preference lists, thus inducing cyclic preferences\. In Section[4\.3](https://arxiv.org/html/2607.09817#S4.SS3), we introduce a hybrid EM algorithmHyb, which combines the traditional EM algorithm andCusand provides the flexibility to accommodate transactions that induce cyclic preferences\.

### 4\.1Incomplete and Complete Likelihood Functions

Recall that\[C\]\[C\]is the set of customers and that each customerc∈\[C\]c\\in\[C\]has a set of transactions𝒟c:=\{\(jℓc,Sℓc\)∣ℓ∈\[kc\]\}\\mathcal\{D\}^\{c\}:=\\\{\(j^\{c\}\_\{\\ell\},S^\{c\}\_\{\\ell\}\)\\mid\\ell\\in\[k\_\{c\}\]\\\}wherekck\_\{c\}is the number of transactions in𝒟c\\mathcal\{D\}^\{c\}\. Without loss of generality, we assume thatjℓc≠jℓ′cj^\{c\}\_\{\\ell\}\\neq j^\{c\}\_\{\\ell^\{\\prime\}\}for allℓ≠ℓ′\\ell\\neq\\ell^\{\\prime\}\. Each set of transactions𝒟c\\mathcal\{D\}^\{c\}is consistent with at least one strict preference list for\[n\]\+\[n\]\_\{\+\}, that is, there are no cycles induced by𝒟c\\mathcal\{D\}^\{c\}, and a reduced DAG for𝒟c\\mathcal\{D\}^\{c\}can be constructed\. Unlike the traditional EM algorithmŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\), which assumes that each transaction is independent, we assume that each customer is independent and transactions associated with the same customer are dependent\. Our EM algorithm selects MC parameters to maximize the likelihood of the observed customer transaction histories, equivalently represented by reduced DAGs\.

Building on \([14](https://arxiv.org/html/2607.09817#S3.E14)\), givenρ\\rhoandλ\\lambda, the log\-likelihood of having the dataset\{𝒟c\}c∈C\\\{\\mathcal\{D\}^\{c\}\\\}\_\{c\\in C\}is

LI​\(λ,ρ\)=∑c=1Clog⁡Pr⁡\[ℰ𝒟c∣λ,ρ\]L\_\{I\}\(\\lambda,\\rho\)=\\sum\_\{c=1\}^\{C\}\\log\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\}\\mid\\lambda,\\rho\]where the subscriptIIstands for*incomplete*andPr⁡\[ℰ𝒟c∣λ,ρ\]\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\}\\mid\\lambda,\\rho\]denotes the probability that the eventℰ𝒟c\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\}occurs given the MC parametersρ\\rhoandλ\\lambda\. AlthoughPr⁡\[ℰ𝒟c∣λ,ρ\]\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\}\\mid\\lambda,\\rho\]has a closed\-form expression according to \([9](https://arxiv.org/html/2607.09817#S2.E9)\), \([10](https://arxiv.org/html/2607.09817#S2.E10)\), and \([11](https://arxiv.org/html/2607.09817#S2.E11)\), it is convoluted and requires a better structure to design an EM algorithm\. We introduce complete\-data variables that record the initial state and transition counts of the unobserved random walk\.

LetFic,σ∈\{0,1\}F^\{c,\\sigma\}\_\{i\}\\in\\\{0,1\\\}be a random variable such thatFic,σ=1F^\{c,\\sigma\}\_\{i\}=1if and only if customerccenters the system from stateiiand its random walk is in the form of the reduced linear extensionσ\\sigma\. For eachσ∼r𝒟c\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}ands∈\[kc\]s\\in\[k\_\{c\}\], letUsσ,c:=∪ℓ=skcSσ​\(ℓ\)cU^\{\\sigma,c\}\_\{s\}:=\\cup\_\{\\ell=s\}^\{k\_\{c\}\}S^\{c\}\_\{\\sigma\(\\ell\)\}andAsσ,c:=Usσ,c¯A^\{\\sigma,c\}\_\{s\}:=\\overline\{U^\{\\sigma,c\}\_\{s\}\}\. LetXi​jc,σ,sX^\{c,\\sigma,s\}\_\{ij\}be a random variable defined as follows:

1. 1\.If the random walk is in the form ofσ\\sigma: 1. \(a\)Ifs=1s=1, thenXi​jc,σ,sX^\{c,\\sigma,s\}\_\{ij\}is the number of times customercctransitions the choice from stateiito statejjduring the course of her choice process starting from the initial state and ending at the first visit ofjσ​\(1\)j\_\{\\sigma\(1\)\}, through states inA1σ,cA^\{\\sigma,c\}\_\{1\}\. 2. \(b\)Ifs\>1s\>1, thenXi​jc,σ,sX^\{c,\\sigma,s\}\_\{ij\}is the number of times customercctransitions the choice from stateiito statejjduring the course of her choice process starting from the first visit ofjσ​\(s−1\)j\_\{\\sigma\(s\-1\)\}and ending at the first visit ofjσ​\(s\)j\_\{\\sigma\(s\)\}, through states inAsσ,cA^\{\\sigma,c\}\_\{s\}\.
2. 2\.Otherwise, the random walk is not consistent withσ\\sigma, soXi​jc,σ,s=0X^\{c,\\sigma,s\}\_\{ij\}=0\.

GivenFc:=\{Fic,σ\}σ∼r𝒟c,i∈\[n\]\+F^\{c\}:=\\\{F^\{c,\\sigma\}\_\{i\}\\\}\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\},i\\in\[n\]\_\{\+\}\},F:=\{Fc\}c∈\[C\]F:=\\\{F^\{c\}\\\}\_\{c\\in\[C\]\},Xc:=\{Xi​jc,σ,s\}σ∼r𝒟c,s∈\[kc\],i∈\[n\],j∈\[n\]\+X^\{c\}:=\\\{X^\{c,\\sigma,s\}\_\{ij\}\\\}\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\},s\\in\[k\_\{c\}\],i\\in\[n\],j\\in\[n\]\_\{\+\}\}, andX:=\{Xc\}c∈\[C\]X:=\\\{X^\{c\}\\\}\_\{c\\in\[C\]\}, we derive a well\-structured likelihood function\. Suppose the random walk of customerccis in the form ofσ\\sigma, then for anyσ′≠σ\\sigma^\{\\prime\}\\neq\\sigma,Fic,σ′=0F^\{c,\\sigma^\{\\prime\}\}\_\{i\}=0andXi​jc,σ′,s=0X^\{c,\\sigma^\{\\prime\},s\}\_\{ij\}=0; besides, the customer enters the system at one of the states in\[n\]\+\[n\]\_\{\+\}, so∑i∈\[n\]\+Fic,σ=1\\sum\_\{i\\in\[n\]\_\{\+\}\}F^\{c,\\sigma\}\_\{i\}=1\. This implies that∑σ∼r𝒟c∑i∈\[n\]\+Fic,σ=1\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}\\sum\_\{i\\in\[n\]\_\{\+\}\}F^\{c,\\sigma\}\_\{i\}=1and the likelihood that customercchas a random walk in the form ofσ\\sigmaand enters the system from stateiiis∏i∈\[n\]\+λiFic,σ\\prod\_\{i\\in\[n\]\_\{\+\}\}\\lambda\_\{i\}^\{F^\{c,\\sigma\}\_\{i\}\}\. After entering stateii, customerccperforms a random walk until the first visit ofjσ​\(1\)j\_\{\\sigma\(1\)\}, via transitioning from stateiito statejjforXi​jc,σ,1X^\{c,\\sigma,1\}\_\{ij\}times\. The likelihood of this sub random walk is∏i∈\[n\],j∈\[n\]\+ρi​jXi​jc,σ,1\\prod\_\{i\\in\[n\],j\\in\[n\]\_\{\+\}\}\\rho\_\{ij\}^\{X^\{c,\\sigma,1\}\_\{ij\}\}, regardless of the ordering of the visits inA1σ,cA^\{\\sigma,c\}\_\{1\}\. Similarly, fors\>1s\>1, after the first visit ofjσ​\(s−1\)j\_\{\\sigma\(s\-1\)\}, customerccperforms a random walk until the first visit ofjσ​\(s\)j\_\{\\sigma\(s\)\}, via transitioning from stateiito statejjforXi​jc,σ,sX^\{c,\\sigma,s\}\_\{ij\}times, regardless of the ordering of the visits inAsσ,cA^\{\\sigma,c\}\_\{s\}\. The likelihood of this sub random walk is∏i∈\[n\],j∈\[n\]\+ρi​jXi​jc,σ,s\\prod\_\{i\\in\[n\],j\\in\[n\]\_\{\+\}\}\\rho\_\{ij\}^\{X^\{c,\\sigma,s\}\_\{ij\}\}\. By the Markov property, conditional on customercc’s random walk being in the form ofσ\\sigma, the likelihood factors over the prefix segment and the subsequent inter\-arrival segments\. Therefore, the likelihood that customercchas a random walk in the form ofσ\\sigma,FcF^\{c\}, andXcX^\{c\}is\(∏i∈\[n\]\+λiFic,σ\)​∏s=1kc∏i∈\[n\],j∈\[n\]\+ρi​jXi​jc,σ,s\\left\(\\prod\_\{i\\in\[n\]\_\{\+\}\}\\lambda\_\{i\}^\{F^\{c,\\sigma\}\_\{i\}\}\\right\)\\prod\_\{s=1\}^\{k\_\{c\}\}\\prod\_\{i\\in\[n\],j\\in\[n\]\_\{\+\}\}\\rho\_\{ij\}^\{X^\{c,\\sigma,s\}\_\{ij\}\}\.

Taking into account all customersc∈\[C\]c\\in\[C\]and all possible reduced linear extensionsσ\\sigma, the likelihood of having the dataset\{𝒟c\}c∈\[C\]\\\{\\mathcal\{D\}^\{c\}\\\}\_\{c\\in\[C\]\}that is consistent withFFandXXis

∏c=1C∏σ∼r𝒟c\(\(∏i∈\[n\]\+λiFic,σ\)​∏s=1kc∏i∈\[n\]∏j∈\[n\]\+ρi​jXi​jc,σ,s\),\\prod\_\{c=1\}^\{C\}\\prod\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}\\left\(\\left\(\\prod\_\{i\\in\[n\]\_\{\+\}\}\\lambda\_\{i\}^\{F^\{c,\\sigma\}\_\{i\}\}\\right\)\\prod\_\{s=1\}^\{k\_\{c\}\}\\prod\_\{i\\in\[n\]\}\\prod\_\{j\\in\[n\]\_\{\+\}\}\\rho\_\{ij\}^\{X^\{c,\\sigma,s\}\_\{ij\}\}\\right\),and the log\-likelihood is

LC​\(λ,ρ\)=∑c=1C∑σ∼r𝒟c\(∑i∈\[n\]\+Fic,σ​log⁡λi\+∑s=1kc∑i∈\[n\]∑j∈\[n\]\+Xi​jc,σ,s​log⁡ρi​j\)\.L\_\{C\}\(\\lambda,\\rho\)=\\sum\_\{c=1\}^\{C\}\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}\\left\(\\sum\_\{i\\in\[n\]\_\{\+\}\}F^\{c,\\sigma\}\_\{i\}\\log\\lambda\_\{i\}\+\\sum\_\{s=1\}^\{k\_\{c\}\}\\sum\_\{i\\in\[n\]\}\\sum\_\{j\\in\[n\]\_\{\+\}\}X^\{c,\\sigma,s\}\_\{ij\}\\log\\rho\_\{ij\}\\right\)\.\(22\)The log\-likelihood function \([22](https://arxiv.org/html/2607.09817#S4.E22)\) is written in terms of the latent variablesFFandXX, where the subscriptCCstands for*complete*\. Sincelog⁡x\\log xis concave inxx,LCL\_\{C\}is concave inλ\\lambdaandρ\\rho\. However, this formulation is not yet useful since we do not have access toFFandXX\. Nevertheless, the EM algorithmCuspresented in the next section replaces these latent variables by their conditional expectations\.

### 4\.2The EM AlgorithmCus

In this section, we describe the EM algorithmCus\. An overview is provided in Section[4\.2\.1](https://arxiv.org/html/2607.09817#S4.SS2.SSS1)\. The expectation step and the maximization step are presented in Sections[4\.2\.2](https://arxiv.org/html/2607.09817#S4.SS2.SSS2)and[4\.2\.3](https://arxiv.org/html/2607.09817#S4.SS2.SSS3), respectively\.

#### 4\.2\.1Overview of the Algorithm

Letλt\\lambda^\{t\}andρt\\rho^\{t\}be the estimated MC parameters at the end of iterationtt\. Letλ0\\lambda^\{0\}andρ0\\rho^\{0\}be the initial MC parameters\. Each iteration consists of an expectation step and a maximization step\.

In the expectation step of iterationtt, we first estimate the expected value ofFic,σF^\{c,\\sigma\}\_\{i\}andXi​jc,σ,sX^\{c,\\sigma,s\}\_\{ij\}, given the eventℰ𝒟\\mathcal\{E\}\_\{\\mathcal\{D\}\}denoting that customercc’s transaction set is𝒟c\\mathcal\{D\}^\{c\}, and the MC parametersλt−1\\lambda^\{t\-1\}andρt−1\\rho^\{t\-1\}\. The estimation forFic,σF^\{c,\\sigma\}\_\{i\}andXi​jc,σ,sX^\{c,\\sigma,s\}\_\{ij\}at iterationttare denoted as

Fic,σ,t=𝔼​\[Fic,σ∣ℰ𝒟c,λt−1,ρt−1\]​and​Xi​jc,σ,s,t=𝔼​\[Xi​jc,σ,s∣ℰ𝒟c,λt−1,ρt−1\],respectively\.F^\{c,\\sigma,t\}\_\{i\}=\\mathbb\{E\}\[F^\{c,\\sigma\}\_\{i\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\]\\text\{ and \}X^\{c,\\sigma,s,t\}\_\{ij\}=\\mathbb\{E\}\[X^\{c,\\sigma,s\}\_\{ij\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\],\\text\{ respectively\}\.LetFt:=\{Fic,σ,t\}c∈\[C\],σ∼r𝒟c,i∈\[n\]\+F^\{t\}:=\\\{F^\{c,\\sigma,t\}\_\{i\}\\\}\_\{c\\in\[C\],\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\},i\\in\[n\]\_\{\+\}\}andXt=\{Xi​jc,σ,s,t\}c∈\[C\],σ∼r𝒟c,s∈\[kc\],i∈\[n\],j∈\[n\]\+X^\{t\}=\\\{X^\{c,\\sigma,s,t\}\_\{ij\}\\\}\_\{c\\in\[C\],\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\},s\\in\[k\_\{c\}\],i\\in\[n\],j\\in\[n\]\_\{\+\}\}\. The expected value ofLC​\(λt−1,ρt−1\)L\_\{C\}\(\\lambda^\{t\-1\},\\rho^\{t\-1\}\), conditional on\{ℰ𝒟\}c∈\[C\]\\\{\\mathcal\{E\}\_\{\\mathcal\{D\}\}\\\}\_\{c\\in\[C\]\}and the MC parametersλt−1\\lambda^\{t\-1\}andρt−1\\rho^\{t\-1\}, can be obtained by pluggingFtF^\{t\}andXtX^\{t\}in \([22](https://arxiv.org/html/2607.09817#S4.E22)\)\.

In the maximization step of iterationtt, givenFtF^\{t\}andXtX^\{t\}, we selectλt\\lambda^\{t\}andρt\\rho^\{t\}as the solution that maximizes the log\-likelihood objective \([22](https://arxiv.org/html/2607.09817#S4.E22)\)\.

If the difference between\(λt,ρt\)\(\\lambda^\{t\},\\rho^\{t\}\)and\(λt−1,ρt−1\)\(\\lambda^\{t\-1\},\\rho^\{t\-1\}\)is within tolerance, we end the EM algorithm\. The algorithm repeats the expectation and maximization steps until convergence\.444The proof of convergence closely followsŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\); Nettleton \([1999](https://arxiv.org/html/2607.09817#bib.bib12)\)hence omitted\.

The EM algorithmCusis briefly outlined as follows\.

Step 1 \(Initialization\):Initializeλ0\\lambda^\{0\}andρ0\\rho^\{0\}where∑i=0nλi0=1\\sum\_\{i=0\}^\{n\}\\lambda^\{0\}\_\{i\}=1and∑j=0nρi​j0=1\\sum\_\{j=0\}^\{n\}\\rho^\{0\}\_\{ij\}=1for alli∈\[n\]i\\in\[n\]\.

Step 2 \(Expectation\):At iterationtt, givenλt−1\\lambda^\{t\-1\}andρt−1\\rho^\{t\-1\}, setFic,σ,t=𝔼​\[Fic,σ∣ℰ𝒟c,λt−1,ρt−1\]F^\{c,\\sigma,t\}\_\{i\}=\\mathbb\{E\}\[F^\{c,\\sigma\}\_\{i\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\]andXi​jc,σ,s,t=𝔼​\[Xi​jc,σ,s∣ℰ𝒟c,λt−1,ρt−1\]X^\{c,\\sigma,s,t\}\_\{ij\}=\\mathbb\{E\}\[X^\{c,\\sigma,s\}\_\{ij\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\]\.

Step 3 \(Maximization\):GivenFtF^\{t\}andXtX^\{t\}, letλt,ρt\\lambda^\{t\},\\rho^\{t\}be the optimal solution of

maxλ,ρ⁡LC​\(λ,ρ\)​over​λ∈ℝ≥0n\+1,ρ∈ℝ≥0n×\(n\+1\)​s\.t\.​∑i∈\[n\]\+λi=1​and​∑j∈\[n\]\+ρi​j=1∀i∈\[n\]\.\\max\_\{\\lambda,\\rho\}L\_\{C\}\(\\lambda,\\rho\)\\text\{ over \}\\lambda\\in\\mathbb\{R\}^\{n\+1\}\_\{\\geq 0\},\\rho\\in\\mathbb\{R\}^\{n\\times\(n\+1\)\}\_\{\\geq 0\}\\text\{ s\.t\. \}\\sum\_\{i\\in\[n\]\_\{\+\}\}\\lambda\_\{i\}=1\\text\{ and \}\\sum\_\{j\\in\[n\]\_\{\+\}\}\\rho\_\{ij\}=1\\quad\\forall i\\in\[n\]\.\(23\)
Step 4 \(Convergence Check\):If the difference between\(λt,ρt\)\(\\lambda^\{t\},\\rho^\{t\}\)and\(λt−1,ρt−1\)\(\\lambda^\{t\-1\},\\rho^\{t\-1\}\)is within tolerance, terminate the algorithm\. Otherwise, move on to the next iteration and go to Step 2\.

We emphasize thatCusis more computationally intensive than the traditional EM algorithmŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\)due to the blowup in the number of random variables\. Nevertheless, our experimental results in Section[5](https://arxiv.org/html/2607.09817#S5)show thatCusis practically feasible when the number of transactions per customer and the number of reduced linear extensions per customer are at a reasonable scale\.

#### 4\.2\.2The Expectation Step

In this section, we compute𝔼​\[Fic,σ∣ℰ𝒟c,λt−1,ρt−1\]\\mathbb\{E\}\[F^\{c,\\sigma\}\_\{i\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\]and𝔼​\[Xi​jc,σ,s∣ℰ𝒟c,λt−1,ρt−1\]\\mathbb\{E\}\[X^\{c,\\sigma,s\}\_\{ij\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\]\. For notation brevity, we focus on one specific customer and drop the notationccfor the customer\. We compute the expected value ofFiσF^\{\\sigma\}\_\{i\}andXi​jσ,sX^\{\\sigma,s\}\_\{ij\}when the customer has a transaction set𝒟\\mathcal\{D\}and the parameters areλt−1\\lambda^\{t\-1\}andρt−1\\rho^\{t\-1\}\.

##### Computation of𝔼​\[Fiσ∣ℰ𝒟,λt−1,ρt−1\]\\mathbb\{E\}\[F^\{\\sigma\}\_\{i\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\]\.

Suppose the random walk is in the form of a reduced linear extensionσ∼r𝒟\\sigma\\sim\_\{r\}\\mathcal\{D\}\. Then, we cannot have any state inU:=∪ℓ=1kSℓU:=\\cup\_\{\\ell=1\}^\{k\}S\_\{\\ell\}as the initial state when the customer enters the system, exceptjσ​\(1\)j\_\{\\sigma\(1\)\}\. Forσ∼r𝒟\\sigma\\sim\_\{r\}\\mathcal\{D\}, recall the computation ofπσ𝒟\\pi^\{\\mathcal\{D\}\}\_\{\\sigma\}in \([10](https://arxiv.org/html/2607.09817#S2.E10)\)\. Let

p𝒟​\(σ\):=∏s=1k−1Pr⁡\[jσ​\(s\)​⤳As\+1σ​jσ​\(s\+1\)\]p\_\{\\mathcal\{D\}\}\(\\sigma\):=\\prod\_\{s=1\}^\{k\-1\}\\Pr\[j\_\{\\sigma\(s\)\}\{\\overset\{A^\{\\sigma\}\_\{s\+1\}\}\{\\leadsto\}\}j\_\{\\sigma\(s\+1\)\}\]\(24\)denote the probability of having a random walk in the form ofjσ​\(1\)​⤳A2σ​jσ​\(2\)​⤳A3σ​…​⤳Akσ​jσ​\(k\)j\_\{\\sigma\(1\)\}\\overset\{A^\{\\sigma\}\_\{2\}\}\{\\leadsto\}j\_\{\\sigma\(2\)\}\\overset\{A^\{\\sigma\}\_\{3\}\}\{\\leadsto\}\.\.\.\\overset\{A^\{\\sigma\}\_\{k\}\}\{\\leadsto\}j\_\{\\sigma\(k\)\}after the first visit ofjσ​\(1\)j\_\{\\sigma\}\(1\)\. Letq𝒟​\(i,σ\)q\_\{\\mathcal\{D\}\}\(i,\\sigma\)be the probability that the random walk is in the form ofσ\\sigmaand the initial state isii\. We have that

q𝒟​\(i,σ\)=\{λi​Pr⁡\[i​⤳U¯​jσ​\(1\)\]​p𝒟​\(σ\)if​i∈U¯,λi​p𝒟​\(σ\)if​i=jσ​\(1\),0otherwise,q\_\{\\mathcal\{D\}\}\(i,\\sigma\)=\\begin\{cases\}\\lambda\_\{i\}\\Pr\[i\\overset\{\\overline\{U\}\}\{\\leadsto\}j\_\{\\sigma\(1\)\}\]p\_\{\\mathcal\{D\}\}\(\\sigma\)&\\text\{if \}i\\in\\overline\{U\},\\\\ \\lambda\_\{i\}p\_\{\\mathcal\{D\}\}\(\\sigma\)&\\text\{if \}i=j\_\{\\sigma\(1\)\},\\\\ 0&\\text\{otherwise\},\\end\{cases\}\(25\)where the parameters\(λ,ρ\)\(\\lambda,\\rho\)in \([25](https://arxiv.org/html/2607.09817#S4.E25)\) are replaced withλt−1\\lambda^\{t\-1\}andρt−1\\rho^\{t\-1\}, respectively\. Conditional onℰ𝒟\\mathcal\{E\}\_\{\\mathcal\{D\}\}, if the random walk is not in the form ofσ\\sigma, thenFiσ=0F^\{\\sigma\}\_\{i\}=0; otherwise, the expected value ofFiσF^\{\\sigma\}\_\{i\}is the probability thatiiis the initial state and the random walk is in the form ofσ\\sigma\. Hence,

𝔼​\[Fiσ∣ℰ𝒟,λt−1,ρt−1\]=q𝒟​\(i,σ\)π𝒟,\\mathbb\{E\}\[F^\{\\sigma\}\_\{i\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\]=\\frac\{q\_\{\\mathcal\{D\}\}\(i,\\sigma\)\}\{\\pi\_\{\\mathcal\{D\}\}\},whereq𝒟​\(i,σ\)q\_\{\\mathcal\{D\}\}\(i,\\sigma\)in \([25](https://arxiv.org/html/2607.09817#S4.E25)\) andπ𝒟\\pi\_\{\\mathcal\{D\}\}in \([11](https://arxiv.org/html/2607.09817#S2.E11)\) have closed\-form expressions in terms of the transaction set𝒟\\mathcal\{D\}and the MC parametersλt−1\\lambda^\{t\-1\}andρt−1\\rho^\{t\-1\}\.

##### Computation of𝔼​\[Xi​jσ,s∣ℰ𝒟,λt−1,ρt−1\]\\mathbb\{E\}\[X^\{\\sigma,s\}\_\{ij\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\]\.

If the random walk is not in the form ofσ\\sigma, thenXi​jσ,s=0X^\{\\sigma,s\}\_\{ij\}=0\. We consider the event that the random walk is in the form ofσ\\sigma\. Conditional onℰ𝒟\\mathcal\{E\}\_\{\\mathcal\{D\}\}, the probability that the random walk is in the form ofσ\\sigmaisπ​\(jσ​\(1\),U\)​p𝒟​\(σ\)/π𝒟\\pi\(j\_\{\\sigma\(1\)\},U\)p\_\{\\mathcal\{D\}\}\(\\sigma\)/\\pi\_\{\\mathcal\{D\}\}asUUis first\-visited atjσ​\(1\)j\_\{\\sigma\(1\)\}and the remaining is in the form of the suffix ofσ\\sigmaafter the first visit ofjσ​\(1\)j\_\{\\sigma\(1\)\}, which occurs with probabilityp𝒟​\(σ\)p\_\{\\mathcal\{D\}\}\(\\sigma\)\.

We are interested in computing the expected number of times that the customer transitions the choice from stateiito statejjduring the course of her choice process starting from the first visit ofjσ​\(s−1\)j\_\{\\sigma\(s\-1\)\}and ending at the first visit ofjσ​\(s\)j\_\{\\sigma\(s\)\}, through states inAsσA^\{\\sigma\}\_\{s\}, whens\>1s\>1\. Whens=1s=1, we compute the number of times the choice transitions from stateiito statejjduring the course of the choice process from the initial state to the first visit ofjσ​\(1\)j\_\{\\sigma\}\(1\)\. To account fors=1s=1ands\>1s\>1, we consider a more general problem\.

Letη:=\{ηi\}i∈\[n\]\+∈ℝ≥0n\+1\\eta:=\\\{\\eta\_\{i\}\\\}\_\{i\\in\[n\]\_\{\+\}\}\\in\\mathbb\{R\}^\{n\+1\}\_\{\\geq 0\}with∑i∈\[n\]\+ηi=1\\sum\_\{i\\in\[n\]\_\{\+\}\}\\eta\_\{i\}=1denote a distribution for the starting state of a random walk\. For example, when the customer enters the system,η=λ\\eta=\\lambda; right after the customer’s first visit ofjσ​\(s\)j\_\{\\sigma\(s\)\},ηjσ​\(s\)=1\\eta\_\{j\_\{\\sigma\(s\)\}\}=1andηj=0\\eta\_\{j\}=0forj∈\[n\]\+∖\{jσ​\(s\)\}j\\in\[n\]\_\{\+\}\\setminus\\\{j\_\{\\sigma\(s\)\}\\\}\. LetA⊆\[n\]A\\subseteq\[n\]be the set of states that are allowed to be visited before arriving at any state inA¯\+\\overline\{A\}\_\{\+\}\. Consider the following system of linear equations adapted from \([4](https://arxiv.org/html/2607.09817#S2.E4)\):

θη​\(j,A¯\)=ηj\+∑i∈Aρi​j​θη​\(i,A¯\)∀j∈\[n\]\+\.\\theta\_\{\\eta\}\(j,\\overline\{A\}\)=\\eta\_\{j\}\+\\sum\_\{i\\in A\}\\rho\_\{ij\}\\theta\_\{\\eta\}\(i,\\overline\{A\}\)\\quad\\forall j\\in\[n\]\_\{\+\}\.Following the same argument as in Section[2\.2\.1](https://arxiv.org/html/2607.09817#S2.SS2.SSS1),θη​\(j,A¯\)\\theta\_\{\\eta\}\(j,\\overline\{A\}\)denotes the expected number of times that statejjis visited during the course of the choice process when the starting state distribution isη\\etaandA¯\\overline\{A\}is offered\. ForT⊆\[n\]\+T\\subseteq\[n\]\_\{\+\}, letη​\(T\):=\{ηj\}j∈T\\eta\(T\):=\\\{\\eta\_\{j\}\\\}\_\{j\\in T\}denote a sub\-vector ofη\\etawith coordinates inTT, and letθη​\(T,A¯\):=\{θη​\(j,A¯\)\}j∈T\\theta\_\{\\eta\}\(T,\\overline\{A\}\):=\\\{\\theta\_\{\\eta\}\(j,\\overline\{A\}\)\\\}\_\{j\\in T\}\. Following \([5](https://arxiv.org/html/2607.09817#S2.E5)\), the closed\-form expression forθη​\(A,A¯\)\\theta\_\{\\eta\}\(A,\\overline\{A\}\)is

θη​\(A,A¯\)=\(\(I−ρ​\(A,A\)\)T\)−1​η​\(A\)=\(\(I−ρ​\(A,A\)\)−1\)T​η​\(A\)\.\\theta\_\{\\eta\}\(A,\\overline\{A\}\)=\\left\(\(I\-\\rho\(A,A\)\)^\{T\}\\right\)^\{\-1\}\\eta\(A\)=\\left\(\(I\-\\rho\(A,A\)\)^\{\-1\}\\right\)^\{T\}\\eta\(A\)\.Following \([6](https://arxiv.org/html/2607.09817#S2.E6)\), the closed\-form expression forθη​\(A¯\+,A¯\)\\theta\_\{\\eta\}\(\\overline\{A\}\_\{\+\},\\overline\{A\}\)is

θη​\(A¯\+,A¯\)=η​\(A¯\+\)\+ρ​\(A,A¯\+\)T​\(\(I−ρ​\(A,A\)\)−1\)T​η​\(A\)\.\\displaystyle\\theta\_\{\\eta\}\(\\overline\{A\}\_\{\+\},\\overline\{A\}\)=\\eta\(\\overline\{A\}\_\{\+\}\)\+\\rho\(A,\\overline\{A\}\_\{\+\}\)^\{T\}\\left\(\(I\-\\rho\(A,A\)\)^\{\-1\}\\right\)^\{T\}\\eta\(A\)\.
LetYi​jY\_\{ij\}be a random variable that denotes the number of times the choice transitions from stateiito statejjduring the choice process starting from a given state distributionη\\etaand ending at a state inA¯\+\\overline\{A\}\_\{\+\}\. Letd∈A¯\+d\\in\\overline\{A\}\_\{\+\}be a destination state\. Letℱη​\(d,A¯\)\\mathcal\{F\}\_\{\\eta\}\(d,\\overline\{A\}\)be the event that the random walk enters at stateddupon the first visit ofA¯\+\\overline\{A\}\_\{\+\}, starting from distributionη\\eta\. Given the starting state distributionη\\etaand the offer setA¯\\overline\{A\}, conditional onddbeing chosen fromA¯\+\\overline\{A\}\_\{\+\}, a closed\-form expression for the expectation ofYi​jY\_\{ij\}is as follows\.

###### Lemma 4\.1\(Şimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\)\)\.

𝔼​\[Yi​j∣ℱη​\(d,A¯\)\]=Pr⁡\[j​⤳𝐴​d\]​ρi​j​θη​\(i,A¯\)θη​\(d,A¯\)\.\\mathbb\{E\}\[Y\_\{ij\}\\mid\\mathcal\{F\}\_\{\\eta\}\(d,\\overline\{A\}\)\]=\\frac\{\\Pr\[j\\overset\{A\}\{\\leadsto\}d\]\\rho\_\{ij\}\\theta\_\{\\eta\}\(i,\\overline\{A\}\)\}\{\\theta\_\{\\eta\}\(d,\\overline\{A\}\)\}\.

Equipped with Lemma[4\.1](https://arxiv.org/html/2607.09817#S4.Thmtheorem1), we compute𝔼​\[Xi​jσ,s∣ℰ𝒟,λt−1,ρt−1\]\\mathbb\{E\}\[X^\{\\sigma,s\}\_\{ij\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\]\. Recall that when the random walk is in the form ofσ\\sigma, it is partitioned into sub random walks, starting from an initial state to the first visit ofjσ​\(1\)j\_\{\\sigma\(1\)\}, followed by the first visit ofjσ​\(s−1\)j\_\{\\sigma\(s\-1\)\}to the first visit ofjσ​\(s\)j\_\{\\sigma\(s\)\}fors\>1s\>1\. By the Markov property, conditional on the endpoints of each segment and the reduced linear extensionσ\\sigma, the likelihood factors into the product of the segment transition probabilities\. Leteje^\{j\}denote a state distribution vector such thatejj=1e^\{j\}\_\{j\}=1forj∈\[n\]j\\in\[n\]andej′j=0e^\{j\}\_\{j^\{\\prime\}\}=0forj′∈\[n\]\+∖\{j\}j^\{\\prime\}\\in\[n\]\_\{\+\}\\setminus\\\{j\\\}\. We have the following closed\-form expression for𝔼​\[Xi​jσ,s∣ℰ𝒟,λt−1,ρt−1\]\\mathbb\{E\}\[X^\{\\sigma,s\}\_\{ij\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\]:

𝔼​\[Xi​jσ,s∣ℰ𝒟,λt−1,ρt−1\]=\{πσ𝒟π𝒟​Pr⁡\[j​⤳U¯​jσ​\(1\)\]​ρi​j​θλ​\(i,U\)θλ​\(jσ​\(1\),U\)if​s=1,πσ𝒟π𝒟​Pr⁡\[j​⤳Asσ​jσ​\(s\)\]​ρi​j​θejσ​\(s−1\)​\(i,Usσ\)θejσ​\(s−1\)​\(jσ​\(s\),Usσ\)if​s∈\[k\]∖\{1\}\.\\mathbb\{E\}\[X^\{\\sigma,s\}\_\{ij\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\]=\\begin\{cases\}\\mbox\{\\Large$\\frac\{\\pi^\{\\mathcal\{D\}\}\_\{\\sigma\}\}\{\\pi\_\{\\mathcal\{D\}\}\}\\frac\{\\Pr\[j\\overset\{\\overline\{U\}\}\{\\leadsto\}j\_\{\\sigma\(1\)\}\]\\rho\_\{ij\}\\theta\_\{\\lambda\}\(i,U\)\}\{\\theta\_\{\\lambda\}\(j\_\{\\sigma\(1\)\},U\)\}$\}&\\text\{if \}s=1,\\\\ \\mbox\{\\Large$\\frac\{\\pi^\{\\mathcal\{D\}\}\_\{\\sigma\}\}\{\\pi\_\{\\mathcal\{D\}\}\}\\frac\{\\Pr\[j\\overset\{A^\{\\sigma\}\_\{s\}\}\{\\leadsto\}j\_\{\\sigma\(s\)\}\]\\rho\_\{ij\}\\theta\_\{e^\{j\_\{\\sigma\(s\-1\)\}\}\}\(i,U^\{\\sigma\}\_\{s\}\)\}\{\\theta\_\{e^\{j\_\{\\sigma\(s\-1\)\}\}\}\(j\_\{\\sigma\(s\)\},U^\{\\sigma\}\_\{s\}\)\}$\}&\\text\{if \}s\\in\[k\]\\setminus\\\{1\\\}\.\\end\{cases\}\(26\)The MC parameters in \([26](https://arxiv.org/html/2607.09817#S4.E26)\) areλt−1\\lambda^\{t\-1\}andρt−1\\rho^\{t\-1\}\. The termπσ𝒟/π𝒟\\pi^\{\\mathcal\{D\}\}\_\{\\sigma\}/\\pi\_\{\\mathcal\{D\}\}is the probability that the random walk is in the form ofσ\\sigma\. The random variableXi​jσ,sX^\{\\sigma,s\}\_\{ij\}is captured by the random variableYi​jY\_\{ij\}in Lemma[4\.1](https://arxiv.org/html/2607.09817#S4.Thmtheorem1)\. Whens=1s=1, the starting distribution isλ\\lambda, the admissible states areU¯\\overline\{U\}, and the destination state isjσ​\(1\)j\_\{\\sigma\(1\)\}\. Whens\>1s\>1, the starting distribution isejσ​\(s−1\)e^\{j\_\{\\sigma\(s\-1\)\}\}, the admissible states areAsσA^\{\\sigma\}\_\{s\}, and the destination state isjσ​\(s\)j\_\{\\sigma\(s\)\}\.

#### 4\.2\.3The Maximization Step

After computingFtF^\{t\}andXtX^\{t\}in the expectation step, we aim to solve \([23](https://arxiv.org/html/2607.09817#S4.E23)\), which can be decomposed into the following optimization sub\-problems:

maxλ​∑c=1C∑σ∼r𝒟c∑i∈\[n\]\+Fic,σ​log⁡λioverλ∈ℝ≥0n\+1s\.t\.∑i∈\[n\]\+λi=1\\max\_\{\\lambda\}\\sum\_\{c=1\}^\{C\}\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}\\sum\_\{i\\in\[n\]\_\{\+\}\}F^\{c,\\sigma\}\_\{i\}\\log\\lambda\_\{i\}\\quad\\text\{over\}\\quad\\lambda\\in\\mathbb\{R\}^\{n\+1\}\_\{\\geq 0\}\\quad\\text\{s\.t\.\}\\quad\\sum\_\{i\\in\[n\]\_\{\+\}\}\\lambda\_\{i\}=1\(27\)and

maxρ​∑c=1C∑σ∼r𝒟c∑s=1kc∑i∈\[n\]∑j∈\[n\]\+Xi​jc,σ,s​log⁡ρi​j​over​ρ∈ℝ≥0n×\(n\+1\)s\.t\.​∑j∈\[n\]\+ρi​j=1∀i∈\[n\]\.\\max\_\{\\rho\}\\sum\_\{c=1\}^\{C\}\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}\\sum\_\{s=1\}^\{k\_\{c\}\}\\sum\_\{i\\in\[n\]\}\\sum\_\{j\\in\[n\]\_\{\+\}\}X^\{c,\\sigma,s\}\_\{ij\}\\log\\rho\_\{ij\}\\text\{ over \}\\rho\\in\\mathbb\{R\}^\{n\\times\(n\+1\)\}\_\{\\geq 0\}\\quad\\text\{s\.t\.\}\\sum\_\{j\\in\[n\]\_\{\+\}\}\\rho\_\{ij\}=1\\quad\\forall i\\in\[n\]\.\(28\)\([27](https://arxiv.org/html/2607.09817#S4.E27)\) and \([28](https://arxiv.org/html/2607.09817#S4.E28)\) are in the form of the problem of computing the maximum likelihood estimators under the multinomial distribution\. According toBishop \([2006](https://arxiv.org/html/2607.09817#bib.bib13)\), the optimal solutionx∗x^\{\*\}of the problem

maxx​∑i=1mai​log⁡xioverx∈ℝ≥0ms\.t\.∑i=1mxi=1\\max\_\{x\}\\sum\_\{i=1\}^\{m\}a\_\{i\}\\log x\_\{i\}\\quad\\text\{over\}\\quad x\\in\\mathbb\{R\}^\{m\}\_\{\\geq 0\}\\quad\\text\{s\.t\.\}\\quad\\sum\_\{i=1\}^\{m\}x\_\{i\}=1\(29\)wherea∈ℝ≥0ma\\in\\mathbb\{R\}^\{m\}\_\{\\geq 0\}and∑i=1mai\>0\\sum\_\{i=1\}^\{m\}a\_\{i\}\>0, is unique and has a closed\-form expressionxi∗=ai/\(∑i=1mai\)x^\{\*\}\_\{i\}=a\_\{i\}/\(\\sum\_\{i=1\}^\{m\}a\_\{i\}\)for alli∈\[m\]i\\in\[m\]\.555For ease of notation, whenai=0a\_\{i\}=0, thenxi=0x\_\{i\}=0, and we setai​log⁡xi=0a\_\{i\}\\log x\_\{i\}=0in the objective of \([29](https://arxiv.org/html/2607.09817#S4.E29)\)\.Therefore, we set

λit=∑c=1C∑σ∼r𝒟cFic,σ,t∑c=1C∑σ∼r𝒟c∑j∈\[n\]\+Fjc,σ,t∀i∈\[n\]\+\\lambda^\{t\}\_\{i\}=\\frac\{\\sum\_\{c=1\}^\{C\}\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}F^\{c,\\sigma,t\}\_\{i\}\}\{\\sum\_\{c=1\}^\{C\}\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}\\sum\_\{j\\in\[n\]\_\{\+\}\}F^\{c,\\sigma,t\}\_\{j\}\}\\quad\\forall i\\in\[n\]\_\{\+\}and

ρi​jt=∑c=1C∑σ∼r𝒟c∑s=1kcXi​jc,σ,s,t∑c=1C∑σ∼r𝒟c∑s=1kc∑k∈\[n\]\+Xi​kc,σ,s,t∀i∈\[n\],j∈\[n\]\+\.\\rho^\{t\}\_\{ij\}=\\frac\{\\sum\_\{c=1\}^\{C\}\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}\\sum\_\{s=1\}^\{k\_\{c\}\}X^\{c,\\sigma,s,t\}\_\{ij\}\}\{\\sum\_\{c=1\}^\{C\}\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}\\sum\_\{s=1\}^\{k\_\{c\}\}\\sum\_\{k\\in\[n\]\_\{\+\}\}X^\{c,\\sigma,s,t\}\_\{ik\}\}\\quad\\forall i\\in\[n\],j\\in\[n\]\_\{\+\}\.

### 4\.3The EM AlgorithmHyb

In addition to the customer transactions\{𝒟c\}c∈\[C\]\\\{\\mathcal\{D\}^\{c\}\\\}\_\{c\\in\[C\]\}where each customer’s transaction set is consistent with at least one strict preference, the hybrid EM algorithmHybalso takes the*independent transaction set*ℐ\\mathcal\{I\}as the input\. The independent transaction setℐ=\{\(jr,Sr\)∣r∈\[I\]\}\\mathcal\{I\}=\\\{\(j\_\{r\},S\_\{r\}\)\\mid r\\in\[I\]\\\}hasIItransactions\(jr,Sr\)\(j\_\{r\},S\_\{r\}\)denoting thatjrj\_\{r\}is chosen from the offer setSrS\_\{r\}in transactionrr\. Each transaction inIIis assumed to be independent\.Hybaims to maximize the likelihood of having both\{𝒟c\}c∈\[C\]\\\{\\mathcal\{D\}^\{c\}\\\}\_\{c\\in\[C\]\}andℐ\\mathcal\{I\}, by selecting the MC parameters\. If all transactions are added toℐ\\mathcal\{I\}, thenHybcaptures the traditional EM algorithm\.

In practice, the independent transaction set provides the flexibility to adapt to real\-life datasets\. Suppose a customer has a transaction set that induces a cyclic preference\. One heuristic is to construct an arc\-weighted directed graph that captures the customer’s preference according to the transactions, and extract a DAG that best describes the customer’s preference\. The DAG construction might involve arc deletions\. Transactions that violate the DAG preference are then not used in the DAG construction, but could provide information about the preference distribution\. As opposed to the DAG\-based heuristic inJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\)that discards the information from the violating arcs, one approach is to include these DAG\-violating transactions inℐ\\mathcal\{I\}\. Another heuristic is to consider the most recent transactions in the DAG construction, and include the older transactions and the DAG\-violating transactions inℐ\\mathcal\{I\}\.

LetGir∈\{0,1\}G^\{r\}\_\{i\}\\in\\\{0,1\\\}be a random variable such thatGir=1G^\{r\}\_\{i\}=1if and only if the random walk of transactionrrenters the system from stateii\. LetYi​jrY^\{r\}\_\{ij\}be a random variable denoting the number of times the choice transitions from stateiito statejjduring the course of the choice process in the random walk of transactionrr\. LetG:=\{Gir\}r∈\[I\],i∈\[n\]\+G:=\\\{G^\{r\}\_\{i\}\\\}\_\{r\\in\[I\],i\\in\[n\]\_\{\+\}\}andY:=\{Yi​jr\}r∈\[I\],i∈\[n\],j∈\[n\]\+Y:=\\\{Y^\{r\}\_\{ij\}\\\}\_\{r\\in\[I\],i\\in\[n\],j\\in\[n\]\_\{\+\}\}\. FollowingŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\), the likelihood of havingℐ\\mathcal\{I\}is

∏r=1I\(\(∏i∈\[n\]\+λiGir\)​∏i∈\[n\],j∈\[n\]\+ρi​jYi​jr\),\\prod\_\{r=1\}^\{I\}\\left\(\\left\(\\prod\_\{i\\in\[n\]\_\{\+\}\}\\lambda\_\{i\}^\{G^\{r\}\_\{i\}\}\\right\)\\prod\_\{\\begin\{subarray\}\{c\}i\\in\[n\],\\\\ j\\in\[n\]\_\{\+\}\\end\{subarray\}\}\\rho\_\{ij\}^\{Y^\{r\}\_\{ij\}\}\\right\),and the log\-likelihood is

L​\(λ,ρ\)=∑r=1I\(∑i∈\[n\]\+Gir​log⁡λi\+∑i∈\[n\]∑j∈\[n\]\+Yi​jr​log⁡ρi​j\)\.L\(\\lambda,\\rho\)=\\sum\_\{r=1\}^\{I\}\\left\(\\sum\_\{i\\in\[n\]\_\{\+\}\}G^\{r\}\_\{i\}\\log\\lambda\_\{i\}\+\\sum\_\{i\\in\[n\]\}\\sum\_\{j\\in\[n\]\_\{\+\}\}Y^\{r\}\_\{ij\}\\log\\rho\_\{ij\}\\right\)\.\(30\)The log\-likelihood of having both\{𝒟c\}c∈\[C\]\\\{\\mathcal\{D\}^\{c\}\\\}\_\{c\\in\[C\]\}andℐ\\mathcal\{I\}, called the*hybrid log\-likelihood*, is

LH​\(λ,ρ\)=LC​\(λ,ρ\)\+L​\(λ,ρ\)\.L\_\{H\}\(\\lambda,\\rho\)=L\_\{C\}\(\\lambda,\\rho\)\+L\(\\lambda,\\rho\)\.
The hybrid EM algorithmHybis briefly outlined as follows\.

Step 1 \(Initialization\):Initializeλ0\\lambda^\{0\}andρ0\\rho^\{0\}where∑i=0nλi0=1\\sum\_\{i=0\}^\{n\}\\lambda^\{0\}\_\{i\}=1and∑j=0nρi​j0=1\\sum\_\{j=0\}^\{n\}\\rho^\{0\}\_\{ij\}=1for alli∈\[n\]i\\in\[n\]\.

Step 2 \(Expectation\):At iterationtt, givenλt−1\\lambda^\{t\-1\}andρt−1\\rho^\{t\-1\}, setFic,σ,t=𝔼​\[Fic,σ∣ℰ𝒟c,λt−1,ρt−1\]F^\{c,\\sigma,t\}\_\{i\}=\\mathbb\{E\}\[F^\{c,\\sigma\}\_\{i\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\],Xi​jc,σ,s,t=𝔼​\[Xi​jc,σ,s∣ℰ𝒟c,λt−1,ρt−1\]X^\{c,\\sigma,s,t\}\_\{ij\}=\\mathbb\{E\}\[X^\{c,\\sigma,s\}\_\{ij\}\\mid\\mathcal\{E\}\_\{\\mathcal\{D\}^\{c\}\},\\lambda^\{t\-1\},\\rho^\{t\-1\}\],Gir,t=𝔼​\[Gir∣ℰ​\(jr,Sr\),λt−1,ρt−1\]G^\{r,t\}\_\{i\}=\\mathbb\{E\}\[G^\{r\}\_\{i\}\\mid\\mathcal\{E\}\(j\_\{r\},S\_\{r\}\),\\lambda^\{t\-1\},\\rho^\{t\-1\}\], andYi​jr,t=𝔼​\[Yi​jr∣ℰ​\(jr,Sr\),λt−1,ρt−1\]Y^\{r,t\}\_\{ij\}=\\mathbb\{E\}\[Y^\{r\}\_\{ij\}\\mid\\mathcal\{E\}\(j\_\{r\},S\_\{r\}\),\\lambda^\{t\-1\},\\rho^\{t\-1\}\], whereℰ​\(jr,Sr\)\\mathcal\{E\}\(j\_\{r\},S\_\{r\}\)denotes the event thatjrj\_\{r\}is chosen fromSr\+\{S\_\{r\}\}\_\{\+\}\.

Step 3 \(Maximization\):GivenFtF^\{t\},XtX^\{t\},GtG^\{t\}, andYtY^\{t\}, letλt,ρt\\lambda^\{t\},\\rho^\{t\}be the optimal solution of

maxλ,ρ⁡LH​\(λ,ρ\)​over​λ∈ℝ≥0n\+1,ρ∈ℝ≥0n×\(n\+1\)​s\.t\.​∑i∈\[n\]\+λi=1​and​∑j∈\[n\]\+ρi​j=1∀i∈\[n\]\.\\max\_\{\\lambda,\\rho\}L\_\{H\}\(\\lambda,\\rho\)\\text\{ over \}\\lambda\\in\\mathbb\{R\}^\{n\+1\}\_\{\\geq 0\},\\rho\\in\\mathbb\{R\}^\{n\\times\(n\+1\)\}\_\{\\geq 0\}\\text\{ s\.t\. \}\\sum\_\{i\\in\[n\]\_\{\+\}\}\\lambda\_\{i\}=1\\text\{ and \}\\sum\_\{j\\in\[n\]\_\{\+\}\}\\rho\_\{ij\}=1\\quad\\forall i\\in\[n\]\.\(31\)
Step 4 \(Convergence Check\):If the difference between\(λt,ρt\)\(\\lambda^\{t\},\\rho^\{t\}\)and\(λt−1,ρt−1\)\(\\lambda^\{t\-1\},\\rho^\{t\-1\}\)is within tolerance, terminate the algorithm\. Otherwise, move on to the next iteration and go to Step 2\.

In the expectation step, the calculation forFFandXXfollows Section[4\.2\.2](https://arxiv.org/html/2607.09817#S4.SS2.SSS2)\. The computation forGGandYYfollows the same idea inŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\)\. The term forGir,tG^\{r,t\}\_\{i\}is as follows:

𝔼​\[Gir∣ℰ​\(jr,Sr\),λt−1,ρt−1\]=λi​Pr⁡\[i​⤳Sr¯​jr\]π​\(jr,Sr\)\\mathbb\{E\}\[G^\{r\}\_\{i\}\\mid\\mathcal\{E\}\(j\_\{r\},S\_\{r\}\),\\lambda^\{t\-1\},\\rho^\{t\-1\}\]=\\frac\{\\lambda\_\{i\}\\Pr\[i\\overset\{\\overline\{S\_\{r\}\}\}\{\\leadsto\}j\_\{r\}\]\}\{\\pi\(j\_\{r\},S\_\{r\}\)\}since when the random walk is consistent with the transaction\(jr,Sr\)\(j\_\{r\},S\_\{r\}\), if it enters the system at stateii, it must be followed by a random walk in the form ofi​⤳Sr¯​jri\\overset\{\\overline\{S\_\{r\}\}\}\{\\leadsto\}j\_\{r\}\. The term forYi​jr,tY^\{r,t\}\_\{ij\}is as follows:

𝔼​\[Yi​jr∣ℰ​\(jr,Sr\),λt−1,ρt−1\]=Pr⁡\[j​⤳Sr¯​jr\]​ρi​j​θλ​\(i,Sr\)θλ​\(jr,Sr\)\\mathbb\{E\}\[Y^\{r\}\_\{ij\}\\mid\\mathcal\{E\}\(j\_\{r\},S\_\{r\}\),\\lambda^\{t\-1\},\\rho^\{t\-1\}\]=\\frac\{\\Pr\[j\\overset\{\\overline\{S\_\{r\}\}\}\{\\leadsto\}j\_\{r\}\]\\rho\_\{ij\}\\theta\_\{\\lambda\}\(i,S\_\{r\}\)\}\{\\theta\_\{\\lambda\}\(j\_\{r\},S\_\{r\}\)\}where the termθλ\\theta\_\{\\lambda\}follows Lemma[4\.1](https://arxiv.org/html/2607.09817#S4.Thmtheorem1)\. The starting state distribution isλ\\lambda, the destination state isjrj\_\{r\}, and the admissible set isSr¯\\overline\{S\_\{r\}\}\.

In the maximization step, the optimization problem \([31](https://arxiv.org/html/2607.09817#S4.E31)\) is in the form of \([29](https://arxiv.org/html/2607.09817#S4.E29)\)\. Therefore, we set

λit=∑c=1C∑σ∼r𝒟cFic,σ,t\+∑r=1IGir,t∑c=1C∑σ∼r𝒟c∑j∈\[n\]\+Fjc,σ,t\+∑r=1I∑j∈\[n\]\+Gjr,t∀i∈\[n\]\+\\lambda^\{t\}\_\{i\}=\\frac\{\\sum\_\{c=1\}^\{C\}\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}F^\{c,\\sigma,t\}\_\{i\}\+\\sum\_\{r=1\}^\{I\}G^\{r,t\}\_\{i\}\}\{\\sum\_\{c=1\}^\{C\}\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}\\sum\_\{j\\in\[n\]\_\{\+\}\}F^\{c,\\sigma,t\}\_\{j\}\+\\sum\_\{r=1\}^\{I\}\\sum\_\{j\\in\[n\]\_\{\+\}\}G^\{r,t\}\_\{j\}\}\\quad\\forall i\\in\[n\]\_\{\+\}and

ρi​jt=∑c=1C∑σ∼r𝒟c∑s=1kcXi​jc,σ,s,t\+∑r=1IYi​jr,t∑c=1C∑σ∼r𝒟c∑s=1kc∑k∈\[n\]\+Xi​kc,σ,s,t\+∑r=1I∑k∈\[n\]\+Yi​kr,t∀i∈\[n\],j∈\[n\]\+\.\\rho^\{t\}\_\{ij\}=\\frac\{\\sum\_\{c=1\}^\{C\}\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}\\sum\_\{s=1\}^\{k\_\{c\}\}X^\{c,\\sigma,s,t\}\_\{ij\}\+\\sum\_\{r=1\}^\{I\}Y^\{r,t\}\_\{ij\}\}\{\\sum\_\{c=1\}^\{C\}\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}^\{c\}\}\\sum\_\{s=1\}^\{k\_\{c\}\}\\sum\_\{k\\in\[n\]\_\{\+\}\}X^\{c,\\sigma,s,t\}\_\{ik\}\+\\sum\_\{r=1\}^\{I\}\\sum\_\{k\\in\[n\]\_\{\+\}\}Y^\{r,t\}\_\{ik\}\}\\quad\\forall i\\in\[n\],j\\in\[n\]\_\{\+\}\.

## 5Experimental Results

To evaluate the performance of our EM algorithms, we design experiments where the ground truth choice models are known\. In Section[5\.1](https://arxiv.org/html/2607.09817#S5.SS1), we introduce the performance measures\. In Section[5\.2](https://arxiv.org/html/2607.09817#S5.SS2), we introduce the benchmark choice models that we compare with\. In Section[5\.3](https://arxiv.org/html/2607.09817#S5.SS3), we present the experimental results on pure synthetic datasets\. In Section[5\.4](https://arxiv.org/html/2607.09817#S5.SS4), we present the experimental results on the semi\-synthetic data constructed from the sushi datasetKamishima \([2003](https://arxiv.org/html/2607.09817#bib.bib4)\)\. These experiments are adapted fromBerbegliaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib3)\)\.

### 5\.1Performance Measures with Ground Truth

We consider two types of performance measures: predictive performance \(unconditional and conditional soft root mean square error\), and revenue\-based measures \(revenue ratio and conditional revenue ratio\)\.

To evaluate predictive performance, we use root mean square error \(RMSE\) to capture how far an estimated MC model is from the ground truth\. Letθ\\thetabe the ground truth model andϕ\\phibe an estimated model\. Letπψ​\(j,S\)\\pi^\{\\psi\}\(j,S\)denote the unconditional probabilityπ​\(j,S\)\\pi\(j,S\)thatjjis chosen fromS\+S\_\{\+\}under modelψ\\psi, whereψ\\psicould beθ\\thetaorϕ\\phi\. FollowingBerbegliaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib3)\), the*soft RMSE*is defined as follows:

∑S⊆\[n\]∑j∈S\+\(πϕ​\(j,S\)−πθ​\(j,S\)\)2∑S⊆\[n\]\(\|S\|\+1\)\.\\sqrt\{\\frac\{\\sum\_\{S\\subseteq\[n\]\}\\sum\_\{j\\in S^\{\+\}\}\\left\(\\pi^\{\\phi\}\(j,S\)\-\\pi^\{\\theta\}\(j,S\)\\right\)^\{2\}\}\{\\sum\_\{S\\subseteq\[n\]\}\(\|S\|\+1\)\}\}\.\(32\)Similarly, using \([2](https://arxiv.org/html/2607.09817#S2.E2)\), letπ𝒟cψ​\(j,S\)\\pi^\{\\psi\}\_\{\\mathcal\{D\}^\{c\}\}\(j,S\)denote the probability thatjjis chosen fromS\+S\_\{\+\}under modelψ\\psi, conditional on the transaction data𝒟c\\mathcal\{D\}^\{c\}of customercc\. Note thatπ𝒟cψ​\(j,S\)=πψ​\(j,S\)\\pi^\{\\psi\}\_\{\\mathcal\{D\}^\{c\}\}\(j,S\)=\\pi^\{\\psi\}\(j,S\)if customercchas no historical transaction, i\.e\.,𝒟c=∅\\mathcal\{D\}^\{c\}=\\varnothing\. The*conditional soft RMSE*is defined as follows:

∑c=1C∑S⊆\[n\]∑j∈S\+\(π𝒟cϕ​\(j,S\)−π𝒟cθ​\(j,S\)\)2∑c=1C∑S⊆\[n\]\(\|S\|\+1\)\.\\sqrt\{\\frac\{\\sum^\{C\}\_\{c=1\}\\sum\_\{S\\subseteq\[n\]\}\\sum\_\{j\\in S^\{\+\}\}\\left\(\\pi^\{\\phi\}\_\{\\mathcal\{D\}^\{c\}\}\(j,S\)\-\\pi^\{\\theta\}\_\{\\mathcal\{D\}^\{c\}\}\(j,S\)\\right\)^\{2\}\}\{\\sum\_\{c=1\}^\{C\}\\sum\_\{S\\subseteq\[n\]\}\(\|S\|\+1\)\}\}\.\(33\)In \([32](https://arxiv.org/html/2607.09817#S5.E32)\) and \([33](https://arxiv.org/html/2607.09817#S5.E33)\), the RMSE is computed over all possible offer sets and all possible selections for each offer set, which ensures robustness\. Additionally, in \([33](https://arxiv.org/html/2607.09817#S5.E33)\), the RMSE is computed over all customers that are present in the data\.666Considering all possible transaction sets \(or DAGs\), which have2Θ​\(n2\)2^\{\\Theta\(n^\{2\}\)\}possibilities, is not computationally practical\.The additive 1 in the denominator represents the no\-purchase option\.

Building on predictive performance, we proceed with conditional and unconditional revenue performance\. Given the revenue vectorrr, under modelψ\\psi, letSψ∗S^\{\*\}\_\{\\psi\}denote the optimal assortment for \([TAO](https://arxiv.org/html/2607.09817#S2.Ex1)\) andRψ​\(S\):=∑j∈Srj​πψ​\(j,S\)R\_\{\\psi\}\(S\):=\\sum\_\{j\\in S\}r\_\{j\}\\pi^\{\\psi\}\(j,S\)denote the expected revenue obtained by offeringSS\. The*revenue ratio*is defined asRθ​\(Sϕ∗\)/Rθ​\(Sθ∗\)R\_\{\\theta\}\(S^\{\*\}\_\{\\phi\}\)/R\_\{\\theta\}\(S^\{\*\}\_\{\\theta\}\)\. That is, under the ground truthθ\\theta, the ratio between the expected revenue of the optimal assortment underϕ\\phiand that under the ground truth\. Underψ\\psi, letSψ,𝒟c∗S^\{\*\}\_\{\\psi,\\mathcal\{D\}^\{c\}\}denote the optimal assortment for \([CAO](https://arxiv.org/html/2607.09817#S2.Ex2)\) andRψ,𝒟c​\(S\):=∑j∈Srj​π𝒟cψ​\(j,S\)R\_\{\\psi,\\mathcal\{D\}^\{c\}\}\(S\):=\\sum\_\{j\\in S\}r\_\{j\}\\pi^\{\\psi\}\_\{\\mathcal\{D\}^\{c\}\}\(j,S\)denote the expected revenue obtained by offeringSSconditional on𝒟c\\mathcal\{D\}^\{c\}\. The*conditional revenue ratio*is

∑c=1CRθ,𝒟c​\(Sϕ,𝒟c∗\)∑c=1CRθ,𝒟c​\(Sθ,𝒟c∗\)\.\\frac\{\\sum\_\{c=1\}^\{C\}R\_\{\\theta,\\mathcal\{D\}^\{c\}\}\(S^\{\*\}\_\{\\phi,\\mathcal\{D\}^\{c\}\}\)\}\{\\sum\_\{c=1\}^\{C\}R\_\{\\theta,\\mathcal\{D\}^\{c\}\}\(S^\{\*\}\_\{\\theta,\\mathcal\{D\}^\{c\}\}\)\}\.\(34\)That is, under the ground truthθ\\theta, we consider the ratio between the total expected revenue of the optimal assortment conditional on𝒟c\\mathcal\{D\}^\{c\}underϕ\\phiand that under the ground truthθ\\theta\.

### 5\.2Benchmark Choice Models

In addition to the MC choice model estimated by the traditional EM algorithmŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\), denotedMc, we compare our estimated choice models with two types of choice models: MNL and latent\-class MNL \(LC\-MNL\)\. The LC\-MNL model is a mixture ofℓ\\ellMNL models, each capturing a customer segment\. Each segments∈\[ℓ\]s\\in\[\\ell\]is associated with a probabilityαs\\alpha\_\{s\}, and each customer belongs to a segment with probabilityαs\\alpha\_\{s\}\. Each type can be further categorized as traditional or partial\-ordering\-basedJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\)\.

Traditional choice model estimation algorithms aim to find the parameters to maximize log\-likelihood \([13](https://arxiv.org/html/2607.09817#S3.E13)\)\. For MNL, when the parameterv0v\_\{0\}is fixed, \([13](https://arxiv.org/html/2607.09817#S3.E13)\) is concave and can be efficiently optimized using standard nonlinear optimization packages\. For LC\-MNL, \([13](https://arxiv.org/html/2607.09817#S3.E13)\) becomes non\-concave\. To ensure comparability, we consider the EM algorithmTrain \([2008](https://arxiv.org/html/2607.09817#bib.bib28)\), as the partial\-ordering\-based LC\-MNL estimation inJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\)is also based on the frameworkTrain \([2008](https://arxiv.org/html/2607.09817#bib.bib28)\)\. In the traditional setting, the estimated MNL and LC\-MNL models are termedMnlandLc\-Mnl, respectively\.

For choice model estimation with panel data, the log\-likelihood objective \([14](https://arxiv.org/html/2607.09817#S3.E14)\) is more complicated\. The objective is non\-concave under MNL\. We proceed with the partial\-ordering\-based MNL estimation\. FollowingJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\)and Section[2\.1\.1](https://arxiv.org/html/2607.09817#S2.SS1.SSS1), consider the DAGDc=\(\[n\]\+,Ac\)D\_\{c\}=\(\[n\]\_\{\+\},A\_\{c\}\)of customercc\. LetΨjc\\Psi^\{c\}\_\{j\}denote the set of products that are reachable from productjjinDcD\_\{c\}, includingjjitself\. The probabilityπ𝒟c\\pi\_\{\\mathcal\{D\}^\{c\}\}can be approximated as

π^𝒟c:=∏j∈\[n\]\+vj∑j′∈Ψjcvj′\.\\hat\{\\pi\}\_\{\\mathcal\{D\}^\{c\}\}:=\\prod\_\{j\\in\[n\]\_\{\+\}\}\\frac\{v\_\{j\}\}\{\\sum\_\{j^\{\\prime\}\\in\\Psi^\{c\}\_\{j\}\}v\_\{j^\{\\prime\}\}\}\.\(35\)It was shown thatπ^𝒟c≤π𝒟c\\hat\{\\pi\}\_\{\\mathcal\{D\}^\{c\}\}\\leq\\pi\_\{\\mathcal\{D\}^\{c\}\}where the equality holds whenDcD\_\{c\}is a directed forest\. A lower bound forπ^𝒟c\\hat\{\\pi\}\_\{\\mathcal\{D\}^\{c\}\}in terms ofπ𝒟c\\pi\_\{\\mathcal\{D\}^\{c\}\}was presented inJagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\)\. Building on \([35](https://arxiv.org/html/2607.09817#S5.E35)\), the approximate log\-likelihood is

L^c​u​s​\(v\):=∑c=1Clog⁡\(∏j∈\[n\]\+vj∑j′∈Ψjcvj′\)=∑c=1Clog⁡π^𝒟c\.\\hat\{L\}^\{cus\}\(v\):=\\sum\_\{c=1\}^\{C\}\\log\\left\(\\prod\_\{j\\in\[n\]\_\{\+\}\}\\frac\{v\_\{j\}\}\{\\sum\_\{j^\{\\prime\}\\in\\Psi^\{c\}\_\{j\}\}v\_\{j^\{\\prime\}\}\}\\right\)=\\sum\_\{c=1\}^\{C\}\\log\\hat\{\\pi\}\_\{\\mathcal\{D\}^\{c\}\}\.\(36\)The objective \([36](https://arxiv.org/html/2607.09817#S5.E36)\), whenv0v\_\{0\}is fixed, is concave inμj=log⁡vj\\mu\_\{j\}=\\log v\_\{j\}for allj∈\[n\]j\\in\[n\]and can be efficiently optimized using standard nonlinear optimization packages\. We focus on the simple*partial order MNL*that maximizes \([36](https://arxiv.org/html/2607.09817#S5.E36)\) as our benchmark, as opposed to the more sophisticated estimation inJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\); Jagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\), which considersℓ1\\ell\_\{1\}\-regularization\. The benchmark partial order MNL model is termedPomnl\.

Building on the approximation \([35](https://arxiv.org/html/2607.09817#S5.E35)\), we turn to the*latent\-class partial order MNL*\(LC\-POMNL\) model introduced inJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\)\. Here, the probabilityπ𝒟c\\pi\_\{\\mathcal\{D\}^\{c\}\}can be approximated as

π^𝒟c:=∑s=1ℓαs​∏j∈\[n\]\+vjs∑j′∈Ψjcvj′s\\hat\{\\pi\}\_\{\\mathcal\{D\}^\{c\}\}:=\\sum\_\{s=1\}^\{\\ell\}\\alpha\_\{s\}\\prod\_\{j\\in\[n\]\_\{\+\}\}\\frac\{v^\{s\}\_\{j\}\}\{\\sum\_\{j^\{\\prime\}\\in\\Psi^\{c\}\_\{j\}\}v^\{s\}\_\{j^\{\\prime\}\}\}\(37\)wherevsv^\{s\}is the MNL attraction vector of segmentss\. Building on \([37](https://arxiv.org/html/2607.09817#S5.E37)\), the goal is to maximize the approximate log\-likelihood objective by solving

maxα,v⁡L^c​u​s​\(α,v\)\\displaystyle\\max\_\{\\alpha,v\}\\hat\{L\}^\{cus\}\(\\alpha,v\):=∑c=1Clog⁡\(∑s=1ℓαs​∏j∈\[n\]\+vjs∑j′∈Ψjcvj′s\)\\displaystyle:=\\sum\_\{c=1\}^\{C\}\\log\\left\(\\sum\_\{s=1\}^\{\\ell\}\\alpha\_\{s\}\\prod\_\{j\\in\[n\]\_\{\+\}\}\\frac\{v^\{s\}\_\{j\}\}\{\\sum\_\{j^\{\\prime\}\\in\\Psi^\{c\}\_\{j\}\}v^\{s\}\_\{j^\{\\prime\}\}\}\\right\)\(38\)s\.t\.∑s=1ℓαs=1,α∈ℝ≥0ℓ,\\displaystyle\\sum\_\{s=1\}^\{\\ell\}\\alpha\_\{s\}=1,\\alpha\\in\\mathbb\{R\}^\{\\ell\}\_\{\\geq 0\},v∈ℝ≥0ℓ×\(n\+1\)​with​v0s=1∀s∈\[ℓ\]\.\\displaystyle v\\in\\mathbb\{R\}^\{\\ell\\times\(n\+1\)\}\_\{\\geq 0\}\\text\{ with \}v^\{s\}\_\{0\}=1\\quad\\forall s\\in\[\\ell\]\.We consider the EM algorithm based onTrain \([2008](https://arxiv.org/html/2607.09817#bib.bib28)\), which aims to solve \([38](https://arxiv.org/html/2607.09817#S5.E38)\)\. This simple partial order MNL serves as our benchmark, as opposed to the more sophisticated estimation inJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\); Jagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\), which considersℓ1\\ell\_\{1\}\-regularization\. The benchmark latent\-class partial order MNL model is termedLc\-Pomnl\.

### 5\.3Synthetic Data

The first stage in the data generation process is the creation of the ground truth\. There aren=10n=10products\. Each product is associated with a revenue uniformly, randomly, and independently chosen from\[1,5\]\[1,5\]\. We construct 2 types of ground truths: Rank List \(or stochastic preference\) and Mallows\-based Rank List\.

The Rank List model has a set of strict preference lists, each associated with a given probability\. Each customer’s strict preference is selected according to the given probability parameters\. In general, Rank List is equivalent to RUM when the number of preferences is unlimitedBlock \([1974](https://arxiv.org/html/2607.09817#bib.bib18)\)\. In the Rank List models that we construct, the first preference list is chosen with probability0\.10\.1and has the no\-purchase option as the first alternative\. FollowingBerbegliaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib3)\), we generate two ground truth models: Rank List with 10 lists \(RL\-10\) and with 100 lists \(RL\-100\)\. The remaining 0\.9 probability is covered by 9 or 99 preference lists characterized as follows: the no\-purchase option is not the top choice; each strict preference is drawn uniformly and independently at random from all possible preferences; each strict preference listℓ\\elloccurs with a probability0\.9​βℓ/\(∑ℓ′βℓ′\)0\.9\\beta\_\{\\ell\}/\(\\sum\_\{\\ell^\{\\prime\}\}\\beta\_\{\\ell^\{\\prime\}\}\)whereβℓ∈\(0,1\)\\beta\_\{\\ell\}\\in\(0,1\)is drawn uniformly and independently at random for all listℓ\\ell\.

To consider a scenario in which customers’ strict preferences are correlated rather than independently drawn, we also generate Rank List ground truths based on the Mallows modelMallows \([1957](https://arxiv.org/html/2607.09817#bib.bib40)\)\. The Mallows model is the most popular among distance\-based ranking models, characterized by a central strict preferenceτ\\tauand a concentration parameterκ∈\(0,1\)\\kappa\\in\(0,1\)\. Here,τ:\[n\]\+→\[n\+1\]\\tau:\[n\]\_\{\+\}\\to\[n\+1\]wherej∈\[n\]\+j\\in\[n\]\_\{\+\}is theτ​\(j\)\\tau\(j\)\-th most preferred product among\[n\]\+\[n\]\_\{\+\}\. The probability of a customer having a strict preferenceτ′\\tau^\{\\prime\}is proportional toκd​\(τ,τ′\)\\kappa^\{d\(\\tau,\\tau^\{\\prime\}\)\}, whered​\(τ,τ′\):=∑i,j∈\[n\]\+:i<j𝟙​\[\(τ​\(i\)−τ​\(j\)\)​\(τ′​\(i\)−τ′​\(j\)\)<0\]d\(\\tau,\\tau^\{\\prime\}\):=\\sum\_\{i,j\\in\[n\]\_\{\+\}:i<j\}\\mathbbm\{1\}\[\(\\tau\(i\)\-\\tau\(j\)\)\(\\tau^\{\\prime\}\(i\)\-\\tau^\{\\prime\}\(j\)\)<0\]is the Kendall\-Tau distance betweenτ\\tauandτ′\\tau^\{\\prime\}\. Namely,d​\(τ,τ′\)d\(\\tau,\\tau^\{\\prime\}\)counts the number of pairwise ordering disagreements betweenτ\\tauandτ′\\tau^\{\\prime\}\. Intuitively, the Mallows model defines a set of similar preferences centered around a common permutation, where the deviation probability decreases exponentially in the number of disagreements\. Whenκ→1\\kappa\\to 1, the preference distribution is uniform; whenκ→0\\kappa\\to 0, the preference distribution is highly centered aroundτ\\tau\. Although the unconditional choice probability under Mallows can be efficiently computed according toDésiret al\.\([2016](https://arxiv.org/html/2607.09817#bib.bib41)\), computing the conditional choice probability could be convoluted\. One approach is to enumerate all possible complete linear extensions, but this yields\(n\+1\)\!\(n\+1\)\!possibilities, and it is unclear how to use reduced linear extensions\. Therefore, we construct Rank List ground truths that approximate the Mallows model, where the unconditional choice probability calculation is tractable when a few strict preferences are sampled\.

We randomly and uniformly pick a central strict preferenceτ\\tauin which the no\-purchase option is not the first alternative\. 2000 strict preferencesτ′\\tau^\{\\prime\}are independently sampled proportionally toκd​\(τ,τ′\)\\kappa^\{d\(\\tau,\\tau^\{\\prime\}\)\}\. In the Mallows\-based Rank List models that we construct, the first preference list is chosen with probability0\.20\.2and has the no\-purchase option as the first alternative\. The remaining 0\.8 is covered by the 2000 strict preference listsτ′\\tau^\{\\prime\}, each associated with probability0\.00040\.0004\. We merge the same preference lists by adding the probabilities\. Two ground truth models are considered: Mallows\-based Rank List withκ=0\.4\\kappa=0\.4\(MRL\-0\.4\) and withκ=0\.7\\kappa=0\.7\(MRL\-0\.7\)\.

In the second stage, we generate in\-sample transaction data from the ground truth, following a setting similar toBerbegliaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib3)\)\. There are 2000 customers, each associated with an underlying strict preference list over\[n\]\+\[n\]\_\{\+\}\. There are 600 periods, each containing 10 transactions\. Each period is associated with an offer setS⊆\[10\]S\\subseteq\[10\]such that3≤\|S\|≤63\\leq\|S\|\\leq 6\. Each transaction contains a customer ID in\[2000\]\[2000\], the offer set, and the product selected according to the customer’s preference list\. The customer of a transaction is chosen uniformly at random\. On average, each customer has600×10/2000=3600\\times 10/2000=3transactions\. We note that if the same productjjis chosen from different offer sets, then these transactions are merged into one transaction wherejjis chosen from the union of the offer sets, so the average value ofkc≤3k\_\{c\}\\leq 3\.

We generate 100 instances for each combination of ground truth and the number of in\-sample customers used to estimate the choice model\. The number of customersC∈\{100,250,500,1000,2000\}C\\in\\\{100,250,500,1000,2000\\\}, and we use transactions associated with customers in\[C\]\[C\]for training, so that the nested structure ensures information gain asCCincreases\. We compare the MC choice models estimated by our EM algorithmsCusandHybwith the benchmark models in Section[5\.2](https://arxiv.org/html/2607.09817#S5.SS2)\. We use customer IDs in\[C\]\[C\]to testCus, which aims to maximize \([14](https://arxiv.org/html/2607.09817#S3.E14)\)\. The estimated choice model is termedCus\-Mc\. To testHyb, we reveal half of the customer IDs in\[C\]\[C\]\. More specifically, only the odd customer IDs are revealed, while transactions associated with even customer IDs are added to the independent set\. The estimated choice model is termedHyb\-Mc\. In practice, customers can be categorized as members or guests, and only the transactions made by members are recorded as customer\-specific\. For each performance measure, we take the average over the 100 instances\. To testLc\-Mnl, we consider the number of segmentsℓ=1,2,…,10\\ell=1,2,\.\.\.,10, and pickℓ\\ellwith the lowest average soft RMSE over the 100 instances\. The number of segments forLc\-Pomnlis selected in the same way\. This selection rule uses the known ground truth and is intended only to select a strong synthetic benchmark\.777We use this approach to align withJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\); Jagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\)\. In applications without ground truth,ℓ\\ellshould be selected using validation log\-likelihood or another implementable model\-selection criterion\.To avoid overfitting, we rule out the in\-sample offer sets for the predictive RMSE measures in \([32](https://arxiv.org/html/2607.09817#S5.E32)\) and \([33](https://arxiv.org/html/2607.09817#S5.E33)\)\. For computational reasons, when testing the conditional soft RMSE \([33](https://arxiv.org/html/2607.09817#S5.E33)\) and the conditional revenue ratio \([34](https://arxiv.org/html/2607.09817#S5.E34)\), we consider onlyc∈\[100\]c\\in\[100\], regardless of the number of in\-sample customersCC\. This tests the impact of the richness of extra transaction data on the conditional measures of a fixed set of customers\.

#### 5\.3\.1Results

Overall, we compare 7 different choice models, 2 from our framework and 5 benchmark models from the previous literatureŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\); Train \([2008](https://arxiv.org/html/2607.09817#bib.bib28)\); Jagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\); Jagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\), on 4 different ground truths\. For each ground truth, we have 5 different data sizes based on the number of customers, each with 100 instances\. In total, 2000 instances are tested for each choice model estimation\. The computationally intensive tasks were executed in parallel on a cluster at the University of Melbourne\.

Before showing the experimental results, we present the metadata and characteristics of the in\-sample transaction data from the 2000 customers for each ground truth in Table[2](https://arxiv.org/html/2607.09817#S5.T2)\. On average, customers drawn from the Rank List have more transactions after merging \(kck\_\{c\}\) than those drawn from the Mallows\-based Rank List, resulting in a higher number of reduced linear extensions\. For the Mallows\-based Rank List, the lower the concentration parameterκ\\kappa, the lower the number of distinct sampled preference lists, indicating that the preference is more concentrated around the central preference\.

ground truthRL\-10RL\-100MRL\-0\.4MRL\-0\.7averagekck\_\{c\}1\.8391\.8341\.6911\.671average \#RLE1\.4301\.4311\.3501\.347
ground truthMRL\-0\.4MRL\-0\.7average \#lists1681\.841999\.37

Table 2:The averagekck\_\{c\}and the average \#RLE are the average \(over 100 instances\) of the average number of transactions after merging and reduced linear extensions \(over 2000 in\-sample customers\), respectively; the average \#lists is the average number of distinct preference lists \(including the first list that has no\-purchase as the top choice, which occurs with probability 0\.2\) over 100 instances\.![Refer to caption](https://arxiv.org/html/2607.09817v1/x1.png)Figure 4:RL\-10 Ground Truth![Refer to caption](https://arxiv.org/html/2607.09817v1/x2.png)Figure 5:RL\-100 Ground Truth![Refer to caption](https://arxiv.org/html/2607.09817v1/x3.png)Figure 6:MRL\-0\.4 Ground Truth![Refer to caption](https://arxiv.org/html/2607.09817v1/x4.png)Figure 7:MRL\-0\.7 Ground TruthThe experimental results are presented in Figures[4](https://arxiv.org/html/2607.09817#S5.F4),[5](https://arxiv.org/html/2607.09817#S5.F5),[6](https://arxiv.org/html/2607.09817#S5.F6), and[7](https://arxiv.org/html/2607.09817#S5.F7)\. We focus on two comparisons: first, the performance comparison between the MC\-based choice models \(Mc,Hyb\-Mc, andCus\-Mc\) and the MNL\-based choice models \(Mnl,Pomnl,Lc\-Mnl, andLc\-Pomnl\); second, the improvement margin comparison between the traditional choice model estimation and the one with panel data\. To ensure a more granular comparison, we also consider the impact of the training data size \(number of customers\) on the performance of each choice model estimation while making these comparisons\.

In general, the MC\-based choice models outperform the MNL\-based choice models when the data size gets larger, or the ground truth distribution is more concentrated on a smaller number of preference lists \(RL\-10 and MRL\-0\.4\), as opposed to spreading out more evenly\. When preferences are more evenly distributed \(RL\-100 and MRL\-0\.7\), MNL\-based choice models outperform MC\-based choice models when the data size is small in most cases\. With large data sizes, MC\-based choice models usually better capture the preference list distribution due to information richness\.

In most cases, compared with MNL and LC\-MNL, estimating an MC results in a greater improvement margin when customer\-level information is incorporated into the choice model estimation, especially when the data size is small\. Although this observation is based on synthetic experiments, it is theoretically supported in Section[3](https://arxiv.org/html/2607.09817#S3)\. When the ground truth is RL\-10 or RL\-100,Mcis the state\-of\-the\-art in terms of the soft RMSE performance metricBerbegliaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib3)\)\. Our framework improves this result by exploiting individual information where transactions are correlated\.

### 5\.4Sushi Data

We assess the performance of estimation, prediction, and the impact on revenue using the sushi dataset, which contains preference lists of 5000 individualsKamishima \([2003](https://arxiv.org/html/2607.09817#bib.bib4)\)\. In the commercial web survey used to collect preference data, each individual was first shown on the screenn=10n=10types of sushi\. The individuals were asked to rank the sushi types according to their preferences\. Each user provides one of the10\!10\!permutations\. Normalized prices are given from the data and used as the revenue vector\.

We follow a setting similar toBerbegliaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib3)\)\. Since the no\-sushi option was not available in the survey, the ground truth model is generated by adding the*no\-sushi*list that ranks the no\-sushi option as the top alternative\. The no\-sushi list is selected with probability half\. With the remaining half, we select one list uniformly at random from the 5000 lists\. We assume that an individual would purchase if one of the topttis available\. That is, the\(t\+1\)\(t\+1\)\-th choice is replaced with the no\-sushi option\. There are at most10\!/\(10−t\)\!10\!/\(10\-t\)\!possible topttpreference lists\. We merge the individuals with the same topttlists and sum up the probabilities to construct the Rank List ground truth\. We testt=5t=5andt=7t=7and follow the same data generation procedure, choice model estimation, and performance evaluation as in Section[5\.3](https://arxiv.org/html/2607.09817#S5.SS3)\. The metadata and characteristics of the in\-sample transaction data for each ground truth are presented in Table[3](https://arxiv.org/html/2607.09817#S5.T3)\.

Table 3:The averagekck\_\{c\}and the average \#RLE are the average number of transactions after merging and reduced linear extensions \(over 2000 in\-sample customers\), respectively; the \#lists is the number of distinct preference lists \(including the no\-sushi list, which occurs with probability 0\.5\) over 100 instances\.#### 5\.4\.1Results

The experimental results are presented in Figures[8](https://arxiv.org/html/2607.09817#S5.F8)and[9](https://arxiv.org/html/2607.09817#S5.F9)\. In general, the MC\-based choice models outperform the MNL\-based choice models, except for the conditional revenue ratio under the top 5 ground truth\. ForHyb\-McandCus\-Mc, this performance metric degrades as the data size gets larger\. One potential reason is the lack of information to fit an MC when panel data is used\.

![Refer to caption](https://arxiv.org/html/2607.09817v1/x5.png)Figure 8:Top 5 Ground Truth![Refer to caption](https://arxiv.org/html/2607.09817v1/x6.png)Figure 9:Top 7 Ground TruthCompared with the top\-7 truncation, the top\-5 truncation might not provide sufficient information to incorporate customer\-level information to fit an MC and improve the conditional revenue performance\. Transaction information from other customers is not valuable for improving the conditional revenue ratio of the first 100 customers\.

Compared with MNL and LC\-MNL, estimating an MC results in a greater improvement margin when the choice model estimation uses panel data, especially for the predictive performance metrics, and when the data size is small\. The revenue\-based performance measures, on the other hand, do not fully reflect that using panel data is more beneficial for MC estimation than MNL and LC\-MNL estimation\. The factor for the revenue improvement margin for MNL and LC\-MNL when panel data is used requires further investigation\. In general, for the estimated choice models with panel data \(Pomnl,Lc\-Pomnl,Hyb\-Mc, andCus\-Mc\), as the number of customers goes beyond 250, the improvement in the revenue\-based metrics is marginal\. Nevertheless,Hyb\-McandCus\-Mcobtain almost optimal expected revenue except for the conditional revenue under the top 5 ground truth\.

## 6Conclusion

In this work, we present EM algorithmsHybandCusfor MC estimation using panel data\. Our framework outperforms the traditional EM algorithm for MC estimationŞimşek and Topaloglu \([2018](https://arxiv.org/html/2607.09817#bib.bib11)\), the traditional MNL\-based estimation, and the partial\-ordering\-MNL\-based estimationJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\); Jagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\)on synthetic data and the semi\-synthetic sushi data\. We provide theoretical and empirical evidence that customer\-level information, which captures correlations between transactions of the same customer, is more valuable for MC estimation\.

Our primary future research direction is to testHybon real data, where customer preferences might be cyclic\. This requires cycle deletion heuristics to extract a DAG that best describes the customer preference, as proposed inJagabathula and Vulcano \([2018](https://arxiv.org/html/2607.09817#bib.bib25)\); Jagabathulaet al\.\([2022](https://arxiv.org/html/2607.09817#bib.bib1)\)\. One potential advantage ofHybis that arc\-violating transactions, which might provide information for the unconditional population choice distribution, can be included in the independent set for training, instead of being discarded\. Other research directions include choice prediction and estimation with panel data for other classes of RUMs, as well as investigating the value of customer\-level information under different ground truth RUMs\.

## References

- \[1\]R\. Anupindi, M\. Dada, and S\. Gupta\(1998\)Estimation of consumer demand with stock\-out based substitution: an application to vending machine products\.Marketing Science17\(4\),pp\. 406–423\.Cited by:[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1)\.
- \[2\]S\. Beggs, S\. Cardell, and J\. Hausman\(1981\)Assessing the potential demand for electric cars\.Journal of Econometrics17\(1\),pp\. 1–19\.Cited by:[§2\.2\.3](https://arxiv.org/html/2607.09817#S2.SS2.SSS3.Px2.p1.14)\.
- \[3\]G\. Berbeglia, A\. Garassino, and G\. Vulcano\(2022\)A comparative empirical study of discrete choice models in retail operations\.Management Science68\(6\),pp\. 4005–4023\.Cited by:[2nd item](https://arxiv.org/html/2607.09817#S1.I1.i2.p1.1),[§5\.1](https://arxiv.org/html/2607.09817#S5.SS1.p2.10),[§5\.3\.1](https://arxiv.org/html/2607.09817#S5.SS3.SSS1.p5.1),[§5\.3](https://arxiv.org/html/2607.09817#S5.SS3.p2.5),[§5\.3](https://arxiv.org/html/2607.09817#S5.SS3.p5.8),[§5\.4](https://arxiv.org/html/2607.09817#S5.SS4.p2.7),[§5](https://arxiv.org/html/2607.09817#S5.p1.1)\.
- \[4\]G\. Berbeglia\(2016\)Discrete choice models based on random walks\.Operations Research Letters44\(2\),pp\. 234–237\.Cited by:[§2\.2](https://arxiv.org/html/2607.09817#S2.SS2.p1.1)\.
- \[5\]C\. M\. Bishop\(2006\)Pattern recognition and machine learning\.Springer\.Cited by:[§4\.2\.3](https://arxiv.org/html/2607.09817#S4.SS2.SSS3.p1.3)\.
- \[6\]J\. Blanchet, G\. Gallego, and V\. Goyal\(2016\)A Markov chain approximation to choice modeling\.Operations Research64\(4\),pp\. 886–905\.Cited by:[§1\.2\.3](https://arxiv.org/html/2607.09817#S1.SS2.SSS3.p1.1),[§2\.2\.1](https://arxiv.org/html/2607.09817#S2.SS2.SSS1.p2.6),[§2\.2\.2](https://arxiv.org/html/2607.09817#S2.SS2.SSS2.p1.16)\.
- \[7\]H\. D\. Block\(1974\)Random orderings and stochastic theories of responses \(1960\)\.InEconomic Information, Decision, and Prediction: Selected Essays: Volume I Part I Economics of Decision,pp\. 172–217\.Cited by:[§5\.3](https://arxiv.org/html/2607.09817#S5.SS3.p2.5)\.
- \[8\]R\. A\. Bradley and M\. E\. Terry\(1952\)Rank analysis of incomplete block designs: i\. the method of paired comparisons\.Biometrika39\(3/4\),pp\. 324–345\.Cited by:[§2\.2\.2](https://arxiv.org/html/2607.09817#S2.SS2.SSS2.p1.9)\.
- \[9\]G\. Brightwell and P\. Winkler\(1991\)Counting linear extensions is \#P\-complete\.InProceedings of the Twenty\-third Annual ACM Symposium on Theory of Computing,pp\. 175–181\.Cited by:[§A\.1\.1](https://arxiv.org/html/2607.09817#A1.SS1.SSS1.1.p1.1),[§A\.1\.1](https://arxiv.org/html/2607.09817#A1.SS1.SSS1.p2.1)\.
- \[10\]N\. Chen, P\. Gao, C\. Wang, and Y\. Wang\(2023\)Assortment optimization for the multinomial logit model with repeated customer interactions\.Available at SSRN 4526247\.Cited by:[§A\.2](https://arxiv.org/html/2607.09817#A1.SS2.1.p1.3),[§A\.2](https://arxiv.org/html/2607.09817#A1.SS2.8.p8.1),[§A\.2](https://arxiv.org/html/2607.09817#A1.SS2.p1.1),[Lemma A\.8](https://arxiv.org/html/2607.09817#A1.Thmtheorem8),[§1\.2\.2](https://arxiv.org/html/2607.09817#S1.SS2.SSS2.p1.1),[footnote 10](https://arxiv.org/html/2607.09817#footnote10),[footnote 9](https://arxiv.org/html/2607.09817#footnote9)\.
- \[11\]C\. T\. Conlon and J\. H\. Mortimer\(2013\)Demand estimation under incomplete product availability\.American Economic Journal: Microeconomics5\(4\),pp\. 1–30\.Cited by:[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1)\.
- \[12\]A\. P\. Dempster, N\. M\. Laird, and D\. B\. Rubin\(1977\)Maximum likelihood from incomplete data via the EM algorithm\.Journal of the Royal Statistical Society Series B: Methodological39\(1\),pp\. 1–22\.Cited by:[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1)\.
- \[13\]A\. Désir, V\. Goyal, S\. Jagabathula, and D\. Segev\(2016\)Assortment optimization under the Mallows model\.Advances in Neural Information Processing Systems29,pp\. 4707–4715\.Cited by:[§5\.3](https://arxiv.org/html/2607.09817#S5.SS3.p3.18)\.
- \[14\]A\. Désir, V\. Goyal, B\. Jiang, T\. Xie, and J\. Zhang\(2024\)Robust assortment optimization under the Markov chain choice model\.Operations Research72\(4\),pp\. 1595–1614\.Cited by:[§1\.2\.3](https://arxiv.org/html/2607.09817#S1.SS2.SSS3.p1.1)\.
- \[15\]A\. Désir, V\. Goyal, D\. Segev, and C\. Ye\(2020\)Constrained assortment optimization under the Markov chain–based choice model\.Management Science66\(2\),pp\. 698–721\.Cited by:[§1\.2\.3](https://arxiv.org/html/2607.09817#S1.SS2.SSS3.p1.1)\.
- \[16\]A\. Désir, V\. Goyal, and J\. Zhang\(2022\)Capacitated assortment optimization: hardness and approximation\.Operations Research70\(2\),pp\. 893–904\.Cited by:[§1\.2\.3](https://arxiv.org/html/2607.09817#S1.SS2.SSS3.p1.1)\.
- \[17\]J\. B\. Feldman and H\. Topaloglu\(2017\)Revenue management under the Markov chain choice model\.Operations Research65\(5\),pp\. 1322–1342\.Cited by:[§1\.2\.3](https://arxiv.org/html/2607.09817#S1.SS2.SSS3.p1.1),[§2\.2\.1](https://arxiv.org/html/2607.09817#S2.SS2.SSS1.p2.6),[§2\.2\.1](https://arxiv.org/html/2607.09817#S2.SS2.SSS1.p4.15)\.
- \[18\]G\. Gallego, G\. Iyengar, R\. Phillips, and A\. Dubey\(2004\)Managing flexible products on a network\.Available at SSRN 3567371\.Cited by:[§2\.2\.2](https://arxiv.org/html/2607.09817#S2.SS2.SSS2.p2.4)\.
- \[19\]A\. Gupta and D\. Hsu\(2020\)Parameter identification in Markov chain choice models\.Theoretical Computer Science808,pp\. 99–107\.Cited by:[§1\.2\.3](https://arxiv.org/html/2607.09817#S1.SS2.SSS3.p1.1),[§3\.2](https://arxiv.org/html/2607.09817#S3.SS2.p2.5)\.
- \[20\]S\. Jagabathula, D\. Mitrofanov, and G\. Vulcano\(2022\)Personalized retail promotions through a directed acyclic graph–based representation of customer preferences\.Operations Research70\(2\),pp\. 641–665\.Cited by:[§A\.1\.1](https://arxiv.org/html/2607.09817#A1.SS1.SSS1.p1.3),[2nd item](https://arxiv.org/html/2607.09817#S1.I1.i2.p1.1),[3rd item](https://arxiv.org/html/2607.09817#S1.I1.i3.p1.1),[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1),[§1\.2\.2](https://arxiv.org/html/2607.09817#S1.SS2.SSS2.p1.1),[§2\.1\.1](https://arxiv.org/html/2607.09817#S2.SS1.SSS1.p1.13),[§2\.1\.1](https://arxiv.org/html/2607.09817#S2.SS1.SSS1.p3.1),[§5\.2](https://arxiv.org/html/2607.09817#S5.SS2.p3.11),[§5\.2](https://arxiv.org/html/2607.09817#S5.SS2.p3.15),[§5\.2](https://arxiv.org/html/2607.09817#S5.SS2.p4.4),[§5\.3\.1](https://arxiv.org/html/2607.09817#S5.SS3.SSS1.p1.1),[§6](https://arxiv.org/html/2607.09817#S6.p1.1),[§6](https://arxiv.org/html/2607.09817#S6.p2.1),[footnote 7](https://arxiv.org/html/2607.09817#footnote7)\.
- \[21\]S\. Jagabathula and P\. Rusmevichientong\(2017\)A nonparametric joint assortment and price choice model\.Management Science63\(9\),pp\. 3128–3145\.Cited by:[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1)\.
- \[22\]S\. Jagabathula and G\. Vulcano\(2018\)A partial\-order\-based model to estimate individual preferences using panel data\.Management Science64\(4\),pp\. 1609–1628\.Cited by:[§A\.1\.1](https://arxiv.org/html/2607.09817#A1.SS1.SSS1.p1.3),[2nd item](https://arxiv.org/html/2607.09817#S1.I1.i2.p1.1),[3rd item](https://arxiv.org/html/2607.09817#S1.I1.i3.p1.1),[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1),[§1\.2\.2](https://arxiv.org/html/2607.09817#S1.SS2.SSS2.p1.1),[§2\.1\.1](https://arxiv.org/html/2607.09817#S2.SS1.SSS1.p1.13),[§2\.1\.1](https://arxiv.org/html/2607.09817#S2.SS1.SSS1.p3.1),[§3\.1](https://arxiv.org/html/2607.09817#S3.SS1.p3.22),[§4\.3](https://arxiv.org/html/2607.09817#S4.SS3.p2.2),[§4](https://arxiv.org/html/2607.09817#S4.p1.1),[§5\.2](https://arxiv.org/html/2607.09817#S5.SS2.p1.4),[§5\.2](https://arxiv.org/html/2607.09817#S5.SS2.p2.1),[§5\.2](https://arxiv.org/html/2607.09817#S5.SS2.p3.15),[§5\.2](https://arxiv.org/html/2607.09817#S5.SS2.p3.7),[§5\.2](https://arxiv.org/html/2607.09817#S5.SS2.p4.1),[§5\.2](https://arxiv.org/html/2607.09817#S5.SS2.p4.4),[§5\.3\.1](https://arxiv.org/html/2607.09817#S5.SS3.SSS1.p1.1),[§6](https://arxiv.org/html/2607.09817#S6.p1.1),[§6](https://arxiv.org/html/2607.09817#S6.p2.1),[footnote 7](https://arxiv.org/html/2607.09817#footnote7)\.
- \[23\]T\. Kamishima\(2003\)Nantonac collaborative filtering: recommendation based on order responses\.InProceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp\. 583–588\.Cited by:[§5\.4](https://arxiv.org/html/2607.09817#S5.SS4.p1.2),[§5](https://arxiv.org/html/2607.09817#S5.p1.1)\.
- \[24\]A\. G\. Kök and M\. L\. Fisher\(2007\)Demand estimation and assortment optimization under substitution: methodology and application\.Operations Research55\(6\),pp\. 1001–1021\.Cited by:[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1)\.
- \[25\]S\. Li, Q\. Luo, Z\. Huang, and C\. Shi\(2025\)Online learning for constrained assortment optimization under Markov chain choice model\.Operations Research73\(1\),pp\. 109–138\.Cited by:[§1\.2\.3](https://arxiv.org/html/2607.09817#S1.SS2.SSS3.p1.1)\.
- \[26\]L\. Lovász and S\. Vempala\(2006\)Fast algorithms for log\-concave functions: sampling, rounding, integration and optimization\.In2006 47th Annual IEEE Symposium on Foundations of Computer Science \(FOCS’06\),pp\. 57–68\.Cited by:[§A\.1\.2](https://arxiv.org/html/2607.09817#A1.SS1.SSS2.2.p2.4),[§A\.1\.2](https://arxiv.org/html/2607.09817#A1.SS1.SSS2.Px3.p1.1),[§A\.1\.2](https://arxiv.org/html/2607.09817#A1.SS1.SSS2.Px3.p2.1),[Theorem A\.5](https://arxiv.org/html/2607.09817#A1.Thmtheorem5)\.
- \[27\]R\. D\. Luce\(1959\)Individual choice behavior: a theoretical analysis\.Wiley New York\.Cited by:[§2\.2\.2](https://arxiv.org/html/2607.09817#S2.SS2.SSS2.p1.9)\.
- \[28\]C\. L\. Mallows\(1957\)Non\-null ranking models\. I\.Biometrika44\(1/2\),pp\. 114–130\.Cited by:[§5\.3](https://arxiv.org/html/2607.09817#S5.SS3.p3.18)\.
- \[29\]D\. McFadden\(1974\)Conditional logit analysis of qualitative choice behavior\.Frontiers in Econometrics,pp\. 105–142\.Cited by:[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p1.1),[§2\.2\.2](https://arxiv.org/html/2607.09817#S2.SS2.SSS2.p1.9)\.
- \[30\]D\. Nettleton\(1999\)Convergence properties of the EM algorithm in constrained parameter spaces\.Canadian Journal of Statistics27\(3\),pp\. 639–648\.Cited by:[footnote 4](https://arxiv.org/html/2607.09817#footnote4)\.
- \[31\]R\. L\. Plackett\(1975\)The analysis of permutations\.Journal of the Royal Statistical Society Series C: Applied Statistics24\(2\),pp\. 193–202\.Cited by:[§2\.2\.2](https://arxiv.org/html/2607.09817#S2.SS2.SSS2.p1.9)\.
- \[32\]M\. L\. Puterman\(2014\)Markov decision processes: discrete stochastic dynamic programming\.John Wiley & Sons\.Cited by:[§2\.2\.1](https://arxiv.org/html/2607.09817#S2.SS2.SSS1.p3.18)\.
- \[33\]A\. S\. Şimşek and H\. Topaloglu\(2018\)An expectation\-maximization algorithm to estimate the parameters of the Markov chain choice model\.Operations Research66\(3\),pp\. 748–760\.Cited by:[2nd item](https://arxiv.org/html/2607.09817#S1.I1.i2.p1.1),[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1),[§3\.1](https://arxiv.org/html/2607.09817#S3.SS1.p2.12),[§4\.1](https://arxiv.org/html/2607.09817#S4.SS1.p1.11),[§4\.2\.1](https://arxiv.org/html/2607.09817#S4.SS2.SSS1.p7.1),[§4\.3](https://arxiv.org/html/2607.09817#S4.SS3.p3.11),[§4\.3](https://arxiv.org/html/2607.09817#S4.SS3.p6.5),[Lemma 4\.1](https://arxiv.org/html/2607.09817#S4.Thmtheorem1),[§4](https://arxiv.org/html/2607.09817#S4.p1.1),[§5\.2](https://arxiv.org/html/2607.09817#S5.SS2.p1.4),[§5\.3\.1](https://arxiv.org/html/2607.09817#S5.SS3.SSS1.p1.1),[§6](https://arxiv.org/html/2607.09817#S6.p1.1),[footnote 4](https://arxiv.org/html/2607.09817#footnote4)\.
- \[34\]C\. Stefanescu\(2009\)Multivariate customer demand: modeling and estimation from censored sales\.Available at SSRN 1334353\.Cited by:[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1)\.
- \[35\]K\. Talluri and G\. van Ryzin\(2004\)Revenue management under a general discrete choice model of consumer behavior\.Management Science50\(1\),pp\. 15–33\.Cited by:[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1),[§2\.2\.2](https://arxiv.org/html/2607.09817#S2.SS2.SSS2.p2.4)\.
- \[36\]K\. E\. Train\(2008\)EM algorithms for nonparametric estimation of mixing distributions\.Journal of Choice Modelling1\(1\),pp\. 40–69\.Cited by:[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1),[§5\.2](https://arxiv.org/html/2607.09817#S5.SS2.p2.1),[§5\.2](https://arxiv.org/html/2607.09817#S5.SS2.p4.4),[§5\.3\.1](https://arxiv.org/html/2607.09817#S5.SS3.SSS1.p1.1)\.
- \[37\]G\. van Ryzin and G\. Vulcano\(2015\)A market discovery algorithm to estimate a general class of nonparametric choice models\.Management Science61\(2\),pp\. 281–300\.Cited by:[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p1.1)\.
- \[38\]G\. van Ryzin and G\. Vulcano\(2017\)An expectation\-maximization method to estimate a rank\-based choice model of demand\.Operations Research65\(2\),pp\. 396–407\.Cited by:[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1)\.
- \[39\]G\. Vulcano, G\. van Ryzin, and R\. Ratliff\(2012\)Estimating primary demand for substitutable products from sales transaction data\.Operations Research60\(2\),pp\. 313–334\.Cited by:[§1\.2\.1](https://arxiv.org/html/2607.09817#S1.SS2.SSS1.p2.1)\.

## Appendix AHardness and Computational Results

In Section[A\.1](https://arxiv.org/html/2607.09817#A1.SS1), we establish \#P\-hardness and randomized approximation schemes for computing the transaction probability under MNL\. In Section[A\.2](https://arxiv.org/html/2607.09817#A1.SS2), we show hardness and computational results for the conditional assortment problems\. As MNL is a special case of MC, the hardness results for MNL also hold for MC\.

### A\.1Computing the Transaction Probability under MNL

#### A\.1\.1\#P\-hardness

In this section, we show that computing the probabilityπ𝒟\\pi\_\{\\mathcal\{D\}\}in \([1](https://arxiv.org/html/2607.09817#S2.E1)\) and the conditional probabilityπ𝒟​\(j,S\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)in \([2](https://arxiv.org/html/2607.09817#S2.E2)\) are both \#P\-hard under MNL\. These results provide theoretical guarantees and necessitate heuristics to approximate the transaction probability\[[22](https://arxiv.org/html/2607.09817#bib.bib25),[20](https://arxiv.org/html/2607.09817#bib.bib1)\]\. In contrast to\[[22](https://arxiv.org/html/2607.09817#bib.bib25),[20](https://arxiv.org/html/2607.09817#bib.bib1)\], where the time complexity depends on the number of complete linear extensions, we consider reduced linear extensions, which could potentially improve computation time\. We note that although these problems are hard in general, they are computationally tractable whenk\!∈poly⁡\(n\)k\!\\in\\operatorname\{poly\}\(n\)\.

We reduce the problem of counting the number of linear extensions\[[9](https://arxiv.org/html/2607.09817#bib.bib16)\]to the problem of computing the \(conditional\) transaction probability\.

###### Theorem A\.1\.

Computingπ𝒟\\pi\_\{\\mathcal\{D\}\}in \([1](https://arxiv.org/html/2607.09817#S2.E1)\) is \#P\-hard under MNL\.

###### Proof\.

We reduce the problem of counting the number of linear extensions of a DAG, which is \#P\-hard\[[9](https://arxiv.org/html/2607.09817#bib.bib16)\], to the problem of computingπ𝒟\\pi\_\{\\mathcal\{D\}\}under MNL\.

Suppose the DAG isD=\(V,A\)D=\(V,A\)withV=\[n\]V=\[n\], i\.e\., there arennvertices labeled 1, 2, …,nn\. We construct𝒟\\mathcal\{D\}as follows\. Let\[n\]\[n\]be the product set\. Let the number of transactionsk=nk=nand let\(jℓ,Sℓ\)\(j\_\{\\ell\},S\_\{\\ell\}\)be such thatjℓ=ℓj\_\{\\ell\}=\\ellandSℓ=\{ℓ\}∪\{ℓ′∣there is anℓ​⤳​ℓ′path inD\}S\_\{\\ell\}=\\\{\\ell\\\}\\cup\\\{\\ell^\{\\prime\}\\mid\\text\{there is an $\\ell\\leadsto\\ell^\{\\prime\}$ path in $D$\}\\\}\. Let the attraction value of no\-purchasev0=nnv\_\{0\}=n^\{n\}\.888Note that encodingnnn^\{n\}only requiresn​log⁡nn\\log nbits, which is polynomial in the input size\.Let the attraction value of other productsvj=1v\_\{j\}=1for allj∈\[n\]j\\in\[n\]\.

We claim that whenn≥5n\\geq 5, ifπ𝒟\\pi\_\{\\mathcal\{D\}\}can be computed in polynomial time, then the number of linear extensions ofDDcan be computed in polynomial time\. We do not considern<5n<5since a brute\-force algorithm can compute the number of linear extensions\.

Since eachi∈\[n\]i\\in\[n\]appears to be chosen fromSiS\_\{i\}in𝒟\\mathcal\{D\}, a reduced linear extension of𝒟\\mathcal\{D\}ranks the products in\[n\]\[n\]\. Although the no\-purchase option is not ranked in the reduced linear extension, it is the least preferred according to𝒟\\mathcal\{D\}\. Furthermore, from the construction of𝒟\\mathcal\{D\},σ\\sigmais a linear extension ofDDif and only ifσ∼r𝒟\\sigma\\sim\_\{r\}\\mathcal\{D\}\. This defines a one\-to\-one mapping between a linear extension ofDDand a reduced linear extension of𝒟\\mathcal\{D\}\. Following \([12](https://arxiv.org/html/2607.09817#S2.E12)\), the probability of having a specific reduced linear extensionσ∼r𝒟\\sigma\\sim\_\{r\}\\mathcal\{D\}is

πσ𝒟=∏i=1n1nn\+\|∪ℓ=inSjσ​\(ℓ\)\|∈\[1\(nn\+n\)n,1\(nn\+1\)n\]\.\\pi^\{\\mathcal\{D\}\}\_\{\\sigma\}=\\prod\_\{i=1\}^\{n\}\\frac\{1\}\{n^\{n\}\+\\left\|\\cup\_\{\\ell=i\}^\{n\}S\_\{j\_\{\\sigma\(\\ell\)\}\}\\right\|\}\\in\\left\[\\frac\{1\}\{\\left\(n^\{n\}\+n\\right\)^\{n\}\},\\frac\{1\}\{\\left\(n^\{n\}\+1\\right\)^\{n\}\}\\right\]\.Letccbe the number of linear extensions ofDD, this implies that

π𝒟∈\[c\(nn\+n\)n,c\(nn\+1\)n\]\.\\pi\_\{\\mathcal\{D\}\}\\in\\left\[\\frac\{c\}\{\\left\(n^\{n\}\+n\\right\)^\{n\}\},\\frac\{c\}\{\\left\(n^\{n\}\+1\\right\)^\{n\}\}\\right\]\.
LetIc:=\[c\(nn\+n\)n,c\(nn\+1\)n\]I\_\{c\}:=\\left\[\\frac\{c\}\{\\left\(n^\{n\}\+n\\right\)^\{n\}\},\\frac\{c\}\{\\left\(n^\{n\}\+1\\right\)^\{n\}\}\\right\]be an interval\. Observe thatc≤n\!c\\leq n\!\. We argue thatIc∩Ic′=∅I\_\{c\}\\cap I\_\{c^\{\\prime\}\}=\\varnothingfor anyc,c′∈\[n\!\]c,c^\{\\prime\}\\in\[n\!\]withc≠c′c\\neq c^\{\\prime\}\. That is, each intervalIcI\_\{c\}is disjoint forc∈\[n\!\]c\\in\[n\!\]\. Knowingπ𝒟\\pi\_\{\\mathcal\{D\}\}implies that a binary search oncccan be used to retrieve the intervalIcI\_\{c\}in polynomial time\. Therefore, it suffices to show that

c\(nn\+1\)n<c\+1\(nn\+n\)n∀c∈\[n\!\]\.\\frac\{c\}\{\(n^\{n\}\+1\)^\{n\}\}<\\frac\{c\+1\}\{\(n^\{n\}\+n\)^\{n\}\}\\quad\\forall c\\in\[n\!\]\.\(39\)Equation \([39](https://arxiv.org/html/2607.09817#A1.E39)\) is equivalent to

\(1\+n−11\+nn\)n<1\+1c∀c∈\[n\!\]\.\\left\(1\+\\frac\{n\-1\}\{1\+n^\{n\}\}\\right\)^\{n\}<1\+\\frac\{1\}\{c\}\\quad\\forall c\\in\[n\!\]\.We show the strictest inequality whenc=n\!c=n\!:

\(1\+n−11\+nn\)n\\displaystyle\\left\(1\+\\frac\{n\-1\}\{1\+n^\{n\}\}\\right\)^\{n\}≤\(1\+nnn\)n≤\(1\+1nn−1\)n=∑q=0n\(nq\)​1nq​\(n−1\)\\displaystyle\\leq\\left\(1\+\\frac\{n\}\{n^\{n\}\}\\right\)^\{n\}\\leq\\left\(1\+\\frac\{1\}\{n^\{n\-1\}\}\\right\)^\{n\}=\\sum\_\{q=0\}^\{n\}\{n\\choose q\}\\frac\{1\}\{n^\{q\(n\-1\)\}\}=1\+nnn−1\+n​\(n−1\)2\!​n2​\(n−1\)\+n​\(n−1\)​\(n−2\)3\!​n3​\(n−1\)\+…\+nn\(n−1\)​\(n−1\)\+1nn​\(n−1\)\\displaystyle=1\+\\frac\{n\}\{n^\{n\-1\}\}\+\\frac\{n\(n\-1\)\}\{2\!n^\{2\(n\-1\)\}\}\+\\frac\{n\(n\-1\)\(n\-2\)\}\{3\!n^\{3\(n\-1\)\}\}\+\.\.\.\+\\frac\{n\}\{n^\{\(n\-1\)\(n\-1\)\}\}\+\\frac\{1\}\{n^\{n\(n\-1\)\}\}≤1\+1nn−2\+n2n2​\(n−1\)\+n3n3​\(n−1\)\+…\+nn−1n\(n−1\)​\(n−1\)\+nnnn​\(n−1\)\\displaystyle\\leq 1\+\\frac\{1\}\{n^\{n\-2\}\}\+\\frac\{n^\{2\}\}\{n^\{2\(n\-1\)\}\}\+\\frac\{n^\{3\}\}\{n^\{3\(n\-1\)\}\}\+\.\.\.\+\\frac\{n^\{n\-1\}\}\{n^\{\(n\-1\)\(n\-1\)\}\}\+\\frac\{n^\{n\}\}\{n^\{n\(n\-1\)\}\}≤∑q=0∞\(1nn−2\)q=1\+1nn−2−1<1\+1n\!\\displaystyle\\leq\\sum\_\{q=0\}^\{\\infty\}\\left\(\\frac\{1\}\{n^\{n\-2\}\}\\right\)^\{q\}=1\+\\frac\{1\}\{n^\{n\-2\}\-1\}<1\+\\frac\{1\}\{n\!\}where the last inequality holds whenevern≥5n\\geq 5\. ∎

###### Theorem A\.2\.

Computingπ𝒟​\(j,S\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)in \([2](https://arxiv.org/html/2607.09817#S2.E2)\) is \#P\-hard under MNL\.

###### Proof\.

We show that under MNL, ifπ𝒟​\(j,S\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)in \([2](https://arxiv.org/html/2607.09817#S2.E2)\) can be computed in polynomial time, thenπ𝒟\\pi\_\{\\mathcal\{D\}\}in \([1](https://arxiv.org/html/2607.09817#S2.E1)\) can be computed in polynomial time\.

Given a transaction set𝒟\\mathcal\{D\}under MNL, we sequentially add artificial transactions\(jℓ,\{jℓ,jℓ′\}\)\(j\_\{\\ell\},\\\{j\_\{\\ell\},j^\{\\prime\}\_\{\\ell\}\\\}\)forℓ=k\+1,k\+2,…,k\+p−1,k\+p\\ell=k\+1,k\+2,\.\.\.,k\+p\-1,k\+pto𝒟\\mathcal\{D\}, until𝒟∪\{\(jℓ,\{jℓ,jℓ′\}\)∣ℓ=k\+1,…,k\+p\}\\mathcal\{D\}\\cup\\\{\(j\_\{\\ell\},\\\{j\_\{\\ell\},j^\{\\prime\}\_\{\\ell\}\\\}\)\\mid\\ell=k\+1,\.\.\.,k\+p\\\}has a unique reduced linear extension, which is a strict ranking for\{j∣j∈\[n\]\+​such that​uj\>u0\}\\\{j\\mid j\\in\[n\]\_\{\+\}\\text\{ such that \}u\_\{j\}\>u\_\{0\}\\\}\. Since the no\-purchase option is always available, we do not know the ranking for products less preferred than no\-purchase\. Let𝒟0=𝒟\\mathcal\{D\}\_\{0\}=\\mathcal\{D\}and𝒟i=𝒟0∪\{\(jk\+ℓ,\{jk\+ℓ,jk\+ℓ′\}\)∣ℓ∈\[i\]\}\\mathcal\{D\}\_\{i\}=\\mathcal\{D\}\_\{0\}\\cup\\\{\(j\_\{k\+\\ell\},\\\{j\_\{k\+\\ell\},j^\{\\prime\}\_\{k\+\\ell\}\\\}\)\\mid\\ell\\in\[i\]\\\}such that\{σ∣σ∼r𝒟i\}⊊\{σ∣σ∼r𝒟i−1\}\\\{\\sigma\\mid\\sigma\\sim\_\{r\}\\mathcal\{D\}\_\{i\}\\\}\\subsetneq\\\{\\sigma\\mid\\sigma\\sim\_\{r\}\\mathcal\{D\}\_\{i\-1\}\\\}fori∈\[p\]i\\in\[p\]\. Letσ∼r𝒟p\\sigma\\sim\_\{r\}\\mathcal\{D\}\_\{p\}be the unique reduced linear extension\. Using \([12](https://arxiv.org/html/2607.09817#S2.E12)\),πσ𝒟p=π𝒟p\\pi^\{\\mathcal\{D\}\_\{p\}\}\_\{\\sigma\}=\\pi\_\{\\mathcal\{D\}\_\{p\}\}can be computed in polynomial time\.

From \([2](https://arxiv.org/html/2607.09817#S2.E2)\), we have that

π𝒟i−1​\(jk\+i,\{jk\+i,jk\+i′\}\)=Pr⁡\[ℰ𝒟i\]Pr⁡\[ℰ𝒟i−1\]=π𝒟iπ𝒟i−1∀i∈\[p\]\.\\pi\_\{\\mathcal\{D\}\_\{i\-1\}\}\(j\_\{k\+i\},\\\{j\_\{k\+i\},j^\{\\prime\}\_\{k\+i\}\\\}\)=\\frac\{\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}\_\{i\}\}\]\}\{\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}\_\{i\-1\}\}\]\}=\\frac\{\\pi\_\{\\mathcal\{D\}\_\{i\}\}\}\{\\pi\_\{\\mathcal\{D\}\_\{i\-1\}\}\}\\quad\\forall i\\in\[p\]\.\(40\)To computeπ𝒟=π𝒟0\\pi\_\{\\mathcal\{D\}\}=\\pi\_\{\\mathcal\{D\}\_\{0\}\}, observe that

π𝒟p=π𝒟​∏i=1pπ𝒟iπ𝒟i−1\.\\pi\_\{\\mathcal\{D\}\_\{p\}\}=\\pi\_\{\\mathcal\{D\}\}\\prod\_\{i=1\}^\{p\}\\frac\{\\pi\_\{\\mathcal\{D\}\_\{i\}\}\}\{\\pi\_\{\\mathcal\{D\}\_\{i\-1\}\}\}\.This implies that if \([40](https://arxiv.org/html/2607.09817#A1.E40)\) can be computed in polynomial time, thenπ𝒟\\pi\_\{\\mathcal\{D\}\}can also be computed in polynomial time\. From Theorem[A\.1](https://arxiv.org/html/2607.09817#A1.Thmtheorem1), computingπ𝒟​\(j,S\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)in \([2](https://arxiv.org/html/2607.09817#S2.E2)\) is also \#P\-hard under MNL\. ∎

#### A\.1\.2Randomized Approximation Schemes

To complement the \#P\-hardness results in Section[A\.1\.1](https://arxiv.org/html/2607.09817#A1.SS1.SSS1), we present randomized approximation schemes for computing the probabilityπ𝒟\\pi\_\{\\mathcal\{D\}\}in \([1](https://arxiv.org/html/2607.09817#S2.E1)\) and the conditional probabilityπ𝒟​\(j,S\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)in \([2](https://arxiv.org/html/2607.09817#S2.E2)\) under MNL\. When the attraction ratio is polynomially bounded, our results imply fully polynomial\-time randomized approximation schemes \(FPRAS\) for these problems\.

For notation brevity, letvmax:=maxj∈\[n\]\+⁡vjv\_\{\\max\}:=\\max\_\{j\\in\[n\]\_\{\+\}\}v\_\{j\}andvmin:=minj∈\[n\]\+⁡vjv\_\{\\min\}:=\\min\_\{j\\in\[n\]\_\{\+\}\}v\_\{j\}, and recall thatvj\>0v\_\{j\}\>0for allj∈\[n\]\+j\\in\[n\]\_\{\+\}\. Let the attraction ratioR:=vmax/vminR:=v\_\{\\max\}/v\_\{\\min\}\.

###### Theorem A\.3\.

Under MNL, for anyε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\), there exists a randomized algorithm that returns an estimateπ^𝒟\\hat\{\\pi\}\_\{\\mathcal\{D\}\}forπ𝒟\\pi\_\{\\mathcal\{D\}\}in \([1](https://arxiv.org/html/2607.09817#S2.E1)\), satisfyingPr⁡\[π^𝒟∈\[\(1−ε\)​π𝒟,\(1\+ε\)​π𝒟\]\]≥1−δ,\\Pr\\left\[\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\\in\[\(1\-\\varepsilon\)\\pi\_\{\\mathcal\{D\}\},\(1\+\\varepsilon\)\\pi\_\{\\mathcal\{D\}\}\]\\right\]\\geq 1\-\\delta,with running time polynomial inn,R,1/εn,R,1/\\varepsilon,log⁡\(1/δ\)\\log\(1/\\delta\), and the encoding length ofvv\. IfR∈poly⁡\(n\)R\\in\\operatorname\{poly\}\(n\), thenπ𝒟\\pi\_\{\\mathcal\{D\}\}admits an FPRAS\.

###### Proof\.

If the directed graph induced byDDcontains a cycle, thenπ𝒟=0\\pi\_\{\\mathcal\{D\}\}=0, and the algorithm returns 0\. Henceforth assume the graph is acyclic\.

The proof consists of three main steps\. First, we define an exponential race that equivalently captures the MNL choice probability\. More specifically, we introducen\+1n\+1independent exponential random variables that equivalently capture the Gumbel random variables in MNL\. Second, we consider the\(n\+1\)\(n\+1\)\-dimensional polytope induced by the partial ordering defined by𝒟\\mathcal\{D\}\. The corresponding joint probability density function \(PDF\) is the product of independent exponential densities\. We truncate the domain so that the excluded tail probability is negligible, and the truncated domain is well bounded\. Third, since the polytope after truncation is well\-structured and the joint PDF is log\-concave, this allows us to adopt the randomized convex\-body integration framework\[[26](https://arxiv.org/html/2607.09817#bib.bib42)\]to approximate the probability mass of the polytope\. Combining these steps implies a randomized approximation scheme forπ𝒟\\pi\_\{\\mathcal\{D\}\}\.

Without loss of generality, we scalevvso thatvj∈\[1,R\]v\_\{j\}\\in\[1,R\]for allj∈\[n\]\+j\\in\[n\]\_\{\+\}\.

##### Exponential Race\.

LetTjT\_\{j\}be independent random variables following the exponential distributionExp​\(vj\)\{\\text\{Exp\}\}\(v\_\{j\}\)\. Here,TjT\_\{j\}can be regarded as the arrival time of elementjj\.

Recall that under the exponential distribution, the support is inx∈\[0,∞\)x\\in\[0,\\infty\)\. For elementjj, the PDF isfj​\(x\)=vj​exp⁡\(−vj​x\)f\_\{j\}\(x\)=v\_\{j\}\\exp\(\-v\_\{j\}x\), and the cumulative distribution function \(CDF\) isFj​\(x\)=1−exp⁡\(−vj​x\)F\_\{j\}\(x\)=1\-\\exp\(\-v\_\{j\}x\)\. Under MNL, the utility of productjjisuj=μj\+εj=ln⁡vj\+εju\_\{j\}=\\mu\_\{j\}\+\\varepsilon\_\{j\}=\\ln v\_\{j\}\+\\varepsilon\_\{j\}, whereεj\\varepsilon\_\{j\}are independent random variables following the Gumbel distributionGumwith CDFGj​\(x\)=exp⁡\(−exp⁡\(−x\)\)G\_\{j\}\(x\)=\\exp\(\-\\exp\(\-x\)\)forx∈ℝx\\in\\mathbb\{R\}\. We show that the exponential arrival ordering is distributionally equivalent to the utility ordering under MNL\.

###### Claim A\.4\.

Letσ:\[n\+1\]→\[n\]\+\\sigma:\[n\+1\]\\to\[n\]\_\{\+\}be a permutation, whereσ​\(r\)\\sigma\(r\)is therr\-th ranked element\. Then

Pr⁡\[uσ​\(1\)\>uσ​\(2\)\>…\>uσ​\(n\+1\)\]=Pr⁡\[Tσ​\(1\)<Tσ​\(2\)<…<Tσ​\(n\+1\)\]\.\\Pr\[u\_\{\\sigma\(1\)\}\>u\_\{\\sigma\(2\)\}\>\.\.\.\>u\_\{\\sigma\(n\+1\)\}\]=\\Pr\[T\_\{\\sigma\(1\)\}<T\_\{\\sigma\(2\)\}<\.\.\.<T\_\{\\sigma\(n\+1\)\}\]\.

###### Proof\.

For eachj∈\[n\]\+j\\in\[n\]\_\{\+\}, letεj′:=−ln⁡Tj−μj\\varepsilon^\{\\prime\}\_\{j\}:=\-\\ln T\_\{j\}\-\\mu\_\{j\}\. We first show thatεj′\\varepsilon^\{\\prime\}\_\{j\}followsGum\. Forx∈ℝx\\in\\mathbb\{R\},

Pr⁡\[εj′≤x\]\\displaystyle\\Pr\[\\varepsilon^\{\\prime\}\_\{j\}\\leq x\]=Pr⁡\[−ln⁡Tj−μj≤x\]=Pr⁡\[Tj≥exp⁡\(−x−μj\)\]\\displaystyle=\\Pr\[\-\\ln T\_\{j\}\-\\mu\_\{j\}\\leq x\]=\\Pr\[T\_\{j\}\\geq\\exp\(\-x\-\\mu\_\{j\}\)\]=1−\(1−exp⁡\(−vj​exp⁡\(−x−μj\)\)\)\\displaystyle=1\-\(1\-\\exp\(\-v\_\{j\}\\exp\(\-x\-\\mu\_\{j\}\)\)\)=exp⁡\(−exp⁡\(μj\)​exp⁡\(−x−μj\)\)=exp⁡\(−exp⁡\(−x\)\)\.\\displaystyle=\\exp\\left\(\-\\exp\(\\mu\_\{j\}\)\\exp\(\-x\-\\mu\_\{j\}\)\\right\)=\\exp\(\-\\exp\(\-x\)\)\.This implies thatεj\\varepsilon\_\{j\}andεj′\\varepsilon^\{\\prime\}\_\{j\}are distributionally equivalent because bothεj\\varepsilon\_\{j\}andεj′\\varepsilon^\{\\prime\}\_\{j\}followGum\. Since theTjT\_\{j\}’s are independent, theεj′\\varepsilon^\{\\prime\}\_\{j\}’s are also independent, implying thatεj\\varepsilon\_\{j\}andεj′\\varepsilon^\{\\prime\}\_\{j\}are joint distributionally equivalent\. Letuj′:=μj\+εj′u^\{\\prime\}\_\{j\}:=\\mu\_\{j\}\+\\varepsilon^\{\\prime\}\_\{j\}\. By construction,uj′:=μj−ln⁡Tj−μj=−ln⁡Tju^\{\\prime\}\_\{j\}:=\\mu\_\{j\}\-\\ln T\_\{j\}\-\\mu\_\{j\}=\-\\ln T\_\{j\}\. Hence, for anyj,j′∈\[n\]\+j,j^\{\\prime\}\\in\[n\]\_\{\+\},

uj′\>uj′′⇔−ln⁡Tj\>−ln⁡Tj′⇔Tj<Tj′,u^\{\\prime\}\_\{j\}\>u^\{\\prime\}\_\{j^\{\\prime\}\}\\iff\-\\ln T\_\{j\}\>\-\\ln T\_\{j^\{\\prime\}\}\\iff T\_\{j\}<T\_\{j^\{\\prime\}\},because−ln⁡y\-\\ln yis strictly decreasing iny∈\(0,∞\)y\\in\(0,\\infty\)\.

Sinceuju\_\{j\}anduj′u^\{\\prime\}\_\{j\}are \(joint\) distributionally equivalent, for any orderingσ\\sigma,

Pr⁡\[uσ​\(1\)\>uσ​\(2\)\>⋯\>uσ​\(n\+1\)\]=Pr⁡\[uσ​\(1\)′\>uσ​\(2\)′\>⋯\>uσ​\(n\+1\)′\]\.\\Pr\\left\[u\_\{\\sigma\(1\)\}\>u\_\{\\sigma\(2\)\}\>\\cdots\>u\_\{\\sigma\(n\+1\)\}\\right\]=\\Pr\\left\[u^\{\\prime\}\_\{\\sigma\(1\)\}\>u^\{\\prime\}\_\{\\sigma\(2\)\}\>\\cdots\>u^\{\\prime\}\_\{\\sigma\(n\+1\)\}\\right\]\.Usinguj′=−log⁡Tju^\{\\prime\}\_\{j\}=\-\\log T\_\{j\}, the event on the right is exactlyTσ​\(1\)<Tσ​\(2\)<⋯<Tσ​\(n\+1\)T\_\{\\sigma\(1\)\}<T\_\{\\sigma\(2\)\}<\\cdots<T\_\{\\sigma\(n\+1\)\}\. Therefore,

Pr⁡\[uσ​\(1\)\>uσ​\(2\)\>…\>uσ​\(n\+1\)\]=Pr⁡\[Tσ​\(1\)<Tσ​\(2\)<…<Tσ​\(n\+1\)\]\.\\Pr\\left\[u\_\{\\sigma\(1\)\}\>u\_\{\\sigma\(2\)\}\>\.\.\.\>u\_\{\\sigma\(n\+1\)\}\\right\]=\\Pr\\left\[T\_\{\\sigma\(1\)\}<T\_\{\\sigma\(2\)\}<\.\.\.<T\_\{\\sigma\(n\+1\)\}\\right\]\.∎

##### Partial\-ordering\-based Polytope\.

From Claim[A\.4](https://arxiv.org/html/2607.09817#A1.Thmtheorem4), we construct a polytope derived from the partial ordering based on𝒟\\mathcal\{D\}\. LetD=\(\[n\]\+,A\)D=\(\[n\]\_\{\+\},A\)be a DAG induced by𝒟\\mathcal\{D\}\. That is, if\(j,j′\)∈A\(j,j^\{\\prime\}\)\\in A, thenuj\>uj′u\_\{j\}\>u\_\{j^\{\\prime\}\}, or distributionally equivalently,Tj<Tj′T\_\{j\}<T\_\{j^\{\\prime\}\}\. We have thatπ𝒟=Pr⁡\[Tj<Tj′​∀\(j,j′\)∈A\]\\pi\_\{\\mathcal\{D\}\}=\\Pr\[T\_\{j\}<T\_\{j^\{\\prime\}\}\\ \\forall\(j,j^\{\\prime\}\)\\in A\]\. The corresponding polytope isK:=\{t∈ℝ≥0n\+1:tj≤tj′​∀\(j,j′\)∈A\}K:=\\\{t\\in\\mathbb\{R\}\_\{\\geq 0\}^\{n\+1\}:t\_\{j\}\\leq t\_\{j^\{\\prime\}\}\\ \\forall\(j,j^\{\\prime\}\)\\in A\\\}\. Let the joint PDF

f​\(t\):=∏j=0nvj​exp⁡\(−vj​tj\),f\(t\):=\\prod\_\{j=0\}^\{n\}v\_\{j\}\\exp\(\-v\_\{j\}t\_\{j\}\),\(41\)thenπ𝒟=∫Kf​\(t\)​𝑑t\\pi\_\{\\mathcal\{D\}\}=\\int\_\{K\}f\(t\)dt\. Note thatffis log\-concave inttbecauseln⁡f​\(t\)=∑j=0nln⁡vj−∑j=0nvj​tj\\ln f\(t\)=\\sum\_\{j=0\}^\{n\}\\ln v\_\{j\}\-\\sum\_\{j=0\}^\{n\}v\_\{j\}t\_\{j\}is affine intt\.

BecauseDDis a DAG, there exists at least one complete linear extensionσ∼c𝒟\\sigma\\sim\_\{c\}\\mathcal\{D\}\. Therefore

π𝒟≥πσ=Pr⁡\[Tσ​\(1\)<Tσ​\(2\)<…<Tσ​\(n\+1\)\]=∏ℓ=1n\+1vσ​\(ℓ\)∑s=ℓn\+1vσ​\(s\)≥1Rn\+1​\(n\+1\)\!\.\\pi\_\{\\mathcal\{D\}\}\\geq\\pi\_\{\\sigma\}=\\Pr\\left\[T\_\{\\sigma\(1\)\}<T\_\{\\sigma\(2\)\}<\.\.\.<T\_\{\\sigma\(n\+1\)\}\\right\]=\\prod\_\{\\ell=1\}^\{n\+1\}\\frac\{v\_\{\\sigma\(\\ell\)\}\}\{\\sum\_\{s=\\ell\}^\{n\+1\}v\_\{\\sigma\(s\)\}\}\\geq\\frac\{1\}\{R^\{n\+1\}\(n\+1\)\!\}\.SinceKKis unbounded, we truncateKKto preserve sufficient probability mass for the analysis\. Let

L:=1Rn\+1​\(n\+1\)\!,B:=ln⁡4​\(n\+1\)ε​L,and​KB:=K∩\[0,B\]n\+1\.L:=\\frac\{1\}\{R^\{n\+1\}\(n\+1\)\!\},B:=\\ln\\frac\{4\(n\+1\)\}\{\\varepsilon L\},\\text\{and \}K\_\{B\}:=K\\cap\[0,B\]^\{n\+1\}\.\(42\)
Letπ~𝒟:=∫KBf​\(t\)​𝑑t\\tilde\{\\pi\}\_\{\\mathcal\{D\}\}:=\\int\_\{K\_\{B\}\}f\(t\)dtbe an estimated probability forπ𝒟\\pi\_\{\\mathcal\{D\}\}after truncation\. Sincevj≥1v\_\{j\}\\geq 1, we have thatPr⁡\[Tj\>B\]=exp⁡\(−vj​B\)≤exp⁡\(−B\)\\Pr\[T\_\{j\}\>B\]=\\exp\(\-v\_\{j\}B\)\\leq\\exp\(\-B\)forj∈\[n\]\+j\\in\[n\]\_\{\+\}\. By the union bound, this implies

Pr⁡\[maxj∈\[n\]\+⁡Tj\>B\]≤\(n\+1\)​exp⁡\(−B\)=ε​L4≤ε​π𝒟4\\Pr\[\\max\_\{j\\in\[n\]\_\{\+\}\}T\_\{j\}\>B\]\\leq\(n\+1\)\\exp\(\-B\)=\\frac\{\\varepsilon L\}\{4\}\\leq\\frac\{\\varepsilon\\pi\_\{\\mathcal\{D\}\}\}\{4\}andπ𝒟−π~𝒟∈\[0,ε​π𝒟/4\]\\pi\_\{\\mathcal\{D\}\}\-\\tilde\{\\pi\}\_\{\\mathcal\{D\}\}\\in\[0,\\varepsilon\\pi\_\{\\mathcal\{D\}\}/4\], or equivalently,

π~𝒟∈\[\(1−ε4\)​π𝒟,π𝒟\]\.\\tilde\{\\pi\}\_\{\\mathcal\{D\}\}\\in\[\(1\-\\frac\{\\varepsilon\}\{4\}\)\\pi\_\{\\mathcal\{D\}\},\\pi\_\{\\mathcal\{D\}\}\]\.\(43\)In the remainder, we approximateπ𝒟\\pi\_\{\\mathcal\{D\}\}by approximatingπ~𝒟\\tilde\{\\pi\}\_\{\\mathcal\{D\}\}, thereby completing the proof\.

##### Randomized Convex\-body Integration\.

To approximateπ~𝒟\\tilde\{\\pi\}\_\{\\mathcal\{D\}\}, we use the theorem which follows from\[[26](https://arxiv.org/html/2607.09817#bib.bib42)\]\.

###### Theorem A\.5\(Adapted from\[[26](https://arxiv.org/html/2607.09817#bib.bib42)\]\)\.

LetK⊆ℝdK\\subseteq\\mathbb\{R\}^\{d\}be a full\-dimensional compact convex body given by a polynomial\-time separation oracle\. Suppose that we are given a pointx∈Kx\\in Kand radii0<rin≤rout0<r\_\{\\mathrm\{in\}\}\\leq r\_\{\\mathrm\{out\}\}such that the Euclidean balls satisfyB2​\(x,rin\)⊆K⊆B2​\(x,rout\)\.B\_\{2\}\(x,r\_\{\\mathrm\{in\}\}\)\\subseteq K\\subseteq B\_\{2\}\(x,r\_\{\\mathrm\{out\}\}\)\.LetΓ:=rout/rin\\Gamma:=r\_\{\\mathrm\{out\}\}/r\_\{\\mathrm\{in\}\}andf:K→ℝ\>0f:K\\to\\mathbb\{R\}\_\{\>0\}be a log\-concave function whose logarithm can be evaluated to polynomial precision in polynomial time\. Suppose that the logarithmic range offfoverKKis bounded byΔ\\Delta, i\.e\.,

ln⁡supt∈Kf​\(t\)inft∈Kf​\(t\)≤Δ\.\\ln\\frac\{\\sup\_\{t\\in K\}f\(t\)\}\{\\inf\_\{t\\in K\}f\(t\)\}\\leq\\Delta\.\(44\)Then, for anyη,δ∈\(0,1\)\\eta,\\delta\\in\(0,1\), there is a randomized algorithm that outputsI^\\hat\{I\}such that

Pr⁡\[\(1−η\)​∫Kf​\(t\)​𝑑t≤I^≤\(1\+η\)​∫Kf​\(t\)​𝑑t\]≥1−δ\.\\Pr\\left\[\(1\-\\eta\)\\int\_\{K\}f\(t\)\\,dt\\leq\\hat\{I\}\\leq\(1\+\\eta\)\\int\_\{K\}f\(t\)\\,dt\\right\]\\geq 1\-\\delta\.The running time is polynomial ind,1/η,log⁡\(1/δ\),Γd,1/\\eta,\\log\(1/\\delta\),\\Gamma,Δ\\Delta, and the encoding length of the separation and evaluation oracles\.

This theorem is a standard consequence of the randomized integration framework for log\-concave functions\[[26](https://arxiv.org/html/2607.09817#bib.bib42)\]\. The aspect\-ratio dependence is handled by the standard rounding preprocessing: starting from a convex body with polynomially boundedΓ\\Gamma, one first applies an affine transformation that brings the support into well\-rounded position, and then applies the log\-concave integration algorithm\.

To use Theorem[A\.5](https://arxiv.org/html/2607.09817#A1.Thmtheorem5), we show that the following requirements hold\. First, there is an efficient separation oracle, i\.e\., it takes polynomial time to verify if any pointt∈ℝn\+1t\\in\\mathbb\{R\}^\{n\+1\}belongs toKBK\_\{B\}\. Second, there existx∈KBx\\in K\_\{B\},rinr\_\{\\mathrm\{in\}\}, androutr\_\{\\mathrm\{out\}\}, such thatB2​\(x,rin\)⊆KB⊆B2​\(x,rout\)B\_\{2\}\(x,r\_\{\\mathrm\{in\}\}\)\\subseteq K\_\{B\}\\subseteq B\_\{2\}\(x,r\_\{\\mathrm\{out\}\}\)andΓ=4​\(n\+2\)​n\+1\\Gamma=4\(n\+2\)\\sqrt\{n\+1\}\. Finally, \([44](https://arxiv.org/html/2607.09817#A1.E44)\) holds withK=KBK=K\_\{B\},ffdefined in \([41](https://arxiv.org/html/2607.09817#A1.E41)\) is log\-concave, andΔ=\(n\+1\)​R​B∈poly⁡\(n,R,1/ε\)\\Delta=\(n\+1\)RB\\in\\operatorname\{poly\}\(n,R,1/\\varepsilon\)\.

The convex bodyKB⊆ℝn\+1K\_\{B\}\\subseteq\\mathbb\{R\}^\{n\+1\}is described by the linear inequalitiestj∈\[0,B\]t\_\{j\}\\in\[0,B\]for allj∈\[n\]\+j\\in\[n\]\_\{\+\}andtj≤tj′t\_\{j\}\\leq t\_\{j^\{\\prime\}\}for all\(j,j′\)∈A\(j,j^\{\\prime\}\)\\in A\. This admits a polynomial\-time separation oracle\.

Letσ∼c𝒟\\sigma\\sim\_\{c\}\\mathcal\{D\}andx∈ℝn\+1x\\in\\mathbb\{R\}^\{n\+1\}be such thatxσ​\(s\)=s​B/\(n\+2\)x\_\{\\sigma\(s\)\}=sB/\(n\+2\)fors∈\[n\+1\]s\\in\[n\+1\]\. For every\(j,j′\)∈A\(j,j^\{\\prime\}\)\\in A, we havexj′−xj≥B/\(n\+2\)x\_\{j^\{\\prime\}\}\-x\_\{j\}\\geq B/\(n\+2\)\. Let

rin:=B4​\(n\+2\)​and​rout:=B​n\+1\.r\_\{\\mathrm\{in\}\}:=\\frac\{B\}\{4\(n\+2\)\}\\text\{ and \}r\_\{\\mathrm\{out\}\}:=B\\sqrt\{n\+1\}\.If‖y−x‖2≤rin\\\|y\-x\\\|\_\{2\}\\leq r\_\{\\mathrm\{in\}\}, thenyj∈\[0,B\]y\_\{j\}\\in\[0,B\]for allj∈\[n\]\+j\\in\[n\]\_\{\+\}and

yj′−yj≥xj′−xj−2​rin≥B2​\(n\+2\)\>0\.y\_\{j^\{\\prime\}\}\-y\_\{j\}\\geq x\_\{j^\{\\prime\}\}\-x\_\{j\}\-2r\_\{\\mathrm\{in\}\}\\geq\\frac\{B\}\{2\(n\+2\)\}\>0\.This impliesB2​\(x,rin\)⊆KBB\_\{2\}\(x,r\_\{\\mathrm\{in\}\}\)\\subseteq K\_\{B\}\. For anyy∈KB⊆\[0,B\]n\+1y\\in K\_\{B\}\\subseteq\[0,B\]^\{n\+1\},‖y−x‖2≤∑j=1n\+1B2=B​n\+1\\\|y\-x\\\|\_\{2\}\\leq\\sqrt\{\\sum\_\{j=1\}^\{n\+1\}B^\{2\}\}=B\\sqrt\{n\+1\}, implying thatKB⊆B2​\(x,rout\)K\_\{B\}\\subseteq B\_\{2\}\(x,r\_\{\\mathrm\{out\}\}\)\. Consequently,Γ=rout/rin=4​\(n\+2\)​n\+1\\Gamma=r\_\{\\mathrm\{out\}\}/r\_\{\\mathrm\{in\}\}=4\(n\+2\)\\sqrt\{n\+1\}\.

SinceKB⊆\[0,B\]n\+1K\_\{B\}\\subseteq\[0,B\]^\{n\+1\}andvj∈\[1,R\]v\_\{j\}\\in\[1,R\]for allj∈\[n\]\+j\\in\[n\]\_\{\+\}, using \([41](https://arxiv.org/html/2607.09817#A1.E41)\) implies that

ln⁡supt∈KBf​\(t\)inft∈KBf​\(t\)≤ln⁡∏j=0nvj∏j=0nvj​exp⁡\(−vj​B\)=B​∑j=0nvj≤\(n\+1\)​B​R\.\\ln\\frac\{\\sup\_\{t\\in K\_\{B\}\}f\(t\)\}\{\\inf\_\{t\\in K\_\{B\}\}f\(t\)\}\\leq\\ln\\frac\{\\prod\_\{j=0\}^\{n\}v\_\{j\}\}\{\\prod\_\{j=0\}^\{n\}v\_\{j\}\\exp\(\-v\_\{j\}B\)\}=B\\sum\_\{j=0\}^\{n\}v\_\{j\}\\leq\(n\+1\)BR\.Moreover, from \([42](https://arxiv.org/html/2607.09817#A1.E42)\), we have thatB=O​\(n​log⁡R\+n​log⁡n\+log⁡\(1/ε\)\)B=O\(n\\log R\+n\\log n\+\\log\(1/\\varepsilon\)\)\.

By settingη=ε/4\\eta=\\varepsilon/4, Theorem[A\.5](https://arxiv.org/html/2607.09817#A1.Thmtheorem5)implies a randomized approximation scheme that outputs an estimateπ^𝒟\\hat\{\\pi\}\_\{\\mathcal\{D\}\}forπ~𝒟\\tilde\{\\pi\}\_\{\\mathcal\{D\}\}such that

Pr⁡\[\(1−ε4\)​π~𝒟≤π^𝒟≤\(1\+ε4\)​π~𝒟\]≥1−δ\\Pr\\left\[\(1\-\\frac\{\\varepsilon\}\{4\}\)\\tilde\{\\pi\}\_\{\\mathcal\{D\}\}\\leq\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\\leq\(1\+\\frac\{\\varepsilon\}\{4\}\)\\tilde\{\\pi\}\_\{\\mathcal\{D\}\}\\right\]\\geq 1\-\\delta\(45\)with running time polynomial innn,RR,1/ε1/\\varepsilon, andlog⁡\(1/δ\)\\log\(1/\\delta\)\. Combining \([43](https://arxiv.org/html/2607.09817#A1.E43)\) and \([45](https://arxiv.org/html/2607.09817#A1.E45)\), on the success event of the integration algorithm, we have that

π^𝒟≥\(1−ε4\)​π~𝒟≥\(1−ε4\)2​π𝒟≥\(1−ε\)​π𝒟\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\\geq\(1\-\\frac\{\\varepsilon\}\{4\}\)\\tilde\{\\pi\}\_\{\\mathcal\{D\}\}\\geq\(1\-\\frac\{\\varepsilon\}\{4\}\)^\{2\}\\pi\_\{\\mathcal\{D\}\}\\geq\(1\-\\varepsilon\)\\pi\_\{\\mathcal\{D\}\}where the last inequality follows sinceε∈\(0,1\)\\varepsilon\\in\(0,1\)\. Similarly,

π^𝒟≤\(1\+ε4\)​π~𝒟≤\(1\+ε\)​π~𝒟≤\(1\+ε\)​π𝒟\.\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\\leq\(1\+\\frac\{\\varepsilon\}\{4\}\)\\tilde\{\\pi\}\_\{\\mathcal\{D\}\}\\leq\(1\+\\varepsilon\)\\tilde\{\\pi\}\_\{\\mathcal\{D\}\}\\leq\(1\+\\varepsilon\)\\pi\_\{\\mathcal\{D\}\}\.Therefore,Pr⁡\[π^𝒟∈\[\(1−ε\)​π𝒟,\(1\+ε\)​π𝒟\]\]≥1−δ\\Pr\\left\[\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\\in\[\(1\-\\varepsilon\)\\pi\_\{\\mathcal\{D\}\},\(1\+\\varepsilon\)\\pi\_\{\\mathcal\{D\}\}\]\\right\]\\geq 1\-\\delta, which proves the existence of the randomized approximation scheme\. ∎

###### Theorem A\.6\.

Under MNL, for anyε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\)and𝒟\\mathcal\{D\}where the induced directed graph is acyclic, there exists a randomized algorithm that returns an estimateπ^𝒟​\(j,S\)\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\(j,S\)forπ𝒟​\(j,S\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)in \([2](https://arxiv.org/html/2607.09817#S2.E2)\), satisfying

Pr⁡\[π^𝒟​\(j,S\)∈\[\(1−ε\)​π𝒟​\(j,S\),\(1\+ε\)​π𝒟​\(j,S\)\]\]≥1−δ,\\Pr\\left\[\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\(j,S\)\\in\[\(1\-\\varepsilon\)\\pi\_\{\\mathcal\{D\}\}\(j,S\),\(1\+\\varepsilon\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)\]\\right\]\\geq 1\-\\delta,with running time polynomial inn,R,1/εn,R,1/\\varepsilon,log⁡\(1/δ\)\\log\(1/\\delta\), and the encoding length ofvv\. IfR∈poly⁡\(n\)R\\in\\operatorname\{poly\}\(n\), thenπ𝒟​\(j,S\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)admits an FPRAS\.

###### Proof\.

Ifj∉S\+j\\notin S\_\{\+\}, the algorithm returns0\. Henceforth, we consider the casej∈S\+j\\in S\_\{\+\}\.

Letη=ε/4\\eta=\\varepsilon/4,ξ=δ/4\\xi=\\delta/4, andπ𝒟​\(j,S\)=π𝒟′/π𝒟\\pi\_\{\\mathcal\{D\}\}\(j,S\)=\\pi\_\{\\mathcal\{D\}^\{\\prime\}\}/\\pi\_\{\\mathcal\{D\}\}with𝒟′=𝒟∪\{\(j,S\)\}\\mathcal\{D\}^\{\\prime\}=\\mathcal\{D\}\\cup\\\{\(j,S\)\\\}\. If the directed graph induced by𝒟′\\mathcal\{D\}^\{\\prime\}has a cycle, return 0\. Otherwise, by Theorem[A\.3](https://arxiv.org/html/2607.09817#A1.Thmtheorem3), there exists a randomized algorithm that returns estimatesπ^𝒟\\hat\{\\pi\}\_\{\\mathcal\{D\}\}forπ𝒟\\pi\_\{\\mathcal\{D\}\}andπ^𝒟′\\hat\{\\pi\}\_\{\\mathcal\{D\}^\{\\prime\}\}forπ𝒟′\\pi\_\{\\mathcal\{D\}^\{\\prime\}\}, satisfying

Pr⁡\[π^𝒟∈\[\(1−η\)​π𝒟,\(1\+η\)​π𝒟\]\]≥1−ξ​and​Pr⁡\[π^𝒟′∈\[\(1−η\)​π𝒟′,\(1\+η\)​π𝒟′\]\]≥1−ξ,\\Pr\\left\[\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\\in\[\(1\-\\eta\)\\pi\_\{\\mathcal\{D\}\},\(1\+\\eta\)\\pi\_\{\\mathcal\{D\}\}\]\\right\]\\geq 1\-\\xi\\text\{ and \}\\Pr\\left\[\\hat\{\\pi\}\_\{\\mathcal\{D\}^\{\\prime\}\}\\in\[\(1\-\\eta\)\\pi\_\{\\mathcal\{D\}^\{\\prime\}\},\(1\+\\eta\)\\pi\_\{\\mathcal\{D\}^\{\\prime\}\}\]\\right\]\\geq 1\-\\xi,with running time polynomial inn,R,1/ηn,R,1/\\eta, andlog⁡\(1/δ\)\\log\(1/\\delta\)\.

The probability that eitherπ^𝒟∈\[\(1−η\)​π𝒟,\(1\+η\)​π𝒟\]\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\\in\[\(1\-\\eta\)\\pi\_\{\\mathcal\{D\}\},\(1\+\\eta\)\\pi\_\{\\mathcal\{D\}\}\]orπ^𝒟′∈\[\(1−η\)​π𝒟′,\(1\+η\)​π𝒟′\]\\hat\{\\pi\}\_\{\\mathcal\{D\}^\{\\prime\}\}\\in\[\(1\-\\eta\)\\pi\_\{\\mathcal\{D\}^\{\\prime\}\},\(1\+\\eta\)\\pi\_\{\\mathcal\{D\}^\{\\prime\}\}\]fails is at most2​ξ=δ/2≤δ2\\xi=\\delta/2\\leq\\delta, which implies that

Pr⁡\[π^𝒟∈\[\(1−η\)​π𝒟,\(1\+η\)​π𝒟\]​and​π^𝒟′∈\[\(1−η\)​π𝒟′,\(1\+η\)​π𝒟′\]\]≥1−δ\.\\Pr\\left\[\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\\in\[\(1\-\\eta\)\\pi\_\{\\mathcal\{D\}\},\(1\+\\eta\)\\pi\_\{\\mathcal\{D\}\}\]\\text\{ and \}\\hat\{\\pi\}\_\{\\mathcal\{D\}^\{\\prime\}\}\\in\[\(1\-\\eta\)\\pi\_\{\\mathcal\{D\}^\{\\prime\}\},\(1\+\\eta\)\\pi\_\{\\mathcal\{D\}^\{\\prime\}\}\]\\right\]\\geq 1\-\\delta\.Letπ^𝒟​\(j,S\)=π^𝒟′/π^𝒟\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\(j,S\)=\\hat\{\\pi\}\_\{\\mathcal\{D\}^\{\\prime\}\}/\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\. When both events are successful, we have that

π^𝒟​\(j,S\)=π^𝒟′π^𝒟≥\(1−η\)​π𝒟′\(1\+η\)​π𝒟=\(1−ε/4\)​π𝒟′\(1\+ε/4\)​π𝒟≥\(1−ε\)​π𝒟′π𝒟=\(1−ε\)​π𝒟​\(j,S\)\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\(j,S\)=\\frac\{\\hat\{\\pi\}\_\{\\mathcal\{D\}^\{\\prime\}\}\}\{\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\}\\geq\\frac\{\(1\-\\eta\)\\pi\_\{\\mathcal\{D\}^\{\\prime\}\}\}\{\(1\+\\eta\)\\pi\_\{\\mathcal\{D\}\}\}=\\frac\{\(1\-\\varepsilon/4\)\\pi\_\{\\mathcal\{D\}^\{\\prime\}\}\}\{\(1\+\\varepsilon/4\)\\pi\_\{\\mathcal\{D\}\}\}\\geq\\frac\{\(1\-\\varepsilon\)\\pi\_\{\\mathcal\{D\}^\{\\prime\}\}\}\{\\pi\_\{\\mathcal\{D\}\}\}=\(1\-\\varepsilon\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)where the last inequality holds because\(1\+ε/4\)​\(1−ε\)=1−3​ε/4−ε2/4≥1−ε\(1\+\\varepsilon/4\)\(1\-\\varepsilon\)=1\-3\\varepsilon/4\-\\varepsilon^\{2\}/4\\geq 1\-\\varepsilonwhenε∈\(0,1\)\\varepsilon\\in\(0,1\)\. Similarly,

π^𝒟​\(j,S\)=π^𝒟′π^𝒟≤\(1\+η\)​π𝒟′\(1−η\)​π𝒟=\(1\+ε/4\)​π𝒟′\(1−ε/4\)​π𝒟≤\(1\+ε\)​π𝒟′π𝒟=\(1\+ε\)​π𝒟​\(j,S\)\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\(j,S\)=\\frac\{\\hat\{\\pi\}\_\{\\mathcal\{D\}^\{\\prime\}\}\}\{\\hat\{\\pi\}\_\{\\mathcal\{D\}\}\}\\leq\\frac\{\(1\+\\eta\)\\pi\_\{\\mathcal\{D\}^\{\\prime\}\}\}\{\(1\-\\eta\)\\pi\_\{\\mathcal\{D\}\}\}=\\frac\{\(1\+\\varepsilon/4\)\\pi\_\{\\mathcal\{D\}^\{\\prime\}\}\}\{\(1\-\\varepsilon/4\)\\pi\_\{\\mathcal\{D\}\}\}\\leq\\frac\{\(1\+\\varepsilon\)\\pi\_\{\\mathcal\{D\}^\{\\prime\}\}\}\{\\pi\_\{\\mathcal\{D\}\}\}=\(1\+\\varepsilon\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)where the last inequality holds because\(1−ε/4\)​\(1\+ε\)=1\+3​ε/4−ε2/4≤1\+ε\(1\-\\varepsilon/4\)\(1\+\\varepsilon\)=1\+3\\varepsilon/4\-\\varepsilon^\{2\}/4\\leq 1\+\\varepsilonwhenε∈\(0,1\)\\varepsilon\\in\(0,1\)\. ∎

### A\.2Hardness and Computability of Conditional Assortment Optimization

MC and MNL are widely used in assortment planning due to their computational tractability for \([TAO](https://arxiv.org/html/2607.09817#S2.Ex1)\)\. However, conditioning on historical transactions significantly alters the problem structure, thus rendering them less tractable even under MNL\. We show that \([CAO](https://arxiv.org/html/2607.09817#S2.Ex2)\) is NP\-hard under MNL conditional on one transaction\. This proof is adapted from\[[10](https://arxiv.org/html/2607.09817#bib.bib10)\], which shows the hardness of a multi\-stage conditional assortment problem\.999We note that it is possible to design an FPTAS for \([CAO](https://arxiv.org/html/2607.09817#S2.Ex2)\) under MNL based on\[[10](https://arxiv.org/html/2607.09817#bib.bib10)\]whenkkis constant\.On the positive side, we show that \([TCAO](https://arxiv.org/html/2607.09817#S2.Ex3)\) under MC is computationally tractable whenkkis small, using an LP\-based approach similar to LP \([7](https://arxiv.org/html/2607.09817#S2.E7)\)\.

###### Theorem A\.7\.

\([CAO](https://arxiv.org/html/2607.09817#S2.Ex2)\) is NP\-hard under MNL, even whenk=1k=1\.

###### Proof\.

We follow the ideas in\[[10](https://arxiv.org/html/2607.09817#bib.bib10)\]\. The proof consists of two main parts\. First, we provide closed\-form expressions for the conditional probabilityπ𝒟​\(j,S\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)when𝒟=\{j1,S1\}=\{\(i,\{i\}\)\}\\mathcal\{D\}=\\\{j\_\{1\},S\_\{1\}\\\}=\\\{\(i,\\\{i\\\}\)\\\}for ani∈\[n\]i\\in\[n\]\. Second, we reduce an NP\-complete problem to \([CAO](https://arxiv.org/html/2607.09817#S2.Ex2)\), where the analysis involves the closed\-form expressions\.

Suppose𝒟=\{\(j1,S1\)\}=\{\(i,\{i\}\)\}\\mathcal\{D\}=\\\{\(j\_\{1\},S\_\{1\}\)\\\}=\\\{\(i,\\\{i\\\}\)\\\}for ani∈\[n\]i\\in\[n\]\. From \([2](https://arxiv.org/html/2607.09817#S2.E2)\) and \([12](https://arxiv.org/html/2607.09817#S2.E12)\),101010Or alternatively,\[[10](https://arxiv.org/html/2607.09817#bib.bib10)\]\.we have that ifi∈Si\\in S, then

π𝒟​\(j,S\)=\{v0\+viV​\(S\+\)if​j=i,0if​j=0,vjV​\(S\+\)if​j∈S∖\{i\};\\pi\_\{\\mathcal\{D\}\}\(j,S\)=\\begin\{cases\}\\mbox\{\\large$\\frac\{v\_\{0\}\+v\_\{i\}\}\{V\(S\_\{\+\}\)\}$\}&\\text\{if \}j=i,\\\\ 0&\\text\{if \}j=0,\\\\ \\mbox\{\\large$\\frac\{v\_\{j\}\}\{V\(S\_\{\+\}\)\}$\}&\\text\{if \}j\\in S\\setminus\\\{i\\\};\\\\ \\end\{cases\}\(46\)ifi∉Si\\notin S, then

π𝒟​\(j,S\)=\{v0V​\(S\+\)​v0\+vivi\+V​\(S\+\)if​j=0,vjvi\+V​\(S\+\)\+vj​\(v0\+vi\)V​\(S\+\)​\(vi\+V​\(S\+\)\)if​j∈S\.\\pi\_\{\\mathcal\{D\}\}\(j,S\)=\\begin\{cases\}\\mbox\{\\large$\\frac\{v\_\{0\}\}\{V\(S\_\{\+\}\)\}\\frac\{v\_\{0\}\+v\_\{i\}\}\{v\_\{i\}\+V\(S\_\{\+\}\)\}$\}&\\text\{if \}j=0,\\\\ \\mbox\{\\large$\\frac\{v\_\{j\}\}\{v\_\{i\}\+V\(S\_\{\+\}\)\}\+\\frac\{v\_\{j\}\(v\_\{0\}\+v\_\{i\}\)\}\{V\(S\_\{\+\}\)\(v\_\{i\}\+V\(S\_\{\+\}\)\)\}$\}&\\text\{if \}j\\in S\.\\\\ \\end\{cases\}\(47\)
Now we reduce the partition problem, which is NP\-complete, to \([CAO](https://arxiv.org/html/2607.09817#S2.Ex2)\)\. In the partition problem, we haveci\>0c\_\{i\}\>0fori∈\[m\]i\\in\[m\]with∑i∈\[m\]ci=2​T\\sum\_\{i\\in\[m\]\}c\_\{i\}=2Tfor an integerm\>0m\>0\. The goal is to find a subset of numbersP⊆\[m\]P\\subseteq\[m\]such that∑i∈Pci=∑i∈\[m\]∖Pci=T\\sum\_\{i\\in P\}c\_\{i\}=\\sum\_\{i\\in\[m\]\\setminus P\}c\_\{i\}=T\.

Given an instance of the partition problem, we construct an instance of \([CAO](https://arxiv.org/html/2607.09817#S2.Ex2)\) under MNL withk=1k=1as follows\. We haven=m\+2n=m\+2products with the following revenues and attraction values:

ri=\{6937if​i∈\[m\],3if​i=m\+1,1if​i=m\+2,​and​vi=\{ciTif​i∈\[m\],1if​i=0,m\+1,m\+2\.r\_\{i\}=\\begin\{cases\}\\frac\{69\}\{37\}&\\text\{if \}i\\in\[m\],\\\\ 3&\\text\{if \}i=m\+1,\\\\ 1&\\text\{if \}i=m\+2,\\\\ \\end\{cases\}\\text\{ and \}v\_\{i\}=\\begin\{cases\}\\frac\{c\_\{i\}\}\{T\}&\\text\{if \}i\\in\[m\],\\\\ 1&\\text\{if \}i=0,m\+1,m\+2\.\\\\ \\end\{cases\}\(48\)Let𝒟=\{\(j1,S1\)\}=\{\(m\+2,\{m\+2\}\)\}\\mathcal\{D\}=\\\{\(j\_\{1\},S\_\{1\}\)\\\}=\\\{\(m\+2,\\\{m\+2\\\}\)\\\}\. LetS∗⊆\[m\+2\]S^\{\*\}\\subseteq\[m\+2\]be an optimal offer set for \([CAO](https://arxiv.org/html/2607.09817#S2.Ex2)\)\. We show thatm\+2∉S∗m\+2\\notin S^\{\*\}andm\+1∈S∗m\+1\\in S^\{\*\}\.

Supposem\+2∈S∗m\+2\\in S^\{\*\}, then from \([46](https://arxiv.org/html/2607.09817#A1.E46)\), \([CAO](https://arxiv.org/html/2607.09817#S2.Ex2)\) is equivalent to \([TAO](https://arxiv.org/html/2607.09817#S2.Ex1)\) with input parametersr′r^\{\\prime\}andv′v^\{\\prime\}described as follows\. Sincem\+2m\+2is already selected from\{0,m\+2\}\\\{0,m\+2\\\}\. We know that offeringm\+2m\+2ensures a revenue ofrm\+2r\_\{m\+2\}\. Therefore, we set the revenuesri′=ri−rm\+2r^\{\\prime\}\_\{i\}=r\_\{i\}\-r\_\{m\+2\}as the shifted revenues andvi′=viv^\{\\prime\}\_\{i\}=v\_\{i\}fori∈\[m\+1\]i\\in\[m\+1\], and setm\+2m\+2as the no\-purchase option with an attraction value ofv0\+vm\+2v\_\{0\}\+v\_\{m\+2\}\. Then we consider revenue\-ordered assortments and have thatS=\[n\]=\[m\+2\]S=\[n\]=\[m\+2\]is optimal for \([CAO](https://arxiv.org/html/2607.09817#S2.Ex2)\), providing an expected revenue of

3⋅vm\+1\+69/37⋅2\+1⋅\(v0\+vm\+2\)v0\+∑i∈\[m\+1\]vi\+vm\+2=3\+118/37\+25=323185<2\.\\frac\{3\\cdot v\_\{m\+1\}\+69/37\\cdot 2\+1\\cdot\(v\_\{0\}\+v\_\{m\+2\}\)\}\{v\_\{0\}\+\\sum\_\{i\\in\[m\+1\]\}v\_\{i\}\+v\_\{m\+2\}\}=\\frac\{3\+118/37\+2\}\{5\}=\\frac\{323\}\{185\}<2\.\(49\)
Supposem\+2∉S∗m\+2\\notin S^\{\*\}, then from \([47](https://arxiv.org/html/2607.09817#A1.E47)\), for anyS⊆\[m\+1\]S\\subseteq\[m\+1\], the revenue obtained by showingSSis

∑j∈S\(1vi\+V​\(S\+\)\+v0\+viV​\(S\+\)​\(vi\+V​\(S\+\)\)\)​rj​vj=∑j∈S\(12\+V​\(S\)\+2\(1\+V​\(S\)\)​\(2\+V​\(S\)\)\)​rj​vj\\displaystyle\\quad\\sum\_\{j\\in S\}\\left\(\\frac\{1\}\{v\_\{i\}\+V\(S\_\{\+\}\)\}\+\\frac\{v\_\{0\}\+v\_\{i\}\}\{V\(S\_\{\+\}\)\(v\_\{i\}\+V\(S\_\{\+\}\)\)\}\\right\)r\_\{j\}v\_\{j\}=\\sum\_\{j\\in S\}\\left\(\\frac\{1\}\{2\+V\(S\)\}\+\\frac\{2\}\{\(1\+V\(S\)\)\(2\+V\(S\)\)\}\\right\)r\_\{j\}v\_\{j\}=∑j∈S\(2\+\(1\+V​\(S\)\)\(1\+V​\(S\)\)​\(2\+V​\(S\)\)\)​rj​vj=∑j∈S\(2​\(2\+V​\(S\)\)−\(1\+V​\(S\)\)\(1\+V​\(S\)\)​\(2\+V​\(S\)\)\)​rj​vj\\displaystyle=\\sum\_\{j\\in S\}\\left\(\\frac\{2\+\(1\+V\(S\)\)\}\{\(1\+V\(S\)\)\(2\+V\(S\)\)\}\\right\)r\_\{j\}v\_\{j\}=\\sum\_\{j\\in S\}\\left\(\\frac\{2\(2\+V\(S\)\)\-\(1\+V\(S\)\)\}\{\(1\+V\(S\)\)\(2\+V\(S\)\)\}\\right\)r\_\{j\}v\_\{j\}=∑j∈S2​\(11\+V​\(S\)−12​\(2\+V​\(S\)\)\)​rj​vj\.\\displaystyle=\\sum\_\{j\\in S\}2\\left\(\\frac\{1\}\{1\+V\(S\)\}\-\\frac\{1\}\{2\(2\+V\(S\)\)\}\\right\)r\_\{j\}v\_\{j\}\.
Therefore,S∗S^\{\*\}is a solution of

maxS⊆\[m\+1\]​∑j∈S2​\(11\+V​\(S\)−12​\(2\+V​\(S\)\)\)​rj​vj\.\\max\_\{S\\subseteq\[m\+1\]\}\\sum\_\{j\\in S\}2\\left\(\\frac\{1\}\{1\+V\(S\)\}\-\\frac\{1\}\{2\(2\+V\(S\)\)\}\\right\)r\_\{j\}v\_\{j\}\.\(50\)
The following lemma is from\[[10](https://arxiv.org/html/2607.09817#bib.bib10)\]\.

###### Lemma A\.8\(\[[10](https://arxiv.org/html/2607.09817#bib.bib10)\]\)\.

Givenrrandvvfrom \([48](https://arxiv.org/html/2607.09817#A1.E48)\), the optimal solutionS∗S^\{\*\}for \([50](https://arxiv.org/html/2607.09817#A1.E50)\) is such thatS∗=S′∪\{m\+1\}S^\{\*\}=S^\{\\prime\}\\cup\\\{m\+1\\\}for someS′⊆\[m\]S^\{\\prime\}\\subseteq\[m\]\. In addition, the expected revenue ofS∗S^\{\*\}is75/37\>275/37\>2if and only if there existsS′⊆\[m\]S^\{\\prime\}\\subseteq\[m\]such thatV​\(S′\)=1V\(S^\{\\prime\}\)=1\.

Combining the above lemma and \([49](https://arxiv.org/html/2607.09817#A1.E49)\) implies thatm\+2∉S∗m\+2\\notin S^\{\*\}andm\+1∈S∗m\+1\\in S^\{\*\}\. The partition problem has a solution if and only if there exists an assortment with expected revenue75/3775/37\. Suppose that there is a solution to the partition problem, then there existsS′⊆\[m\]S^\{\\prime\}\\subseteq\[m\]such that∑i∈S′ciT=1\\sum\_\{i\\in S^\{\\prime\}\}\\frac\{c\_\{i\}\}\{T\}=1, so the expected revenue is75/3775/37\. On the other hand, if there is no solution to the partition problem, then for anyS′⊆\[m\]S^\{\\prime\}\\subseteq\[m\], the expected revenue using the assortmentS′∪\{m\+1\}S^\{\\prime\}\\cup\\\{m\+1\\\}is strictly less than75/3775/37\. ∎

###### Theorem A\.9\.

There exists an algorithm for \([TCAO](https://arxiv.org/html/2607.09817#S2.Ex3)\) under MC that takes time polynomial ink\!k\!,nn, and the encoding length ofλ,ρ,r\\lambda,\\rho,r, and𝒟\\mathcal\{D\}\. Ifk\!∈poly⁡\(n\)k\!\\in\\operatorname\{poly\}\(n\), then \([TCAO](https://arxiv.org/html/2607.09817#S2.Ex3)\) under MC is polynomial\-time solvable\.

###### Proof\.

Given𝒟=\{\(jℓ,Sℓ\)∣ℓ∈\[k\]\}\\mathcal\{D\}=\\\{\(j\_\{\\ell\},S\_\{\\ell\}\)\\mid\\ell\\in\[k\]\\\}, we recall the closed\-form expression forπ𝒟​\(j,S\)\\pi\_\{\\mathcal\{D\}\}\(j,S\)whenS∼t𝒟S\\sim\_\{t\}\\mathcal\{D\}\. Then we adapt LP \([7](https://arxiv.org/html/2607.09817#S2.E7)\) to find the optimal assortmentS∗S^\{\*\}for \([TCAO](https://arxiv.org/html/2607.09817#S2.Ex3)\)\.

Recall thatAsσ:=∪ℓ=skSσ​\(ℓ\)¯A^\{\\sigma\}\_\{s\}:=\\overline\{\\cup\_\{\\ell=s\}^\{k\}S\_\{\\sigma\(\\ell\)\}\}, and from \([24](https://arxiv.org/html/2607.09817#S4.E24)\) that forσ∼r𝒟\\sigma\\sim\_\{r\}\\mathcal\{D\},

p𝒟​\(σ\):=∏s=1k−1Pr⁡\[jσ​\(s\)​⤳As\+1σ​jσ​\(s\+1\)\]p\_\{\\mathcal\{D\}\}\(\\sigma\):=\\prod\_\{s=1\}^\{k\-1\}\\Pr\[j\_\{\\sigma\(s\)\}\{\\overset\{A^\{\\sigma\}\_\{s\+1\}\}\{\\leadsto\}\}j\_\{\\sigma\(s\+1\)\}\]denotes the probability of having a random walk in the form ofjσ​\(1\)​⤳A2σ​jσ​\(2\)​⤳A3σ​…​⤳Akσ​jσ​\(k\)j\_\{\\sigma\(1\)\}\\overset\{A^\{\\sigma\}\_\{2\}\}\{\\leadsto\}j\_\{\\sigma\(2\)\}\\overset\{A^\{\\sigma\}\_\{3\}\}\{\\leadsto\}\.\.\.\\overset\{A^\{\\sigma\}\_\{k\}\}\{\\leadsto\}j\_\{\\sigma\(k\)\}after the first visit tojσ​\(1\)j\_\{\\sigma\}\(1\)\. Recall thatU:=∪ℓ∈\[k\]SℓU:=\\cup\_\{\\ell\\in\[k\]\}S\_\{\\ell\}\. From \([10](https://arxiv.org/html/2607.09817#S2.E10)\) and \([11](https://arxiv.org/html/2607.09817#S2.E11)\), we have that

π𝒟=∑ℓ∈\[k\]π​\(jℓ,U\)​\(∑σ∼r𝒟:σ​\(1\)=ℓp𝒟​\(σ\)\)\\pi\_\{\\mathcal\{D\}\}=\\sum\_\{\\ell\\in\[k\]\}\\pi\(j\_\{\\ell\},U\)\\left\(\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}:\\sigma\(1\)=\\ell\}p\_\{\\mathcal\{D\}\}\(\\sigma\)\\right\)\(51\)where the termπ​\(jℓ,U\)\\pi\(j\_\{\\ell\},U\)is the probability of having a prefix random walk until the first visit ofjℓj\_\{\\ell\}for someℓ∈\[k\]\\ell\\in\[k\], and the term∑σ∼r𝒟:σ​\(1\)=jℓp𝒟​\(σ\)\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}:\\sigma\(1\)=j\_\{\\ell\}\}p\_\{\\mathcal\{D\}\}\(\\sigma\)considers all possible suffix random walks\.

We consider three cases to computePr⁡\[ℰ𝒟∩ℰ​\(j,S\)\]\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}\}\\cap\\mathcal\{E\}\(j,S\)\]for anyS∼t𝒟S\\sim\_\{t\}\\mathcal\{D\}\. First, ifj∈S∖Uj\\in S\\setminus U, then the customer’s first visit toS∪US\\cup Uenters atjj\. After the first visit tojj, the customer continues the random walk fromjjtojℓj\_\{\\ell\}, through states inU¯\\overline\{U\}\. The remaining suffix, starting from the first visit ofjσ​\(1\)j\_\{\\sigma\(1\)\}, is consistent with someσ\\sigma, whereσ​\(1\)=ℓ\\sigma\(1\)=\\ellandσ∼r𝒟\\sigma\\sim\_\{r\}\\mathcal\{D\}, with probabilityp𝒟​\(σ\)p\_\{\\mathcal\{D\}\}\(\\sigma\)\. Therefore,

Pr⁡\[ℰ𝒟∩ℰ​\(j,S\)\]=π​\(j,S∪U\)​\(∑σ∼r𝒟Pr⁡\[j​⤳U¯​jσ​\(1\)\]​p𝒟​\(σ\)\)\.\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}\}\\cap\\mathcal\{E\}\(j,S\)\]=\\pi\(j,S\\cup U\)\\left\(\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}\}\\Pr\[j\\overset\{\\overline\{U\}\}\{\\leadsto\}j\_\{\\sigma\(1\)\}\]p\_\{\\mathcal\{D\}\}\(\\sigma\)\\right\)\.\(52\)Second, letJ=\{jℓ∣ℓ∈\[k\]\}J=\\\{j\_\{\\ell\}\\mid\\ell\\in\[k\]\\\}\. Ifj∈Jj\\in J, i\.e\.,j=jℓj=j\_\{\\ell\}for someℓ∈\[k\]\\ell\\in\[k\], then the customer’s first visit toS∪US\\cup Uenters atj=jℓj=j\_\{\\ell\}\. The remaining suffix, starting from the first visit tojℓj\_\{\\ell\}, is consistent with someσ\\sigma, whereσ​\(1\)=ℓ\\sigma\(1\)=\\ellandσ∼r𝒟\\sigma\\sim\_\{r\}\\mathcal\{D\}, with probabilityp𝒟​\(σ\)p\_\{\\mathcal\{D\}\}\(\\sigma\)\. Therefore,

Pr⁡\[ℰ𝒟∩ℰ​\(j,S\)\]=π​\(j,S∪U\)​\(∑σ∼r𝒟:σ​\(1\)=ℓp𝒟​\(σ\)\)\.\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}\}\\cap\\mathcal\{E\}\(j,S\)\]=\\pi\(j,S\\cup U\)\\left\(\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}:\\sigma\(1\)=\\ell\}p\_\{\\mathcal\{D\}\}\(\\sigma\)\\right\)\.\(53\)Finally, ifj∈S∩\(U∖J\)j\\in S\\cap\(U\\setminus J\), thenPr⁡\[ℰ𝒟∩ℰ​\(j,S\)\]=0\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}\}\\cap\\mathcal\{E\}\(j,S\)\]=0since there exists a more preferred product inS∩JS\\cap J\.

From \([2](https://arxiv.org/html/2607.09817#S2.E2)\), \([TCAO](https://arxiv.org/html/2607.09817#S2.Ex3)\) under MC is

maxS∼t𝒟​∑j∈SPr⁡\[ℰ𝒟∩ℰ​\(j,S\)\]π𝒟​rj\.\\max\_\{S\\sim\_\{t\}\\mathcal\{D\}\}\\sum\_\{j\\in S\}\\frac\{\\Pr\[\\mathcal\{E\}\_\{\\mathcal\{D\}\}\\cap\\mathcal\{E\}\(j,S\)\]\}\{\\pi\_\{\\mathcal\{D\}\}\}r\_\{j\}\.\(54\)Observe that in \([51](https://arxiv.org/html/2607.09817#A1.E51)\), \([52](https://arxiv.org/html/2607.09817#A1.E52)\), and \([53](https://arxiv.org/html/2607.09817#A1.E53)\), the termsπ𝒟\\pi\_\{\\mathcal\{D\}\},∑σ∼r𝒟Pr⁡\[j​⤳U¯​jσ​\(1\)\]​p𝒟​\(σ\)\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}\}\\Pr\[j\\overset\{\\overline\{U\}\}\{\\leadsto\}j\_\{\\sigma\(1\)\}\]p\_\{\\mathcal\{D\}\}\(\\sigma\), and∑σ∼r𝒟:σ​\(1\)=ℓp𝒟​\(σ\)\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}:\\sigma\(1\)=\\ell\}p\_\{\\mathcal\{D\}\}\(\\sigma\)are irrelevant toSS, only depend on𝒟\\mathcal\{D\}, and can be computed in time polynomial ink\!k\!andnn\. Let the*scaled*revenue of productjjbe

rj𝒟:=\{∑σ∼r𝒟Pr⁡\[j​⤳U¯​jσ​\(1\)\]​p𝒟​\(σ\)π𝒟​rjif​j∈U¯,∑σ∼r𝒟:σ​\(1\)=ℓp𝒟​\(σ\)π𝒟​rjif​j=jℓ​for some​ℓ∈\[k\],0otherwise\.r^\{\\mathcal\{D\}\}\_\{j\}:=\\begin\{cases\}\\mbox\{\\large$\\frac\{\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}\}\\Pr\[j\\overset\{\\overline\{U\}\}\{\\leadsto\}j\_\{\\sigma\(1\)\}\]p\_\{\\mathcal\{D\}\}\(\\sigma\)\}\{\\pi\_\{\\mathcal\{D\}\}\}$\}r\_\{j\}&\\text\{if \}j\\in\\overline\{U\},\\\\ \\mbox\{\\large$\\frac\{\\sum\_\{\\sigma\\sim\_\{r\}\\mathcal\{D\}:\\sigma\(1\)=\\ell\}p\_\{\\mathcal\{D\}\}\(\\sigma\)\}\{\\pi\_\{\\mathcal\{D\}\}\}$\}r\_\{j\}&\\text\{if \}j=j\_\{\\ell\}\\text\{ for some \}\\ell\\in\[k\],\\\\ 0&\\text\{otherwise\}\.\\end\{cases\}Then \([54](https://arxiv.org/html/2607.09817#A1.E54)\) can be written as

maxS∼t𝒟​∑j∈Sπ​\(j,S∪U\)​rj𝒟\.\\max\_\{S\\sim\_\{t\}\\mathcal\{D\}\}\\sum\_\{j\\in S\}\\pi\(j,S\\cup U\)r^\{\\mathcal\{D\}\}\_\{j\}\.\(55\)
Observe that \([55](https://arxiv.org/html/2607.09817#A1.E55)\) is in a form similar to \([TAO](https://arxiv.org/html/2607.09817#S2.Ex1)\)\. The main tweak while adapting LP \([7](https://arxiv.org/html/2607.09817#S2.E7)\) is that we can regard the transparent conditional assortment problem as if all the products inUUare included inSSwithout loss of optimality, because the chosen productjjis either fromS∖US\\setminus UorJJ, regardless of which products inU∖JU\\setminus Jare included inSS\. Therefore, we have the following LP formulation for \([55](https://arxiv.org/html/2607.09817#A1.E55)\):

ming\\displaystyle\\min\_\{g\}∑i∈\[n\]λi​gi\\displaystyle\\sum\_\{i\\in\[n\]\}\\lambda\_\{i\}g\_\{i\}subject togi≥ri𝒟\\displaystyle g\_\{i\}\\geq r^\{\\mathcal\{D\}\}\_\{i\}∀i∈\[n\],\\displaystyle\\forall i\\in\[n\],gi≥∑j∈\[n\]ρi​j​gj\\displaystyle g\_\{i\}\\geq\\sum\_\{j\\in\[n\]\}\\rho\_\{ij\}g\_\{j\}∀i∈U¯\.\\displaystyle\\forall i\\in\\overline\{U\}\.Similar to \([7](https://arxiv.org/html/2607.09817#S2.E7)\),gig\_\{i\}denotes the expected revenue obtained when the customer visits stateii\. Ifi∈Ui\\in U, then we may includeiiinSSwithout loss of optimality, sogi=ri𝒟g\_\{i\}=r^\{\\mathcal\{D\}\}\_\{i\}andiiis present in the first set of constraints but not the second\. Otherwise,gi=max⁡\{ri𝒟,∑i∈\[n\]ρi​j​gj\}g\_\{i\}=\\max\\\{r^\{\\mathcal\{D\}\}\_\{i\},\\sum\_\{i\\in\[n\]\}\\rho\_\{ij\}g\_\{j\}\\\}, i\.e\., the expected revenuegig\_\{i\}is eitherri𝒟r^\{\\mathcal\{D\}\}\_\{i\}from stateiior∑j∈\[n\]ρi​j​gj\\sum\_\{j\\in\[n\]\}\\rho\_\{ij\}g\_\{j\}by transitioning to other statesj∈\[n\]j\\in\[n\]\. Letg∗g^\{\*\}be the optimal solution, then offering\{i∣gi∗=ri𝒟\}\\\{i\\mid g^\{\*\}\_\{i\}=r^\{\\mathcal\{D\}\}\_\{i\}\\\}maximizes the expected revenue\. ∎