Newsgroup: it.hobby.enigmi
Titolo: Quale strategia vincente?

Mi hanno proposto il seguente gioco che mi è sembrato carino, ho fatto
una ricerca e non mi pare che sia stato trattato nel ng e quindi ve lo
propongo anche a voi.
Abbiamo i soliti due giocatori, vogliamo essere fantasiosi?
Chiamiamoli Alice e Bob :o)
Ogni giocatore riceve un numero uniformamente distribuito tra 0 ed 1 e
può decidere se tenerselo o scartarlo per riceverne un altro (sempre
uniformamente distribuito tra 0 ed 1). Dopo che i giocatori hanno
fatto la propria scelta ed hanno eventualmente ricevuto il secondo
numero vince il giocatore con il numero più alto. Che strategia deve
adottare Alice per avere almeno il 50% di probabilità di vittoria?
Naturalmente, affinchè il gioco sia simmetrico, i due giocatori devono
fare la scelta senza sapere quale sarà quella dell'avversario.
In un messaggio a parte propongo la prima soluzione che mi era venuta
in mente e che si è rilevata tanto referenziale quanto sbagliata.
Ciao,
GaS


Cosi', a occhio, direi che convenga cambiare numero se quello che si
riceve e' inferiore a 0,5, perche' la probabilita' di riceverne uno
piu' alto e' superiore a quella di riceverlo piu' basso, ma e' il
primissimo pensiero che classicamente in questi giochi si rivela
sbagliato.
Devo pensarci su un momento.
.

 in mente e che si è rilevata tanto referenziale quanto sbagliata.
Mi sembra interessante riportarla per il suo valore didattico, per
lezioni del tipo "scopri la magagna".
Metto uno spoiler perchè, anche se sbagliata, segna un po' la strada
verso una possibile soluzione corretta:
S
.
.
.
P
.
.
.
O
.
.
.
I
.
.
.
L
.
.
.
E
.
.
.
R
Mettiamoci, come detto, nei panni di Alice: una strategia vincente
deve essere naturalmente del tipo "se il primo numero che ricevo è
minore di un valore x lo scarto, altrimenti lo tengo". Ma quanto vale
x?
Facciamo un po' di calcoli sapendo che se x esiste sarà adottato anche
da Bob che quindi adotterà la stessa strategia.
Sia a il primo valore assegnatomi e b quello assegnato a Bob, ho 4
casi:
-	a<x e b<x
Probabilità dell'evento=x^2
Probabilità di vincita: 1/2
-	a<x e b>x
Probabilità dell'evento =x*(1-x)
Probabilità di vincita:  un certo valore T
-	a>x e b<x
Probabilità dell'evento=x*(1-x)
Probabilità di vincita:  un certo valore 1-T
-	a>x e b>x
Probabilità dell'evento=(1-x)^ 2
Probabilità di vincita: 1/2
Sommando i prodotti delle probabilità dei quattro casi la x viene
semplificata (!) e si ha una probabilità di vincita di 1/2.
Da ciò ne ho dedotto che la probabilità di vincita è indipendente da x
e quindi non esiste una strategia vincente! Faccio quello che mi pare
e la probabilità di vittoria è sempre la stessa.....
Dopo pochi secondi un senso di paradosso a cominciato ad assalirmi (e
se a=0 che faccio? e se vale 1?) e sono ritornato sui miei passi.
:o))
Ciao,
Gabriele

La strategia vincente potrebbe essere "se mi capita un numero inferiore a 
0,5, ne pesco un altro visto che ho piu' del 50% di probabilità di 
migliorare, altrimenti mi tengo il numero". Ovviamente, essendo il gioco 
simmetrico, sia A, sia B hanno la stessa probabilità di vittoria.
P. 

 Dopo pochi secondi un senso di paradosso a cominciato ad assalirmi
Il punto e' questo: hai assunto che entrambi i concorrenti
utilizzassero la stessa strategia. A questo punto la situazione e'
simmetrica e la probabilità di vincita e' del 50%.
Il vero senso del gioco e' trovare la strategia migliore, ossia tale
che un avversario che agisca diversamente possa solo peggiorare la
propria situazione.

 sbagliato.
