Fritt skolevalg del 1 - Geografi

Generelt om “fritt skolevalg”

Det går en debatt rundt “fritt skolevalg” om dagen. Regjeringen har et forslag på høring som omhandler å innføre karakterbasert opptak i alle fylker. Det vanligste alternativet til karakterbasert opptak er å basere seg på geografi. Både politikere og andre folk har meninger om hvordan inntak av elever skal gjøres.

Uansett hvilket system som ender opp med å bli brukt, er det til slutt en modell som vil fordele elever til skoler. Debatten mangler en konkret tilnærming til modeller – politikere har ønsker uten å nødvendigvis ha forståelse for hva som kan gjennomføres i praksis og hva implikasjonene av ulike modeller kan være.

Vi skal undersøke problematikken i tre artikler: geografi, karakterer og segregering. Denne artikkelen tar kun for seg geografi: først tar vi utelukkende hensyn til geografi, og deretter tar vi med elevenes prioriteter (ønsker). De to neste artiklene i trilogien vil ta for seg modeller for karakterer og segregering.

I denne artikkelen: Geografi

Vi begynner med å se på hvilke hensyn folk ønsker at en modell skal ta. Deretter drøfter vi utfordringer med rettferdighet som oppstår i ren geografisk fordeling og formulerer problemet som et optimeringsproblem. Dette er både teoretisk interessant og kan gjennomføres i praksis. Oslo har ca. \(7000\) elever i hvert trinn på VGS, og ca \(30\) skoler. Den matematiske modellen løses raskt – vi får en optimal løsning på under ett sekund.

Vi ser deretter på modeller for fordeling som tar hensyn til at elevene kan ha prioriteter over skolene. Når prioriteter er med i modellen er rettferdighet heller ikke uproblematisk: vi får en konflikt mellom fordelingens stabilitet og Pareto-effektivitet. Den gode nyheten er at også her finnes det algoritmer som garanterer optimal løsninger.

Innhold

Hensyn som en modell skal ta

Leser man debatter, innlegg og tilsvar til høringen er det tre faktorer som går igjen:

  • Geografi - mange mener at det er positivt om reisetiden er kort for elevene.
  • Karakterer - de fleste mener at karakterer og innsats bør gi positivt utslag.
  • Segregering - rent karakterbasert inntak kan føre til forskjeller mellom skolene.

Her er en samling sitater som oppsummerer hva folk mener:

Geografi

Selv om Rogaland praktiserer fritt skolevalg i hele fylket, har vi hatt noen geografiske forhold som tas med i betraktning i arbeidet med inntaket.” [kilde]

Elevenes rett til rimelig reisevei må sikres, også de med dårlige karakterer.” [kilde]

Karakterer

Som med alle andre systemer er ikke fritt skolevalg perfekt. Problemet er likevel aldri at elevene får lov til å velge selv.” [kilde]

I motsetning til tilfeldigheter som postnummer, er karakterer i hvert fall noe man kan påvirke selv.” [kilde]

Segregering

De skolene som får godt renommé, vil få flere søkere med gode karakterer. De andre skolene vil få de elevene som har dårligere karakterer. Denne sorteringa av elever er samfunnsmessig betenkelig.” [kilde]

Vi tror ikke på et system som samler elever med lave karakterer i samme klasserom. Det forsterker forskjellene i samfunnet vårt. Vi vil ha mindre ulikhet, ikke mer.” [kilde]

Motstridende meninger

Man kan ikke oppfylle alle krav samtidig – en faktor går nødvendigvis på bekostning av andre (med mindre den brukes som en ren tie-breaker).

Om valget skal ligge hos elevene må alle elever ha like store muligheter til å komme inn på den skolen og det tilbudet de ønsker.” [kilde]

Alle elever kan ikke ha like stor mulighet med mindre man bruker loddtrekning. Ved loddtrekning mister vi muligheten for en god geografisk fordeling.

