Bytteringer

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.

Bytteringer, eller Top Trading Cycles (TTC) på engelsk, er en algoritme som løser dette problemet. Algoritmen har to svært gunstige egenskaper: den er strategisikker og Pareto-optimal. Les mer om disse egenskapene nedenfor. En annen algoritme som løser samme problem er Utsatt Aksept.

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

Her er noen fordeler med algoritmen Bytteringer:

• 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.
• Pareto-effektiv: Det vil aldri forekomme at personer kunne ha byttet seg i mellom og blitt mer fornøyde. Se for deg et resultat der Ola får A og Kari får B, men Ola foretrakk B fremfor A og Kari foretrakk A fremfor B. En slik situasjon vil aldri oppstå. Det er bevist at det ikke eksisterer noen algoritme som både eliminerer misunnelse (se nedenfor) og samtidig er Pareto-effektiv. Man må velge mellom én av disse egenskapene.

Viktig å vite

• “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. Med Bytteringer kan slik misunnelse oppstå, og denne algoritmen er derfor mindre populær i situasjoner der personene har juridiske rettigheter til å bli prioritert.

Algoritmen Bytteringer 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 Bytteringer 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 Bytteringer gir en effektiv fordeling, så kan såkalt “misunnelse” oppstå. Petter blir misunnelig på Ola, fordi Petter foretrekker gruppe A og gruppe A foretrekker Petter foran Ola.

{"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": "B", "Ola": "A", "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", "B"], "Ola": ["A"]}