E' quello che ho pensato anche io.
Per avere almeno il 50% delle probabilita' di vincere,
data l'assoluta simmetria del gioco, bisogna che entrambi
adottino la stessa strategia ottimale.
Considerando che non si hanno informazioni su quello
che ha l'altro giocatore, o scelgo a caso se
cambiare numero (ma allora penso non ci sia
differenza con caso di un solo numero),
oppure stabilisco una soglia sul primo numero
per decidere quando chiederne un altro.
Se la soglia e' s, allora la media dei
miei numeri e' (1+s-s^2)/2, come si vede
sommando  (1/2)*s + integrale di x
tra s e 1.
Questa funzione vale giustamente 1/2 in 0 e in 1
(che corrispondono alle scelte di cambiare mai o sempre)
e assume un massimo in x=1/2 dove vale 5/8 = 0.625.
Quindi direi che entrambi i giocatori fanno come dice il bragozzi,
ovvero tengono il numero se e' maggiore di 0.5 e lo cambiano se e' minore.
ciao,
g.

 adottare Alice per avere almeno il 50% di probabilità di vittoria?
S
P
O
I
L
E
R
S
P
O
I
L
E
R
Io ho provato a fare queste considerazioni, non so se siano giuste o 
contengono delle falle.
Dovessi giocare contro un qualcuno che non so che scelta faccia, assumo 
che questa persona tenga il numero se maggiore di 0.50 e lo cambi se 
minore di 0.50. Assunto questa, ho in mente una strategia ben precisa: 
se mi arriva un numero minore di 0.67 lo cambio, se me ne arriva uno 
uguale o maggiore lo tengo, ora provo a spiegare il perché.
Le possibilitá che un mio avversario riceva un numero maggiore di 0.50 é 
il 50%. Se ne riceve uno minore lo cambia e ha di nuovo il 50% di 
riceverne uno maggiore. Risultato: 75% > 0.50 ; 25% < 0.50.
Quindo se io ricevo ad esempio il numero 0.51 ho praticamente il 75% di 
perdere pur essendo maggiore di 0.50.
Supponiamo di ricevere 0.60. Quale probabilitá ho di vincere? Ho il 25% 
che lui abbia un numero inferiore a 0.50 a cui devo sommare la 
probabilitá che lui abbia un numero superiore a 0.50 ma inferiore a 0.60 
(quindi il 20% del 75% -> quindi 15%). Risultato: con il mio 0.60 ho il 
40% di vincere e il 60% di perdere.
Con il 0.67, i conti sono: 25% + (33% del 75%) = 50%.
Secondo me, giocassi contro di voi dovrei tenere il numero solo se 
uguale o maggiore a 0.67.
Puó essere un ragionamento giusto???

 ovvero tengono il numero se e' maggiore di 0.5 e lo cambiano se e' minore.
E perchè mai? :o)
Non sempre una valor medio più alto corrisponde ad una più alta
probabilità di vittoria. Consideriamo due dadi con le facce così
numerate:
A) 4,4,4,4,0,0
B) 3,3,3,3,3,3
Il dado A ha un valor medio delle facce di 16/6 mentre il B di 18/6 ma
se tiriamo un dado a testa e il numero più alto vince tu quale dado
sceglieresti?
Il problema è più tosto di quanto sembra a prima vista.
Ciao,
Gabriele

 E perchè mai? :o)
Perche' non mi veniva in mente niente di meglio, ammetto
che mi ha sfiorato esattamente il tuo stesso pensiero, ma
non sapevo bene come affrontare la cosa.
Cioe' avevo pensato di far giocare virtualmente
due giocatori, uno con soglia S1 e uno con soglia S2 per
vedere chi vince, o matematicamente ma non ne avevo voglia
(cioe', non ero capace...) o almeno con una simulazione
ma non avevo tempo (cioe', non ne avevo voglia)...
ciao,
g.

 g.
Ho passato meta' mattinata a calcolare la stessa cosa, ma regolarmente
qualcosa mi distrae.
Vogliamo lavorare in team?
Allora: data una soglia S, al di sotto della quale il giocatore
ritira, la probabilita' che il numero risultante sia inferiore a S e'
S^2 e che sia superiore e' 1-S^2.
In generale, la probaiblita' che il numero sia inferiore a un
qualsiasi N e' N*S se N<S,   S^2+(S+1)(N-S) se N>S
Questo e' un punto di partenza.

 S1.
Abbiamo tre possibilità:
1) Bob si ritrova con un numero N < S1.
La probabilita'  di vittoria di  Alice è 1-N*S2
La probabilita' di questo evento e' S1^2.
2) Bob si ritrova con S1<N<S2.
La probabilita'  di vittoria di Alice è 1-N*S2
La probabilita' di questo evento e' (S1+1)*(S2-S1).
3) Bob si ritrova con N>S2.
La probabilita'  di vittoria di Alice è (S2+1)*(1-N)
La probabilita' di questo evento e' (S1+1)*(1-S2).