Derfor skal man selvfølgelig ha mulighet til å ta lokale hensyn, så elever for slipper å reise mange timer hver vei. […] Problemet er likevel aldri at elevene får lov til å velge selv.” [kilde]

Tar man hensyn til geografi må det nødvendigvis gå utover ønsker. Unntaket er dersom elevenes ønsker sammenfaller med geografien, men det er et resultat av datasettet og ikke algoritmen. Vi ønsker å diskutere generelle algoritmer, ikke spesifikke datasett.

Fritt skolevalg er den mest rettferdige av mange urettferdige inntaksmodeller.” [kilde]

Dette er avhengig av definisjonen av “rettferdighet”, men også implementasjonen av algoritmen. Det er mange måter å implementere et karakterbasert inntak på, og noen av disse er mer urettferdige enn andre – dette kommer vil tilbake til i neste del av artikkelserien.

Geografisk fordeling uten prioriteter

Geografisk fordeling og rettferdighet

Selv når vi ignorerer elevenes prioriteter, karakterer og segregering det ikke åpenbart hva som er en rettferdig geografisk fordeling. Vi viser dette ved hjelp av et eksempel med \(2\) elever og \(3\) skoler, men tilsvarende utfordringer oppstår selvsagt i større fordelingsproblemer også.

Eksempel. Anta at vi har to elever \(e_1\) og \(e_2\). Det er tre skoler å velge mellom, men hver av disse har kun plass til én elev. Det er flere tenkelige løsninger på dette problemet

I figuren nedenfor ser vi elevene (svarte sirkler), skolene (hvite firkanter) og distansene (linjene som forbinder svarte sirkler og hvite firkanter) de må reise for å komme seg på skolen.

  • Løsning 1. Vi sender \(e_1\) til \(s_2\) og \(e_2\) til \(s_3\). Den totale distansen for begge elever blir \(1 + 18 = 19\). Elev \(e_1\) får kort reisevei mens elev \(e_2\) får lang reisevei. Fordelingen som løser dette problemet er \((1, 18)\), som angir distansene som henholdsvis \(e_1\) og \(e_2\) må reise.
  • Løsning 2. Vi sender \(e_1\) til \(s_1\) og \(e_2\) til \(s_2\). Den totale distansen for begge elever blir \(10 + 10 = 20\), og fordelingen i dette tilfellet er \((10, 10)\). Som vi ser får \(e_1\) betydelig lengre reisevei, mens reiseveien til \(e_2\) blir betydelig redusert.

Løsning 1 gir fordelingen \((1, 18)\) og minimerer summen av distansene. Dette fører til minst mulig reisetid i sum for elevene. Det er en god strategi for samfunnet som helhet, men kanskje ikke så rettferdig for elev \(e_2\).

Løsning 2 fører til at maksimal distanse blir \(10\). Summen av reisetiden er større, men reisetidene er mer jevnt fordelt. Den maksimale reisetiden til en elev er \(10\), og ikke \(18\) som i forrige løsning.

Vi kommer tilbake til denne utfordringen, men først formulerer vi fordelingen som et optimeringsproblem.

Geografisk fordeling som optimeringsproblem

Her formaliserer vi problemet litt og skisserer hvordan geografisk fordeling kan formuleres som et optimeringsproblem. Lesere som ikke er interessert i matematikken kan hoppe over de neste 3 seksjonene.

Notasjon og forutsetninger

La oss ta et steg bort fra politikk og løse et geografisk fordelingsproblem. Vi ser helt bort fra elevenes egne ønsker og eventuell segregering – fokuset er kun geografi.

Vi antar at summen av skolenes kapasitet (ledige plasser) er lik antall elever, men problemet kan løses når dette ikke er tilfellet også. Vi ignorerer linjene (e.g. elektrofag, studiespesialisering) som elever kan velge, og ser kun på elever og skoler.

  • Vi har en mengde elever \(E=\{e_1, e_2, \dots, e_i, \dots \}\).
  • Vi har en mengde skoler \(S=\{s_1, s_2, \dots, s_j, \dots \}\).
  • For hvert par \((e_i, s_j)\) har vi en distanse \(d_{ij}\) – målt i avstand (kilometer) eller reisetid (minutter).
  • Hver skole \(s_j\) har en kapasitet \(K_j\), som er antall elever det er plass til.

