View in EDS

Fair integer programming under dichotomous and cardinal preferences.

Saved in:
Bibliographic Details
Title: Fair integer programming under dichotomous and cardinal preferences.
Authors: Demeulemeester, Tom1,2 (AUTHOR) tom.demeulemeester@kuleuven.be, Goossens, Dries2,3 (AUTHOR), Hermans, Ben1,4 (AUTHOR), Leus, Roel1 (AUTHOR)
Source: European Journal of Operational Research. Feb2025, Vol. 320 Issue 3, p465-478. 14p.
Subjects: Kidney exchange, Integer programming, Real variables, Integers, Tardiness
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. • We study how to fairly select one of the optimal solutions of integer programs. • Our methods apply to integer programs with binary, integer, or real decision variables. • Computational performance is evaluated for kidney exchange and machine scheduling. • One of our mechanisms uses similar run times as finding one optimal solution. [ABSTRACT FROM AUTHOR]
Copyright of European Journal of Operational Research is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 180409787
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Fair integer programming under dichotomous and cardinal preferences.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Demeulemeester%2C+Tom%22">Demeulemeester, Tom</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> tom.demeulemeester@kuleuven.be</i><br /><searchLink fieldCode="AR" term="%22Goossens%2C+Dries%22">Goossens, Dries</searchLink><relatesTo>2,3</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Hermans%2C+Ben%22">Hermans, Ben</searchLink><relatesTo>1,4</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Leus%2C+Roel%22">Leus, Roel</searchLink><relatesTo>1</relatesTo> (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22European+Journal+of+Operational+Research%22">European Journal of Operational Research</searchLink>. Feb2025, Vol. 320 Issue 3, p465-478. 14p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Kidney+exchange%22">Kidney exchange</searchLink><br /><searchLink fieldCode="DE" term="%22Integer+programming%22">Integer programming</searchLink><br /><searchLink fieldCode="DE" term="%22Real+variables%22">Real variables</searchLink><br /><searchLink fieldCode="DE" term="%22Integers%22">Integers</searchLink><br /><searchLink fieldCode="DE" term="%22Tardiness%22">Tardiness</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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. • We study how to fairly select one of the optimal solutions of integer programs. • Our methods apply to integer programs with binary, integer, or real decision variables. • Computational performance is evaluated for kidney exchange and machine scheduling. • One of our mechanisms uses similar run times as finding one optimal solution. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of European Journal of Operational Research is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=180409787
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.ejor.2024.08.023
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 14
        StartPage: 465
    Subjects:
      – SubjectFull: Kidney exchange
        Type: general
      – SubjectFull: Integer programming
        Type: general
      – SubjectFull: Real variables
        Type: general
      – SubjectFull: Integers
        Type: general
      – SubjectFull: Tardiness
        Type: general
    Titles:
      – TitleFull: Fair integer programming under dichotomous and cardinal preferences.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Demeulemeester, Tom
      – PersonEntity:
          Name:
            NameFull: Goossens, Dries
      – PersonEntity:
          Name:
            NameFull: Hermans, Ben
      – PersonEntity:
          Name:
            NameFull: Leus, Roel
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 02
              Text: Feb2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 03772217
          Numbering:
            – Type: volume
              Value: 320
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: European Journal of Operational Research
              Type: main
ResultId 1