Se moltiplico probabilità di vittoria per probabilità evento e sommo
il tutto, ottengo, se non ho sbagliato i calcoli, la probabilità di
vittoria di Alice in funzione di S1, S2 e N (e qui qualcosa non mi
torna; mi suona male che ci sia ancora N).
A= (N-1)*S1*S2^2 -   N*S1^2*S2   -   S2^2   +   N*S1*S2  +  S1*S2  -
N*S1  + S2 -  N + 1

No, secondo me qualcosa non va.

 fare la scelta senza sapere quale sarà quella dell'avversario.
Il problema visto dall'interno secondo me non ha soluzioni, perche'
qualunque sia la tua strategia su A il giocatore B puo' usare una strategia
esattamente opposta e vincere sempre, e siccome non sai come sceglie B...
Se guardiamo il problema dall'esterno secondo me basta cambiare a casaccio:
avrai sempre una possibilita' del 50% visto che siete in due a giocare.

 
Cosa ne dici di quello che ho scritto io?


L'ho notato adesso. Mi ero perso nei miei calcoli e non avevo visto
che c'erano altre risposte.
Direi che sia corretto, ma parte dal principio che l'altro giocatore
usi una strategia ben precisa.
Che cosa succede se anche l'altro cambia per valori minori di 0.67?

Ho gia' capito che ci rimuginero' su tutto il fine settimana!


Secondo me non torna, tu infatti ragioni sulla singola uscita (per
esempio che esca 0,6 piuttosto che 0,67) che è un evento a probabilità
"nulla". Ragionando su una strategia globale ("se ricevo un numero più
piccolo di x cambio altrimenti lo tengo") le cose cambiano.
Per esempio si può calcolare che se io adotto la strategia con x=0,6
contro chi usa una strategia con x=0,5 io ho il 50,5% di probabilità
di vincere.
Ciao,
Gabriele


Il problema si riduce a trovare la strategia migliore in assoluto,
indipendentemente da quello che fa l'altro. E sicuramente l'unica
strategia possibile è quella di ritentare se il primo numero è
inferiore ad una soglia S. Ma qual è la soglia S ottimale? Mi son
detto: faccio una simulazione bruteforce e troverò quel 0.67 che
qualcuno ha scovato. E invece guardate un po':
 0   .5003427734375
 .01   .5043494921875
 .02   .510741484375
 .03   .5150598828125
 .04   .5190055859375
 .05   .5245569921875
 .06   .5273223828125
 .07   .5327870703125
 .08   .537400234375
 .09   .5403677734375
 .1   .5458534765625
 .11   .5488521484375
 .12   .551882109375
 .13   .55640765625
 .14   .559393359375
 .15   .
5637671875
 .16   .567283515625
 .17   .5708463671875
 .18   .57230640625
 .19   .575517734375
 .2   .5816433984375
 .21   .584567109375
 .22   .5856180078125
 .23   .5890254296875
 .24   .5917451953125
 .25   .594374453125
 .26   .59606625
 .27   .5977478515625
 .28   .60115484375
 .29   .6031171875
 .3   .60464078125
 .31   .6057001953125
 .32   .6086751953125
 .33   .6091957421875
 .34   .6127788671875
 .35   .612511796875
 .36   .615099765625
 .37   .61682546875
 .38   .618289921875
 .39   .6183876171875
 .4   .61883671875
 .41   .6207991015625
 .42   .622060546875
 .43   .622495546875
 .44   .6230712890625
 .45   .623708125
 .46   .6244725390625
 .47   .6237780078125
 .48   .625924140625
 .49   .624702734375
 .5   .625933984375
 .51   .626350078125
 .52   .6251337109375
 .53   .624778203125
 .54   .6234550390625
 .55   .624334375
 .56   .624466875
 .57   .6221616015625
 .58   .622048828125
 .59   .6213915234375
 .6   .620309453125
 .61   .620485
 .62   .6169751171875
 .63   .61779375
 .64   .6147984765625
 .65   .614054296875
 .66   .611862421875
 .67   .611089140625
 .68   .609927265625
 .69   .6080218359375
 .7   .605124296875
 .71   .6029445703125
 .72   .5994819140625
 .73   .598602890625
 .74   .596688125
 .75   .5947608984375
 .76   .5922309765625
 .77   .5867342578125
 .78   .586014765625
 .79   .5824393359375
 .8   .5774597265625
 .81   .576909765625
 .82   .5735475
 .83   .57100484375
 .84   .5687375390625
 .85   .56408640625
 .86   .5588081640625
 .87   .5568778125
 .88   .55197359375
 .89   .547604765625
 .9   .544676875
 .91   .541497421875
 .92   .53455640625
 .93   .5317834765625
 .94   .528380625
 .95   .5244102734375
 .96   .520133046875
 .97   .51394578125
 .98   .5079650390625
 .99   .504650234375
 1   .4996458984375
La funzione è piuttosto piatta, ma il max sembra proprio dalle parti
di S=0.5
Ciao!!!  :o)
Livio

