Referanser

Allokering har blitt studert siden 60-tallet, og er et aktivt forskningsfelt. Ordet “allokering” er en popularisering av det som gjerne kalles “matching”, “market design”, “mechanism design” eller “school choice” i forskningslitteraturen. Nye algoritmer dukker opp med jevne mellomrom, selv om de viktigste egenskapene og algoritmene ble funnet opp for mange tiår siden.

Diagram som viser grupper og personer

Denne tjenesten skal være transparent og forskningsbasert. Algoritmene er godt dokumentert, så en typisk bruker trenger ikke å lese forskningsartikler – men nedenfor finnes vitenskapelige referanser for de som ønsker det.

Vær kritisk til algoritmer som er “black-box”, “proprietære” eller “AI”-baserte. Vage beskrivelser og komplisert språk brukes ofte til å dekke over slett arbeid. Dersom noen ikke kan forklare helt tydelig hvilke egenskaper en algoritme har og hva den gjør, bør du være skeptisk – spesielt i situasjoner som involverer mennesker.

Wikipedia

Dersom du ikke har noen kjennskap til feltet, kan det være lurt å starte på Wikipedia:

Forskningsartikler

De som ønsker å gå i dybden bør lese forskningsartikler. Det er skrevet mye, og som i alle forskningsfelt er noe av varierende kvalitet. Nedenfor oppgis noen av de kjente artiklene som denne tjenesten er basert på. De fleste av disse er sitert mange ganger. Noen er sitert mange tusen ganger og er i bruk i mange land.

Grunnleggende

Atila og Tayfun skriver godt og forståelig. Her er to artikler som er en fin introduksjon:

  • Abdulkadiroğlu, Atila, and Tayfun Sönmez. 2003. “School Choice: A Mechanism Design Approach.” DOI
    En velskrevet og lettleselig artikkel, som sammenligner den uheldige Boston-mekanismen med de langt bedre mekanismene Deferred Acceptance (Utsatt aksept) og Top Trading Cycles (Bytteringer). Hvis du skal lese én artikkel for å forstå allokering, så er det sannsynligvis denne.

  • Abdulkadiroğlu, Atila, and Tayfun Sönmez. 2013. “Matching Markets: Theory and Practice.”
    Sammendrag av historikk, de viktigste teoretiske resultatene og nyvinninger i Two-Sided Matching og One-Sided Matching. Seksjon 4 om School Choice er spesielt relevant.

Reallokering

Reallokering handler om å bytte når man allerede har blitt tildelt noe. Fastlegebytter, studentboliger og stillinger i interne prosjekter er typiske eksempler.

  • Abdulkadiroğlu, Atila, and Tayfun Sönmez. 1999. “House Allocation with Existing Tenants.” DOI
    To algoritmer som gir samme utfall i situasjoner der personer allerede er allokert til grupper. Begge er basert på TTC, og utfallet er derfor Pareto-effektivt, individuelt rasjonelt og mekanismene er strategisikre.

  • Huitfeldt, Ingrid, Victoria Marone, and Daniel C. Waldinger. 2024. “Designing Dynamic Reassignment Mechanisms: Evidence from GP Allocation.” DOI
    Denne artikkelen tar for seg den fastlegeordningen, og viser hvordan resultatene fra artikkelen “House Allocation with Existing Tenants” kan brukes til å drastisk forbedre den norske fastlegeordningen. Resultatene er implementert i Reallokering. Se også leserinnlegget Enkelt å forbedre fastlegeordningen - med en algoritme. Både DA og TTC er i prinsippet mulig å bruke, og artikkelen anbefaler TTC med en spesifikk prioritering.

Efficiency Adjusted Deferred Acceptance Mechanism (EADAM)

EADAM er en pen generalisering av Utsatt aksept som tillater at personer blir forbigått om det ikke skader dem. Algoritmen er implementert under navnet Effektiv utsatt aksept.

  • Kesten, Onur. 2010. “School Choice with Consent.”
    Artikkelen introduserer EADAM, som forbedrer det stabile utgangspunktet fra Deferred Acceptance (Utsatt aksept) ved å gjøre den mer effektiv. EADAM er ikke strategisikker. Krever at hver person gir samtykke til å bli forbigått, men at en person samtykker kan aldri skade den personen. Kan utvides til situasjonen der gruppene har svake prioriteter. Kjøretiden er O(|E| |E|), der E er kanter i den bipartitte grafen.

  • Tang, Qianfeng, and Jingsheng Yu. 2014. “A New Perspective on Kesten’s School Choice with Consent Idea.” DOI
    En ny og bedre algoritme som regner ut EADAM enda raskere. Kjøretiden er O(|E| |V|), der V er noder i den bipartitte grafen. Kan utvides til situasjoner der gruppene har svake prioriteter.

  • Faenza, Yuri, and Xuan Zhang. 2022. “Legal Assignments and Fast EADAM with Consent via Classic Theory of Stable Matchings.” DOI
    En enda raskere måte å regne ut EADAM på, som har O(|E|) kjøretid. Baksiden er at denne algoritmen ikke utvides til situasjonen der gruppene har svake prioriteter.

Svake preferanser

  • Erdil, Aytek, and Haluk Ergin. 2008. “What’s the Matter with Tie-Breaking? Improving Efficiency in School Choice.” DOI
    Utvider DA til tilfellet der gruppene har svake preferanser ved hjelp av Stable Improvement Cycles (SIC). Denne varianten er ikke strategisikker, og ingen algoritme som tar hensyn til svake preferanser er strategisikker.

  • Erdil, Aytek, and Haluk Ergin. 2017. “Two-Sided Matching with Indifferences.” DOI
    Introduserer både WOSMA og ESMDA. Begge er stabile, men ingen er strategisikre. Worker-Optimal Stable Matching Algorithm (WOSMA) utvider DA til tilfellet der både personene og gruppene har svake preferanser / prioriteringer. Kun personene inngår i velferdskriteriet. Efficient and Stable Matching Algorithm (ESMA) utvider også DA til svake perferanser, men både personene og gruppene inngår i velferdskriteriet (symmetrisk behandling).

Optimering

Kildene for algoritmen bak Optimal allokering:

Praktisk anvendelse

  • Abdulkadiroğlu, Atila, Parag A. Pathak, and Alvin E. Roth. 2009. “Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match.” DOI
    Sammenligner data fra Boston og New York på ulike algoritmer. Skolene har svake preferanser, og NYC har hele 90 000 studenter. DA med tie-breaking får 32 100 inn på førstevalget. Student-optimal stable matching (DA pluss SIC) får 32 700 inn på førstevalget (+1.9%). TTC får 34 700 inn på førstevalget (+8.1%). Merk at TTC ikke er stabil, og SOSM ikke er strategisikker.

Manipulasjon

Historisk