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 studenter skal tildeles praksisplasser. Studenter oppgir sine preferanser over praksisplasser. Praksisplassene har på sin side en prioritering over studentene, f.eks. basert på karakterer, relevant erfaring eller geografisk tilhørighet.

Bytteringer, eller Top Trading Cycles (TTC) på engelsk, er en algoritme som løser dette problemet. Algoritmen har to 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 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.

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.
• 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 Anna får A og Oscar får B, men Anna foretrakk B fremfor A og Oscar 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 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. 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": "Oscar", "preferences": ["A", "B"]}, 
                      {"id": "Anna",  "preferences": ["A", "B"]}], 
          "groups": [{"id": "A", "capacity": 1, "priorities": ["Oscar", "Anna"]}, 
                     {"id": "B", "capacity": 1, "priorities": ["Anna", "Oscar"]}]
}}

Resultat:

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

Eksempel 2

Dette eksempelet viser at selv om Bytteringer gir en Pareto-effektiv fordeling, så kan såkalt “misunnelse” oppstå. Lea blir misunnelig på Anna, fordi Lea foretrekker gruppe A og gruppe A foretrekker Lea foran Anna.

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

Resultat:

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

Resultat:

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

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": "C", "Marcus": "A"}