Diagram som viser grupper og personer

Hvilket problem løser dette?

Tenk deg at personer skal allokeres til grupper med begrenset kapasitet. Hver person har preferanser over gruppene, og hver gruppe har en prioritering som angir en rekkefølge for hvem de skal ta inn først. Dette problemet oppstår f.eks. når barn skal tildeles barnehageplass. Foreldrene oppgir sine preferanser over barnehager i nærmiljøet. Barnehagene har på sin side en prioritering over barna, f.eks. basert på alder eller om de har søsken som allerede går i barnehagen.

Utsatt aksept, eller Deferred Acceptance (DA) på engelsk, er en algoritme som løser dette problemet. Algoritmen har to svært gunstige egenskaper: den er strategisikker og stabil (“misunnelse” oppstår aldri). Les mer om disse egenskapene nedenfor. En annen algoritme som løser samme problem er Bytteringer.

Bruksområder

Tabellen nedenfor gir noen klassiske bruksområder. Noen av disse løses effektivt og i Norge i dag, mens andre er typiske bruksområder internasjonalt der Norge i dag ikke bruker noen algoritme, eller lar hver kommune bestemme selv.

Bruksområde Personer Grupper Preferanser Prioriteter
Barnehageopptak Foreldre Barnehager Foreldrenes ønsker Søsken i barnehagen, alder på barnet, funksjonsnedsettelser, osv.
Grunnskoleopptak Foreldre Skoler Foreldrenes ønsker Nærskoleprinsippet (elever sortert etter avstand), søsken, osv.
Turnusplasser Leger Sykehus Legenes ønsker Legenes karaktersnitt, karakterer i spesifikke fag, alder, osv.
Militæret Vernepliktige Avdelinger Den vernepliktiges ønsker Hva enn hver avdeling ønsker å prioritere (karakterer, resultater fra sesjon, osv.)
Studentboliger Studenter Boliger Studentenes ønsker Tid i køen, studentens alder, osv.

Gruppenes prioritering er ofte ikke entydig, og å velge en god prioritering er en del av jobben med å modellere inntaksprosessen. Eksempelvis kan det være tenkelig at forsvarets avdeling “Fallskjermjeger” ville prioritert søkere hovedsaklig etter fysisk evne, mens avdelingen “Etterretnings­analytiker” ville prioritert etter mer akademiske ferdigheter. Hver gruppe kan prioritere søkerne ulikt og etter egne kriterier, så lenge de rangerer søkerne på en objektiv måte.

Fordeler

  • Strategisikker: Ingen tjener på å lyve om sine preferanser. Det lønner seg alltid å være ærlig om hva man ønsker, så lenge personene får rangere alle gruppene.
  • “Misunnelse” oppstår aldri: 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. Utsatt aksept garanterer at ingen blir forbigått, og algoritmen er derfor et populært valg for inntak til barnehager, skoler, osv. verden over.

Viktig å vite

  • Ikke Pareto-effektiv: Med Utsatt aksept kan det forekomme at personer kunne ha byttet seg i mellom og blitt mer fornøyde. Med andre ord: det kan hende at Ola får A og Kari får B, men Ola foretrakk B fremfor A og Kari foretrakk A fremfor B. Det er bevist at det ikke eksisterer noen algoritme som både eliminerer misunnelse og samtidig er Pareto-effektiv. Man må velge mellom én av disse egenskapene.

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

Eksempler

Du kan teste Utsatt aksept 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 lite og enkelt eksempel som viser input-formatet som brukes i APIet.

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

Resultat: 

{"Kari": "A", "Ola": "B"}

Eksempel 2

Dette eksempelet viser at selv om Utsatt aksept gir en fordeling uten “misunnelse”, så er den ikke Pareto-effektiv. I løsningen kan Ola og Kari bytte plass og begge vil bli mer fornøyde.

{"data": {
     "persons": [
         {"id": "Kari",   "preferences": ["B", "A", "C"]},
         {"id": "Ola",    "preferences": ["A", "B", "C"]},
         {"id": "Petter", "preferences": ["A", "B", "C"]}
     ],
     "groups": [
         {"id": "A", "capacity": 1, "priorities": ["Kari", "Petter", "Ola"]},
         {"id": "B", "capacity": 1, "priorities": ["Ola", "Kari", "Petter"]},
         {"id": "C", "capacity": 1, "priorities": ["Ola", "Kari", "Petter"]}
     ]}}

Resultat: 

{"Kari": "A", "Ola": "B", "Petter": "C"}

Eksempel 3

Dersom personene også har en oppgitt kapasitet, og minst én kapasitet er større enn 1, så har vi et mange-til-mange problem. Hver person kan gå til flere grupper, og hver gruppe kan ta inn flere personer. Algoritmen kan håndtere slike problemer, men mange-til-mange varianten er ikke strategisikker. Dersom minst én kapasitet er større enn 1, så vil APIet returnere en annen struktur på resultatet: for hver person returneres en liste med grupper, heller enn én gruppe.

{"data": {
     "persons": [
         {"id": "Kari", "capacity": 2, "preferences": ["B", "A"]},
         {"id": "Ola",  "capacity": 2, "preferences": ["A", "B"]}
     ],
     "groups": [
         {"id": "A", "capacity": 2, "priorities": ["Kari", "Ola"]},
         {"id": "B", "capacity": 1, "priorities": ["Ola", "Kari"]}
     ]}}

Resultat: 

{"Kari": ["A"], "Ola": ["A", "B"]}