6.5 Stabil matching — Gale-Shapley

`Gale-Shapley`-algoritmen, blokkerende par, stabil matching og mann-/kvinneorientert kjøring — en fremvoksende gjenganger.

50 min

6 oppgaver

Stabil matchingGale-Shapley

Din fremgang i kapitlet

0 / 6 oppgaver

Kapitlets plass i kurset

Bygger på

6.4Grådighet — Huffman og aktivitetsutvelgelse

Brukes videre i

6.PPrøver til del 6: Dynamisk programmering, grådighet og stabil matching

Stabil matching er registrert i 2 av de 17 settene i grunnlaget — men
verifisert til stede i 6 av de 7 settene med dagens hjelpemiddelkode E (des
2022 til aug 2025), fraværende bare i des 2025. Regn med at den kommer.

De 17 settene fra august 2015 til august 2023 er grunnlaget for alle
prosentene i denne boka, og de stopper i august 2023. Tallet 2 av 17 er derfor
et historisk tall, og det undervurderer temaet kraftig: i settene med dagens
eksamensordning er Gale-Shapley nesten fast inventar.

Prioritet i skjelettet er kjenne til, men behandle den som noe du må
kunne. Kapitlet er kort, og gevinsten er stor.

Tre sjangre henter fra kapitlet, og de skrives ut i klarspråk her:

- Sjanger D — definisjon med egne ord, altså én presis setning med
hovedpoenget først. «Definér et blokkerende par» er den klassiske.
- Sjanger C — håndkjøring, altså at du utfører algoritmen steg for steg og
oppgir bare sluttilstanden. Svarformen er den ferdige matchingen, og
hvilken orientering du kjørte — det siste avgjør hvilken matching du får.
- Sjanger H — åpen algoritmedesign, altså en kort skisse. Den klassiske
her: «kan disse to være paret i en stabil matching?»

Slik er kapitlet lagt opp (50 min):

Innhold	Tid
Stabil matching og blokkerende par	ca. 12 min
`Gale-Shapley`, steg for steg	ca. 16 min
Egenskapene: terminering, stabilitet og frier-optimalitet	ca. 12 min
Å bruke algoritmen som designverktøy	ca. 10 min

Forkunnskaper

- kap. 6.4 — grådighet. Gale-Shapley er grådig i
ånden: hver frier går alltid til den beste som ennå ikke har avvist henne, og
det valget angres aldri. Argumentet for at det virker, ligner
bytteargumentet derfra.
- kap. 1.1 — de asymptotiske symbolene. Kjøretiden er
$O(n^2)$ , og tellingen er kort nok til å gjøres i hodet.

Ingen andre forkunnskaper trengs. Dette kapitlet er selvstendig, og det er en
del av grunnen til at det er verdt å ta tidlig hvis du er i tidsnød.

Merk at flyt ikke brukes her. Stabil matching er et annet problem enn den
maksimale matchingen i kap. 5.3: der handler det om
hvor mange som kan pares, her om hvem som pares med hvem, gitt
preferanser.

Notasjons- og pseudokodeliste

Stabil matching og blokkerende par (~12 min)

Hvert år søker tusenvis av studenter opptak til studieplasser. Studentene har
en rangert liste over studier, og studiene har en rangert liste over søkere. Å
fordele plassene handler ikke bare om å få flest mulig plassert — det handler
om å plassere dem slik at ingen to parter har grunn til å hoppe av avtalen.

Det er nettopp den siste egenskapen som kalles stabilitet, og den er
overraskende presis.

Matching

M(x)

Blokkerende par

(f, m)

Stabil matching

en matching er stabil når det ikke finnes noe blokkerende par. Da har ingen to parter et felles motiv for å bryte ut av tildelingene sine. Stabil betyr ikke optimal for alle. En stabil matching kan gi noen deres tredjevalg; den lover bare at ingen to kan forbedre seg sammen .

✏️Eksempel 1: Er denne matchingen stabil?

Fire søkere og fire lag har disse preferanselistene, best først:

