Fair integer programming under dichotomous and cardinal preferences
Tom Demeulemeester,
Dries Goossens,
Ben Hermans and
Roel Leus
European Journal of Operational Research, 2025, vol. 320, issue 3, 465-478
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.
Keywords: Integer programming; Fairness; Inequity; Randomization; Column generation (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:
Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172400660X
Full text for ScienceDirect subscribers only
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:320:y:2025:i:3:p:465-478
DOI: 10.1016/j.ejor.2024.08.023
Access Statistics for this article
European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati
More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().