Fair Allocation of Mixed Divisible and Indivisible Goods: A Comparative Study

Abstract

Denne avhandlingen tar for seg utfordringen med å rettferdig fordele blandete delbare og udelelige varer ved å tilpasse etablerte algoritmer fra deres respektive fagfelt, samt å utvikle enkle polynomiske algoritmer til å finne gode foredlinger. Målet er å utforske effektiviteten og praktikaliteten til disse algoritmene samt koble feltet med blandete varer til det mer velkjente feltet med kun udelelige varer. Det ble utført empiriske eksperimenter på tilfeldig genererte instanser, der rettferdighetsmål som MaxiMinShare og Maximum Nash Welfare ble evaluert. Resultatene viser tilfredsstillende utfall i flertallet av tilfellene, noe som antyder potensialet for å tilpasse udelelige algoritmer til problemer med blandet fordeling. Imidlertid er omfanget av disse resultatene begrenset til betingelsene som ble brukt i denne studien, så ytterligere teoretiske beviser er nødvendig for å etablere robustheten og anvendeligheten til disse algoritmene i ulike scenarier. Likevel gir denne forskningen verdifulle innsikter i feltet for rettferdig fordeling av blandete varer.

This thesis addresses the challenge of fairly allocating mixed divisible and indivisible goods by adapting established algorithms from their respective fields, and creating naive polynomial time algorithms. The objective is to explore the effectiveness of these algorithms in solving the problem of mixed allocation in an attempt to bridge the gap to the more well studied field with only indivisible goods. Empirical experiments were conducted on randomly generated instances, evaluating metrics such as MaxiMinShare and Maximum Nash Welfare. The results demonstrate satisfactory outcomes in a majority of cases, suggesting the potential of adapting indivisible algorithms for mixed allocation problems. However, the scope of these results is limited to the conditions employed in this study, so further theoretical proofs are needed to establish the robustness and applicability of these algorithms across various scenarios. Nevertheless, this research provides valuable insights into the field of fair allocation of mixed goods.