Effektiv utsatt aksept

Hvilket problem løser dette?

Denne algoritmen er bygget på Utsatt aksept, så det er anbefalt å lese om den algoritmen først. Denne algoritmen har to styrker som kan gjøre den til et bedre valg enn Utsatt aksept:

• Samtykke til å bli forbigått. Hver person får mulighet til å samtykke til å bli forbigått, men kun i situasjoner samtykket ikke vil skade dem selv. Dette kan tillate et resultat der flere personer blir fornøyde.
• Svake prioriteringer. Algoritmen kan håndtere svake prioriteringer hos gruppene. Svake prioriteringer oppstår ofte i prioritetsgrupper dersom man ikke har en naturlig måte å rangere innad i gruppene på.

Vi skal demonstrere begge disse egenskapene med eksempler.

Samtykke til å bli forbigått

La oss se på et eksempel med fire personer og fire grupper. Vi kjører følgende data på Utsatt aksept:

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

Problemet er illustrert i figuren nedenfor. Kun personenes preferanser er tegnet, og kun førstevalg (solid mørk linje) og andrevalg (stiplet linje) er vist i figuren.

Svaret vi får gir Kari 2. valget, Ola 2. valget, Petter 2. valget og Lise 2. valget.

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

Dersom Ola, Lise og Petter bytter plass innbyrdes, kan alle tre får sitt førstevalg. Ola tar Lise sin plass hos A, Lise tar Petter sin plass hos C og Petter tar Ola sin plass hos B. De tre personene Ola, Lise og Petter blir alle mer fornøyde, uten at det går ut over Kari.

Byttet lar seg likevel ikke gjøre med Utsatt aksept, fordi Kari ville blitt forbigått av Ola i gruppe A. Kari har nemlig gruppe A som førsteønske, og gruppe A prioriterer Kari foran Ola. Kari ville blitt “misunnelig” på Ola.

Men Kari ville uansett ikke fått gruppe A. Dersom Kari samtykker til å bli forbigått i situasjoner som uansett ikke vil skade hennes eget resultat, kan vi innfri flere ønsker. Kari har aldri insentiv til å ikke samtykke, fordi hennes samtykke kan ikke skade hennes resultat – det kan kun hjelpe andre. Likevel bør vi innhente samtykke i noen situasjoner, fordi det av juridiske grunner kan kreves at ingen blir forbigått uten eksplisitt samtykke.

La oss kjøre Effektiv Utsatt Aksept på samme problem, der Kari eksplisitt gir samtykke til å bli forbigått dersom det uansett ikke vil skade hennes resultat:

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

Merk at dersom feltet "consenting" mangler, så antas det implisitt at personen ikke gir samtykke.

Her er resultatet:

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

Kari får fremdeles sitt 2. valg. Hun vil som nevnt aldri ende opp i en verre gruppe ved å gi samtykke. Men på grunn av hennes samtykke kan både Ola, Petter og Lise få sitt 1. valg innvilget.

Oppsummert kan kravet om at ingen skal bli forbigått, som er sentralt i Utsatt aksept, føre til at personer som Kari “blokkerer” andre. Ved å innhente samtykke fra Kari kan vi hjelpe andre med å få et bedre resultat. Det er aldri insentiv til å ikke samtykke, fordi algoritmen garanterer at en person som samtykker aldri ender opp med et dårligere resultat.

Svake prioriteringer hos gruppene

De fleste algoritmene krever en prioriteringsliste som ikke tillater at noen prioriteres likt. For eksempel ["Petter", "Kari", "Ola"]. Men hva om en gruppe er likegyldig mellom Kari og Ola? En svak prioritering, som ["Petter", ["Kari", "Ola"]], representerer dette. Gruppen har Petter som førsteprioritet og Kari og Ola som delt andreprioritet.

Her er et eksempel der gruppe A har en svak prioritering:

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

Dersom vi bruker Utsatt aksept til å løse dette problemet må vi bryte den svake prioriteringen. Det er to måter å bryte den på:

• Velger vi ["Petter", "Kari", "Ola"] får alle sitt 2. ønske.
• Velger vi ["Petter", "Ola", "Kari"] får både Ola og Petter sitt 1. ønske.

