IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v320y2025i3p465-478.html
   My bibliography  Save this article

Fair integer programming under dichotomous and cardinal preferences

Author

Listed:
  • Demeulemeester, Tom
  • Goossens, Dries
  • Hermans, Ben
  • Leus, Roel

Abstract

One cannot make truly fair decisions using integer linear programs unless one controls the selection probabilities of the (possibly many) optimal solutions. For this purpose, we propose a unified framework when binary decision variables represent agents with dichotomous preferences, who only care about whether they are selected in the final solution. We develop several general-purpose algorithms to fairly select optimal solutions, for example, by maximizing the Nash product or the minimum selection probability, or by using a random ordering of the agents as a selection criterion (Random Serial Dictatorship). We also discuss in detail how to extend the proposed methods when agents have cardinal preferences. As such, we embed the “black-box” procedure of solving an integer linear program into a framework that is explainable from start to finish. Lastly, we evaluate the proposed methods on two specific applications, namely kidney exchange (dichotomous preferences), and the scheduling problem of minimizing total tardiness on a single machine (cardinal preferences). We find that while the methods maximizing the Nash product or the minimum selection probability outperform the other methods on the evaluated welfare criteria, methods such as Random Serial Dictatorship perform reasonably well in computation times that are similar to those of finding a single optimal solution.