Alma:  Ravn, Solve, Tind, Ulv        Ravn:  Birk, Alma, Dag, Cora
Birk:  Solve, Ravn, Ulv, Tind        Solve: Alma, Cora, Birk, Dag
Cora:  Ravn, Tind, Solve, Ulv        Tind:  Cora, Dag, Alma, Birk
Dag:   Solve, Tind, Ravn, Ulv        Ulv:   Dag, Birk, Cora, Alma

Er matchingen Alma–Tind, Birk–Solve, Cora–Ravn, Dag–Ulv stabil?

Framgangsmåten er mekanisk: gå gjennom hver søker, se på alle lagene hun
rangerer høyere enn sitt eget, og sjekk om noen av dem rangerer henne
høyere enn sitt eget.

Søker	Har	Foretrekker	Vil laget bytte?
Alma	Tind	Ravn, Solve	Ravn har Cora og rangerer Alma foran Cora — ja
Birk	Solve	— (Solve er førstevalget)	—
Cora	Ravn	— (Ravn er førstevalget)	—
Dag	Ulv	Solve, Tind, Ravn	Tind har Alma og rangerer Dag foran Alma — ja

Svaret: nei, matchingen er ikke stabil.
Den blokkeres blant annet av paret (Alma, Ravn): Alma foretrekker Ravn
framfor Tind, og Ravn foretrekker Alma framfor Cora. Ett slikt par er nok.
Fullstendig finnes 4 blokkerende par her:
(Alma, Ravn), (Alma, Solve), (Dag, Tind), (Dag, Ravn).

Legg merke til at Birk og Cora begge har fått førstevalget sitt. Det hjelper

ikke — stabilitet er en egenskap ved hele matchingen, ikke ved den enkelte.
Svarformen på eksamen: «Nei — (Alma, Ravn) er et blokkerende par, fordi

Alma foretrekker Ravn framfor Tind og Ravn foretrekker Alma framfor Cora.» To
linjer. Du trenger ikke liste alle de blokkerende parene når oppgaven bare

spør om matchingen er stabil.

📝Oppgave 1

(Innstegsoppgave, sjanger D — definisjon med egne ord, altså én presis setning
med hovedpoenget først.)

Definér et blokkerende par, og forklar med én setning hva det betyr at en
matching er stabil.

`Gale-Shapley`, steg for steg (~16 min)

Det bemerkelsesverdige er at en stabil matching alltid finnes, uansett
hvordan preferanselistene ser ut — og at den kan finnes med en algoritme som
er enkel nok til å håndkjøres på fem minutter.

📜Pseudokode-kontrakt: `Gale-Shapley`

Antagelser om representasjon. To sider med

n

deltakere hver. Hver
deltaker har en fullstendig rangering av alle på den andre siden. Den ene
siden utpekes som friere, den andre som mottakere — dette valget kalles
orienteringen, og det er en del av oppgaven.

Prebetingelse: begge sider har fullstendige preferanselister.
Postbetingelse: algoritmen returnerer en matching som er stabil, og som
er den beste mulige for hver eneste frier blant alle stabile matchinger.

Gale-Shapley(F, M)
  Input:  friere F og mottakere M med fullstendige preferanselister
  Output: en stabil matching
  alle i F og M er ledige
  while det finnes en ledig frier f som ikke har fridd til alle
      m = den hoeyest rangerte paa f sin liste som ikke har avvist f
      if m er ledig
          par f og m
      else if m foretrekker f framfor sin naavaerende g
          par f og m
          g blir ledig igjen
      else
          m avviser f
  return matchingen
  Kjoeretid: O(n^2)

Invarianten i én setning: en mottaker som først har blitt paret, forblir
paret resten av kjøringen — og hun bytter bare oppover på sin egen liste.

Legg merke til asymmetrien. Frierne beveger seg nedover på listene sine:
hver gang de blir avvist, går de til neste. Mottakerne beveger seg oppover:
de bytter bare når et bedre tilbud kommer. Det er denne asymmetrien som gjør at
orienteringen betyr noe.

Kjøretid: $O(n^2)$ . Hver frier frir til hver mottaker høyst én gang —
en avvisning er endelig — så det finnes høyst $n^2$ frierier, og hvert koster
konstant tid med en rangtabell.

✏️Eksempel 2: `Gale-Shapley` med søkerne som friere