Å manuelt bryte opp svake prioriteringer og kjøre mange ganger for å sjekke resultatene er tidkrevende. Med en svak prioritering over 2 personer er det bare 2 måter å bryte den opp på. Men med en svak prioritering over f.eks. 5 personer er det 5 * 4 * 3 * 2 * 1 = 120 måter å bryte prioriteringen på.

Denne algoritmen håndterer svake prioriteringer automatisk. Resultatet på eksempelet ovenfor er:

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

Dette er nyttig dersom man har prioritetsgrupper uten noen naturlig måte å rangere innad i gruppene på.

Fordeler

• “Misunnelse” oppstår kun ved samtykke: Ingen vil bli forbigått med mindre de samtykker. Dersom en person gir samtykke, vil personen aldri ende opp med et verre resultat. Derfor er det heller aldri noe insentiv til å ikke samtykke. Vi bør likevel eksplisitt be om samtykke i noen situasjoner, fordi det kan innebære at en person sier fra seg en juridisk rettighet til å ikke bli forbigått.
• Svake prioriteringer: Svake prioriteringer oppstår ofte innad i prioritetsgrupper. En mulig løsning er å bruke loddtrekning til å vilkårlig rangere personer innad i hver prioriteringsgruppe. Men dette fører ofte til sub-optimale resultater, fordi noen loddtrekninger gir bedre resultater enn andre. Dersom det er reellt at man ikke har noen god måte å rangere innad i en prioritetsgruppe på, er denne algoritmen et godt valg.

Kombinasjoner av samtykke og svake prioriteringer håndteres også.

Viktig å vite

• Ikke Pareto-effektiv: Generelt er algoritmen ikke Pareto-effektiv. Dersom alle gir samtykke, så er algoritmen Pareto-effektiv. Ettersom det kan finnes mer enn én Pareto-effektiv løsning, er den ikke garantert å gi samme resultat som andre Pareto-effektive algoritmer, f.eks. Bytteringer.
• Ikke strategisikker: I motsetning til Utsatt Aksept kan det teoretisk lønne seg å lyve om sine preferanser. Dersom en person vet nøyaktig hva alle andre vil velge, kan personen potensielt oppnå bedre resultater ved å oppgi uærlige preferanser. I praksis er dette vanskelig å utnytte fordi det krever detaljert kunnskap om andres valg.

Eksempler

Du kan teste Effektiv 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

Et lite eksempel som viser APIet med samtykke, men uten svake preferanser. Det er Anna, Oscar og Elias som får plass, enten Lea og Maria samtykker eller ei. Dersom Lea og Maria ikke samtykker, får de tre personene henholdsvis 2. valg, 2. valg og 1. valg. Dersom de derimot begge samtykker, får Anna, Oscar og Elias sine førsteønsker.

{"data": {"persons": [
  {"id": "Anna",  "preferences": ["A", "B"], "consenting": false},
  {"id": "Oscar", "preferences": ["B", "A"], "consenting": false},
  {"id": "Lea",   "preferences": ["A", "B"], "consenting": true},
  {"id": "Maria", "preferences": ["B"],      "consenting": true},
  {"id": "Elias", "preferences": ["A", "B"], "consenting": false}],

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

Resultat:

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

Eksempel 2

Dette eksempelet viser alle muligheter APIet gir: både samtykker og svake prioriteringer. Løsningen er at Kari, Lise og Gunvor alle får sine førsteønsker innvilget. Dersom Ola ikke gir samtykke, vil løsningen bli verre for de andre. Dersom de svake prioriteringene tas bort blir løsningen også verre.

{"data": {"persons": [{"id": "Kari",    "preferences": ["C", "A"]}, 
                      {"id": "Ola",     "preferences": ["C", "B"], "consenting": true},
                      {"id": "Petter",  "preferences": ["A", "C"]},
                      {"id": "Lise",    "preferences": ["B", "A", "C"]},
                      {"id": "Gunvor",  "preferences": ["A", "C", "B"]}], 

          "groups": [{"id": "A", "capacity": 1, 
                      "priorities": [["Kari", "Lise"], ["Petter", "Gunvor"]]}, 
                     {"id": "B", "capacity": 1, 
                      "priorities": ["Gunvor", "Ola", "Lise"]},
                     {"id": "C", "capacity": 1, 
                      "priorities":  [["Lise", "Gunvor", "Kari"], ["Ola", "Petter"]]}]
}}

Resultat:

{"Kari": "C", "Lise": "B", "Gunvor": "A"}