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

Congestion and Penalization in Optimal Transport

Author

Listed:
  • Marcelo Gallardo
  • Manuel Loaiza
  • Jorge Ch'avez

Abstract

In this paper we introduce two novel models derived from the discrete optimal transport problem. The first model extends the traditional transport problem by adding a quadratic congestion factor directly into the cost function, while the second model replaces conventional constraints with weighted penalization terms. We present theoretical results, for the characterization of interior and corner solution for some specific cases, and we perform smooth comparative statics analysis. We also propose an $O((N+L)(NL)^2)$ algorithm for computing the optimal plan for the penalized model. Additionally, in the annex, we provide some examples that illustrate the main results of the paper.

Suggested Citation

  • Marcelo Gallardo & Manuel Loaiza & Jorge Ch'avez, 2024. "Congestion and Penalization in Optimal Transport," Papers 2410.07363, arXiv.org, revised Oct 2024.
    • Handle: RePEc:arx:papers:2410.07363
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Alfred Galichon, 2016. "Optimal Transport Methods in Economics," Economics Books, Princeton University Press, edition 1, number 10870.
    2. Arnaud Dupuy & Alfred Galichon, 2014. "Personality Traits and the Marriage Market," Journal of Political Economy, University of Chicago Press, vol. 122(6), pages 1271-1319.
    3. Milgrom, Paul & Shannon, Chris, 1994. "Monotone Comparative Statics," Econometrica, Econometric Society, vol. 62(1), pages 157-180, January.
    4. Federico Echenique & Joseph Root & Fedor Sandomirskiy, 2024. "Stable matching as transportation," Papers 2402.13378, arXiv.org.
    5. Federico Echenique & M. Bumin Yenmez, 2015. "How to Control Controlled School Choice," American Economic Review, American Economic Association, vol. 105(8), pages 2679-2694, August.
    6. John William Hatfield & Paul R. Milgrom, 2005. "Matching with Contracts," American Economic Review, American Economic Association, vol. 95(4), pages 913-935, September.
    7. Muriel Niederle & Leeat Yariv, 2009. "Decentralized Matching with Aligned Preferences," Working Papers 2009-3, Princeton University. Economics Department..
    8. Arnaud Dupuy & Alfred Galichon, 2022. "A note on the estimation of job amenities and labor productivity," Quantitative Economics, Econometric Society, vol. 13(1), pages 153-177, January.
    9. A. F. Izmailov & M. V. Solodov, 2023. "Convergence rate estimates for penalty methods revisited," Computational Optimization and Applications, Springer, vol. 85(3), pages 973-992, July.
    10. Muriel Niederle & Leeat Yariv, 2009. "Decentralized Matching with Aligned Preferences," NBER Working Papers 14840, National Bureau of Economic Research, Inc.
    11. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    12. Agarwal, Nikhil & Somaini, Paulo, 2021. "Empirical Models of Non-transferable Utility Matching," Research Papers 3982, Stanford University, Graduate School of Business.
    13. Alvin E. Roth, 1982. "The Economics of Matching: Stability and Incentives," Mathematics of Operations Research, INFORMS, vol. 7(4), pages 617-628, November.
    14. repec:hal:spmain:info:hdl:2441/361levbcs399s9oa154em6h9jl is not listed on IDEAS
    15. Echenique,Federico & Immorlica,Nicole & Vazirani,Vijay V. (ed.), 2023. "Online and Matching-Based Market Design," Cambridge Books, Cambridge University Press, number 9781108831994.
    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. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    2. Ehlers, Lars & Hafalir, Isa E. & Yenmez, M. Bumin & Yildirim, Muhammed A., 2014. "School choice with controlled choice constraints: Hard bounds versus soft bounds," Journal of Economic Theory, Elsevier, vol. 153(C), pages 648-683.
    3. Kojima, Fuhito & Tamura, Akihisa & Yokoo, Makoto, 2018. "Designing matching mechanisms under constraints: An approach from discrete convex analysis," Journal of Economic Theory, Elsevier, vol. 176(C), pages 803-833.
    4. Jeremy T. Fox, 2018. "Estimating matching games with transfers," Quantitative Economics, Econometric Society, vol. 9(1), pages 1-38, March.
    5. Yenmez, M. Bumin, 2018. "A college admissions clearinghouse," Journal of Economic Theory, Elsevier, vol. 176(C), pages 859-885.
    6. Yuichiro Kamada & Fuhito Kojima, 2020. "Accommodating various policy goals in matching with constraints," The Japanese Economic Review, Springer, vol. 71(1), pages 101-133, January.
    7. Alfred Galichon & Simon Weber, 2024. "Matching under Imperfectly Transferable Utility," Papers 2403.05222, arXiv.org, revised Oct 2024.
    8. Marco LiCalzi, 2022. "Bipartite choices," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 45(2), pages 551-568, December.
    9. Jiang, Zhishan & Tian, Guoqiang, 2013. "Matching with Couples: Stability and Algorithm," MPRA Paper 57936, University Library of Munich, Germany, revised Jul 2014.
    10. Ehlers, Lars & Klaus, Bettina, 2016. "Object allocation via deferred-acceptance: Strategy-proofness and comparative statics," Games and Economic Behavior, Elsevier, vol. 97(C), pages 128-146.
    11. Bloch, Francis & Cantala, David & Gibaja, Damián, 2020. "Matching through institutions," Games and Economic Behavior, Elsevier, vol. 121(C), pages 204-231.
    12. Hatfield, John William & Kojima, Fuhito, 2010. "Substitutes and stability for matching with contracts," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1704-1723, September.
    13. Battal Doğan & Kemal Yildiz, 2023. "Choice with Affirmative Action," Management Science, INFORMS, vol. 69(4), pages 2284-2296, April.
    14. Alvin E. Roth, 2010. "Marketplace Institutions Related to the Timing of Transactions," NBER Working Papers 16556, National Bureau of Economic Research, Inc.
    15. 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," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 89(6), pages 3085-3114.
    16. Avataneo, Michelle & Turhan, Bertan, 2021. "Slot-specific priorities with capacity transfers," Games and Economic Behavior, Elsevier, vol. 129(C), pages 536-548.
    17. Umut M. Dur & Scott Duke Kominers & Parag A. Pathak & Tayfun Sönmez, 2013. "The Demise of Walk Zones in Boston: Priorities vs. Precedence in School Choice," NBER Working Papers 18981, National Bureau of Economic Research, Inc.
    18. Alfred Galichon & Scott Kominers & Simon Weber, 2014. "An Empirical Framework for Matching with Imperfectly Transferable Utility," Working Papers hal-03460155, HAL.
    19. Assaf Romm, 2014. "Implications of capacity reduction and entry in many-to-one stable matching," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 43(4), pages 851-875, December.
    20. Kazuo Murota, 2016. "Discrete convex analysis: A tool for economics and game theory," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 1(1), pages 151-273, December.

    More about this item

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