Pith. sign in

REVIEW 2 major objections 4 minor 42 references

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

T0 review · 2 major / 4 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Markov-chain choice models gain accuracy when customer transaction histories are treated as partial rankings rather than independent draws.

desk verdict First clean panel-data EM for Markov-chain choice models, with real gains over Şimşek–Topaloglu and partial-order MNL on the usual synthetic/sushi setups; fixed-ranking premise is the only real soft spot. read the letter →

arxiv 2607.09817 v1 pith:IOAXN3Z4 submitted 2026-07-10 cs.LG stat.ML

Yalcin Akcay , Gerardo Berbeglia , Young-San Lin This is my paper
classification cs.LGstat.ML
keywords Markovchainchoicemodelpaneldataexpectation-maximizationpartialorderassortmentoptimizationconditionalprobabilityreducedlinearextension
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Retailers now observe repeated purchases by the same customer, so successive choices are correlated. This paper shows that the Markov-chain choice model can exploit those correlations: each customer's history is turned into a partial ranking (a directed acyclic graph of revealed preferences), and new EM algorithms maximize the likelihood of those rankings. On synthetic data and sushi preference lists the resulting models improve both population-level and personalized choice predictions relative to the classical independent-transaction EM and to partial-order multinomial-logit estimators. The same conditional probabilities also support personalized assortment optimization; the paper maps the computational cost of those problems and isolates the cases that remain tractable. The practical message is that customer-level panel data is more valuable for Markov-chain models than for multinomial logit, and that the gain is available with algorithms that stay practical at moderate history lengths.

What carries the argument

The complete-data likelihood that factors a customer's random walk into an initial-state indicator and successive transition counts along each reduced linear extension consistent with the observed partial order; the EM algorithm replaces those latent counts by their conditional expectations given the current parameters.

What would settle it

On a panel data set whose customers exhibit genuine preference drift or irreducible cycles, re-run Cus/Hyb after cycle-removal heuristics and check whether soft RMSE and conditional revenue ratios still improve over the independent-transaction MC-EM baseline.

Watch

Extended reading notes

Core claim

Expectation-maximization algorithms that treat each customer's transaction history as a partial ranking (equivalently, a reduced linear extension of a DAG) recover Markov-chain parameters more accurately than the classical independent-transaction EM, improving both unconditional and conditional soft RMSE and revenue ratios on the synthetic and sushi instances examined.

Load-bearing premise

Each customer's observed purchases are generated by a single fixed strict ranking drawn once from the population model (or can be made acyclic by a preprocessing step that treats leftover transactions as independent).

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper develops a panel-data framework for the Markov chain (MC) choice model. It treats each customer’s transaction history as a partial order (equivalently a reduced DAG) and proposes two EM algorithms, Cus and Hyb, that maximize the likelihood of these partial orders rather than treating transactions as independent. Cus assumes every history is acyclic; Hyb mixes preference-consistent histories with an independent-transaction set. On synthetic Rank-List / Mallows-based Rank-List instances and a semi-synthetic sushi construction, both algorithms improve soft RMSE and revenue ratios relative to the independent-transaction MC-EM of Şimşek & Topaloglu (2018) and partial-order MNL estimators adapted from Jagabathula & Vulcano (2018). A secondary contribution supplies #P-hardness of transaction probabilities under MNL, an FPRAS when attraction ratios are polynomial, NP-hardness of conditional assortment optimization even for a single transaction, and a polynomial-time LP for transparent conditional assortment optimization under MC when the number of observed products per customer is small.

Significance. If the fixed-ranking premise holds, the work supplies the first systematic estimation, prediction and assortment pipeline for MC under panel data and demonstrates that customer-level partial-order information can improve both population-level parameter recovery and personalized decisions. The closed-form E-step expressions (25)–(26), the hybrid construction that re-uses discarded arcs, the hardness reductions, and the transparent-CAO LP are concrete technical contributions that clarify the computational landscape of conditional choice under MC/MNL. The experimental design (100 replications, nested customer counts, both predictive and revenue metrics) is careful and the reported gains are coherent with the identification gap between MNL and MC established in Section 3.

major comments (2)
  1. The complete-data likelihood (22) and the E-step closed forms (25)–(26) rest on the premise that each customer is generated by a single fixed strict ranking (or that cycles can be cleanly separated into a DAG plus independent transactions). Section 6 flags real-data cycles as future work, yet the empirical claims are stated for “panel data” without quantifying sensitivity to ranking drift or imperfect cycle removal. A controlled experiment that injects preference drift or noisy cycle-removal heuristics and reports the degradation of Cus/Hyb relative to independent-transaction MC-EM would make the scope of the gains precise.
  2. In the sushi experiments (Figures 8–9) the conditional revenue ratio of Hyb-Mc and Cus-Mc deteriorates with sample size under the top-5 truncation, while soft RMSE continues to improve. The text offers only a brief conjecture (“lack of information to fit an MC”). Because conditional revenue is a primary decision metric, a short diagnostic (e.g., how often the estimated conditional assortment differs from the ground-truth conditional assortment, or the effect of the transparent constraint) is needed to confirm that the predictive gains translate into reliable assortment decisions.
