Dating e statistica, come scegliere il partner migliore

Che tipo di strategia si può seguire per scegliere il miglior partner possibile? Può aiutarci il ricorso alla statistica?
In altre parole, come si sposano dating e statistica?
Nella sua rubrica bisettimanale di matematica ricreativa sul Guardian, Alex Bello ha di recente riproposto, in versione dating, un problema più noto come Secretary Problem. Questa la versione di Alex Bello:

Siete single alla ricerca di un partner, e avete tre porte chiuse davanti a voi. Dietro ogni porta c’è un potenziale partner.
Avete facoltà di aprire una qualunque delle tre porte, vedere la persona che era nascosta dalla porta e decidere se è quella giusta per voi. Se decidete per il sì, fermate la ricerca e non scoprirete mai chi c’era dietro le altre due porte. Se decidete per il no, allora escludete la prima persona che avete visto e scegliete, ancora a caso, la seconda porta da aprire. Anche qui, se vi va bene la persona che scoprite, vi fermate e non aprirete mai la terza porta. Altrimenti procedete con la terza porta e vi tenete la persona che c’è dietro.

La premessa è che, posti di fronte ai tre potenziali partner, chiamiamoli A, B e C, sapreste metterli in ordine di gradimento. Ma, all’inizio del gioco, non avete nessuna informazione sull’identità e sulla presenza delle tre persone.
Quale strategia potete seguire per rendere massima la probabilità di pescare il partner migliore?

Dating e statistica, quale porta aprire?

Se scegliamo solo sulla base delle informazioni che abbiamo all’inizio del gioco, la probabilità di pescare la persona giusta è di 1/3, sia che ci fermiamo alla prima porta, che alla seconda o alla terza.
Intuitivamente, quindi, occorre costruire un minimo di informazione su cui ragionare. Possiamo farlo aprendo la prima porta, e prendendo la persona che c’è dietro come riferimento per la ricerca.
Apriamo ora la seconda e vediamo chi ci viene proposto: se la giudichiamo migliore della prima, scegliamo questa persona e ci fermiamo. Altrimenti procediamo alla terza porta, e alla relativa scelta, a questo punto obbligata.

Scegliere per il meglio diventa così più probabile

Possiamo convincercene, elencando tutte le possibili sequenze della scoperta di A, B e C ed evidenziando la persona che l’algoritmo ci porta a scegliere. Supponiamo che A sia la migliore scelta, B la successiva e C la peggiore.

Le possibili sequenza sono sei:

A B C → C : il primo elemento sarebbe la scelta migliore, quindi saltiamo la seconda e siamo costretti alla terza
A C B → B
B A C → A
B C A → A : qui va meglio, scartiamo la seconda e la migliore scelta è dietro la terza porta
C A B → A
C B A → B

Come si vede, la probabilità di scegliere A, cioè il partner migliore, è salita a 3 casi su 6, quindi al 50%. Quella di finire con C, la scelta peggiore, è scesa a 1 caso su 6, cioè circa il 17%.

Un caso particolare del Secretary Problem

Il caso di dating e statistica proposto da Alex Bello è un caso particolare del Secretary Problem, un problema di statistica pubblicato per la prima volta nel 1960 da Martin Gardner nella sua rubrica su Scientific American. Nei vent’anni successivi il problema è stato analizzato, indirizzato, esteso ad altri scenari.

Perché Secretary Problem? Il nome deriva dall’applicazione reale più “utile”:

Dovete assumere una segretaria e avete davanti a voi un centinaio di curricula da esaminare. Certo, li potreste esaminare tutti, per avere la sicurezza di scegliere per il meglio. Magari, però, accettate di rischiare una scelta non ottimale, ma risparmiandovi un po’ di lavoro.
La soluzione consiste nell’esaminare una certa quantità di curricula, un campione, per farsi un’idea dei candidati disponibili. Poi esaminate gli altri, fermandovi al primo che risulti migliore dei candidati del campione inizialmente esaminato.

Quanto deve essere ampio questo campione, per massimizzare la probabilità di scegliere il candidato migliore?

Rimandando per la dimostrazione all’articolo di Wikipedia, viene fuori che, quanto maggiore è il numero di cv da esaminare, tanto più il campione tende ad esserne la frazione 1 ⁄ e, dove e è il numero di Eulero, familiare a chi mastica logaritmi e analisi matematica in generale, e pari a 2,71828 …
Ne segue: 1 ⁄ e = 0,368 … ≅ 37%

