🤖 machine learning

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

This paper introduces a novel framework for Markov chain choice models with panel data that leverages partial-ordering preference information to develop superior EM algorithms for parameter estimation, while also establishing the computational complexity of personalized choice prediction and assortment optimization.

Original authors: Yalcin Akcay, Gerardo Berbeglia, Young-San Lin

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yalcin Akcay, Gerardo Berbeglia, Young-San Lin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out what a group of people really likes to eat. In the old days, detectives looked at a giant pile of receipts from a restaurant. They assumed every single order was a fresh, independent guess, like flipping a coin. If someone ordered sushi, then pizza, then a burger, the old math treated those three choices as three separate, unconnected events.

But here's the twist: people aren't coins. If a customer orders a spicy tuna roll, then later orders a spicy tuna roll again, that's a clue! It suggests they really like spicy tuna. This paper introduces a new way to look at these "receipts" (which the authors call panel data) by treating them as a connected story for each specific customer, rather than a random pile of paper.

The New Detective Tool: The Markov Chain

The authors propose using a specific math tool called a Markov Chain (MC) choice model. Think of this model as a "preference map." Instead of just saying "I like sushi," the model maps out a journey. It asks: "If I'm currently thinking about sushi, what am I likely to think about next? Do I jump to sashimi, or do I give up and order a soda?"

The big discovery in this paper is that when you have a customer's history (their panel data), this "journey" map becomes much easier to draw accurately. The authors ran simulations (computer experiments) and tested their method on a real-world dataset of 5,000 people's sushi preferences. They found that by using the customer's history to update the map, their new algorithms (Cus and Hyb) were much better at guessing what people would buy next compared to the old methods.

What the Old Methods Got Wrong

The paper explicitly argues against the idea that you can just ignore the connection between a single customer's past orders.

The "Independent" Myth: The authors show that if you treat every order as a totally new, random event (the traditional way), you miss out on the "partial ordering" of preferences. It's like trying to guess a person's favorite movie by looking at a random list of movies they watched, without realizing they watched all the sequels in order.
The MNL Trap: There is a very popular, simpler model called the Multinomial Logit (MNL). The paper proves that for this specific model, looking at a customer's history does not help you figure out the general population's preferences any better than just looking at the total pile of receipts. However, for the Markov Chain model they are using, the history does make a huge difference. It's like saying: "For some types of riddles, looking at the clues in order helps; for others, it doesn't."

The "Hybrid" Detective

The authors also created a "hybrid" detective tool called Hyb. In the real world, sometimes a customer's history is messy. Maybe they ordered a burger, then a salad, then a burger again in a way that doesn't make a perfect logical line (a "cycle").

The Cus algorithm is strict: it only works if the customer's history forms a perfect, logical line of preference.
The Hyb algorithm is flexible: it takes the messy, non-linear parts of the history and treats them as "independent" data points, while keeping the clean, logical parts as a connected story. This allows the model to use all the data without getting confused by the messy bits.

How Well Did It Work?

The authors didn't just guess; they measured it.

The Setup: They created 2,000 different test scenarios using synthetic data (fake customers) and also tested on the sushi dataset involving 5,000 individuals.
The Results: In their simulations, the new methods (Cus and Hyb) consistently beat the old methods.
- When the data was small (only 100 customers), the new methods were significantly better at predicting what people would buy.
- As the number of customers grew to 2,000, the new methods continued to outperform the old ones, especially in predicting specific customer choices.
- In terms of money (revenue), the new methods helped retailers make better decisions on which items to display. For example, in the sushi tests, the new models achieved nearly 100% of the possible maximum revenue in many cases, whereas the older models lagged behind.

The Bottom Line

This paper suggests that if you want to understand how people choose things, you shouldn't just look at the "what" (the product); you should look at the "story" (the history). By treating a customer's past choices as a connected journey rather than random events, you can build a much sharper map of their preferences. The authors found that this approach works best when using the Markov Chain model, turning a messy pile of receipts into a clear, personalized guide for what customers will want next.

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

Problem Statement

Traditional assortment planning relies on choice models where historical transactions are assumed to be independent and identically distributed (i.i.d.) draws from a random utility model (RUM). This framework utilizes unconditional choice probabilities, ignoring correlations between transactions made by the same customer. However, the availability of panel data (detailed individual transaction histories) challenges this independence assumption.

The paper addresses three core problems in the context of the Markov Chain (MC) choice model using panel data:

Parameter Estimation: How to estimate MC parameters by incorporating customer-specific historical transaction information (partial-ordering preferences) rather than treating transactions as independent.
Conditional Choice Prediction: How to compute the probability of a customer choosing a product from an offer set, conditional on their specific past transaction history.
Assortment Optimization: How to determine the optimal set of products to offer a specific customer (conditional assortment optimization) to maximize expected revenue, given their history.

The authors investigate whether exploiting individual transaction information improves population-level estimation for MC models compared to Multinomial Logit (MNL) models and traditional estimation methods.

Methodology

Theoretical Framework

The authors formalize the problem using partial-ordering preference information. A customer's transaction history $D_c$ is represented as a Directed Acyclic Graph (DAG) where arcs indicate pairwise preferences derived from observed choices.