Geografisk fordeling som min-cost flow

Geografisk fordeling er et optimeringsproblem som kan løses i teori og praksis. Det kan formuleres som et såkalt Mixed Integer Program, eller som min-cost flow i et nettverk. Kantene i nettverket har ulike kapasiteter, og det er knyttet kostnader til hvordan man sender informasjon over nettverket. Algoritmer for min-cost flow har vært kjent siden 1960-tallet, og flere gode algoritmer løser problemet effektivt.

For å formulere problemet som min-cost flow lager vi et nettverk med noder og kanter:

  • Vi lager en source node \(s\). Fra noden \(s\) kobler vi en kant til hver elev \(e_i\). Kapasiteten settes til \(1\).
  • Mellom hver elev \(e_i\) og skole \(s_j\) lager vi en kant med kostnad lik distansen \(d_{ij}\). Kapasiteten settes til \(1\).
  • Vi kobler hver skole \(s_j\) til en sink node \(t\), og setter kapasitet \(K_j\) på kantene.

I source noden \(s\) legger vi til en supply lik antall elever. I sink noden \(t\) legger vi en demand lik antall elever. Oppgaven til min-cost flow nettverket er å minimere kostnaden av å “frakte” elevene fra \(s\) til \(t\). Variabelen \(x_{ij}\) blir satt til \(1\) dersom elev \(e_i\) blir plassert på skole \(s_j\), og \(0\) hvis ikke.

Flyten (flow) av elever inn i hver node må være lik flyten ut av hver node. Figuren nedenfor viser et lite nettverk som fordeler tre elever på to skoler. Kanten mellom \(e_3\) og \(s_1\) er ikke vist for å gjøre figuren litt mer ryddig.

Geografisk fordeling som et lineært problem

Alle min-cost flow problemer kan formuleres som lineære optimeringsproblemer. Her er en mulig formulering av dette problemet:

\begin{align} & \text{minimer} && \sum_i \sum_j d_{ij} x_{ij} \tag{total distanse}\\ & \text{gitt} && \sum_j x_{ij} = x_{si} && \forall \, i \tag{flow inn i $e_i$ lik flow ut}\\ & && \sum_i x_{ij} = x_{jt} && \forall \, j \tag{flow inn i $s_j$ lik flow ut} \\ & && \sum_i x_{si} = |E| && \tag{alle elever fordeles}\\ & && x_{jt} \leq K_j && \forall \, j && \tag{skolekapasiteter} \\ & && x_{si} \leq 1 && \forall \, i \\ & && x_{ij} \leq 1 && \forall \, (i, j) \\ \end{align}

Praktiske hensyn og kommentarer

Figuren nedenfor viser en fordeling av \(500\) elever på \(5\) skoler, der kapasiteten \(K_j = 100\) for alle skoler \(s_j\). Tenk deg at du ser på et kart, der skolene er firkanter med ulike fargekoder. Elevenes bosteder er representert ved sirklene, og disse er fargelagt etter hvilken skole algoritmen har plassert dem i.

  • I praksis ville man brukt modellen som veiledning og kjørt den flere ganger.
  • Valg av distanser er en implementasjonsdetalj. Man kan bruke distanse i luftlinje, distanse langs veier eller reisetid. Reisetid kan nok i praksis hentes via Google Maps sitt API.
  • I praksis fordeler vi elever med spesielle hensyn først. Fordeler man elever fra barneskoler til ungdomsskoler kan dette f.eks. innebære å fordele de som har eldre søsken på ulike skoler først.
  • Problemet kan løses ved hjelp av grafalgoritmer (min-cost flow solvere) eller mer generelle optimeringsalgoritmer (lineære solvere). Her er min-cost flow fornuftig fordi vi raskt får heltallsløsninger. Med andre ord: det gir ikke mening å sette \(x_{12} = 0.5\), vi må ha \(x_{12} = 0\) eller \(x_{12} = 1\).
  • Problemet løses raskt. Oslo har ca. \(7000\) VGS elever på hvert trinn og ca. \(30\) skoler. Det er ca \(10^{80}\) atomer i universet og \(10^{10279}\) mulige fordelinger av elevene. Min-cost flow løser problemet på \(0.1\) sekunder (simulerte data).