Bruk preferanselistene fra Eksempel 1.

Kjør Gale-Shapley med søkerne som friere. Ledige friere behandles i
alfabetisk rekkefølge.

Oppgi den ferdige matchingen.

Steg	Frieri	Hva som skjer
1	Alma frir til Ravn	Ravn var ledig og tar imot
2	Birk frir til Solve	Solve var ledig og tar imot
3	Cora frir til Ravn	Ravn beholder Alma — Cora frir videre
4	Cora frir til Tind	Tind var ledig og tar imot
5	Dag frir til Solve	Solve beholder Birk — Dag frir videre
6	Dag frir til Tind	Tind beholder Cora — Dag frir videre
7	Dag frir til Ravn	Ravn beholder Alma — Dag frir videre
8	Dag frir til Ulv	Ulv var ledig og tar imot

Sluttilstanden — det du ville levert på eksamen:
Matchingen er Alma–Ravn, Birk–Solve, Cora–Tind, Dag–Ulv,
kjørt med søkerne som friere.
Tre ting er verdt å studere i tavlen.
For det første: Cora blir avvist av Ravn i steg 3 og går videre til Tind. Hun
kommer aldri tilbake til Ravn — en avvisning er endelig, og det er nettopp det
som gir kjøretiden

O(n^2)

.
For det andre: Dag frir fire ganger før han lander. Han er sist ute og møter
lag som allerede har bedre tilbud. Det er ikke urettferdig, det er

preferanselistene.

For det tredje: ingen mottaker byttet ut noen underveis i denne kjøringen —
alle avvisningene skjedde ved at mottakeren beholdt den hun hadde. Det skjer

ikke alltid, men det gjør tavlen kort her.

Kontrollen før du leverer: fire par, alle fire søkere og alle fire lag
brukt nøyaktig én gang. Og — hvis du har tid — sjekk raskt at ingen blokkerende
par finnes.

📝Oppgave 2

Eksamensnivå, sjanger C

Tre studenter og tre veiledere har disse preferanselistene, best først:

Iben:  Sol, Nord, Vest        Sol:   Kian, Iben, Lea
Kian:  Sol, Vest, Nord        Nord:  Iben, Lea, Kian
Lea:   Nord, Sol, Vest        Vest:  Lea, Kian, Iben

Kjør Gale-Shapley med studentene som friere, i alfabetisk rekkefølge.

Oppgi den ferdige matchingen.

Egenskapene: terminering, stabilitet og frier-optimalitet (~12 min)

Tre påstander skal sitte, og de er alle korte nok til å skrives på én linje
hver på eksamen.

📜De tre egenskapene til `Gale-Shapley`

1. Algoritmen terminerer, og alle blir paret.

Hver frier frir til hver mottaker høyst én gang, så det finnes høyst $n^2$
frierier og løkka må stoppe. At alle blir paret følger av et lite argument:
var en frier ledig til slutt, ville hun ha fridd til alle $n$ mottakerne og
blitt avvist av hver. Men en mottaker som har blitt fridd til, forblir paret
resten av kjøringen — så alle $n$ mottakerne ville vært opptatt, og da måtte
alle $n$ frierne vært paret. Selvmotsigelse.

2. Matchingen er alltid stabil.

Anta at $(f, m)$ blokkerer: $f$ foretrekker $m$ framfor sin egen, og $m$
foretrekker $f$ framfor sin egen. Siden $f$ foretrekker $m$ , må $f$ ha fridd
til $m$ tidligere — friere går strengt nedover listen. Da må $m$ ha avvist $f$
eller byttet henne ut senere, og mottakere bytter bare oppover. Altså står
$m$ nå med noen hun rangerer over $f$ — i strid med antagelsen.

3. Matchingen er frier-optimal.

Hver eneste frier får den beste partneren hun kan få i noen som helst
stabil matching. Samtidig får hver mottaker den dårligste hun kan få i noen
stabil matching. Fordelen ligger altså hos den som frir.

Konsekvensen for eksamen: matchingen er ikke entydig. Bytter du
orientering, kan du få en annen — og begge er stabile. Derfor skal svaret på en
håndkjøring alltid si hvilken orientering du kjørte.