minor comments (4)
  1. Notation for reduced versus complete linear extensions (σ ∼ r D versus σ ∼ c D) is introduced late; a short glossary or consistent superscript would help readers of Sections 2.2.3 and 4.
  2. Table 2 reports average number of reduced linear extensions but does not state the maximum observed; a column for max #RLE would clarify the practical scale of the E-step enumeration.
  3. The selection of the number of latent classes ℓ for LC-MNL / LC-POMNL uses ground-truth soft RMSE. A footnote already notes that validation log-likelihood should be used in practice; elevating this remark into the main text would avoid any appearance of oracle model selection.
  4. Minor typos: “S ¸imşek” appears with inconsistent spacing; “T ransactions” in the heading of 2.2.3; arXiv date July 2026 is presumably a placeholder.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: EM maximizes an explicit panel-data likelihood of reduced linear extensions; soft-RMSE and revenue ratios are evaluated against independently generated ground-truth models or public sushi rankings.

full rationale

The derivation chain is self-contained and non-circular. Section 3 defines the panel log-likelihood L_cus as the sum of log π_Dc over customers, where π_Dc is the MC probability of the observed reduced linear extensions (closed forms (10)–(11)); the traditional independent-transaction likelihood L_trad is the usual product of single-transaction probabilities. The EM algorithms Cus/Hyb (Section 4) construct a complete-data likelihood (22) whose latent variables are the unobserved random-walk prefixes and inter-arrival segments consistent with those extensions, then iterate standard E-step expectations (25)–(26) and closed-form multinomial M-steps. This is ordinary incomplete-data maximum likelihood, not a definitional loop. The theoretical gap between MNL and MC (Proposition 3.1 vs. the n=2 identification example) follows from the respective closed forms and does not import a uniqueness theorem from the authors. Hardness results (Theorems A.1–A.2, A.7) are independent reductions from counting linear extensions and PARTITION. Empirical claims compare estimated models to independently sampled Rank-List/Mallows ground truths and the public sushi preference lists via soft RMSE (32)–(33) and revenue ratios (34); no fitted constant is renamed a prediction. Self-citations are only to algorithmic baselines (ŞT18, JV18) used for comparison, not load-bearing premises. The sole modeling premise (fixed strict ranking per customer, or cycle-to-independent-transaction separation) is an assumption, not a circular reduction. Score 1 reflects only the ordinary presence of self-citations that are not load-bearing.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claims rest on the standard Markov-chain choice model, the modeling decision that each customer draws a single fixed ranking, and the technical assumption that the transition sub-matrix on non-offered products has spectral radius less than one. No new physical entities are postulated; free parameters are the usual MC parameters estimated by EM and the number of latent classes chosen for the MNL baselines.

free parameters (3)
  • MC initial vector λ and transition matrix ρ
    Estimated by the EM algorithms; the reported performance gains are relative to other estimators of the same parameters.
  • number of latent classes ℓ for LC-MNL / LC-POMNL
    Selected by lowest average soft RMSE against the known ground truth (Section 5.3); used only for the synthetic benchmarks.
  • Mallows concentration κ and Rank-List probabilities
    Hand-chosen ground-truth generators (κ ∈ {0.4,0.7}, 10 or 100 lists) that define the synthetic data.
assumptions (4)
  • domain assumption Each customer possesses a single fixed strict ranking over products that is consistent with all of her observed transactions (or can be made acyclic by arc deletion).
    Stated in Section 2.1 and used to define the reduced DAG and the complete-data likelihood (22).
  • domain assumption The spectral radius of ρ([n],[n]) is strictly less than one, guaranteeing that (I−ρ(S̄,S̄)) is invertible.
    Invoked after equation (5) to ensure unique choice probabilities.
  • domain assumption Customers are drawn independently; transactions of distinct customers are independent.
    Used to write the panel log-likelihood as a sum over customers (14).
  • standard math Counting linear extensions of a DAG is #P-complete (Brightwell–Winkler).
    Used in the hardness reduction of Theorem A.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Estimation, Prediction, and Assortment Optimization for Markov Chain Choice Models with Panel Data." pith.science (2026). https://pith.science/paper/IOAXN3Z4

@misc{pith2026260709817,
  author       = {Pith},
  title        = {Pith review of: Estimation, Prediction, and Assortment Optimization for Markov Chain Choice Models with Panel Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IOAXN3Z4}},
  note         = {Machine review of arXiv:2607.09817}
}
read the original 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 Simsek 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.

