Hvordan velge riktig allokeringsalgoritme?

Dersom du skal allokere barnehagebarn til barnehager, elever til skoler, ansatte til prosjekter, eller mer generelt: personer til grupper, så finnes det flere algoritmer å velge mellom. Denne artikkelen viser hvilke avveininger du bør gjøre når du velger algoritme, og hvordan hver algoritme gir ulike resultater på et lite eksempel.

Alle algoritmene er ekstremt raske og oppnår bedre resultater enn hva man kan få til manuelt. Det finnes dog ingen perfekt algoritme som løser alle problemstillinger, fordi det er noen avveininger mellom matematiske egenskaper som er uunngåelige.

De tre algoritmene

• Utsatt aksept: Et godt valg når individets rett til å ikke bli forbigått i gruppenes prioritering er viktigere enn at resultatet gjør så mange som mulig fornøyde. Den er strategisikker, så det lønner seg aldri for personene å lyve om sine preferanser.
• Bytteringer: Ofrer individets rett til å ikke bli forbigått for å oppnå bedre resultater for de fleste, ved å la personene bytte plasser. Denne algoritmen er også strategisikker.
• Optimal allokering: Gjør at så mange som mulig blir fornøyde. Ikke strategisikker, og ofrer individets rett til å ikke bli forbigått. Kan også vektlegge hvor fornøyde gruppene blir med sin tildeling.

For mange reelle problemstillinger, spesielt de som er formelle og involverer juridiske rettigheter, er Utsatt aksept anbefalt. Dette er også algoritmen som er mest populær internasjonalt. Et kraftig alternativ er Effektiv utsatt aksept, som vi ikke kommer til å dekke i denne artikkelen.

Les gjennom denne artikkelen og gjør opp din egen mening om hvilken algoritme som passer best til ditt formål. Om du har spørsmål så er det bare å ta kontakt!

Egenskaper

Her er en tabell som viser algoritmene og ulike egenskaper som de enten besitter eller ikke:

* - Optimal allokering klarer ikke alltid å beviselig garantere optimalitet for store problemer.

Når vi sier at f.eks. Utsatt aksept er Fri for misunnelse, så betyr det at uansett hvilket datasett man bruker, så vil misunnelse garantert aldri oppstå. Det er mulig at, for enkelte datasett, så vil også Bytteringer resultere i en allokering som er fri for misunnelse – men det er ikke garantert.

Her er en kort oppsummering av hva egenskapene betyr.

Strategisikkerhet

En algoritme er strategisikker dersom det alltid lønner seg å oppgi ærlige preferanser. Dersom en algoritme derimot ikke er strategisikker, er det mulig at en person kan oppnå bedre resultater ved å lyve. Dette er uheldig fordi det betyr at deltakerne kan oppnå gevinst ved å tenke strategisk, f.eks. “Hvor mange andre kommer til å søke på denne skolen?”, heller enn å simpelthen oppgi sine ærlige preferanser.

For at en algoritme skal være strategisikker må personene få lov til å rangere alle gruppene. Jo færre grupper man får rangere, desto mer strategi kreves: tenk på et VGS-inntak der hver elev kun får lov til å sette opp ønske for én skole. Da må eleven tenke veldig strategisk, og bør ikke sette opp en for populær skole dersom han ikke har godt nok karaktersnitt.

Fri for misunnelse

Misunnelse betyr at noen blir forbigått av andre i gruppenes prioritering. Her er et eksempel: Ola får gruppe A mens Kari ikke gjør det, samtidig som Kari foretrekker gruppe A fremfor hva hun fikk, og gruppe A foretrekker Kari fremfor Ola. Da sier vi at Kari har berettiget misunnelse (“justified envy”) på Ola. Kari har med andre ord blitt forbigått av Ola i prioriteringen til gruppe A.

Det er matematisk bevist at det ikke finnes noen algoritme som både er fri for misunnelse og Pareto-optimal samtidig: det er en avveining mellom individets rett til å ikke bli forbigått og personers mulighet til å kunne bytte plasser.

