Problem sekretarki: dlaczego powinieneś odrzucić pierwszych 37%

Zatrudnij najlepszego kandydata, widząc go tylko raz

N kandydatów zgłasza się na stanowisko, jedno po drugim w losowej kolejności. Po każdej rozmowie musisz natychmiast zaakceptować lub odrzucić kandydata - nie ma możliwości cofnięcia się. Możesz ocenić tylko tych kandydatów, których widziałeś, a nie tych, którzy nadal czekają na rozmowę. Jakie strategie maksymalizują Twoją szansę na wybranie jednego najlepszego kandydata z wszystkich N? To problem sekretarki - kanoniczny przykład teorii optymalnego zatrzymania, a jego rozwiązanie jest nieoczekiwane i proste: odrzuć pierwszych N/e kandydatów bez względu na to, jak dobrymi wydają się być, potem zaakceptuj pierwszego kolejnego kandydata, który przewyższa wszystkich widzianych dotąd.

Dlaczego ustalone graniczną wartość 'patrzy i skoczek' jest optymalna

Oznaczmy graniczną wartość r: odmawiaj pierwszym r-1 kandydatom bez wyjątku (fazę 'patrzenia', używaną tylko do oszacowania, co to 'dobrze'), a następnie akceptuj pierwszego kandydata po tym, który przewyższa wszystkie widziane dotychczas kandydatury. Aby ta strategia wybrała najlepszego kandydata, muszą jednocześnie spełnić dwie rzeczy: najbardziej preferowany kandydat musi pojawić się po pozycji r, a żaden z kandydatów na pozycjach od r do (pozycja - 1) nie może wyglądać jak fałszywy 'najlepszy dotychczas' przed przybyciem rzeczywistego najlepszego. Przeanalizujmy prawdopodobieństwo sukcesu dla danej graniczną wartości r z N kandydatami:

P(sukces | granica r) = (r / N) · ∑_(k=r..N-1) 1/k Zastanówmy się, że x = r/N jest ciągłą ułamkiem i pozwólmy, aby N rosnąć do nieskończoności; suma staje się całką a wyrażenie upraszcza się do P(x) ≈ -x·ln(x). Pochodną tego wyrażenia obliczamy i ustawiamy ją równą zero, co daje maksymalizator x = 1/e, więc optymalna graniczną wartość to r ≈ N/e, a prawdopodobieństwo sukcesu na tej granicy wynosi dokładnie 1/e ≈ 0,368 - rzadki przypadek, w którym optymalna strategia i wartość, którą osiąga, zbiegają się do tego samego stałą.

P(success | cutoff r) = (r / N) · ∑_(k=r..N-1) 1/k

Zaskakująca wielkość rozwiązania

Dla N=100 kandydatów, zasada mówi: odrzuć pierwszych 37 (100/e ≈ 36,8) wprost, a następnie zatrudnij pierwszego kandydata po nich, który przewyższy wszystkich widzianych dotychczas. Zdobywa się na to sukces w odkryciu jednego najlepszego kandydata z 100 około 37% czasu - znacznie lepszy wynik niż 1%, jaki byś uzyskał, zgadując losowo, a niezwykle, ta prawdopodobieństwo sukcesu niemal się nie zmienia wraz z rosnącym N: konverguje do 1/e i pozostaje na tym poziomie, czy N wynosi 20, czy 20 000. Strategia jest niezmiennicza względem skalowania w rzeczywistym sensie: zapamiętanie 'odrzuć pierwszych 37%' działa dla dowolnej wielkości puli kandydatów.

Gdzie model nie działa w praktyce

Klasyczna wersja problemu przyjmuje silne założenia, które rzadko są spełnione: N jest znane z góry, kandydati pojawiają się w losowej i równomiernie rozłożonej kolejności, możesz bez zarzutu ocenić każdego nowego kandydata względem wszystkich poprzednich, a jedynym twoim celem jest zdobycie najlepszego kandydata - drugi najlepszy kandydat liczy się tak samo jak najgorszy. W rzeczywistych procesach zatrudniania występuje niepewność dotycząca wielkości puli kandydatów, korrelerowana kolejność pojawiania się (silni kandydaci często grupują się w okresie ukończenia studiów), szumowa ocena oraz fakt, że firma zwykle preferuje 'bardzo dobrego kandydata, który jest pewny' nad 'najlepszego kandydata, który jest rzadko'. Wersje problemu ograniczają każdy z tych założeń - w przypadku 'nieznanej N', 'kardinalnej nagrody', gdzie oceniasz kandydatów na podstawie ich rzeczywistej jakości, a nie jedynie na podstawie zwycięstwa lub porażki, oraz 'mnożnych zatrudnieniach' - i każda ma inny, ogólnie mniej jasny, optymalny zasieg.

Weryfikacja Monte Carlo

Zamiast wierzyć w rachunek różniczkowy, demo sprawdza go bezpośrednio: dla wybranej wartości N wykonuje wiele niezależnych losowych permutacji kandydatów uporządkowanych. Dla każdego możliwego punktu podziału r od 1 do N liczy ile razy zasada 'odrzuć pierwszych r-1, a następnie zadbaj o najlepszego rekordzistę' daje prawdziwą najlepszą kandydatkę. Narysowanie stopnia wygranych przeciwko r/N tworzy krzywą, która osiąga jasno widoczny maksimum blisko x=1/e≈0,368 z wysokością maksimum również blisko 1/e≈0,368 - obie liczby, ujemna część do pominięcia i prawdopodobieństwo sukcesu, są tą samą stałą potwierdzoną empirycznie, a nie założoną.

for (let r = 1; r <= N; r++) {
  let wins = 0;
  for (let trial = 0; trial < TRIALS; trial++) {
    const perm = shuffledRanks(N);
    let bestSoFar = Math.max(...perm.slice(0, r - 1), 0);
    for (let i = r - 1; i < N; i++) {
      if (perm[i] > bestSoFar) { if (perm[i] === N) wins++; break; }
    }
  }
  winRate[r] = wins / TRIALS;
}

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Secretary Problem — Optimal Stopping & the 37% Rule i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.