Rettferdighet i store problemer

I avsnittet om rettferdighet ovenfor studerte vi følgende eksempel:

  • Løsning 1. Vi sender \(e_1\) til \(s_2\) og \(e_2\) til \(s_3\). Løsningen \((1, 18)\) gir total distanse \(1 + 18 = 19\).
  • Løsning 2. Vi sender \(e_1\) til \(s_1\) og \(e_2\) til \(s_2\). Løsningen \((10, 10)\) gir total distanse \(10 + 10 = 20\).

Vi kan bruke min-cost flow til å få balanserte løsninger ved å endre målfunksjonen. Enhver glatt, monontont økende og konveks funksjon av \(d_{ij}\) er et fornuftig valg. Vi har mange muligheter, men det er vanlig å opphøye \(d_{ij}\) med \(p\). Med andre ord, vi endrer målfunksjonen fra

\begin{align} \sum_i \sum_j d_{ij} x_{ij} \qquad \text{til} \qquad \sum_i \sum_j d_{ij}^p x_{ij} \end{align}

og får en parameter \(p \in [ 1, \infty)\) som vi kan justere.

  • Når \(p=1\) minimerer vi summen av elevenes distanse.
  • Når \(p \to \infty\) minimerer vi maksimal distanse som en elev må reise.
  • Når \(p=2\) forsøker vi å balansere elevenes reisetid ved å minimere kvadratsummen.

Dersom vi setter \(p=2\), ser vi i det tidligere eksempelet at:

  • Mulighet 1. Vi sender \(e_1\) til \(s_2\) og \(e_2\) til \(s_3\). Den totale distansen blir \(1^2 + 18^2 = 325\).
  • Mulighet 2. Vi sender \(e_1\) til \(s_1\) og \(e_2\) til \(s_2\). Den totale distansen blir \(10^2 + 10^2 = 200\).

Når \(p=2\) får vi mulighet 2 som løsning, fordi dette gir lavest verdi.

Figuren nedenfor viser en fordeling med \(p=1\). Legg merke til at distansene som elevene må reise har ganske stor spredning.

Figuren nedenfor viser en fordeling med \(p=2\). Nå er distansene mer sentrerte rundt \(15\). Merk at dette er på bekostning av at elevene reiser lengre i sum. Elever som bor rett ved den blå skolen blir fordelt til den grønne og må belage seg på lengre reisetid for å hjelpe elever som bor lengre unna.

Geografisk fordeling med prioriteter

Geografi kan kombineres med elevenes ønsker, og flere effektive algoritmer finnes for dette problemet. Vi tenker oss at elev \(e_i\) har skole \(s_j\) som prioritet \(p_{ij}\). Eksempelvis betyr \(p_{21} = 1\) at elev \(e_2\) har skole \(s_1\) som første prioritet. Med andre ord: skolene prioriterer elevene ved hjelp av \(d_{ij}\) og elevene prioriterer skolene ved hjelp av \(p_{ij}\). Vi ønsker i utgangspunktet å gjøre elevene fornøyde i sine valg av skoler, men når mange elever prioriterer samme skole bruker vi skolen sin prioritet til å velge elever.

For å forstå problematikken som oppstår i slike situasjoner trenger vi noen begreper.

Notasjon og begreper