Quindi: vi spazzolate il 37% dei cv, poi scegliete il primo che sia migliore del campione esaminato. La probabilità di scegliere il miglior candidato è anch’essa pari a 1 ⁄ e, quindi al 37% circa. Non male.
Certo, qualche rischio lo correte: se il miglior candidato fosse nel campione esaminato inizialmente, finireste per scegliere l’ultimo cv, quali che siano le sue capacità.

Semplice simulazione in Ruby

Una semplice simulazione in Ruby consente di verificare come dal 50% di probabilità nel caso di 3 candidati si scenda via via, tendendo al 37%.
Il listato del programma è in fondo all’articolo. Le istruzioni per crearsi un ambiente Ruby sono qui.

Il programma dà questo tipo di statistica:

numero di elementi: 3, campione iniziale: 1
numero di permutazioni: 6

occorrenze per valore scelto: {1=>3, 2=>2, 3=>1}
in percentuale: {1=>50.0, 2=>33.3, 3=>16.7}

occorrenze per posizione della scelta: {2=>3, 3=>3}
in percentuale: {2=>50.0, 3=>50.0}
posizione media: 2.5

Portando il numero di elementi a 6:

numero di elementi: 6, campione iniziale: 2
numero di permutazioni: 720

occorrenze per valore scelto: {1=>308, 2=>164, 3=>92, 4=>60, 5=>48, 6=>48}
in percentuale: {1=>42.8, 2=>22.8, 3=>12.8, 4=>8.3, 5=>6.7, 6=>6.7}

occorrenze per posizione della scelta: {3=>240, 4=>120, 5=>72, 6=>288}
in percentuale: {3=>33.3, 4=>16.7, 5=>10.0, 6=>40.0}
posizione media: 4.57

Con 9 elementi:

numero di elementi: 9, campione iniziale: 3
numero di permutazioni: 362880

occorrenze per valore scelto: {1=>147312, 2=>71712, ...}
in percentuale: {1=>40.6, 2=>19.8, ...}

occorrenze per posizione della scelta: {4=>90720, 5=>54432, ...}
in percentuale: {4=>25.0, 5=>15.0, 6=>10.0, 7=>7.1, 8=>5.4, 9=>37.5}
posizione media: 6.65

Infine, con 12 elementi:

numero di elementi: 12, campione iniziale: 4
numero di permutazioni: 479001600

occorrenze per valore scelto: {1=>189452160, 2=>87845760, ...}
in percentuale: {1=>39.6, 2=>18.3, ...}
occorrenze per posizione della scelta: {5=>95800320, 6=>63866880, ..., 12=>174182400}
in percentuale: {5=>20.0, 6=>13.3, ..., 12=>36.4}
posizione media: 8.75

Quindi la probabilità di scegliere per il meglio scende dal 50% con 3 elementi al 42,8% con 6 elementi, al 40,6 con 9 elementi, al 39,6% con 12 elementi. Elencare tutte le permutazioni per un maggior numero di elementi va oltre le possibilità del mio algoritmo risolutivo (e del mio pc).

Interessante vedere anche come si sposta la posizione media in cui ci si ferma nella scelta.
Si va dalla posizione 2,5 su 3 elementi, alla posizione 4,57 su 6 elementi, alla posizione 6,65 su 9 elementi, alla posizione 8,75 su 12 elementi.
L’efficacia dell’abbinare dating e statistica si manifesta, quindi, in presenza di un numero elevato di candidati.

Le varianti del secretary problem

Due varianti del problema sono divertenti, oltre che interessanti.

La prima variante: il Postdoc Problem

Supponiamo che state scegliendo, tra dei cv di neolaureati, una persona a cui assegnare un dottorato post-laurea. Siete sicuri che scegliere il migliore sia la cosa giusta da fare?
In questo scenario, teorizzato da Robert J. Vanderbei come Postdoc Problem, il migliore probabilmente avrà offerte più allettanti, ad esempio, nel caso ipotizzato da Vanderbei, da Harvard. Lui accetterà l’altra offerta, e voi sarete costretti a ripetere la selezione. Meglio allora puntare subito al second best, quello appena meno bravo del migliore.
Tradotto per dating e statistica, siamo certi che sia meglio scegliere il partner più attraente, e che non convenga piuttosto cercare stabilità e affidabilità nel partner appena meno appealing?

Una sintesi del risultato di Vanderbei mostra che, adattando l’algoritmo al nuovo scenario, la probabilità di scegliere il second best tende al 25%, al crescere del numero di candidati. Quindi è più semplice scegliere il migliore!

La seconda variante, uno scenario di dating e statistica più realistico

Mentre nella scelta della segretaria i cv sono tutti sulla scrivania, quindi posso contarli e utilizzarne il 37% come campione, applicare la stessa strategia alla selezione di un partner è, probabilmente, un altro paio di maniche.