Conditional Probability: The probability of a choice $j$ from set $S$ , given history $D$ , is derived using reduced linear extensions (strict rankings consistent with the observed DAG).
MC vs. MNL: The paper establishes a theoretical gap between MC and MNL. Under MNL, panel data does not add identification power for parameters if population choice probabilities are known. In contrast, for MC, customer-level information significantly improves parameter identifiability, particularly when the set of observed assortments is limited.

Algorithms: Expectation-Maximization (EM)

The primary contribution is the development of novel EM algorithms to estimate MC parameters ( $\lambda$ for initial states, $\rho$ for transition probabilities) using panel data.

Algorithm Cus (Customer-specific):
- Assumption: Each customer's transaction set is consistent with at least one strict preference list (no cycles).
- Mechanism: The algorithm treats the customer's underlying strict preference (represented as a reduced linear extension $\sigma$ ) and their initial state as latent variables.
- E-Step: Computes the expected values of latent variables (initial state indicators and transition counts) conditional on the observed DAG and current parameter estimates. This involves calculating probabilities of random walks consistent with the reduced linear extensions.
- M-Step: Updates parameters $\lambda$ and $\rho$ by maximizing the expected complete-data log-likelihood, resulting in closed-form solutions based on the expected counts.
Algorithm Hyb (Hybrid):
- Motivation: Real-world data may contain cyclic preferences or inconsistent transactions that violate a strict DAG.
- Mechanism: Hyb combines the Cus algorithm (for transactions consistent with a DAG) and the traditional EM algorithm (for independent transactions).
- Flexibility: It allows "violating" transactions (those causing cycles) to be treated as independent observations in the traditional likelihood component, rather than discarding them entirely. This captures information about the unconditional population distribution while still leveraging the DAG structure for consistent histories.

Computational Complexity

The paper presents hardness results for conditional choice prediction and assortment optimization. While traditional assortment optimization under MC is solvable in polynomial time, the conditional versions (CAO and TCAO) are shown to be computationally challenging. However, the authors provide closed-form expressions for conditional choice probabilities under MC, reducing the computational burden compared to general RUMs.

Key Contributions

Initiation of MC Panel Data Study: To the best of the authors' knowledge, this is the first framework to study choice modeling with panel data specifically under the Markov Chain model.
Novel EM Algorithms: The proposal of Cus and Hyb algorithms that incorporate partial-ordering-based customer preference information. These algorithms outperform the traditional EM algorithm for MC (S¸im¸sek and Topaloglu, 2018) and MNL-based partial-order benchmarks (Jagabathula and Vulcano, 2018).
Theoretical Identification Gap: A demonstration that while MNL parameters can be identified without linking transactions to specific customers (given sufficient assortment data), MC parameters benefit significantly from panel data, especially in scenarios with limited assortment observations.
Computational Landscape: A clarification of the computational hardness and tractability for conditional choice prediction and assortment optimization under MC and MNL, complementing the estimation framework.

Experimental Results

The authors evaluated their methods on synthetic datasets and a semi-synthetic dataset derived from the sushi preference data (5,000 individuals).

Performance Metrics: The study used Soft Root Mean Square Error (RMSE) for predictive accuracy and Revenue Ratios for decision-making performance.
Synthetic Data:
- The proposed Cus-MC and Hyb-MC models consistently outperformed traditional MC estimation, MNL, and Latent-Class MNL (LC-MNL) variants, particularly as the number of customers increased.
- The improvement was most pronounced when the ground truth distribution was concentrated on a smaller number of preference lists (e.g., Rank List with 10 lists or Mallows with high concentration).
- Panel data incorporation yielded greater improvement margins for MC estimation compared to MNL estimation, especially with smaller data sizes.
Sushi Data:
- MC-based models generally outperformed MNL-based models in revenue ratios and predictive accuracy.
- Hyb-MC and Cus-MC achieved near-optimal expected revenue in most scenarios.
- An exception was noted in the "Top 5" truncation scenario where conditional revenue performance degraded with larger data sizes, suggesting that limited transaction depth (fewer top choices observed) may restrict the ability to fit complex MC structures using panel data alone.

Significance and Claims

The paper claims that customer-level information is more valuable for Markov Chain estimation than for MNL estimation. By systematically leveraging correlations in individual transaction histories, the proposed framework enhances both predictive accuracy and assortment optimization performance.

The authors position their work as a foundational step, noting that:

The framework bridges the gap between traditional independent transaction models and the reality of correlated customer behavior.
The Hyb algorithm offers a practical heuristic for real-world datasets where preferences may be cyclic, allowing for the retention of information that would otherwise be discarded by strict DAG-based heuristics.
Future work involves testing these algorithms on real-world data with cyclic preferences and extending the framework to other classes of Random Utility Models.

The paper maintains a modest tone regarding its claims, acknowledging that while synthetic results are strong, real-world validation (particularly regarding cyclic preferences) remains a necessary future direction. It does not claim universal superiority over all models in all contexts but highlights specific conditions (MC models, limited assortments, panel data availability) where the proposed methods offer distinct advantages.