Funksjonen \(P: E \to \mathbb{Z}_+\) gir innvilget prioriteter til elever under en fordeling. Eksempelvis betyr \(P(e_1, e_2) = (1, 2)\) at elev \(e_1\) fikk sitt førstevalg og \(e_2\) fikk sitt andrevalg.

  • Pareto-dominasjon. En fordeling \(a\) dominerer en fordeling \(b\) dersom ingen av prioritetene i \(a\) er verre enn prioritetene i \(b\), og minst én elev har bedre prioritet i \(a\). Eksempelvis dominerer fordelingen \(P_a(e_1, e_2) = (1, 1)\) fordelingen \(P_b(e_1, e_2) = (2, 1)\). Ingen av fordelingene \(P_a(e_1, e_2) = (1, 2)\) og \(P_b(e_1, e_2) = (2, 1)\) dominerer hverandre.
  • Stabilitet. En fordeling er stabil dersom den eliminerer misunnelse. Misunnelse oppstår hvis det finnes en elev \(e_i\) som foretrekker en skole \(s_j\) fremfor skolen han fikk, og skolen \(s_j\) også foretrekker ham fremfor minst én av sine elever.
  • Elev \(e_1\) er “misunnelig” på \(e_2\)
  • Pareto-effektivitet. En fordeling \(a\) er Pareto-effektiv dersom det ikke finnes noen andre fordelinger som dominerer \(a\). Et problem kan ha flere fordelinger som er Pareto-effektive.

Stabilitet vs. Pareto-effektivitet

Generelt er det en trade-off mellom stabilitet og Pareto-effektivitet. Figuren nedenfor viser skoler og elever på et kart (avstander er representative for avstander i problemet), der hver skole \(s_j\) har kapasitet \(K_j = 1.\) Pilene viser elevers prioriteter. De små linjene som går på tvers av pilene indikerer prioriteringene til hver elev (f.eks. betyr tre linjer at eleven hadde denne skolen på tredje plass i søknaden).

Figuren ovenfor viser et problem der fordelingen \(P_{\text{stabil}}(e_1, e_2, e_3) = (2, 2, 2)\) er vist med tykke piler. Fordelingen vist med tykke piler er stabil, men ikke Pareto-effektiv.

  • Å bekrefte at fordelingen er stabil innebærer å sjekke at ingen elever opplever misunnelse. La oss bekrefte at \(e_2\) ikke opplever misunnelse. Han foretrekker skolen \(s_1\) fremfor sin skole \(s_3\), men \(s_1\) foretrekker ikke \(e_2\) fremfor sin elev \(e_1\) (fordi distansen til \(e_2\) er større enn distansen til \(e_1\)).
  • For å bekrefte at fordelingen ikke er Pareto-effektiv viser vi et moteksempel nedenfor: en fordeling som dominerer \(P_{\text{stabil}}\).

Figuren ovenfor viser et problem der fordelingen \(P_{\text{effektiv}}(e_1, e_2, e_3) = (1, 1, 2)\) er vist med tykke piler. Fordelingen er Pareto-effektiv, men ikke stabil.

  • For å bekrefte at fordelingen er Pareto-effektiv må man bekrefte at det ikke finnes en fordeling som dominerer \(P_{\text{effektiv}}\). Den eneste fordelingen som kan dominere \(P_{\text{effektiv}}\) er \(P(e_1, e_2, e_3) = (1, 1, 1)\), og denne fordelingen kan ikke oppnås.
  • For å bekrefte at fordelingen er ustabil må vi finne en elev som opplever misunnelse. Elev \(e_3\) foretrekker \(s_1\) fremfor \(s_3\), og \(s_1\) foretrekker \(e_3\) fremfor sin innvilgede elev \(e_2\). Elev \(e_3\) opplever misunnelse, derfor er \(P_{\text{effektiv}}\) ustabil.

Valget mellom stabilitet og Pareto-effektivitet må avgjøres av en beslutningstaker. I USA har stabilitet blitt brukt for å unngå søksmål som kan oppstå når en elev opplever misunnelse. Valget er til dels avhengig av om man tolker det som at en elev har rettighet eller større mulighet for bli plassert på nærliggende skoler. I eksempelet ovenfor er fordelingen \(P_{\text{effektiv}}\) ikke verre for noen elev enn fordelingen \(P_{\text{stabil}}\).

