Implementing Matroid Constraints in Fair Allocation: A MIP-based Implementation and Empirical Study using Julia
Abstract
Denne oppgaven studerer bruken av matroiderestriksjoner for rettferdig fordeling av udelelige goder. En implementasjon av matroiderestriksjoner i Julia blir demonstrert, og denne bygd på toppen av MIP-er for å finne rettferdige fordelinger. Implementasjonen består av to forskjellige fremgangsmåter: lazy constraints-metoden, hvor restriksjonene blir lagt til mens MIP-en løses, og loop-metoden, som løser MIP-en iterativt og legger til restriksjoner etter hver iterasjon. Vi bruker matroiderestriksjonene både på en symmetrisk måte, slik at agentene deler den samme restriksjonen, og en asymmetrisk måte, hvor hver agent har hennes egen restriksjon. Ett sett med eksperimenter med tilfeldige, MNW og MMS fordelinger viser at rettferdige fordelinger kan fortsatt bli funnet når vi bruker matroiderestriksjoner, og i noen tilfeller øker EF1-approksimasjonsfaktoren. De empiriske resultatene viser også at EF1 ikke er garantert for MNW-fordelinger med matroiderestriksjoner, men de oppnår fortsatt sterke tilnærminger for EF1, EFX og MMS. I tillegg gir ytelsesmålingene positive resultater når det gjelder kjøretiden for å finne fordelinger under restriksjoner, spesielt i forhold til fordelingene uten restriksjoner. This thesis studies the use of matroid constraints for fair allocation of indivisible goods. An implementation of matroid constraints in Julia is presented, which is built on top of MIPs for finding fair allocations. The implementation consists of two different approaches: the lazy constraints method, where constraints are added during the MIP solving, and the loop method, which iteratively solves the MIP and adds constraints after each iteration. We use the matroid constraints both in a symmetric manner, such that the agents share the same constraint, and an asymmetric manner, where each agent has her own constraint. A set of experiments with random, MNW, and MMS allocations show that fair allocations can still be found when applying matroid constraints, and in some cases the EF1 approximation factor increases. The empirical results also show that EF1 is not guaranteed for matroid constrained MNW allocations, but they still provide strong approximations for EF1, EFX, and MMS. Additionally, the benchmarks show positive results regarding the running time for finding the allocations with constraints, especially in relation to the unconstrained setting.