IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2310.00260.html
   My bibliography  Save this paper

On Sinkhorn's Algorithm and Choice Modeling

Author

Listed:
  • Zhaonan Qu
  • Alfred Galichon
  • Johan Ugander

Abstract

For a broad class of choice and ranking models based on Luce's choice axiom, including the Bradley--Terry--Luce and Plackett--Luce models, we show that the associated maximum likelihood estimation problems are equivalent to a classic matrix balancing problem with target row and column sums. This perspective opens doors between two seemingly unrelated research areas, and allows us to unify existing algorithms in the choice modeling literature as special instances or analogs of Sinkhorn's celebrated algorithm for matrix balancing. We draw inspirations from these connections and resolve important open problems on the study of Sinkhorn's algorithm. We first prove the global linear convergence of Sinkhorn's algorithm for non-negative matrices whenever finite solutions to the matrix balancing problem exist. We characterize this global rate of convergence in terms of the algebraic connectivity of the bipartite graph constructed from data. Next, we also derive the sharp asymptotic rate of linear convergence, which generalizes a classic result of Knight (2008), but with a more explicit analysis that exploits an intrinsic orthogonality structure. To our knowledge, these are the first quantitative linear convergence results for Sinkhorn's algorithm for general non-negative matrices and positive marginals. The connections we establish in this paper between matrix balancing and choice modeling could help motivate further transmission of ideas and interesting results in both directions.

