Diagram som viser grupper og personer

Hvilket problem løser dette?

Personer skal allokeres til grupper med begrenset kapasitet. Hver person har en rangering over gruppene, og hver gruppe har en rangering over personene. Både gruppene og personene kan ha en kapasitet, som angir hvor mange som kan tildeles gruppen eller personen.

Optimal allokering løser dette problemet ved å formulere det som et matematisk optimeringsproblem. Algoritmen gir en poengscore for hver kobling mellom person og gruppe. Dersom Anna har Gruppe A som førstevalg, Gruppe B som andrevalg og Gruppe C som tredjevalg, så vil en fordeling som gir Anna førstevalget føre til flest poeng, andrevalget litt færre poeng og tredjevalget enda færre poeng. Optimal allokering maksimerer antall poeng på en rettferdig måte over både gruppene og personene.

Bruksområder

I Utsatt Aksept og Bytteringer er det personene som skal bli fornøyde, ikke gruppene. I mange tilfeller, f.eks. skoleopptak, så er dette naturlig: skolene eksisterer for å gjøre elevene fornøyde, ikke motsatt. I andre situasjoner, f.eks. opptak til militæret, kan man argumentere for at det også er viktig at gruppene får gode kandidater tildelt. Denne algoritmen balanserer hensynene med en parameter person_weight.

  • I eksempelet med opptak til militæret kan det være naturlig å sette f.eks. person_weight=0.8.
  • I noen tilfeller har gruppene verken preferanse eller prioritet. Dersom frivillige personer skal fordeles på aktiviteter, så har aktivitetene sannsynligvis verken noen preferanse eller prioritet. Da setter man person_weight=1.0.

Fordeler

  • Maksimerer tilfredshet: Algoritmen forsøker å tildele slik at flest mulig får sine høyest rangerte ønsker oppfylt. I praksis får ofte svært mange sitt førsteønske om det er mulig.
  • Beskytter de minst fornøyde: Balanse er også tatt med i beregningen. Dette sikrer rettferdighet, i den forstand at algoritmen ikke vil gjøre én person veldig tilfreds på andres bekostning. Den vil foretrekke å balansere utfallet.

Viktig å vite

  • Ikke strategisikker: I motsetning til Utsatt Aksept og Bytteringer, kan det teoretisk lønne seg å lyve om sine preferanser. Dersom en person vet hva alle andre vil velge, kan han potensielt oppnå bedre resultater ved å oppgi uærlige preferanser. I praksis er dette ofte vanskelig å utnytte fordi det krever detaljert kunnskap om andres valg. I motsetning til Boston-mekanismen er ikke denne algoritmen åpenbart enkelt å manipulere.
  • “Misunnelse” kan oppstå: Misunnelse, eller “justified envy” på engelsk, er et teknisk begrep fra forskningslitteraturen. Se for deg at Ola fikk gruppe B, men foretrakk gruppe A. Dersom Kari fikk gruppe A, og gruppe A prioriterte Ola fremfor Kari, så blir Ola “misunnelig” på Kari. Ola har blitt forbigått av Kari i prosessen. Denne formen for misunnelse kan oppstå, så algoritmen bør ikke brukes i situasjoner der personene har juridiske rettigheter til å bli prioritert.
  • Ikke garantert optimal: Algoritmen heter “Optimal allokering” fordi den løser et optimeringsproblem, ikke fordi den garantert gir et optimalt resultat. I praksis er resultatet ofte svært nær den teoretisk beste løsningen. Det er matematisk bevist at ingen algoritme kan garantere den aller beste løsningen innen rimelig tid. Algoritmen gjør derfor et intelligent søk og returnerer den beste løsningen den finner.

Algoritmen Optimal allokering har noen klare fordeler, men også noen ulemper. For mer informasjon om valg av algoritme, les gjerne Hvordan velge riktig allokeringsalgoritme?

Parametre

Denne algoritmen har en parameter som kan endres:

  • person_weight: Et tall mellom 0 og 1 som angir i hvilken grad personene vektlegges fremfor gruppene. Bruk et høyt tall, f.eks. 0.99, dersom du ønsker å maksimere hvor fornøyde personene blir. Dersom du heller ønsker å vektlegge gruppene, bruk et lavt tall, f.eks. 0.01. For å vektlegge personer og grupper likt, velg omtrent 0.5. Det kan være lurt å eksperimentere. Dersom verdien ikke blir oppgitt blir den satt til person_weight=0.99.

Ofte er det mer hensiktsmessig å velge 0.99 heller enn 1.0, og 0.01 heller enn 0.0. Da vektlegger vi ett av målene mest, men det andre målet teller også litt. I situasjoner der gruppene ikke har noen reell rangering, kan man gi inn en vilkårlig rangering og sette person_weight=1.0.

Eksempel: bruk av parameter person_weight

Her er et eksempel som viser effekten av person_weight:

  {"data": {
  "persons": [
    {"id": "Anna", "capacity": 1, "preferences":  ["A", "B"]},
    {"id": "Oscar", "capacity": 1, "preferences": ["B", "A"]}
  ],
  "groups": [
    {"id": "A", "capacity": 1, "priorities": ["Oscar", "Anna"]},
    {"id": "B", "capacity": 1, "priorities": ["Anna", "Oscar"]}
  ]},
  "parameters": {"person_weight": 0.99}}

I løsningen er det personenes rangering av gruppene som avgjør utfallet:

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

Endrer vi til "person_weight": 0.01 så er det gruppenes rangering av personene som avgjør:

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

Eksempler

Du kan teste Optimal allokering på eksempelene nedenfor i APIet helt gratis. Eksempelene er små for å vise struktur og hva som er mulig. Med betalt tilgang kan du sende inn store datasett. De fleste problemer løses på under ett sekund.

Eksempel 1

Her er et enkelt eksempel som viser input-formatet som brukes i APIet. Både personene og gruppene har egentlig preferanser, og problemet er symmetrisk. Grunnen til at APIet bruker “priorities” heller enn “preferences” for grupper er for å være kompatibel med andre algoritmer.

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

Resultat: 

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

Eksempel 2

Dette eksempelet viser at optimal allokering maksimerer tilfredshet, men kan skape “misunnelse”. Lea blir misunnelig på Oscar, fordi gruppe D foretrekker Lea fremfor Oscar.

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

Resultat: 

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

Eksempel 3

Dette eksempelet viser et mange-til-mange problem, der personene også har en kapasitet. Både Anna og Oscar kan delta i opptil 2 grupper hver. Resultatet blir at Anna får A og C, mens Oscar får B og C. Begge får dermed sine to høyest prioriterte grupper.

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

Resultat: 

{"Anna": ["A", "C"], "Oscar": ["B", "C"]}