✏️Eksempel 3: Den motsatte orienteringen

Bruk de samme preferanselistene som i Eksempel 1 og 2, men kjør nå
Gale-Shapley med lagene som friere, i alfabetisk rekkefølge.

a) Oppgi matchingen.
b) Sammenlign med resultatet fra Eksempel 2.

Steg	Frieri	Hva som skjer
1	Ravn frir til Birk	Birk var ledig og tar imot
2	Solve frir til Alma	Alma var ledig og tar imot
3	Tind frir til Cora	Cora var ledig og tar imot
4	Ulv frir til Dag	Dag var ledig og tar imot

Matchingen er Alma–Solve, Birk–Ravn, Cora–Tind, Dag–Ulv,
kjørt med lagene som friere.
Ingen avvisninger i det hele tatt: hvert lag fridde til sitt førstevalg, og alle
fire var ledige. Det er ikke typisk, men det er hva disse listene gir.
b) Sammenligningen:

Søker	Søkerne frir	Lagene frir
Alma	Ravn	Solve
Birk	Solve	Ravn
Cora	Tind	Tind
Dag	Ulv	Ulv

Alma og Birk bytter plass; Cora og Dag får det samme uansett.

Og det er nøyaktig som forventet av frier-optimaliteten. Alma har Ravn som
førstevalg og får ham når hun selv frir; når lagene frir, får hun Solve — som

er hennes andrevalg. Ravn har Birk som førstevalg og får ham når lagene

frir.
Begge matchingene er stabile. Det kan du kontrollere ved å lete etter
blokkerende par i begge — det finnes ingen.
Fellen her er å tro at matchingen er entydig. Det er den ikke, og derfor er
orienteringen en del av svaret.

📝Oppgave 3

Eksamensnivå, sjanger F

Ta stilling til hver av påstandene om Gale-Shapley:

a) Algoritmen kan i noen tilfeller ende opp uten å pare alle.
b) Matchingen algoritmen finner, er entydig bestemt av preferanselistene.
c) Algoritmen er $O(n^2)$ .
d) Hver mottaker får sin best mulige partner blant alle stabile
matchinger.

Å bruke algoritmen som designverktøy (~10 min)

Den siste sjangeren er den mest krevende, og den kommer som en kort
designoppgave: kan disse to være paret i en stabil matching?

Svaret bygger på frier-optimaliteten, og oppskriften er kort.

Å avgjøre om et bestemt par er mulig

O(n^2)

📝Oppgave 4

Eksamensnivå, sjanger H

Bruk preferanselistene fra Eksempel 1.

Kan Alma og Tind være paret i en stabil matching? Begrunn.

📝Oppgave 5

Eksamensnivå, sjanger F…

En kandidat skriver: «Stabil matching og maksimal matching er det samme
problemet — begge parer to sider med hverandre, så begge kan løses med
maks-flyt.»

Er utsagnet riktig? Svar ja eller nei, og forklar forskjellen.

📝Oppgave 6

Eksamensnivå, sjanger…

Bruk preferanselistene fra oppgave 2 (Iben, Kian, Lea mot Sol, Nord, Vest).

a) Kjør Gale-Shapley med veilederne som friere.
b) Får noen et annet resultat enn i oppgave 2?

Typiske feil

De to første koster hele oppgaven.

- Å tro at matchingen er entydig. Orienteringen avgjør: den siden som frir,
får sitt beste mulige stabile utfall, den andre sitt dårligste. Svaret på en
håndkjøring skal derfor si hvilken orientering du kjørte.
- Å snu frier-optimaliteten. Det er frierne som kommer best ut, ikke
mottakerne. Mottakerne bytter bare oppover, men de får likevel sitt dårligst
mulige stabile utfall.
- Å blande stabil matching med maksimal matching. Maksimal matching spør
hvor mange, og løses med maks-flyt. Stabil matching spør hvem, og krever
preferanser.
- Å tro at ett blokkerende par må gjøre begge misfornøyde med alt. Kravet
er bare at begge foretrekker hverandre framfor sine egne tildelinger. At
én er misfornøyd, holder ikke.
- Å la en frier gå tilbake til en som har avvist henne. En avvisning er
endelig. Det er nettopp det som gir grensen på $n^2$ frierier.
- Å la en mottaker bytte nedover. Mottakere bytter bare til noen de
rangerer høyere enn den de har.
- Å oppgi $O(n)$ som kjøretid. Den er $O(n^2)$ : hver av de $n$ frierne kan
fri til hver av de $n$ mottakerne.