Pareto-optimal

En algoritme er Pareto-optimal dersom fordelingen er slik at ingen kan bytte til seg noe bedre uten at det går ut over noen andre. Dersom f.eks. Ola og Kari kan innbyrdes bytte plass og begge to blir mer fornøyde, så er ikke fordelingen Pareto-optimal.

To utfall kan begge være Pareto-optimale. Dersom fire personer får ønsker (1, 2, 2, 2) i et utfall, og (2, 1, 1, 1) i et annet utfall, så er begge to Pareto-optimale. Dette er vist i figuren nedenfor. Solide mørke linjer angir førstevalget og stiplete linjer angir andrevalget.

En løsning er å gi Anna førstevalget og alle andre andrevalget. En annen løsning er å gi Anna andrevalget og alle andre førstevalget. Det er gruppenes prioritering som bestemmer hvilken løsning som blir valgt. Begge er Pareto-optimale, fordi ingen kan bytte innbyrdes og få bedre plasser uten at det går ut over noen.

Eksempel

Her er et eksempel der tre personer (Anna, Oscar og Lea) søker på tre grupper (A, B og C). Hver gruppe har plass til én person. Personene har preferanser over gruppene, f.eks. har Anna gruppe C som sitt førstevalg. Gruppene har prioriteter over personene, f.eks. prioriterer gruppe C personen Oscar høyest.

Her er to eksempler på problemer der gruppene har ulike prioriteringer:

• I nærskoleprinsippet er gruppene skoler, og det kan hende at Oscar bor nærmest skole C.
• Dersom man følger reglene for gruppene som gir prioritet til kommunale barnehager, så kan det være at Oscar prioriteres høyt fordi han har søsken i barnehage C.

Gruppene kan også ha samme prioritering, f.eks. på inntak til VGS når alle skolene rangerer elever etter karaktersnitt. I slike tilfeller gir Utsatt aksept og Bytteringer identisk resultat.

Personenes preferanser

Gruppenes prioriteter

Vi skal se at de tre algoritmene gir tre ulike resultater på dette eksempelet.

Utsatt aksept

Dersom vi bruker algoritmen Utsatt aksept, så kan vi sende inn følgende data til APIet:

{"data": 
{"persons": [{"id": "Anna",  "preferences": ["C", "A", "B"]},
             {"id": "Oscar", "preferences": ["B", "A", "C"]},
             {"id": "Lea",   "preferences": ["B", "C", "A"]}],
 "groups": [{"id": "A", "capacity": 1, "priorities": ["Lea", "Anna", "Oscar"]},
            {"id": "B", "capacity": 1, "priorities": ["Anna", "Oscar", "Lea"]},
            {"id": "C", "capacity": 1, "priorities": ["Oscar", "Lea", "Anna"]}]
}}

Da får vi dette resultatet:

{"Anna": "A", "Oscar": "B", "Lea": "C"}

Anna får sitt 2. valg, Oscar får sitt 1. valg og Lea får sitt 2. valg.

• Fordelingen er fri for misunnelse, fordi ingen har blitt forbigått av andre.
• Fordelingen er tilfeldigvis Pareto-optimal i dette eksempelet, men Utsatt aksept garanterer ikke denne egenskapen generelt.

Bytteringer

Dersom vi bruker algoritmen Bytteringer på datasettet, så får vi følgende resultat:

{"Anna": "C", "Oscar": "B", "Lea": "A"}

Anna får sitt 1. valg, Oscar får sitt 1. valg og Lea får sitt 3. valg.

• Fordelingen er Pareto-optimal, fordi ingen kan bytte til seg bedre plasser uten at det går ut over andre.
• Fordelingen er ikke fri for misunnelse, fordi Lea føler seg forbigått av Anna. Lea foretrekker gruppe C foran sin gruppe, og gruppe C foretrekker Lea fremfor Anna, men likevel fikk Anna gruppe C.

