Sei in ritardo per il lavoro, devi parcheggiare: se ti appoggi al primo slot libero potresti dover fare molta strada a piedi, arrivando ancora più in ritardo, se vai troppo in là rischi di non trovare posti liberi e dover tornare indietro. Quando fermarsi? Ce lo dice il problema dell optimal stopping.
Per risolvere una moltitudine di problemi con applicazioni reali c’e` bisogno di raccogliere dati. Questo periodo di acquisizione ha un costo misurabile in termini di tempo e denaro, per questo non può essere infinito. Tuttavia un periodo troppo breve di raccolta dati comporta la scarsità di quest’ultimi. Secondo il problema dell optimal stopping il periodo di raccolta dati dovrebbe impiegare il 37% del tempo totale
La storia del problema della segretaria
Una delle prime apparizioni nel mondo della matematica e dell’informatica teorica di questo problema e` stata formulata nella copia di di Scientific American del Febbraio 1960 in questo modo: “Si immagini di dover intervistare un set di candidati per una posizione da segretaria. I candidati vengono intervistati in ordine casuale e ad ognuno di essi può essere assegnato un punteggio. In ogni momento si può decidere assumere il candidato che si ha di fronte, terminando la ricerca, oppure passare al prossimo senza possibilità di richiamare il precedente.” La storia di questo problema non e` ben chiara ma pare che il primo ad aver scoperto la ormai nota “regola del 37%” sia Merrill Flood, un matematico americano, nel 1958. Merrill dichiara di aver considerato il problema a partire al 1949 ma rimanda ad altri matematici che prima di lui hanno tentato la risoluzione. Dopo la pubblicazione su American Scientist nel 1960 il problema e` diventato uno dei più discussi in numerosi papers di matematica e informatica teorica.
Assumere il miglior candidato
Secondo la formulazione nel paragrafo precedente il nostro scopo e` quello di assumere il miglior candidato. E` ovvio che essere “il migliore fin’ora” non basta poiche` altrimenti dovremmo assumere il primo che ascoltiamo. Più andiamo avanti più la chance di essere i migliori e` scarsa: il secondo candidato ha una chance di 50/50 di essere il migliore, il sesto 1/6 il trentesimo 1/30. Fra le tante strategie applicabili la migliore e` chiamata “look than leap” e si basa sul problema dell optimal stopping. La strategia consiste in due fasi: nella prima (look) si collezionano dati, quindi si scartano a priori tutti i candidati, nella seconda (leap) si assume il primo candidato che rispecchia il modello ideale che ci siamo creati con i dati ottenuti. In un pool di due candidati tutto ciò che possiamo fare e` tirare la sorte, in un pool di tre però possiamo fare di meglio: dipende da cosa facciamo con il secondo intervistato, ma comunque le chances di assumere il migliore sono del 33%. Con il crescere del pool osserviamo che otteniamo la maggiore possibilità` di assumere il candidato migliore se terminiamo la fase di looking dopo il 37% dei candidati.
Altri problemi a cui questa regola e` applicabile
Il problema e` facilmente applicabile alla vendita della propria abitazione. Quando arriva un’offerta possiamo accettare o rifiutare ma il rifiuto ha un costo preciso. In questo caso però abbiamo anche il vantaggio di avere già una scala sulla quale valutare le offerte: ci troviamo davanti a quello che in matematica viene chiamato full-information game. Anche l’obiettivo qui è diverso poiché non vogliamo solo accettare la migliore offerta ma guadagnare il più possibile da tutto il processo. Attraverso un’analisi di mercato si può predirre il range di offerte che ci aspettiamo. Attraverso tutti questi dati ogni volta che riceviamo una nuova offerta ciò che dobbiamo chiederci e` se la chance di un’offerta migliore moltiplicata per il valore che ci aspettiamo compensare i costi di attesa. Ovviamente assumendo che le probabilità di ricevere una buona offerta non cambino e che riceveremo sempre un’offerta. Un altro problema che vede una risoluzione legata alla optimal stopping e` il problema del parcheggio. La ricerca del parcheggio ha dei costi predefiniti in termini di tempo, carburante e spazio. Tuttavia a questo problema si aggiunge l’importante variabile degli altri automobilisti che stanno cercando parcheggio. Ogni volta che ci si presenta un post libero possiamo decidere se parcheggiare o cercare un posto migliore. In questo caso la durata della fase di looking dipende dal tasso di occupazione del parcheggio ossa quanti posti prevediamo essere occupati: se un parcheggio costa poco oppure e` gratuito e` molto probabile che abbia un alto tasso di occupazione. Più il tasso e` alto piu` il parcheggio sarà` lontano dalla destinazione.