Og den gjennomgående: å skrive en lang forklaring når svaret er en
matching. Fire par på én linje, pluss orienteringen. Det er hele svaret.

Kjøretidene samlet

Dette er kapitlets puggeflate. Eksamen er hjelpemiddelfri, så tabellen må ligge
i hodet.

Operasjon	Kjøretid	Krav / egenskap
`Gale-Shapley`	$O(n^2)$	krever fullstendige preferanselister på begge sider
Ett frieri	$\Theta(1)$	med en rangtabell for oppslag av «foretrekker»
Antall frierier	høyst $n^2$	hver frier frir til hver mottaker høyst én gang
Å sjekke om en matching er stabil	$O(n^2)$	gå gjennom alle par og se etter blokkerende par
Begge orienteringer	$O(n^2)$	to kjøringer; rammer inn hele rommet av stabile utfall
Maksimal matching via flyt	$O(VE^2)$	et annet problem — se kap. 5.3

Én presisering som er verdt å ta med seg. Gale-Shapley er den eneste
algoritmen i denne boka som svarer på et spørsmål om preferanser. Alle de
andre optimerer et tall — lengde, vekt, verdi, flyt. Her er det ingen
målfunksjon å maksimere; kravet er bare fraværet av blokkerende par.

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp
har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet
gjelder kjernestoffet.

Stabil matching

O(n^2)

Blokkerende par

et par som ikke er sammen, men der begge foretrekker hverandre framfor sine egne tildelinger. Ett eneste blokkerende par gjør matchingen ustabil. Kravet om at begge foretrekker er det som gjør stabile matchinger mulige i det hele tatt.

`Gale-Shapley`

O(n^2)

Orientering

hvilken av de to sidene som frir. Valget avgjør hvilken stabil matching du får, og det skal oppgis i svaret på en håndkjøring. Finnes bare én stabil matching, gir begge orienteringene den samme — og da er «best» og «dårligst» det samme.

Frier-optimalitet

hver frier får den beste partneren hun kan få i noen som helst stabil matching. Samtidig får hver mottaker den dårligste hun kan få i noen stabil matching. Fordelen ligger hos den som tar initiativ — det er den setningen som oftest snus feil vei på eksamen.

Terminering av `Gale-Shapley`

n^2

Stabilitetsargumentet

(f,m)

Mottakerens byttestrategi

en mottaker beholder alltid det beste tilbudet hun har fått, og bytter bare til noen hun rangerer høyere . Derfor forblir hun paret resten av kjøringen når hun først har fått et tilbud. Hun beveger seg bare oppover — mens frierne beveger seg nedover på sine lister.

Frierens strategi

n^2

Stabil mot maksimal matching

maksimal matching spør hvor mange som kan pares, og løses med maks-flyt. Stabil matching spør hvem som pares med hvem, gitt preferanser. I stabil matching er antallet ikke noe problem — alle kan alltid pares. Et flytnett har ingen plass til rangeringer, og derfor kan ikke stabil matching løses med flyt.

Preferanseliste

en fullstendig rangering av alle deltakerne på den andre siden, best først. Både friere og mottakere har en. Fullstendigheten er en forutsetning for at algoritmen skal kunne pare alle.

Sjanger C — håndkjøring

oppgavetypen der du utfører algoritmen steg for steg og oppgir sluttilstanden. Svarformen her er den ferdige matchingen og hvilken orientering du kjørte . Kontrollen: alle på begge sider skal være brukt nøyaktig én gang.

Sjanger D — definisjon med egne ord

oppgavetypen der du forklarer et begrep presist og kort. «Definér et blokkerende par» er den klassiske fra dette kapitlet. Hovedpoenget først: at begge foretrekker hverandre framfor sine egne tildelinger.

Sjanger H — «kan disse to være paret?»

O(n^2)

Repetisjonsoppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.