.png){kind=icon}
.png){kind=icon}
Return
Fair integer programming under dichotomous and cardinal preferences
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2024.08.023.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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-boxprocedure 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
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W