Stable Matching na Uniwersytecie Kalifornijskim w Berkeley

By Daniel Kaszyński
ogólne

Czy warto proaktywnie szukać, czy czekać na okazje?

Dziś chciałbym chwile opowiedzieć o problemie, z którym się zapoznałem podczas wyjazdu do Simons Laufer Mathematics Institute; instytut działający przy Uniwersytecie Kalifornijskim w Berkeley. Wyjazd miał miejsce w dniach 19-26 listopada 2023 r. i był związany z realizowanymi badaniami w ramach programu NAWA. Poniżej fotka ;)

drawing

Przedstawiony w niniejszym wpisie problem został mi szczegółowo i dokładnie przedstawiony przez prof. Pawła Prałata. UWAGA: wszelkie nieścisłości i błędy zawarte w tym wpisie, mają jedynie jednego autora: ja nim jestem!

Przejdźmy jednak do rzeczy.

Założenia problemu

Załóżmy, że mamy dwie grupy interesariuszy: osoby z niebieskimi koszulkami ($B$ - blue) oraz osoby noszące koszulki czerwone ($R$ - red)$^1$. Przyjmijmy również, że liczba osób / jednostek w każdej z grup jest taka sama; liczba ta nazywana będzie dalej $n$ (np. gdy $n=5$ to oznaczy, że mamy $10$ osób: $5$ niebieskich, i $5$ czerwonych). Każda z osób, zarówno w grupie $B$ i $R$, ma jakąś permutację preferencji wyboru osób, w drugiej grupie.

Dla przykładu:

$B_{3, 1:6} = [6, 2, 1, 4, 5, 3]$
$R_{3, 1:6} = [2, 1, 6, 4, 3, 5]$

Na liście preferencji 3 aktora w niebieskiej koszulce, $B_{3}$, każda liczba oznacza preferencję jaką $B_{3,}$ darzy poszczególne osoby w koszulkach czerwonych $R$. Im niższy indeks preferencji (tj. $1$ jest najniższy, potem $2$, $3$, $\dots$, $n$), tym większą mamy preferencje do danego reprezentanta grupy przeciwnej$^2$.

Oznacza to, że $3$ blue-man najmniej ceni sobie $R_{1,}$: pierwsza wartość dla $B_{3}$ to $6$, czyli $R_{1}$ jest na ostatniej możliwej pozycji względem preferencji $B_{3}$. Dalej, $B_{3}$ bardzo ceni $R_{2,}$ (pozycja $2$), a najbardziej ceni $R_{3,}$ (pozycja $1$) - patrz na kolejne wartości wektora $B_{3,}$.

Niestety, w tym przypadku preferencje $B_{3,}$ nie są odwzajemnione przez preferencje $R_{3,}$; czerwony o nr. $3$ najbardziej preferował niebieskiego o numerze $2$). $R_{3,}$ ocenia $B_{3,}$ bardzo nisko – ostatnia pozycja na liście preferencji (patrz na wartość R_{3,3}).

Z przyjętej notacji możemy wnioskować, ze zarówno $B$ jak i $R$ beda macierzami kwadratowymi o wymiarach $6 \times 6$; w ogólności $n \times n$.

Pytanie o realizację preferencji

OK. Dla zadanego kontekstu sytuacji – niebiescy, czerwoni, ich preferencje – pytania, jakie nam się nasuwają to:

  1. Czy istnieje stabilne parowanie – ang. matching – osób z $B$ i $R$. Parowanie stabilne rozumiane jest tutaj jako takie parowanie, w którym nie możemy wymienić “partnerów” żadnych z dwóch par, i każdy jest z tego zadowolony (tj. każdej osobie z $B$ i $R$ poprawiła się pozycja w preferencjach jego partnera).$^3$
  2. Mając stabilne parowanie, która z grup jest średnio “bardziej” zadowolona z tego parowania; tj. która z grup $B$ czy $R$ ma średnio niższy indeks sparowanego partnera. Gdyby każdy z nas dostał się na wymarzone studia, to każdy z nas miałby indeks sparowanego uniwersytetu równy $1$ – czyli średnia wynosiłaby również $1$).