di S=0.5
Ciao Livio, scusa ma non capisco che cosa rappresentano i valori in tabella. 
Come hai fatto la simulazione?
Ciao,
GaS 

 Come hai fatto la simulazione?
Ciao GaS,
anch'io rileggendomi non mi sono capito molto :o(
A destra il valore di soglia S usato.
A sinistra il valor medio del numero di uscita ottenuto come media di
100.000 esperimenti per ogni valore di soglia.
Spero che adesso sia chiaro.
Ciao!!!  :o)
Livio
Nel dubbio, questo è il programmino:
Dim AA(100)
For J = 0 To 100
    s = J / 100
    For K = 1 To 100000
        A = Rnd
        If A < s Then A = Rnd
        AA(J) = AA(J) + A
    Next K
Next J
For J = 0 To 100   'stampa
    s = J / 100
    Text1 = Text1 + Str(s) + "  " + Str(AA(J) / 100000) + Chr$(13) +
Chr$(10)
Next J

 fare la scelta senza sapere quale sarà quella dell'avversario.
O non ho capito il problema, o non capisco cosa vi impegnate a fare.
Se esistesse una strategia che fa vincere più della metà delle volte tutti e 
due i contendenti, la cosa mi sembrerebbe davvero strana.
Cosa c'è dietro?
-- 
Ciao, Silv:o)

 Cosa c'è dietro?
Quello che cerco è una strategia di gioco che mi permetta di vincere con 
almeno il 50% delle probabilità. Naturalmente se anche l'avversario adotasse 
la stessa strategia (ottimale) le probabilità di vittoria sarebbero del 
50-50, in tutti gli altri casi io sarei avvantaggiato (o, comunque, mai 
svantaggiato).
Ciao,
Gabriele 

100.000 esperimenti per ogni valore di soglia.
Ma quel valore di .625 (=5/8) poteva essere tirato fuori con due calcoletti 
come  ha fatto Giovanni nel suo post (mi meraviglio di te, la forza bruta 
per simili cose... :o)
E' assodato che adottando una strategia con la soglia a 0,5 si ha, in media, 
il numero finale più alto. Ma questo non permette assolutamente di 
concludere che questa sia la scelta ottimale, ti riporto quanto scrivevo in 
risposta a Giovanni questo pomeriggio:
____________________________________
Non sempre una valor medio più alto corrisponde ad una più alta
probabilità di vittoria. Consideriamo due dadi con le facce così
numerate:
A) 4,4,4,4,0,0
B) 3,3,3,3,3,3
Il dado A ha un valor medio delle facce di 16/6 mentre il B di 18/6 ma
se tiriamo un dado a testa e il numero più alto vince tu quale dado
sceglieresti?
____________________________________
Ciao,
Gabriele 

 avvantaggiato (o, comunque, mai svantaggiato).
ok, capito.
Forse , come dici tu, non bisogna cercare di migliorare la media. Oltre 5/8 
non si riesce ad andare.
Prima di abbandonare questa strada volevo fare qualche considerazione che 
magari potrebbe aiutare qualcuno.
A volte in questi giochi la migliore strategia non è deterministica, ma 
probabilistica.
Mi spiego. Certe volte la cosa migliore da fare è affidarsi al caso nelle 
decisioni. Che faccio, cambio o no? Tiro un moeta e decido. Così frego chi è 
sicuro che tengo e chi gioca sul fatto che cambio.
La strategia della soglia è caratterizzata da una funzione a gradino: fino a 
x=1/2 tengo con probabilità 0 (ovvero cambio sistematicamente), per x>1/2 
tengo con probabilità 1.
Si possono usare funzioni meno "brusche". In generale dato un valore x 
potrei decidere di tenerlo con probabilità f(x).
Per esempio se vedo 0.2 me lo tengo solo il 20% delle volte, 0.8 l'80% e in 
generale il valore x lo tengo con probabilità x.
In generale vinco x con probabilità f(x) (se mi tengo x) e 1/2 con 
probabilità 1-f(x) (se cambio).
La vincita vale
V = x*f(x) + 1/2*(1-f(x))
  = 1/2 + f(x)*(x-1/2)   [1]