Optimal allokering

Dersom vi bruker algoritmen Optimal allokering, så får vi følgende resultat:

{"Anna": "C", "Oscar": "A", "Lea": "B"}

Anna får sitt 1. valg, Oscar får sitt 2. valg og Lea får sitt 1. valg.

• Fordelingen er Pareto-optimal, fordi ingen kan bytte til seg bedre plasser uten at det går ut over andre.
• Fordelingen er ikke fri for misunnelse, fordi Oscar føler seg forbigått av Lea. Oscar foretrekker gruppe B foran sin gruppe, og gruppe B foretrekker Oscar foran Lea. Likevel fikk Lea gruppe B.

Fordelingen er ikke strategisikker. Oscar kan oppnå et bedre resultat ved å lyve om sine preferanser. Dersom Oscar oppgir usanne preferanser ["B", "C", "A"] i stedet for sine ærlige preferanser ["B", "A", "C"], så vil Oscar få gruppe B (sitt 1. valg) i stedet for gruppe A (sitt 2. valg):

{"data": 
{"persons": [{"id": "Anna",  "preferences": ["C", "A", "B"]},
             {"id": "Oscar", "preferences": ["B", "C", "A"]},
             {"id": "Lea",   "preferences": ["B", "C", "A"]}],
 "groups": [{"id": "A", "capacity": 1, "priorities": ["Lea", "Anna", "Oscar"]},
            {"id": "B", "capacity": 1, "priorities": ["Anna", "Oscar", "Lea"]},
            {"id": "C", "capacity": 1, "priorities": ["Oscar", "Lea", "Anna"]}]
}}

Dersom vi kjører algoritmen får vi følgende resultat:

{"Anna": "C", "Oscar": "B", "Lea": "A"}

Oscar får nå sitt 1. valg ved å lyve, Anna får sitt 1. valg, men Lea får sitt 3. valg.

Merk at både Bytteringer og Optimal allokering gir Pareto-optimale fordelinger, fordi det ikke nødvendigvis er én unik Pareto-optimal fordeling. Forskjellen er at Bytteringer er strategisikker, mens Optimal allokering ofte klarer å få flere personer inn på førstevalget.

Oppsummering

Grunnen til at flere algoritmer er tilgjengelige er fordi det ikke finnes en perfekt algoritme. Det er f.eks. bevist matematisk at det ikke finnes noen algoritme som resulterer i en fordeling som garantert både er fri for misunnelse og samtidig Pareto-optimal.

I formelle situasjoner (opptak til barnehager, skoler, osv.), der personer har juridiske rettigheter til å ikke bli forbigått, er det vanlig å bruke Utsatt aksept. I mindre formelle situasjoner er Bytteringer et godt valg, fordi:

• Den er strategisikker, så personene slipper å måtte tenke strategisk.
• Den er Pareto-optimal, så det finnes ingen som kan bytte plass og tjene på det (derav navnet).
• Den tillater gruppene å prioritere personene (med potensielt ulike prioriteringer).
• Den gir ofte gode empiriske resultater, i den forstand at mange får sitt førsteønske.

På fiktive data med ti grupper og tusen personer får vi følgende resultater:

• Utsatt aksept: 725 fikk førstevalget, 111 fikk andrevalget, 45 tredjevalget, 31 fjerdevalget, 22 femtevalget, osv.
• Bytteringer: 923 fikk førstevalget, 38 fikk andrevalget, 14 fikk tredjevalget, 5 fikk fjerdevalget, osv.
• Optimal allokering: 940 fikk førstevalget, 45 fikk andrevalget, resten kunne ikke plasseres.

Bytteringer får svært mange inn på førstevalget, samtidig som den er strategisikker. Ulempene er at den ikke får inn like mange som Optimal allokering på førstevalget, og at den i motsetning til Utsatt aksept kan skape misunnelse. Om du ønsker å diskutere hvilken algoritme som er best egnet til ditt bruksområde, så er det bare å ta kontakt.