Na pierwsze pytanie odpowiedział David Gale i Lloyd Shapley. Wykazał on, że da się skonstruować stabilne parowanie (tzw. stable matching), a procedura tego parowania jest następująca:

  1. Dla pierwszego z grupy $B$ przypisujemy matching równy jego najbardziej preferowanej jednostce w $R$ (np. $B_1$ preferował najbardziej $R_3$).
  2. Dla drugiego z grupy $B$ przypisujemy matching równy jego najlepszej pozycji względem jego preferencji; teraz może zaistnieć jedna z dwóch sytuacji:
    • BRAK KONFLIKTU Przypisanie $B_2$ jest różne od $R_3$ (np. $B_2$ mógłby najbardziej preferować $R_1$), albo
    • KONFLIKT Przypisanie $B_2$ jest takie samo jak dla $B_1$, czyli $R_3$ (lub ogólniej dla któregokolwiek $B$). Wtedy sprawdzamy preferencje $R_3$ – czy bardziej woli $B_1$ czy $B_2$; wybierany jest ten, którego woli $R_3$. Jeżeli $R_3$ odrzuci $B_2$, to $B_2$ musi wybrać kolejną pod względem preferencji jednostkę z $R$; jeżeli $R_3$ odrzuci $B_1$, to $B_1$ musi zacząć szukać sobie nowego parowania (i patrzy na swoją listę preferencji).
  3. Działamy analogicznie dalej dla wszystkich kolejnych jednostek z grupy $B$.

Co do zasady algorytm działa tak: $B$ składają po kolei propozycje parowania dla $R$, używając przy tym indywidualnych list preferencji.

Jeżeli $R$ nie mają jeszcze parowania, to przyjmują propozycje $B$; jeżeli już mają parowania, to sprawdzają, czy nowa propozycja partnera nie jest lepsza (pod względem preferencji $R$), od propozycji wcześniej przyjętej; jeżeli tak jest, to odrzucają poprzednia i przyjmują nową; jeżeli nie to pozostają przy poprzedniej).

Mając na względzie przedstawiony algorytm postępowania, widać jasno, że występuje różnica w postępowaniu: $B$ są proaktywni (składają propozycje), a $R$ są reaktywni (przyjmują albo odrzucają propozycje $B$).

Mam nadzieję, że Pytanie 2 zaczyna nabierać sensu: kto będzie miał lepszą wartość realizowanej preferencji: proaktywni $B$ czy reaktywni $R$.$^4$

Na pierwszy rzut oka może wydawać się, że lepiej być w grupie $R$ – w końcu czekamy na pierwszą propozycję, a potem, jeżeli pojawi się coś lepszego, to możemy odrzucić poprzedni wybór i przejść do nowej propozycji. Powiedzielibyśmy: wydaje się, że strategia “cherry-picking” jest lepsza. Ja przynajmniej taką intuicję miałem jak się pierwszy raz zapoznałem z tym problemem…

Posymulujmy…

Otóż nie… Jakby powiedział Pan Piotr Fronczewski,,Przed rozwiązaniem zadania należy zabrać się za symulacje’’. Symulacja posłuży nam do weryfikacji, która z grup posiada lepszą wartość średniej preferencji. Symulacje przygotowałem w języku R.

# Losujemy liste preferencji B i R.
rm(list=ls())
n <- 100

b <- matrix(NA, nrow=n, ncol=n)
r <- matrix(NA, nrow=n, ncol=n)
m <- rep(NA, n)

for(i in 1:n){
  b[i, ] <- sample(1:n, n)  
  r[i, ] <- sample(1:n, n)
}

Easy – wygenerowaliśmy macierze B i R z preferencjami (pamiętaj: w kolumnach B i R są informacje, jak bardzo prefereują jednostki z przeciwnej grupy, np. w B[1,1] będziemy mieli pozycje $R{1}$ na liście preferencji $B_{1}$).

Dla wygody możemy przyjąć, że algorytm uzupełniania preferencji jest następujący: na początku sprawdzamy, co by było, gdyby każdy z $B$ miał przypisaną najbardziej preferowaną przez siebie jednostkę $R$. Zapisujemy to do wektora m (od wektora parowania / matching‘u).

m <- apply(b, 1, which.min)

Czyli m[1] zawiera informację, kogo przypisaliśmy dla $B_1$, dla m[2] kogo przypisaliśmy dla $B_2$, itd.

Dla porządku proponuję, że za każdym razem, gdy coś robimy na wektorze m, żebyśmy ograniczyli wybory B (np. jeżeli kiedyś $B_1$ miał przypisane $R_3$, a $R_3$ potem odrzuciła $B_1$ na rzecz $B_2$, to $B_1$ już nie będzie rozważał $R_3$ w swoich preferencjach).$^5$

for(i in 1:n){
  b[i, m[i]] <- NA
}

No i teraz to, co nam pozostaje, to sprawdzenie, czy przypadkiem nie mamy powtórzeń w m – tj. kilka jednostek z $B$ wybrało tego samego $R$.

