Utsatt aksept

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 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 i Norge i dag, mens andre er typiske bruksområder internasjonalt der Norge i dag ikke bruker noen algoritme.

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 Anna fikk gruppe B, men foretrakk gruppe A. Dersom Oscar fikk gruppe A, og gruppe A prioriterte Anna fremfor Oscar, så blir Anna “misunnelig” på Oscar. Anna har blitt forbigått av Oscar 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 Anna får A og Oscar får B, men Anna foretrakk B fremfor A og Oscar 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": "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 selv om Utsatt aksept gir en fordeling uten “misunnelse”, så er løsningen ikke nødvendigvis Pareto-effektiv. I løsningen kan Anna og Oscar bytte plass og begge vil bli mer fornøyde.

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

Resultat:

{"Anna": "A", "Oscar": "B", "Lea": "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": "Anna",  "capacity": 2, "preferences": ["B", "A"]},
         {"id": "Oscar", "capacity": 2, "preferences": ["A", "B"]}
     ],
     "groups": [
         {"id": "A", "capacity": 2, "priorities": ["Anna", "Oscar"]},
         {"id": "B", "capacity": 1, "priorities": ["Oscar", "Anna"]}
     ]}}

Resultat:

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

Eksempel 4

Her er et litt større eksempel med seks personer og tre grupper. Legg merke til at ikke alle personene rangerer alle gruppene, og ikke alle gruppene rangerer alle personene. Når f.eks. Anna rangerer gruppe B, men gruppe B ikke rangerer henne, vil Anna aldri kunne tildeles gruppe B. Begge må rangere hverandre for å kunne matches.

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

Resultat:

{"Anna": "A", "Oscar": "B", "Elias": "A", "Marcus": "C"}