e la media si calcola integrando su 0,1. Nell'esempio con f(x)=x la media 
risulta 7/12, non un granché.
Comunque dalla [1] si vede che per x<1/2 ci conviene annullare f(x) per non 
scendere sotto il valore di 1/2.
Per x>1/2 massimizziamo la vincita ponendo f(x)=1.
Quindi anche così torniamo alla solita strategia deterministica che ha media 
5/8
Detto questo, lascio stare la media e mi concentro su qualcos'altro.
-- 
Ciao, Silv:o)
media si ottiene integrando
questo caso con probabilità f(x)
o provato a sotituire alla "funzione a gradino" che caratterizza la 
stragtegia della soglia 

 e quindi non esiste una strategia vincente! 
Mmm, questo IMO significa semplicemente che non esiste una soglia x
valida per entrambi che massimizzi la probabilità di vittoria. In altre
parole, A non può sapere in anticipo quale soglia adotterà B (come
diceva anche Livio).
Supponiamo quindi che A adotti una soglia x e che B adotti una soglia y.
La probabilità che A vinca, se ho fatto bene i calcoli (?), vale:
P = 1/2 + 1/2 (x-y)(1 - xy - max(x,y))
A deve scegliere x in modo che, qualunque sia y scelta da B, P sia
almeno 1/2. Ad esempio, x=1/2 non soddisfa questo criterio, perché se B
scegliesse y = 7/12 si avrebbe P = 1/2 - 1/192.
Insomma, occorre trovare per ogni x il minimo valore di P al variare di
y e poi trovare il valore di x per cui tale minimo ha il valore massimo.
Ora è tardi e non ho voglia di fare i calcoli, lascio ad altri la lieta
incombenza...
Maurizio

On 9 Mar, 23:23, "Gabriele \"GaS\" Carelli"

Allora tagliamo la testa al toro. Facciamo scontrare Alice, che ogni
100000 esperimenti cambierà soglia e Bob che manterrà la soglia a 0.5:
a sinistra la soglia usata da alice, a destra il numero delle vittorie
di Bob:
 0   62751
 .01   61984
 .02   61801
 .03   61586
 .04   61077
 .05   60763
 .06   60314
 .07   60194
 .08   59743
 .09   59063
 .1   59159
 .11   58405
 .12   58511
 .13   58313
 .14   57526
 .15   57287
 .16   57120
 .17   57111
 .18   56296
 .19   56566
 .2   55983
 .21   55910
 .22   55346
 .23   55355
 .24   54706
 .25   54686
 .26   54462
 .27   54473
 .28   53818
 .29   53691
 .3   53419
 .31   53209
 .32   53301
 .33   52804
 .34   52602
 .35   52560
 .36   52378
 .37   51998
 .38   51779
 .39   51658
 .4   51576
 .41   51190
 .42   51272
 .43   50958
 .44   51055
 .45   50589
 .46   50395
 .47   50368
 .48   50350
 .49   50182
 .5   50172
 .51   49785
 .52   49784
 .53   49761
 .54   49494
 .55   49616
 .56   49726
 .57   49660
 .58   49414
 .59   49497
 .6   49481
 .61   49706
 .62   49738
 .63   49397
 .64   49828
 .65   49725
 .66   50120
 .67   50023
 .68   50257
 .69   50319
 .7   50348
 .71   50430
 .72   50660
 .73   51118
 .74   51316
 .75   51822
 .76   51732
 .77   51990
 .78   52509
 .79   52649
 .8   52934
 .81   53147
 .82   53447
 .83   53963
 .84   54400
 .85   54800
 .86   55098
 .87   55766
 .88   56227
 .89   56297
 .9   57094
 .91   57785
 .92   57916
 .93   58297
 .94   58803
 .95   59709
 .96   60377
 .97   60861
 .98   61213
 .99   61744
 1   62545
Il risultato surprised myself  :o)
Ciao!!!  :o)
Livio

 On 9 Mar, 23:23, "Gabriele \"GaS\" Carelli"
Succede questa cosa buffa:
Usando soglia 0,5 ottengo un valor medio in uscita di 0,625.
Allora mi chiedo: perché usare soglia=0,5 se tanto da 0,5 a 0,625
saranno mediamente perdenti? Allora adotto soglia=0,625
Ora però il valor medio in uscita è 0,617. Allora uso soglia 0,617
Ottengo un valor medio = 0,618.
Allora uso soglia = 0,618 e ottengo valor medio in uscita = 0,618.
Un momento! 0.618 è il divin rapporto! Allora sono nel giusto, Dio è
con me!
Ciao!!!  :o)
Livio

