EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2978. Fair integer programming under dichotomous preferences

Invited abstract in session WA-43: Market Design 2, stream Market Design.

Wednesday, 8:30-10:00
Room: 99 (building: 306)

Authors (first author is the speaker)

1. Tom Demeulemeester
ORSTAT, KU Leuven
2. Dries Goossens
Business Informatics and Operations Management, Ghent University
3. Ben Hermans
ORSTAT, KU Leuven
4. Roel Leus
ORSTAT, KU Leuven

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

Status: accepted

Back to the list of papers