Suggested Citation

  • Demeulemeester, Tom & Goossens, Dries & Hermans, Ben & Leus, Roel, 2025. "Fair integer programming under dichotomous and cardinal preferences," European Journal of Operational Research, Elsevier, vol. 320(3), pages 465-478.
  • Handle: RePEc:eee:ejores:v:320:y:2025:i:3:p:465-478
    DOI: 10.1016/j.ejor.2024.08.023
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172400660X
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2024.08.023?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Tayfun Sönmez & Alvin E. Roth & M. Utku Ünver, 2007. "Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences," American Economic Review, American Economic Association, vol. 97(3), pages 828-851, June.
    2. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    3. Aziz, Haris & Mestre, Julián, 2014. "Parametrized algorithms for random serial dictatorship," Mathematical Social Sciences, Elsevier, vol. 72(C), pages 1-6.
    4. William Thomson, 2022. "On the axiomatic theory of bargaining: a survey of recent results," Review of Economic Design, Springer;Society for Economic Design, vol. 26(4), pages 491-542, December.
    5. Imai, Haruo, 1983. "Individual Monotonicity and Lexicographic Maxmin Solution," Econometrica, Econometric Society, vol. 51(2), pages 389-401, March.
    6. Duddy, Conal, 2015. "Fair sharing under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 73(C), pages 1-5.
    7. Anna Bogomolnaia & Herve Moulin, 2004. "Random Matching Under Dichotomous Preferences," Econometrica, Econometric Society, vol. 72(1), pages 257-279, January.
    8. Gibbard, Allan, 1977. "Manipulation of Schemes That Mix Voting with Chance," Econometrica, Econometric Society, vol. 45(3), pages 665-681, April.
    9. Carvalho, Margarida & Lodi, Andrea, 2023. "A theoretical and computational equilibria analysis of a multi-player kidney exchange program," European Journal of Operational Research, Elsevier, vol. 305(1), pages 373-385.
    10. Thomson, William, 1994. "Cooperative models of bargaining," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 2, chapter 35, pages 1237-1284, Elsevier.
    11. Constantino, Miguel & Klimentova, Xenia & Viana, Ana & Rais, Abdur, 2013. "New insights on integer-programming models for the kidney exchange problem," European Journal of Operational Research, Elsevier, vol. 231(1), pages 57-68.
    12. Demeulemeester, Tom & Goossens, Dries & Hermans, Ben & Leus, Roel, 2023. "A pessimist’s approach to one-sided matching," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1087-1099.
    13. Bogomolnaia, Anna & Moulin, Herve & Stong, Richard, 2005. "Collective choice under dichotomous preferences," Journal of Economic Theory, Elsevier, vol. 122(2), pages 165-184, June.
    14. Murnighan, J Keith & Roth, Alvin E & Schoumaker, Francoise, 1988. "Risk Aversion in Bargaining: An Experimental Study," Journal of Risk and Uncertainty, Springer, vol. 1(1), pages 101-124, March.
    15. Roth, Alvin E & Murnighan, J Keith, 1982. "The Role of Information in Bargaining: An Experimental Study," Econometrica, Econometric Society, vol. 50(5), pages 1123-1142, September.
    16. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    17. Haris Aziz & Anna Bogomolnaia & Hervé Moulin, 2019. "Fair Mixing: the Case of Dichotomous Preferences," Post-Print hal-03047451, HAL.
    18. Bailey Flanigan & Paul Gölz & Anupam Gupta & Brett Hennig & Ariel D. Procaccia, 2021. "Fair algorithms for selecting citizens’ assemblies," Nature, Nature, vol. 596(7873), pages 548-552, August.
    19. Renaud Chicoisne, 2023. "Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes," Computational Optimization and Applications, Springer, vol. 84(3), pages 789-831, April.
    20. Chen, Violet Xinying & Hooker, J.N., 2022. "Combining leximax fairness and efficiency in a mathematical programming model," European Journal of Operational Research, Elsevier, vol. 299(1), pages 235-248.
    21. Willard I. Zangwill, 1967. "The Convex Simplex Method," Management Science, INFORMS, vol. 14(3), pages 221-238, November.
    22. Aziz, Haris & Brandt, Felix & Brill, Markus, 2013. "The computational complexity of random serial dictatorship," Economics Letters, Elsevier, vol. 121(3), pages 341-345.
    23. Chengbin Chu, 1992. "A branch‐and‐bound algorithm to minimize total tardiness with different release dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 265-283, March.
    24. Florian Brandl & Felix Brandt & Hans Georg Seedig, 2016. "Consistent Probabilistic Social Choice," Econometrica, Econometric Society, vol. 84, pages 1839-1880, September.
    25. Roth, Alvin E. & Malouf, Michael W. K. & Murnighan, J. Keith, 1981. "Sociological versus strategic factors in bargaining," Journal of Economic Behavior & Organization, Elsevier, vol. 2(2), pages 153-177, June.
    26. Baptiste, Philippe & Carlier, Jacques & Jouglet, Antoine, 2004. "A Branch-and-Bound procedure to minimize total tardiness on one machine with arbitrary release dates," European Journal of Operational Research, Elsevier, vol. 158(3), pages 595-608, November.
    27. P. C. Fishburn, 1984. "Probabilistic Social Choice Based on Simple Voting Comparisons," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 51(4), pages 683-692.
    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. Tom Demeulemeester & Dries Goossens & Ben Hermans & Roel Leus, 2023. "Fair integer programming under dichotomous and cardinal preferences," Papers 2306.13383, arXiv.org, revised Apr 2024.
    2. Aziz, Haris & Brandl, Florian & Brandt, Felix & Brill, Markus, 2018. "On the tradeoff between efficiency and strategyproofness," Games and Economic Behavior, Elsevier, vol. 110(C), pages 1-18.
    3. Committee, Nobel Prize, 2012. "Alvin E. Roth and Lloyd S. Shapley: Stable allocations and the practice of market design," Nobel Prize in Economics documents 2012-1, Nobel Prize Committee.
    4. Haris Aziz & Patrick Lederer & Xinhang Lu & Mashbat Suzuki & Jeremy Vollen, 2024. "Sequential Payment Rules: Approximately Fair Budget Divisions via Simple Spending Dynamics," Papers 2412.02435, arXiv.org.
    5. Alvin E. Roth, 2007. "Repugnance as a Constraint on Markets," Journal of Economic Perspectives, American Economic Association, vol. 21(3), pages 37-58, Summer.
    6. Xiaohui Bei & Guangda Huzhang & Warut Suksompong, 2018. "Truthful Fair Division without Free Disposal," Papers 1804.06923, arXiv.org, revised Apr 2020.
    7. Xiaohui Bei & Guangda Huzhang & Warut Suksompong, 2020. "Truthful fair division without free disposal," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 55(3), pages 523-545, October.
    8. Carvalho, Margarida & Lodi, Andrea, 2023. "A theoretical and computational equilibria analysis of a multi-player kidney exchange program," European Journal of Operational Research, Elsevier, vol. 305(1), pages 373-385.
    9. Stephen Leider & William S. Lovejoy, 2016. "Bargaining in Supply Chains," Management Science, INFORMS, vol. 62(10), pages 3039-3058, October.
    10. Brandt, Felix & Saile, Christian & Stricker, Christian, 2022. "Strategyproof social choice when preferences and outcomes may contain ties," Journal of Economic Theory, Elsevier, vol. 202(C).
    11. Brandl, Florian & Brandt, Felix, 2024. "A natural adaptive process for collective decision-making," Theoretical Economics, Econometric Society, vol. 19(2), May.
    12. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    13. Jérémy Picot, 2012. "Random aggregation without the Pareto principle," Review of Economic Design, Springer;Society for Economic Design, vol. 16(1), pages 1-13, March.
    14. Klimentova, Xenia & Biró, Péter & Viana, Ana & Costa, Virginia & Pedroso, João Pedro, 2023. "Novel integer programming models for the stable kidney exchange problem," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1391-1407.
    15. Gaurav, Abhishek & Picot, Jérémy & Sen, Arunava, 2017. "The decomposition of strategy-proof random social choice functions on dichotomous domains," Mathematical Social Sciences, Elsevier, vol. 90(C), pages 28-34.
    16. Anna Bogomolnaia, 2015. "The Most Ordinally-Efficient of Random Voting Rules," HSE Working papers WP BRP 106/EC/2015, National Research University Higher School of Economics.
    17. Morrill, Thayer & Roth, Alvin E., 2024. "Top trading cycles," Journal of Mathematical Economics, Elsevier, vol. 112(C).
    18. YIlmaz, Özgür, 2011. "Kidney exchange: An egalitarian mechanism," Journal of Economic Theory, Elsevier, vol. 146(2), pages 592-618, March.
    19. Aziz, Haris & Brandl, Florian & Brandt, Felix, 2015. "Universal Pareto dominance and welfare for plausible utility functions," Journal of Mathematical Economics, Elsevier, vol. 60(C), pages 123-133.
    20. Yılmaz, Özgür, 2014. "Kidney exchange: Further utilization of donors via listed exchange," Journal of Mathematical Economics, Elsevier, vol. 51(C), pages 178-186.

    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:eee:ejores:v:320:y:2025:i:3:p:465-478. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.