Suggested Citation

  • Zhaonan Qu & Alfred Galichon & Johan Ugander, 2023. "On Sinkhorn's Algorithm and Choice Modeling," Papers 2310.00260, arXiv.org.
    • Handle: RePEc:arx:papers:2310.00260
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Malachy Carey & Chris Hendrickson & Krishnaswami Siddharthan, 1981. "A Method for Direct Estimation of Origin/Destination Trip Matrices," Transportation Science, INFORMS, vol. 15(1), pages 32-49, February.
    2. Pedro Uribe & C. G. de Leeuw & H. Theil, 1966. "The Information Approach to the Prediction of Interregional Trade Flows," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 33(3), pages 209-220.
    3. H. Theil & Guido Rey, 1966. "A Quadratic Programming Approach to the Estimation of Transition Probabilities," Management Science, INFORMS, vol. 12(9), pages 714-721, May.
    4. Odran Bonnet & Alfred Galichon & Yu-Wei Hsieh & Keith O’Hara & Matt Shum, 2022. "Yogurts Choose Consumers? Estimation of Random-Utility Models via Two-Sided Matching [Unobserved Product Differentiation in Discrete-Choice Models: Estimating Price Elasticities and Welfare Effects," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 89(6), pages 3085-3114.
    5. Daniel McFadden & Kenneth Train, 2000. "Mixed MNL models for discrete response," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 15(5), pages 447-470.
    6. Serina Chang & Emma Pierson & Pang Wei Koh & Jaline Gerardin & Beth Redbird & David Grusky & Jure Leskovec, 2021. "Mobility network models of COVID-19 explain inequities and inform reopening," Nature, Nature, vol. 589(7840), pages 82-87, January.
    7. Richard W. Cottle & Steven G. Duvall & Karel Zikan, 1986. "A lagrangean relaxation algorithm for the constrained matrix problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 33(1), pages 55-76, February.
    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.
    9. Michael H. Schneider & Stavros A. Zenios, 1990. "A Comparative Study of Algorithms for Matrix Balancing," Operations Research, INFORMS, vol. 38(3), pages 439-455, June.
    10. 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.
    11. Alfred Galichon & Bernard Salani'e, 2021. "Matching with Trade-offs: Revealed Preferences over Competing Characteristics," Papers 2102.12811, arXiv.org.
    12. Sebastian Maier & Petur Zachariassen & Martin Zachariasen, 2010. "Divisor-Based Biproportional Apportionment in Electoral Systems: A Real-Life Benchmark Study," Management Science, INFORMS, vol. 56(2), pages 373-387, February.
    13. Friedrich Pukelsheim, 2014. "Biproportional scaling of matrices and the iterative proportional fitting procedure," Annals of Operations Research, Springer, vol. 215(1), pages 269-283, April.
    14. Hausman, Jerry A. & Ruud, Paul A., 1987. "Specifying and testing econometric models for rank-ordered data," Journal of Econometrics, Elsevier, vol. 34(1-2), pages 83-104.
    15. Lamond, B. & Stewart, N. F., 1981. "Bregman's balancing method," Transportation Research Part B: Methodological, Elsevier, vol. 15(4), pages 239-248, August.
    16. Richard R. Batsell & John C. Polking, 1985. "A New Class of Market Share Models," Marketing Science, INFORMS, vol. 4(3), pages 177-198.
    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. Kerem Akartunalı & Philip A. Knight, 2017. "Network models and biproportional rounding for fair seat allocations in the UK elections," Annals of Operations Research, Springer, vol. 253(1), pages 1-19, June.
    3. Qi Feng & J. George Shanthikumar & Mengying Xue, 2022. "Consumer Choice Models and Estimation: A Review and Extension," Production and Operations Management, Production and Operations Management Society, vol. 31(2), pages 847-867, February.
    4. Xiao-Yue Gong & Vineet Goyal & Garud N. Iyengar & David Simchi-Levi & Rajan Udwani & Shuangyu Wang, 2022. "Online Assortment Optimization with Reusable Resources," Management Science, INFORMS, vol. 68(7), pages 4772-4785, July.
    5. Peng Shi, 2022. "Optimal Priority-Based Allocation Mechanisms," Management Science, INFORMS, vol. 68(1), pages 171-188, January.
    6. Gerardo Berbeglia & Alvaro Flores & Guillermo Gallego, 2021. "The Refined Assortment Optimization Problem," Papers 2102.03043, arXiv.org.
    7. Arjun Seshadri & Johan Ugander, 2020. "Fundamental Limits of Testing the Independence of Irrelevant Alternatives in Discrete Choice," Papers 2001.07042, arXiv.org.
    8. Wong, S.C. & Wong, C.W. & Sze, N.N., 2008. "Attitudes of public light bus drivers to penalties to combat red light violations in Hong Kong," Transport Policy, Elsevier, vol. 15(1), pages 43-54, January.
    9. Ruxian Wang & Zizhuo Wang, 2017. "Consumer Choice Models with Endogenous Network Effects," Management Science, INFORMS, vol. 63(11), pages 3944-3960, November.
    10. 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.
    11. Torlak, Elvisa, 2004. "Foreign Direct Investment, Technology Transfer and Productivity Growth. Empirical Evidence for Hungary, Poland, Romania, Bulgaria and the Czech Republic," Conference papers 331189, Purdue University, Center for Global Trade Analysis, Global Trade Analysis Project.
    12. Siikamaki, Juha & Layton, David F., 2007. "Discrete choice survey experiments: A comparison using flexible methods," Journal of Environmental Economics and Management, Elsevier, vol. 53(1), pages 122-139, January.
    13. Ben Aoki-Sherwood & Catherine Bregou & David Liben-Nowell & Kiran Tomlinson & Thomas Zeng, 2024. "Bounding Consideration Probabilities in Consider-Then-Choose Ranking Models," Papers 2401.11016, arXiv.org.
    14. Hong il Yoo, 2012. "The perceived unreliability of rank-ordered data: an econometric origin and implications," Discussion Papers 2012-46, School of Economics, The University of New South Wales.
    15. 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.
    16. Amel Awadelkarim & Arjun Seshadri & Itai Ashlagi & Irene Lo & Johan Ugander, 2023. "Rank-heterogeneous Preference Models for School Choice," Papers 2306.01801, arXiv.org.
    17. Wei Qi & Xinggang Luo & Xuwang Liu & Yang Yu & Zhongliang Zhang, 2019. "Product Line Pricing under Marginal Moment Model with Network Effect," Complexity, Hindawi, vol. 2019, pages 1-13, February.
    18. 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.
    19. Siikamaki, Juha & Layton, David F., 2001. "Logit Models For Pooled Contingent Valuation And Contingent Rating And Ranking Data: Valuing Benefits From Forest Biodiversity Conservation," 2001 Annual meeting, August 5-8, Chicago, IL 20616, American Agricultural Economics Association (New Name 2008: Agricultural and Applied Economics Association).
    20. Patriksson, Michael, 2008. "A survey on the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 185(1), pages 1-46, February.

    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:2310.00260. 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.