Multiple Opinionated Knapsacks

Abstract

Fordeling av ressurser, enten med mål om rettferdighet eller optimalitet, er en grunnleggende problemstilling i flere deler av ethvert samfunn. Vi utforsker fordeling av udelelige gjenstander mellom agenter som alle har et eget budsjett. En gjenstand har to attributter: profitt og kostnad. Profitten til en gjenstand varierer basert på hvilken agent som får den, mens kostnaden er lik for alle agentene. Målet er å maksimere den totale summen av profittene til hver agent, under kravet om at summen av kostnadene til en agent ikke overskider budsjettet. Vi kaller dette problemet ``the multiple opinionated knapsack problem'', og presenterer en algoritme som vurderer alle mulige fordelinger, untatt de den kan bevise at ikke er optimale. "The multiple knapsack problem" er identisk, unntatt at profitten til en gjenstand ikke endres basert på hvilken agent som får den. Vi endrer eksisterende optimaliseringer for the multiple knapsack problem slik at de passer til varianten med subjektive profitter, og vurderer bidragene deres etter endringene. I tillegg gjøres en vurdering av hvilke av optimaliseringene som kan ha verdi dersom vi ønsker å endre algoritmen til å finne rettferdige fordelinger i stedet for optimale.

Det viser seg at de fleste av optimaliseringene kan endres til å passe subjektive profitter, og fortsatt redusere kjøretiden betydelig, til tross for at alle optimaliseringene blir svakere grunnet den økte kompleksiteten av problemet. Enkelte av optimaliseringene baserer seg og på å argumentere for at profitten en gjenstand genererer er uavhengig av hvilken agent de blir allokert til, som naturligvis gjør at de ikke kan anvendes med subjektive profitter. Vi konkluderer med at vår implementasjon av algoritmen ikke klarer å utkonkurrere tilgjengelige algoritmer for å løse ``Integer Linear Program''(ILP) problemer, men at enkelte av optimaliseringene kan anvendes for å løse rettferdig fordelingsproblemer, som de generiske løsningene for ILP'er sliter med.

Allocating resources, whether fairly or optimally, is a fundamental challenge in many parts of society. We investigate the allocation of a set of indivisible items amongst agents which each have a budget. Each item has two properties: a profit and a cost. The profit depends on which agent it is allocated to, while the cost is the same for every agent. The goal is to maximize the total amount of profit, while ensuring that the total cost of the items allocated to an agent does not exceed that agent's budget. We call this problem the multiple opinionated knapsack problem, and present an exhaustive algorithm for finding optimal solutions to it, which intelligently prevents investigating suboptimal solutions. The multiple knapsack problem is identical, except that the profit of an item is the same for all agents, i.e., the agents are not opinionated. We adapt established optimizations for the multiple knapsack problem to the opinionated variant, and review their efficacy. Additionally, we consider which of these optimizations could remain useful if one wished to adopt the algorithm to find fair allocations of items as opposed to optimal ones.

We find that most of the optimizations survive the transition to subjective profits rather well, although the increased complexity of the new problem does have its consequences on how effective each optimization is. There are also certain optimizations that rely on arguing that the profit of an item is independent of which agent receives it, which naturally have to be excluded. Unfortunately our implementation is not efficient enough to outcompete current Integer Linear Program (ILP)-solvers, but some of the optimizations may prove useful when adapting the algorithm to find fair allocations, as ILP-solvers are generally ill-suited for such tasks.