IDEAS home Printed from https://ideas.repec.org/p/arx/papers/1911.06716.html

A Generalized Markov Chain Model to Capture Dynamic Preferences and Choice Overload

Author

Listed:
  • Kumar Goutam
  • Vineet Goyal
  • Agathe Soret

Abstract

Assortment optimization is an important problem that arises in many industries such as retailing and online advertising where the goal is to find a subset of products from a universe of substitutable products which maximize seller's expected revenue. One of the key challenges in this problem is to model the customer substitution behavior. Many parametric random utility maximization (RUM) based choice models have been considered in the literature. However, in all these models, probability of purchase increases as we include more products to an assortment. This is not true in general and in many settings more choices hurt sales. This is commonly referred to as the choice overload. In this paper we attempt to address this limitation in RUM through a generalization of the Markov chain based choice model considered in Blanchet et al. (2016). As a special case, we show that our model reduces to a generalization of MNL with no-purchase attractions dependent on the assortment S and strictly increasing with the size of assortment S. While we show that the assortment optimization under this model is NP-hard, we present fully polynomial-time approximation scheme (FPTAS) under reasonable assumptions.

Suggested Citation

  • Kumar Goutam & Vineet Goyal & Agathe Soret, 2019. "A Generalized Markov Chain Model to Capture Dynamic Preferences and Choice Overload," Papers 1911.06716, arXiv.org, revised Dec 2020.
    • Handle: RePEc:arx:papers:1911.06716
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/1911.06716
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Paat Rusmevichientong & David Shmoys & Chaoxu Tong & Huseyin Topaloglu, 2014. "Assortment Optimization under the Multinomial Logit Model with Random Choice Parameters," Production and Operations Management, Production and Operations Management Society, vol. 23(11), pages 2023-2039, November.
    2. Vivek F. Farias & Srikanth Jagabathula & Devavrat Shah, 2013. "A Nonparametric Approach to Modeling Choice with Limited Data," Management Science, INFORMS, vol. 59(2), pages 305-322, December.
    3. Benjamin Scheibehenne & Rainer Greifeneder & Peter M. Todd, 2010. "Can There Ever Be Too Many Options? A Meta-Analytic Review of Choice Overload," Journal of Consumer Research, Journal of Consumer Research Inc., vol. 37(3), pages 409-425, October.
    4. Kalyan Talluri & Garrett van Ryzin, 2004. "Revenue Management Under a General Discrete Choice Model of Consumer Behavior," Management Science, INFORMS, vol. 50(1), pages 15-33, January.
    5. James M. Davis & Guillermo Gallego & Huseyin Topaloglu, 2014. "Assortment Optimization Under Variants of the Nested Logit Model," Operations Research, INFORMS, vol. 62(2), pages 250-273, April.
    6. Dan Zhang & William L. Cooper, 2005. "Revenue Management for Parallel Flights with Customer-Choice Behavior," Operations Research, INFORMS, vol. 53(3), pages 415-431, June.
    7. R. L. Plackett, 1975. "The Analysis of Permutations," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 24(2), pages 193-202, June.
    8. Jose Blanchet & Guillermo Gallego & Vineet Goyal, 2016. "A Markov Chain Approximation to Choice Modeling," Operations Research, INFORMS, vol. 64(4), pages 886-905, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Antoine Désir & Vineet Goyal & Danny Segev & Chun Ye, 2020. "Constrained Assortment Optimization Under the Markov Chain–based Choice Model," Management Science, INFORMS, vol. 66(2), pages 698-721, February.
    2. Zhengchao Wang & Heikki Peura & Wolfram Wiesemann, 2024. "Randomized Assortment Optimization," Operations Research, INFORMS, vol. 72(5), pages 2042-2060, September.
    3. Antoine Désir & Vineet Goyal & Bo Jiang & Tian Xie & Jiawei Zhang, 2024. "Robust Assortment Optimization Under the Markov Chain Choice Model," Operations Research, INFORMS, vol. 72(4), pages 1595-1614, July.
    4. Ali Aouad & Danny Segev, 2021. "Display Optimization for Vertically Differentiated Locations Under Multinomial Logit Preferences," Management Science, INFORMS, vol. 67(6), pages 3519-3550, June.
    5. Yicheng Bai & Jacob Feldman & Danny Segev & Huseyin Topaloglu & Laura Wagner, 2024. "Assortment Optimization Under the Multi-Purchase Multinomial Logit Choice Model," Operations Research, INFORMS, vol. 72(6), pages 2631-2664, November.
    6. Antoine Désir & Vineet Goyal & Jiawei Zhang, 2022. "Technical Note—Capacitated Assortment Optimization: Hardness and Approximation," Operations Research, INFORMS, vol. 70(2), pages 893-904, March.
    7. Strauss, Arne K. & Klein, Robert & Steinhardt, Claudius, 2018. "A review of choice-based revenue management: Theory and methods," European Journal of Operational Research, Elsevier, vol. 271(2), pages 375-387.
    8. Yufeng Cao & Paat Rusmevichientong & Huseyin Topaloglu, 2023. "Revenue Management Under a Mixture of Independent Demand and Multinomial Logit Models," Operations Research, INFORMS, vol. 71(2), pages 603-625, March.
    9. Kameng Nip & Zhenbo Wang & Zizhuo Wang, 2021. "Assortment Optimization under a Single Transition Choice Model," Production and Operations Management, Production and Operations Management Society, vol. 30(7), pages 2122-2142, July.
    10. Shipra Agrawal & Vashist Avadhanula & Vineet Goyal & Assaf Zeevi, 2019. "MNL-Bandit: A Dynamic Learning Approach to Assortment Selection," Operations Research, INFORMS, vol. 67(5), pages 1453-1485, September.
    11. Dimitris Bertsimas & Velibor V. Mišić, 2019. "Exact First-Choice Product Line Optimization," Operations Research, INFORMS, vol. 67(3), pages 651-670, May.
    12. Omar El Housni & Marouane Ibn Brahim & Danny Segev, 2026. "Maximum Load Assortment Optimization: Approximation Algorithms and Adaptivity Gaps," Operations Research, INFORMS, vol. 74(1), pages 408-429, January.
    13. Pin Gao & Yuhang Ma & Ningyuan Chen & Guillermo Gallego & Anran Li & Paat Rusmevichientong & Huseyin Topaloglu, 2021. "Assortment Optimization and Pricing Under the Multinomial Logit Model with Impatient Customers: Sequential Recommendation and Selection," Operations Research, INFORMS, vol. 69(5), pages 1509-1532, September.
    14. Ali Aouad & Danny Segev, 2023. "The Stability of MNL-Based Demand Under Dynamic Customer Substitution and Its Algorithmic Implications," Operations Research, INFORMS, vol. 71(4), pages 1216-1249, July.
    15. Meng Qi & Ho‐Yin Mak & Zuo‐Jun Max Shen, 2020. "Data‐driven research in retail operations—A review," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(8), pages 595-616, December.
    16. Jacob B. Feldman & Huseyin Topaloglu, 2017. "Revenue Management Under the Markov Chain Choice Model," Operations Research, INFORMS, vol. 65(5), pages 1322-1342, October.
    17. Flores, Alvaro & Berbeglia, Gerardo & Van Hentenryck, Pascal, 2019. "Assortment optimization under the Sequential Multinomial Logit Model," European Journal of Operational Research, Elsevier, vol. 273(3), pages 1052-1064.
    18. Guang Li & Paat Rusmevichientong & Huseyin Topaloglu, 2015. "The d -Level Nested Logit Model: Assortment and Price Optimization Problems," Operations Research, INFORMS, vol. 63(2), pages 325-342, April.
    19. Yicheng Liu & Xiao Alison Chen & Yan Liu & Zizhuo Wang, 2025. "Simultaneous vs. Sequential: Optimal Assortment Recommendation in Multistore Retailing," Manufacturing & Service Operations Management, INFORMS, vol. 27(3), pages 825-842, May.
    20. Nan Liu & Yuhang Ma & Huseyin Topaloglu, 2020. "Assortment Optimization Under the Multinomial Logit Model with Sequential Offerings," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 835-853, July.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:1911.06716. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.