Figures

Figures reproduced from arXiv: 2607.09817 by the authors.

Figure 1
Figure 1. The DAG for D 2A linear extension is also called a topological ordering. 5 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. The reduced DAG for D 3 The Value of Panel Information In this section, we investigate the value of using panel data while estimating a choice model. In Section 3.1, we present the log-likelihood functions, which measure the performance of choice model parameter estimation. In Section 3.2, we provide an example that highlights how exploiting individual transaction information can improve MC parameter estimation. In … view at source ↗
Figure 3
Figure 3. The ground truth MC and the parameters to be determined. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: RL-10 Ground Truth 100 250 500 1000 2000 # customers MNL POMNL LC-MNL LC-POMNL MC Hyb-MC Cus-MC model 0.048 0.035 0.029 0.026 0.024 0.046 0.034 0.029 0.026 0.025 0.048 0.035 0.029 0.026 0.024 0.048 0.035 0.029 0.026 0.024 0.073 0.051 0.039 0.030 0.023 0.065 0.043 0.031…
Figure 5
Figure 5. Figure 5: RL-100 Ground Truth 23 [PITH_FULL_IMAGE:figures/full_fig_p023_5.png]
Figure 6
Figure 6. Figure 6: MRL-0.4 Ground Truth 100 250 500 1000 2000 # customers MNL POMNL LC-MNL LC-POMNL MC Hyb-MC Cus-MC model 0.049 0.037 0.034 0.031 0.030 0.051 0.043 0.040 0.037 0.037 0.049 0.037 0.034 0.031 0.030 0.049 0.038 0.034 0.031 0.030 0.061 0.041 0.031 0.023 0.017 0.056 0.036 0.0…
Figure 7
Figure 7. Figure 7: MRL-0.7 Ground Truth 24 [PITH_FULL_IMAGE:figures/full_fig_p024_7.png]
Figure 8
Figure 8. Figure 8: Top 5 Ground Truth 100 250 500 1000 2000 # customers MNL POMNL LC-MNL LC-POMNL MC Hyb-MC Cus-MC model 0.063 0.056 0.054 0.053 0.053 0.080 0.076 0.075 0.074 0.074 0.063 0.056 0.054 0.053 0.053 0.064 0.057 0.055 0.053 0.053 0.056 0.039 0.029 0.022 0.017 0.058 0.036 0.028…
Figure 9
Figure 9. Figure 9: Top 7 Ground Truth 26 [PITH_FULL_IMAGE:figures/full_fig_p026_9.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

42 extracted references

  1. [1]

    Operations Research , volume=

    Personalized retail promotions through a directed acyclic graph--based representation of customer preferences , author=. Operations Research , volume=. 2022 , publisher=

    2022

  2. [2]

    Blanchet, Jose and Gallego, Guillermo and Goyal, Vineet , journal=. A. 2016 , publisher=

    2016

  3. [3]

    Management Science , volume=

    A comparative empirical study of discrete choice models in retail operations , author=. Management Science , volume=. 2022 , publisher=

    2022

  4. [4]

    Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages=

    Nantonac collaborative filtering: recommendation based on order responses , author=. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages=

  5. [5]

    and Topaloglu, Huseyin , journal=

    Feldman, Jacob B. and Topaloglu, Huseyin , journal=. Revenue management under the. 2017 , publisher=

    2017

  6. [6]

    2014 , publisher=

    Markov decision processes: discrete stochastic dynamic programming , author=. 2014 , publisher=

    2014

  7. [7]

    Available at SSRN 3567371 , year=

    Managing flexible products on a network , author=. Available at SSRN 3567371 , year=

  8. [8]

    Management Science , volume=

    Revenue management under a general discrete choice model of consumer behavior , author=. Management Science , volume=. 2004 , publisher=

    2004

Show all 42 references
  1. [9]

    Journal of Econometrics , volume=

    Assessing the potential demand for electric cars , author=. Journal of Econometrics , volume=. 1981 , publisher=

    1981

  2. [10]

    Available at SSRN 4526247 , year=

    Assortment optimization for the multinomial logit model with repeated customer interactions , author=. Available at SSRN 4526247 , year=

  3. [11]

    Operations Research , volume=

    An expectation-maximization algorithm to estimate the parameters of the. Operations Research , volume=. 2018 , publisher=

    2018

  4. [12]

    Convergence properties of the

    Nettleton, Dan , journal=. Convergence properties of the. 1999 , publisher=

    1999

  5. [13]

    Pattern recognition and machine learning , author=

  6. [14]

    The Complete Journey , howpublished =

  7. [15]

    50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art , pages=

    Reducibility among combinatorial problems , author=. 50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art , pages=. 2009 , publisher=

    1958

  8. [16]

    Counting linear extensions is \#

    Brightwell, Graham and Winkler, Peter , booktitle=. Counting linear extensions is \#

  9. [17]

    Available at SSRN 3934096 , year=

    Bounds, heuristics, and prophet inequalities for assortment optimization , author=. Available at SSRN 3934096 , year=

  10. [18]

    Economic Information, Decision, and Prediction: Selected Essays: Volume I Part I Economics of Decision , pages=

    Random orderings and stochastic theories of responses (1960) , author=. Economic Information, Decision, and Prediction: Selected Essays: Volume I Part I Economics of Decision , pages=. 1974 , publisher=

    1960

  11. [19]

    Constrained assortment optimization under the

    D. Constrained assortment optimization under the. Management Science , volume=. 2020 , publisher=

    2020

  12. [20]

    Operations Research , volume=

    Capacitated assortment optimization: Hardness and approximation , author=. Operations Research , volume=. 2022 , publisher=

    2022

  13. [21]

    the method of paired comparisons , author=

    Rank analysis of incomplete block designs: I. the method of paired comparisons , author=. Biometrika , volume=. 1952 , publisher=

    1952

  14. [22]

    Frontiers in Econometrics , year=

    Conditional Logit Analysis of Qualitative Choice Behavior , author=. Frontiers in Econometrics , year=

  15. [23]

    1959 , publisher=

    Individual choice behavior: A Theoretical Analysis , author=. 1959 , publisher=

    1959

  16. [24]

    Journal of the Royal Statistical Society Series C: Applied Statistics , volume=

    The analysis of permutations , author=. Journal of the Royal Statistical Society Series C: Applied Statistics , volume=. 1975 , publisher=

    1975

  17. [25]

    Management Science , volume=

    A partial-order-based model to estimate individual preferences using panel data , author=. Management Science , volume=. 2018 , publisher=

    2018

  18. [26]

    Operations Research Letters , volume=

    Discrete choice models based on random walks , author=. Operations Research Letters , volume=. 2016 , publisher=

    2016

  19. [27]

    and Laird, Nan M

    Dempster, Arthur P. and Laird, Nan M. and Rubin, Donald B. , journal=. Maximum likelihood from incomplete data via the. 1977 , publisher=

    1977

  20. [28]

    , journal=

    Train, Kenneth E. , journal=. 2008 , publisher=

    2008

  21. [29]

    Operations Research , volume=

    Estimating primary demand for substitutable products from sales transaction data , author=. Operations Research , volume=. 2012 , publisher=

    2012

  22. [30]

    Management Science , volume=

    A market discovery algorithm to estimate a general class of nonparametric choice models , author=. Management Science , volume=. 2015 , publisher=

    2015

  23. [31]

    Operations Research , volume=

    An expectation-maximization method to estimate a rank-based choice model of demand , author=. Operations Research , volume=. 2017 , publisher=

    2017

  24. [32]

    Management Science , volume=

    A nonparametric joint assortment and price choice model , author=. Management Science , volume=. 2017 , publisher=

    2017

  25. [33]

    Marketing Science , volume=

    Estimation of consumer demand with stock-out based substitution: An application to vending machine products , author=. Marketing Science , volume=. 1998 , publisher=

    1998

  26. [34]

    Operations Research , volume=

    Demand estimation and assortment optimization under substitution: Methodology and application , author=. Operations Research , volume=. 2007 , publisher=

    2007

  27. [35]

    American Economic Journal: Microeconomics , volume=

    Demand estimation under incomplete product availability , author=. American Economic Journal: Microeconomics , volume=. 2013 , publisher=

    2013

  28. [36]

    Available at SSRN 1334353 , year=

    Multivariate customer demand: modeling and estimation from censored sales , author=. Available at SSRN 1334353 , year=

  29. [37]

    Robust assortment optimization under the

    D. Robust assortment optimization under the. Operations Research , volume=. 2024 , publisher=

    2024

  30. [38]

    Online learning for constrained assortment optimization under

    Li, Shukai and Luo, Qi and Huang, Zhiyuan and Shi, Cong , journal=. Online learning for constrained assortment optimization under. 2025 , publisher=

    2025

  31. [39]

    Parameter identification in

    Gupta, Arushi and Hsu, Daniel , journal=. Parameter identification in. 2020 , publisher=

    2020

  32. [40]

    , journal=

    Mallows, Colin L. , journal=. Non-null ranking models. 1957 , publisher=

    1957

  33. [41]

    Assortment optimization under the

    D. Assortment optimization under the. Advances in Neural Information Processing Systems , volume=. 2016 , pages=

    2016

  34. [42]

    2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) , pages=

    Fast algorithms for log-concave functions: sampling, rounding, integration and optimization , author=. 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) , pages=. 2006 , organization=

    2006

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.