Praktiske hensyn og kommentarer

Uansett om man går for stabilitet eller Pareto-effektivitet finnes det algoritmer som garanterer optimale løsninger:

  • Gale-Shapley algoritmen som ble introdusert i artikkelen “College Admissions and the Stability of Marriage” av Gale et al. i 1962 finner garantert en stabil fordeling som ikke er dominert av noen andre stabile fordelinger. Løsningen er optimal blant alle stabile fordelinger. Merk at fordelingen som Gale-Shapley algoritmen finner fremdeles kan være dominert av ustabile fordelinger.
  • Top Trading Cycles (TTC) algoritmen som beskrives i artikkelen “School Choice: A Mechanism Design Approach” av Abdulkadiroğlu et al. i 2003 finner garantert en effektiv fordeling – den er ikke dominert av noen andre fordelinger, stabile eller ikke. Ulempen er at fordelingen som TTC finner ikke nødvendigvis er stabil.

Begge algoritmene er enkle, men for å unngå en veldig lang artikkel beskrives de ikke her.

Oppsummering

Når man kun tar hensyn til geografi, er fordeling av elever på skoler et problem som kan løses både i teori og praksis. Bruker man en optimeringsmodell er man garantert at det ikke finnes noen bedre løsning. Beslutningstakere må velge en verdi for \(p\) i målfunksjonen i min-cost flow som sier noe om oppfattelsen av hva som er en rettferdig balanse mellom individuelle distanser og summen av distansene.

Geografi og elevenes egne ønsker kan kombineres til å fordele elever på best mulig måte. Elevene prioriterer individuelt skolene, og skolene prioriterer elevene basert på distanse. Beslutningstakere må velge hva som er viktigst av stabilitet og Pareto-effektivitet. Uansett hvilken modell man velger finnes det gode algoritmer.

I Norge i dag er geografiske hensyn en del av fordelingen i flere fylker. Personlig har jeg ikke innsikt i hvordan dette løses i praksis. Dersom modellene vi har diskutert ikke blir brukt av beslutningstakere, bør de absolutt vurderes – elevene vil få bedre reisetider, bli mer fornøyde og skolenes kapasiteter kan utnyttes bedre.

Notater og referanser

  • Allerede i 1973 ble artikkelen “Computed School Assignments in a Large District” publisert av Allen D. Franklin. Han formulerer problemet med en lineær modell og foreslår \(p=2\). Ved å klassifisere studenter i raser og karaktergrupper gir han en modell som fordeler slik at etnisitet- og karakterforskjeller blir små. I 1973 var det nok utfordrende å behandle data, implementere algoritmer og få ut en løsning i praksis. Han skriver “The major difficulty in most school-redistricting problems is the assembly of a database.” I dag er data tilgjengelig og problemet kan enkelt løses i praksis.
  • For mer informasjon om stabilitet og Pareto-effektivitet kan man lese “College Admissions and the Stability of Marriage” av Gale et al., “School Choice: A Mechanism Design Approach” av Abdulkadiroğlu et al. og “A Cost-Minimizing Algorithm for School Choice” av Aksoy et al. Den sistnevnte artikkelen løser problemet med min-cost flow over prioritetene og ignorerer geografien.
  • Skolenes prioriteter over elevene trenger ikke nødvendigvis å være basert på distanser: antall søsken som allerede går på skolen, elevens karaktersnitt og andre egenskaper ved elever kan brukes. På en side er det en fordel at modellen er så enkel at elever, foresatte og beslutningstakere kan forstå den. På en annen side er eventuell manglende forståelse ingen unnskyldning for å bruke dårlige modeller.

En stor takk til Sean Meling Murray og Gunvor Lemvik for verdifulle innspill til artikkelen.