con me!
Allora ora prova ad usare questo valore (che non è esattamente il divin 
rapporto ma il figliolino picolo) nella formula analitica correttamente 
fornita da Maurizio........
....che ne dite?
Ciao,
Gas 

 fornita da Maurizio........
Esatto: ponendo x  = (sqrt(5)-1)/2 nella mia formula si ottiene una
funzione di y il cui valore minimo è proprio 1/2. Inutile dire che il
valore di 1/2 si ottiene per y = (sqrt(5)-1)/2.
Questo mi pare risolva la questione...
Maurizio

 adottare Alice per avere almeno il 50% di probabilità di vittoria?
Faccio un tentativo anch'io:
Sia Alice che Bob tengono il numero se e` maggiore di una certa soglia
e lo cambiano se e` minore.  Chiamo:
  a = soglia di Alice
  b = soglia di Bob
  na = primo numero ricevuto da Alice 
  nb = primo numero ricevuo da Bob
** Caso [A]: a < b
* caso [A1]:  na > b, nb > b
entrambi mantengono il numero, che e` unif. distr. in (b, 1)
prob. evento: (1-b)^2
prob. vitt. A: 1/2
* caso [A2]: a < na < b < nb
entrambi mantengono il numero, ma quello di A e` minore
prob. evento: (1-b)(b-a)
prob. vitt. A: 0
* caso [A3]: na < a, nb > b
B mantiene il numero, A lo cambia
prob. evento: a*(1-b)
prob. vitt. A: (1-b)/2
* caso [A4]: na > a, nb < b
A mantiene il numero, b lo cambia
prob. evento: (1-a)*b
prob. vitt. A: (1+a)/2
* caso [A5]: na < a, nb < b
entrambi cambiano
prob. evento: a*b
prob. vitt. A: 1/2
probabilita` di vittoria di Alice nel caso [A]:
sum((prob. evento) * (prob. vitt.) nei 5 sottocasi), cioe`:
Va = (1-b)^2 / 2  +  (1-b)^2 * a / 2  +  a*b/2  +  (1-a^2)*b / 2  =
(-b*a^2 + (b^2-b+1)*a + b^2-b+1) / 2
** Caso [B]: a > b
stessi conti, scambiando a e b:
Va = (-(b+1)*a^2 + (b^2+b+1)*a + 1-b) / 2
le due curve si incontrano quando a = b, e questo e` un buon segno.
-----------------------------------------
Cosa conviene fare ad Alice?
Ovviamente le conviene sceglere a in modo da massimizzare la
probabilita` di vincita (supponiamo per ora che conosca b).
Per trovare il massimo deriviamo:
** caso [A]: a < b
d Va / d a = (-2*b*a +b^2-b+1)/2
che e` nulla per   a = (b^2-b+1)/(2*b)
e ci serve solo se a < b, cioe`  (dopo qualche sembplice conto che non
trovo piu` e non ho voglia di rifare):
b > (sqrt(5) - 1) / 2
** caso [B]: a > b
d Va / d a = (-2*(b+1)*a + b^2+b+1)/2
che e` nulla per   a = (b^2+b+1) / (2*(b+1))
e ci serve per  b < (sqrt(5)-1)/2
Come e` fatta questa funzione che ci da` la soglia migliore per A in
funzione di b?
Con qualche conto e un programma per i grafici di funzione si vede che
e` crescente nell'intervallo (0, (sqrt(5)-1)/2) e decrescente
nell'intervallo ((sqrt(5)-1)/2, 1), e
f(0) = 0.5 
f((sqrt(5)-1)/2) = (sqrt(5)-1)/2
f(1) = 0.5
Se b=0 o b=1, cioe` se Bob ha un numero uniformmente distribuito in
(0,1), la soglia migliore per Alice e` 0.5, che e` anche quella che
da` il valore medio maggiore, e questo era abbastanza intuitivo.
Nei casi intermedi, un po' a sorpresa, la soglia migliore e` piu`
alta.
Quanto vale la probabilita` di vittoria di Alice nel caso che conosca
la soglia di Bob e scelga la soglia giusta?
Nell'intervallo ((sqrt(5)-1)/2, 1) vale:
VMa(b) = (b^4+2*b^3-b^2+2*b+1) / 8*b
che e` crescente e vale 0.5 per b=(sqrt(5)-1)/2 e vale 5/8 per b=1.
Non ho voglia di fare tutti i conti anche per l'intervallo (0,
(sqrt(5)-1)/2), ma a occhio e grafici si vede che vale 5/8 per b=0 e
decresce fino a 0.5.
----------------------------------
Tornando alla domanda iniziale: Che strategia deve adottare Alice per
avere almeno il 50% di probabilità di vittoria?
Tutti questi conti non rispondono alla domanda, pero` rispondono alla
domanda simmetrica: "Cosa conviene fare a Bob?"  (A saperlo prima
avrei fatto i conti invertiti.)
La probabilita` di vittoria di Alice nel caso migliore (per lei) vale
0.5 per b=(sqrt(5)-1)/2, ed e` maggiore in tutti gli altri casi.
La probabilita` di vittoria di Bob quindi, nel caso piu` sfigato per
lui, vale 0.5 per b=(sqrt(5)-1)/2, mentre per tutti gli altri valori
di b e` minore.
Quindi l'unico valore che garantisce a Bob una probabilita di vittoria
del 50% indipendentemente dalla strategia di Alice e:
  soglia = (sqrt(5) - 1) / 2
(Ovviamente la stessa soglia vale anche per Alice.)
P.S.: Spero di aver fatto i conti giusti e di non aver perso degli a e
dei b per strada.
P.S.2: Non ho riletto quello che ho scritto.
        Mauro

 con me!
Beh, forse ce lo potevamo aspettare.
Così non ti viene voglia di cambiare un numero oltre la soglia, solo perchè 
è inferiore al valore atteso!
Quello che segue coincide in parte con molte cose già dette, ma mica potevo 
buttare tre pagine di conti così, senza gloria!
Supponiamo che Alice utilizzi una strategia di soglia s.
Dobbiamo confrontare non le strategie di Alice e Bob, ma piuttosto due 
possibili strategie di Bob e Bob1.
Supponiamo che Bob1 utilizzi una strategia neutra (la stessa soglia di 
Alice), e Bob una diversa (maggiorante o minorante) e vediamo se la 
strategia di Alice si può battere.
Se Bob adotta una strategia maggiornate di soglia y>p, vediamo che succede.
Siamo interessati a studiare solo i casi in cui ai Bob capita un numero 
compreso tra p e y. Negli altri casi le due strategie sono indistinguibili. 
Se in quei casi la strategia di Bob va meglio della neutra, allora la 
strategia è migliore, altrimenti tanto vale tenere la neutra.
Cominciamo a vedere le strategie maggiornati (y>p).
Supponiamo che ai Bob esca un numero compreso tra p e y.
In quei casi Bob1 si tiene la distribuzione uniforme su (p,y) di media 
m=(p+y)/2, Bob la cambia con una uniforme su (0,1).
Vediamo cosa può succedere ad Alice nel frattempo:
1) Tra 0 e p ha cambiato.
Adesso ha una distribuzione uniforme su (0,1), la stessa di Bob.
Bob la batte la metà delle volte.
Bob1 la batte con probabilità m
2) Tra p e y ha tenuto.
Adesso ha una distribuzione uniforme su (p,y), la stessa di Bob1
Bob la batte con probabilità 1-m
Bob1 la batte la metà delle volte.
3) Tra y e 1 ha tenuto
Adesso ha una distribuzione uniforme su (y,1), di media m=(1+y)/2
Bob la batte con probabilità 1-m
Bob1 non la batte mai
Fatti i conti si vede che la strategia di Bob è migliore di quella di Bob1 
se y < 1/(p+1)
Se scegliessimo p in modo che 1/(p+1) = p (eccolo, il magico phi che fa 
capolino) saremmo all'assurdo che le strategie maggioranti che possono 
batterla sarebbero minoranti! Quindi la strategia di soglia p=(sqrt(5)-1)/2 
non è migliorabile con una maggiorazione.
Con altri numeri minori di p, per ogni strategia ne avremmo potuto una 
migliore aumentando la soglia.
Per esempio per p=7/12 basta prendere una soglia 7/12<y<12/19 per fare 
meglio
Se invece Bob adotta una strategia minorante (y<p), i casi da analizzare 
sono quelli in cui i Bob pescano un numero compreso tra y e p.
In quei casi Bob se lo tiene, Bob1 l'avrebbe cambiato. Bob si tiene il 
numero distribuito uniformemente in (y, p) con media m=(y+p)/2, Bob1 lo 
cambia con uno distribuito tra 0 e 1, di media 1/2.
Guardiamo nel frattempo cosa è successo ad Alice:
1) Tra 0 e p ha cambiato.
Adesso ha una uniforme in (0,1)
Bob ha un numero di media m, quindi vince con probabilità m;
Bob1 vince solo una volta su due.
2) Tra p e 1 Alice ha tenuto.
Ha una uniforme su (p,1), di media (1+p)/2
Bob perde sistematicamente, pur avendo una distribuzione con una media m non 
disprezzabile
Bob1 ha media peggiore, ma vince con probabilità (p-1)/2
Facendo i conti, si vede che la strategia di Bob è migliore di quella di 
Bob1 solo se y>1/p-1
Se scegliessimo 1/p-1 = p (rieccolo!) l'equazione sarebbe soddisfatta solo 
per y>p. Di nuovo siamo all'assurdo che le strategie minoranti per battere 
la neutra devono essere maggioranti.
Quindi le strategie con p=(sqrt(5)-1)/2 non sono migliorabili neanche dal 
basso!
Se avessimo preso per Alice un valore di soglia maggiore p, l'equazione 
y>1/p-1 avrebbe avuto soluzioni!
Per esempio, per p=2/3 basterebbe prendere una soglia di 1/2<y<3/4 per 
trovare una strategia migliore con soglia più bassa.
-- 
Ciao, Silv:o)

"Gabriele GaS Carelli" ha scritto nel messaggio
Abbiamo i soliti due giocatori, vogliamo essere fantasiosi?
Chiamiamoli Alice e Bob :o)
Ogni giocatore riceve un numero uniformamente distribuito tra 0 ed 1 e
può decidere se tenerselo o scartarlo per riceverne un altro (sempre
uniformamente distribuito tra 0 ed 1). Dopo che i giocatori hanno
fatto la propria scelta ed hanno eventualmente ricevuto il secondo
numero vince il giocatore con il numero più alto. Che strategia deve
adottare Alice per avere almeno il 50% di probabilità di vittoria?
Naturalmente, affinchè il gioco sia simmetrico, i due giocatori devono
fare la scelta senza sapere quale sarà quella dell'avversario.
-----------
Ok per i due tentativi:  soglia = (RADQ(5)-1)/2
Ma se si potesse decidere di tenere o scartare il numero ricevuto
con un massimo di 3 volte (o di 4 o 5 ecc...)?
Non è che basta fare
(RADQ(N^2+1)-1)/N     o magari       ((N^N+1)^(1/N)-1)/N      ?
N=numero massimo di tentativi a disposizione
Ciao, Nino 

 dei b per strada.
Sembra proprio che tu abbia tirato fuori il risultato corretto come fatto 
anche da Livio (quasi), Maurizio e Silvio: complimenti a tutti.
Alla prossima,
Gabriele 

Passato il fine settimana, do la mia soluzione (che magari conicide
con qualcuna gia' data).
Bob ha come soglia S1, Alice S2, con S1<S2
Possiamo suddividere i numeri in tre gruppi:
a)  0<N<S1
b) S1<N<S2
c) S2<N<1
Se entrambi i giocatori finiscono in uno stesso gruppo. c'e' il 50% di
probabilita' che vinca A.
Se finiscono in gruppi diversi, che e' nel gruppo maggiore vince (per
gruppo maggiore intendo quello che comprende i numeri piu' alti.
Probabilita' che B sia nel gruppo a: S1^2
Probaiblita' di vittoria di A (ossia 50% di probabilita' di essere in
a + probabilita' di essere in B o C): 1-(S1*S2/2)
Probabilita' che B sia in b: (S2-S1) *(1+S1)
Probabilita' di vittoria di A: S2*(S2-S1)/2 + (1-S2^2)
Probabilita' che B sia in c: (1-S2)*(1+S1)
Probaiblita' di vittoria di A: (1-S2^2)/2
La prob complessiva di vittoria di A e' quindi:
P(A, S1, S2) = (S1^2)*(1-(S1*S2/2)) +   (S2-S1) *(1+S1) * (S2*(S2-S1)/
2 + (1-S2^2)) +  (1-S2)*(1+S1)*  (1-S2^2)/2
per S1<S2 e
P(A, S1, S2)= 1 - l'espressione precedente scambiando S1 e S2
per S1>S2
A questo punto si verifica per quale S1 viene minimizzata P(A) e
otteniamo la strategia di Bob.
A questo punto otteniamo una P(A, S2). Verifichiamo quale valore di S2
la massimizza ed ecco la strategia di Alice.
E ora tocca ai colcoli.

 E ora tocca ai colcoli.
Primi "rosoltoti" dei "colcoli";
S1<S2 :
P(A, S1, S2) = (1 + S2 -S1 + S1*S2 - S2^2 + S1^2*S2 - S1* S2^2 +
S1^3*S2 - S1*S2^3)/2
S2<S1:
P(A, S1, S2) = (1 + S2 - S1 - S1*S2 + S1^2 + S1^2*S2 - S1* S2^2 +
S1^3*S2 - S1*S2^3)/2