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

Near-feasible Fair Allocations in Two-sided Markets

Author

Listed:
  • Javier Cembrano
  • Andr'es Moraga
  • Victor Verdugo

Abstract

We study resource allocation in two-sided markets from a fundamental perspective and introduce a general modeling and algorithmic framework to effectively incorporate the complex and multidimensional aspects of fairness. Our main technical contribution is to show the existence of a range of near-feasible resource allocations parameterized in different model primitives to give flexibility when balancing the different policymaking requirements, allowing policy designers to fix these values according to the specific application. To construct our near-feasible allocations, we start from a fractional resource allocation and perform an iterative rounding procedure to get an integer allocation. We show a simple yet flexible and strong sufficient condition for the target feasibility deviations to guarantee that the rounding procedure succeeds, exhibiting the underlying trade-offs between market capacities, agents' demand, and fairness. To showcase our framework's modeling and algorithmic capabilities, we consider three prominent market design problems: school allocation, stable matching with couples, and political apportionment. In each of them, we obtain strengthened guarantees on the existence of near-feasible allocations capturing the corresponding fairness notions, such as proportionality, envy-freeness, and stability.

Suggested Citation

  • Javier Cembrano & Andr'es Moraga & Victor Verdugo, 2025. "Near-feasible Fair Allocations in Two-sided Markets," Papers 2506.01178, arXiv.org.
  • Handle: RePEc:arx:papers:2506.01178
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Alvin E. Roth, 2018. "Marketplaces, Markets, and Market Design," American Economic Review, American Economic Association, vol. 108(7), pages 1609-1658, July.
    2. Thành Nguyen & Rakesh Vohra, 2019. "Stable Matching with Proportionality Constraints," Operations Research, INFORMS, vol. 67(6), pages 1503-1519, November.
    3. Herve Moulin, 2004. "Fair Division and Collective Welfare," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262633116, December.
    4. Narges Ahani & Tommy Andersson & Alessandro Martinello & Alexander Teytelboym & Andrew C. Trapp, 2021. "Placement Optimization in Refugee Resettlement," Operations Research, INFORMS, vol. 69(5), pages 1468-1486, September.
    5. Javier Cembrano & Jos'e Correa & Gonzalo D'iaz & Victor Verdugo, 2024. "Proportionality in Multiple Dimensions to Design Electoral Systems," Papers 2410.03304, arXiv.org.
    6. M. L. Balinski & G. Demange, 1989. "An Axiomatic Approach to Proportionality Between Matrices," Mathematics of Operations Research, INFORMS, vol. 14(4), pages 700-719, November.
    7. Tommy Andersson & Lars Ehlers, 2020. "Assigning Refugees to Landlords in Sweden: Efficient, Stable, and Maximum Matchings," Scandinavian Journal of Economics, Wiley Blackwell, vol. 122(3), pages 937-965, July.
    8. Haeringer, Guillaume, 2018. "Market Design: Auctions and Matching," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262037548, December.
    9. Thành Nguyen & Rakesh Vohra, 2018. "Near-Feasible Stable Matchings with Couples," American Economic Review, American Economic Association, vol. 108(11), pages 3154-3169, November.
    10. Gaffke, Norbert & Pukelsheim, Friedrich, 2008. "Divisor methods for proportional representation systems: An optimization approach to vector and matrix apportionment problems," Mathematical Social Sciences, Elsevier, vol. 56(2), pages 166-184, September.
    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. Chao Huang, 2022. "Two-sided matching with firms' complementary preferences," Papers 2205.05599, arXiv.org, revised May 2022.
    2. Oelbermann, Kai-Friederike, 2016. "Alternate Scaling algorithm for biproportional divisor methods," Mathematical Social Sciences, Elsevier, vol. 80(C), pages 25-32.
    3. Paolo Serafini, 2015. "Certificates of optimality for minimum norm biproportional apportionments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 44(1), pages 1-12, January.
    4. Ata Atay & Sylvain Funck & Ana Mauleon & Vincent Vannetelbosch, 2025. "Matching markets with farsighted couples," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 64(3), pages 465-481, May.
    5. Chao Huang, 2022. "Firm-worker hypergraphs," Papers 2211.06887, arXiv.org, revised Nov 2023.
    6. Jullien, Bruno & Pavan, Alessandro & Rysman, Marc, 2021. "Two-sided Markets, Pricing, and Network Effects," TSE Working Papers 21-1238, Toulouse School of Economics (TSE).
    7. Chao Huang, 2021. "Unidirectional substitutes and complements," Papers 2108.12572, arXiv.org.
    8. Afacan, Mustafa Oğuz & Hu, Gaoji & Li, Jiangtao, 2024. "Housing markets since Shapley and Scarf," Journal of Mathematical Economics, Elsevier, vol. 111(C).
    9. Hai Nguyen & Thành Nguyen & Alexander Teytelboym, 2021. "Stability in Matching Markets with Complex Constraints," Management Science, INFORMS, vol. 67(12), pages 7438-7454, December.
    10. Chao Huang, 2023. "Concave many-to-one matching," Papers 2309.04181, arXiv.org.
    11. Ce Liu & Ziwei Wang & Hanzhe Zhang, 2023. "Self-Enforced Job Matching," Papers 2308.13899, arXiv.org.
    12. Aygün, Orhan & Turhan, Bertan, 2021. "How to De-reserve Reserves," ISU General Staff Papers 202103100800001123, Iowa State University, Department of Economics.
    13. Magnus Lodefalk & Fredrik Sjöholm & Aili Tang, 2022. "International trade and labour market integration of immigrants," The World Economy, Wiley Blackwell, vol. 45(6), pages 1650-1689, June.
    14. Gabrielle Demange, 2018. "New electoral systems and old referendums," PSE Working Papers hal-01852206, HAL.
    15. Demange, Gabrielle, 2012. "On party-proportional representation under district distortions," Mathematical Social Sciences, Elsevier, vol. 63(2), pages 181-191.
    16. Marco LiCalzi, 2022. "Bipartite choices," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 45(2), pages 551-568, December.
    17. Yokote, Koji, 2021. "Consistency of the doctor-optimal equilibrium price vector in job-matching markets," Journal of Economic Theory, Elsevier, vol. 197(C).
    18. Chao Huang, 2021. "Stable matching: an integer programming approach," Papers 2103.03418, arXiv.org, revised Apr 2022.
    19. Josué Ortega & Erel Segal-Halevi, 2022. "Obvious manipulations in cake-cutting," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 59(4), pages 969-988, November.
    20. Jens Gudmundsson & Jens Leth Hougaard & Erik Ansink, 2024. "Towards fully decentralized environmental regulation," Tinbergen Institute Discussion Papers 24-035/VIII, Tinbergen Institute.

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