Exploring Matroids in Fair Allocation: Building the Matroids.jl Library

Abstract

Denne oppgaven utforsker rollen matroider spiller innen rettferdig fordeling, med mål for øyet å utvikle Matroids.jl, et Julia-bibliotek som muliggjør empirisk analyse av algoritmer for rettferdig fordeling som bruker matroider. Matroids.jl implementerer funksjonalitet for å representere og tilfeldig generere grafiske matroider. I tillegg implementeres Knuths algoritme for å tilfeldig sette opp vilkårlige matroider. Tre nylige algoritmer for rettferdig fordeling med matroierang-verdifunksjoner beskrives og deres behov til Matroids.jl analyseres. Matroids.jl implementerer også funksjonalitet for å evaluere en fordeling mot de fleste vanlige rettferdighetsmål. Til slutt benyttes biblioteket til å sette opp en serie eksperimenter som kjøres på de tre utvalgte algoritmene, og resultatene presenteres.

This thesis explores the role of matroids in the context of fair allocation, for the purpose of building Matroids.jl, a proof-of-concept Julia library enabling the empirical study of matroidal fair allocation algorithms. To this end, functionality is given for the representation and random generation of graphic matroids. In addition, Knuth's algorithm for the erection of arbitrary matroids is implemented. Three recent fair allocation algorithms are studied and implemented. Also implemented is the functionality for evaluating an allocation against a variety of common fairness notions. The library is finally used to construct an experimental setup and the results of running the implemented algorithms on diverse matroids are described.