Più che conoscere a priori tra quanti potenziali partner potrò scegliere, infatti, è sensato pensare che possa darmi un certo tempo massimo per scegliere, ad esempio tre anni. Immaginando che il mio appeal sia costante in questo periodo, e che quindi possa esaminare partner con ritmo costante, quale strategia ottimizza la mia scelta, tenendo conto che un partner lasciato è da dimenticare?

Nel 1984, il matematico belga F. Thomas Bruss, affrontò uno scenario in cui:

in un periodo fisso pari a T,
si presenta un numero non noto a priori di possibili partner,
tutti con la stessa distribuzione statistica del momento in cui si presenteranno (alcuni potranno arrivare subito, altri allo scadere del tempo T)

La miglior strategia

In questo scenario la miglior strategia consiste ancora nel collezionare un campione, e poi scegliere il primo candidato migliore del campione esaminato. Quello che cambia è il criterio per determinare il blocco iniziale di candidati.
Non più 1 ⁄ e dei possibili partner (il cui numero non è noto a priori), ma tutti i candidati che arriveranno entro il il tempo t, entro il quale la probabilità di arrivo di ciascun campione sia pari a 1 ⁄ e.
Se la distribuzione di arrivo è lineare, basterà quindi collezionare il campione che arriva entro il 37% circa del periodo che ci siamo dati per scegliere.

Quindi, se vogliamo sistemarci al massimo in tre anni, la miglior strategia dettata da dating e statistica è folleggiare per il primo anno, e poi acchiappare la prima (o il primo) che ci faccia dimenticare le follie del primo anno.
Non scommetterei, però, che il giorno dopo non arrivi chi ci tenterà a cambiare idea.

Dating e statistica, il listato del programma di simulazione in Ruby

# ------------------------------------
# simulazione del "Segretary Problem"
#    - per ogni possibile permutazione di (1..n_elementi)
#    - dove 1 ha il valore massimo e n_elementi il valore minimo
#    - vengono osservati i primi (n_elementi / e) campioni
#    - di questi campioni viene memorizzato quello di valore maggiore
#    - si procede poi a esaminare i campioni successivi
#    - fermandosi al primo che abbia valore maggiore di quello memorizzato
#    - eventualmente si sceglie comunque l'ultimo elemento della permutazione
#
# by p.p. - Lecco, 10 ottobre 2018
# ------------------------------------
#
n_elementi = 9
lista = (1..n_elementi).to_a
n_permutazioni = lista.permutation.count
campione = (n_elementi / Math.exp(1)).to_i
#
# l'hash "conta" memorizza le occorrenze dei valori degli elementi scelti per ogni permutazione
# l'hash "conta_pos" memorizza le occorrenze della posizione degli elementi scelti
conta = Hash.new(0)
conta_pos = Hash.new(0)
#
# generazione delle possibili permutazioni ed esecuzione dell'algoritmo di scelta
lista.permutation.each do |permutazione|
	min = permutazione[0..campione-1].min
	scelto = 0
	pos_scelto = -1
	(campione..(n_elementi-1)).each do |indice|
		prossimo = permutazione[indice]
		if prossimo < min then
			scelto = prossimo
			pos_scelto = indice + 1
		end
		break if scelto != 0
	end
	if scelto == 0 then
		scelto = permutazione[n_elementi - 1]
		pos_scelto = n_elementi
	end
#	print permutazione, ": ", "scelta: ", scelto, "\n"
	conta[scelto] += 1
	conta_pos[pos_scelto] += 1
end
#
# stampa della sintesi statistica della simulazione
print "\n", "numero di elementi: ", n_elementi, ", campione iniziale: ", campione, "\n"
print "numero di permutazioni: ", n_permutazioni, "\n\n"
#
print "occorrenze per valore scelto: ", conta.sort.to_h, "\n"#
(1..n_elementi).each do |indice|
	conta[indice] = (100.0 * conta[indice]/n_permutazioni).round(1)
end
print "in percentuale: ", conta.sort.to_h, "\n\n"
#
print "occorrenze per posizione della scelta: ",conta_pos.sort.to_h, "\n"
pos_media = 0.0
(1..n_elementi).each do |indice|
	pos_media += indice * conta_pos[indice]
end
pos_media = (pos_media / n_permutazioni)
((campione+1)..n_elementi).each do |indice|
	conta_pos[indice] = (100.0 * conta_pos[indice]/n_permutazioni).round(1)
end
print "in percentuale: ", conta_pos.sort.to_h, "\n"
#
print "posizione media: ", pos_media.round(2)
print "\n"