Jeżeli wybrali oni tego samego $R$, to sprawdzamy, co ma do powiedzenia ten wybrany $R$ (on wybiera tego $B$, którego bardziej preferuje: który ma najniższy indeks na swojej liście preferencji).

Dla jednostek, które zostają odrzucone przypisujemy sztuczną wartość $-1$ (żeby ich łatwo znaleźć). I dla nich zaczynami sprawdzać znowu ich listy preferencji…

k <- 1

while (length(unique(m)) != n & k <= 10000) {
  for(i in 1:n){
    b[i, m[i]] <- NA
  }
  
  for(i in unique(m)){
    ind <- m == i
    if(sum(ind) > 1) {
      ind2 <- r[i,] & ind & r[i,] != min(r[i,ind])
      m[ind2] <- -1
    }
  }
  ind <- which(m==-1)
  if(length(ind) == 1){
    m[ind] <- which.min(b[ind, ])
  }else{
    m[ind] <- apply(b[ind, ], 1, which.min)
  }
  k <- k +1
}

Taki algorytm przypisania generuje wektor m (tj. którego $B$ przypisać do którego $R$), który jest permutacją liczb $1$, $2$, $\dots$, $n$.

Jakie są średnie indeksy przypisania dla $B$ i $R$?

results <- matrix(NA, nrow = n, ncol = 2)
for(i in 1 : n){
  results[i,1] <- min(b[i,], na.rm = TRUE)-1 #
  results[i,2] <- r[m[i], i]
}

To, kto ma w końcu lepiej?!

Sprawdźmy, kto ma lepszą wartość realizowanej preferencji:

#------------------------------------------------------
paste('B average index: ', mean(results[,1], na.rm=TRUE)) # "B average index:   4.08"
paste('R average index: ', mean(results[,2], na.rm=TRUE)) # "R average index:  22.23"
#------------------------------------------------------
paste('B expected index: ', log(n))      # "B expected index:  4.60"
paste('R expected index: ', n / log(n))  # "R expected index:  21.72"

W pierwszych dwóch wierszach pokazujemy wartości średniej realizowanej preferencji, wyznaczone na podstawie przygotowaną symulację. Kolejne dwa wiersze, to wyniki analitycznie wyznaczonej wartości oczekiwanej tych preferencji. Tobie pozostawiam sprawdzenie, czy wyniki zbiegają asymptotycznie do znanej – dzięki prof. Prałatowi – wartości oczekiwanej ;)

Oznacza to, że dla zadanego problemu (równe liczności $B$ i $R$) średnio lepiej być tym proaktywnym! Intuicja jest taka, że $B$ idą zgodnie ze swoją listą preferencji (zaczynają od indeksu $1$, jak nie może być to wtedy $2$ itd.). Natomiast $R$ są biorcami propozycji $B$; czerwoni mogą jedynie przyjmować lub odrzucać (oczywiście, jeżeli mogą, to odrzucają gorsze preferencje na rzecz tych lepszych).

$^1$ W rzeczywistości wiadomo, że nie interesują nas kolory koszulek; jako inny – empiryczny - przykład omawianego problemu możecie przyjąć, np. że niebieskimi są świeżo upieczeni absolwenci studiów medycznych, a czerwonymi są szpitale przyjmujące tych absolwentów do pracy; lub grupa osób, które laczy się, z jakiegokolwiek powodu, w pary.
$^2$ Przykład z życia wzięty: kończąc liceum przygotowujemy listę preferencji wyboru studiów: najbardziej preferowana uczelnia ma $1$ pozycję/indeks w naszej liście preferencji, potem kolejna uczelnia ma pozycję/indeks $2$ itd.).
$^3$ Popatrzmy na przykład: niech preferencje poszczególnych grup beda zadane przez macierze $B = [[1, 2], [2, 1]]$, oraz $R = [[1, 2], [2, 1]]$. Przyjmijmy również, że parujemy jednostkę $B_1$ z $R_2$, a $B_2$ z $R_1$. Zwróćmy uwagę, że w takim parowaniu, nikt nie jest zadowolony. $B_1$ preferuje $R_1$, a $B_2$ preferuje $R_2$. Co więcej, również z perspektywy $R_1$ i $R_2$ sytuacja ta nie jest optymalna (powiedzieć można: Pareto Optymalna). Łatwo można pokazać, że gdyby teraz $B_1$ został sparowany z $R_1$, a $B_2$ z $R_2$, to mielibyśmy stabilny matching - nie da się zmienić nikomu pary, nie pogarszając przy tym ich preferencji.
$^4$ Przykład: czy lepiej zapraszać do tańca (proaktywnie składać propozycje tańca), czy czekać na te propozycje?
$^5$ Bo i po co! Życie toczy sie dalej!