Quesito con la Susi
Maurizio Codogno
La Susi e il suo amico Gianni sono stati invitiati a partecipare a un gioco
a premi del tipo "collaborativo", di svolgimento a loro sconosciuto.
Vengono messi in due stanze distinte, senza nessuna possibilità di
comunicazione con l'esterno, e gli viene chiesto di puntare su un numero da
1 a 10. Chi avrà puntato sul numero più alto vince, e otterrà 1000 euro
moltiplicati per il numero scelto (ad esempio, se il numero scelto è il 6
vincerà 6000 euro). Se però entrambi puntano sullo stesso numero, nessuno
vince.
Questo tipo di gioco è detto "collaborativo" perché generalmente dà adito a
dei paradossi: entrambi i giocatori hanno interesse a puntare sul 10 per
massimizzare la propria vincita, e quindi finiscono con il perdere tutto.
Ma Gianni e la Susi sono amiconi, e prima di iniziare hanno deciso di
dividersi fraternamente la vincita. Inoltre, con tutti i quesiti che hanno
dovuto risolvere per la Settimana Enigmistica, sanno entrambi trovare la
migliore strategia dato il vincolo di operare alla cieca.
E noi sappiamo farlo?
Ricordo che il gioco e` a priori sconosciuto: insomma, quello che non
voglio permettere e` dire "Susi scegliera` sempre l'opzione migliore e
Gianni la peggiore".
Chi non sapesse da dove partire per affrontare il problema può iniziare con
due problemi più semplici. Nel primo, il premio è sempre di 1000 euro,
qualunque sia il numero vincente. Nel secondo, si può solo scegliere tra i
numeri 1 e 2. Attenti, però! la soluzione di questi casi particoari *non*
si può generalizzare (ho un controesempio)
ciao, .mau.
ps: qualcuno ha della bibliografia su questo tipo particolare di giochi
collaborativi, dove i giocatori collaborano ma senza sapere le mosse
dell'altro?
Roberto Corda
Partiamo dal presupposto che Gianni e Susy si odino tra loro
almeno quanto io li odio. :-)
Maurizio Codogno wrote:
> La Susi e il suo amico Gianni sono stati invitiati a partecipare a un gioco
> a premi del tipo "collaborativo", di svolgimento a loro sconosciuto.
> Vengono messi in due stanze distinte, senza nessuna possibilità di
> comunicazione con l'esterno, e gli viene chiesto di puntare su un numero da
> 1 a 10. Chi avrà puntato sul numero più alto vince, e otterrà 1000 euro
> moltiplicati per il numero scelto (ad esempio, se il numero scelto è il 6
> vincerà 6000 euro). Se però entrambi puntano sullo stesso numero, nessuno
> vince.
>
Quindi la tabella e' la seguente: (i numeri vanno considerati in migliaia) G\S
1 2 3 4 5 6 7 8 9 10
1 (0,0) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9) (0,10)
2 (2,0) (0,0) (0,3) (0,4) ...
3 (3,0) (3,0) (0,0) (0,4)
Si legge in questo modo: se gianni gioca 2 (seconda riga) e Susy gioca 3 (terza
colonna)
gianni ricevera' zero lire e Susy 3000 (0,3)
Applico l'algoritmo di minimax, ovvero la legge di murphy: "qualsiasi cosa io
faccia
il mio avversario avra' fatto la cosa che mi danneggia di piu'"
Notare che parto dal presupposto che l'unico dato che mi interessa e' il mio
guadagno
non quello del mio avversario (nota importante non essendo questo un gioco
a somma zero, ovvero un gioco in cui una mia vittoria porta ad una sconfitta
uguale
e contraria nell'avversario)
Quindi se Susy gioca 1 Gianni giochera' tutto tranne che 1, anzi giochera'
sicuramente
10 volendo massimizzare il proprio guadagno. Lo stesso ragionamento si puo fare
con 2, 3, 4 ecc. Il punto in cui le due opposte volonta in qualche modo
(paradossale)
coincidono e' il punto (10,10) dove entrambi non guadagnano nulla.
> Ma Gianni e la Susi sono amiconi, e prima di iniziare hanno deciso di
> dividersi fraternamente la vincita. Inoltre, con tutti i quesiti che hanno
> dovuto risolvere per la Settimana Enigmistica, sanno entrambi trovare la
> migliore strategia dato il vincolo di operare alla cieca.
Quanto alla cieca? Ovvero in quali di queste condizioni siamo?
-i giocatori possono comunicare tramite una prima serie di giocate
"protocollarii" in cui decidono come comportarsi in seguito.
- i giocatori hanno (o meno) ricordo delle giocate precedenti (vedi tit-4-tat
usato
per il dilemma del prigioniero)
- I giocatori hanno semplicemente deciso di dividersi la vincita in una fase
extra-gioco
(non credo che sia questa la possibilita')
Ho in mente tre strategie diverse a seconda del caso, non so se sono ottime
ma sicuramente sono buone.
> ciao, .mau.
>
> ps: qualcuno ha della bibliografia su questo tipo particolare di giochi
> collaborativi, dove i giocatori collaborano ma senza sapere le mosse
> dell'altro?
" Teoria dei giochi e comportamento economico"?... forse tratta solo dei giochi
competitivi.. guardo a casa.
Ciao, Roberto
Matteo Dell'Amico
>Nel primo, il premio è sempre di 1000 euro, qualunque sia il numero
>vincente.
In questo caso, dato che la situazione e` simmetrica, non credo che si
possa fare meglio di tirare a caso. Si avrebbe 9/10 di probabilita` di
vincere il premio (o, per dirla in un altro modo, una vincita media di 900
euro).
>Nel secondo, si può solo scegliere tra i numeri 1 e 2.
Anche in questo caso l'eventuale vincita e` costante (2000 euro). Di nuovo,
conviene tirare a caso, si avrebbe il 50% di probabilita` di vittoria.
--
Saluti,
Matteo
Roberto Corda
Seguono le mie soluzioni del gioco, piu' una critica alla domanda stessa e la
proposta di un
nuovo gioco molto simile a quello proposto
Roberto Corda
Roberto Corda wrote:
[errore di trasmissione ha zappato 2 pagine di messaggio ..%$@$%.. riscrivo tutto
dannaz..]
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
La teoria dei giochi e' un modo per modellare la razionalita' e le preferenze (la
psicologia)
dei giocatori. per questo motivo e' necessario indagare piu' a fondo che tipo di
rapporto
lega Gianni e Susy. A seconda del rapporto umano intercorrente propongo un
diverso
algoritmo, o piu' precisamente strategia.
-Primo algorimo: si odiano a morte.
E' il tipo di rapporto di cui parlavo nel post precedente. I due giocatori
tendono a
massimizzare il proprio profitto senza curarsi delle vittorie (o sconfitte)
altrui.
Semplifico il gioco per amor di concisione, il ragionamento fatto e' facilmente
estensibile
al gioco proposto. Diciamo Che i competitori possano scegliere solo tra 3 numeri.
La tabella (in gergo "bimatrice") diventa:
G\S 1 2 3
1 (0,0) (0,2) (0,3)
2 (2,0) (0,0) (0,3)
3 (3,0) (3,0) (0,0)
Gianni (e susy in maniera duale) ragiona in questo modo:
se S gioca 1 io massimizzero' il mio profitto giocando 3
se S gioca 2 -idem- giocando 3
se S gioca 3 mi e' indifferente qualsiasi giocata perche' comunque guadagnero'
niente.
Riassumendo Gianni (e dualmente Susy) decide in questo modo che l'unica cosa
razionale
da fare e' giocare sempre 3.
Questo stato di cose descritto dal ragionamento seguente si chiama "esistenza di
una
strategia dominante (non strettamente tale per la precisione)" in altre parole
esiste
un modo di comportarsi nel gioco che permette di vincere sempre o perlomeno di
non
perdere.
Nella TdG si conclude che se una strategia dominante esiste il giocatore
razionale
la usa. - la cosa che mi sono sempre chiesto e' come modellare il giocatore
irrazionale
ma questo e' un altro discorso -
- Secondo Algoritmo: sono sposati con la comunione dei beni.
In questo caso la cooperazione e' possibile in quanto i premi vengono spartiti
tra idue
ma con un trucco, la tabella, e quindi il gioco, e' cambiata diventando:
G\S 1 2 3
1 (0,0) (1,1) (1.5,1.5)
2 (1,1) (0,0) (1.5, 1.5)
3 (1.5,1.5) (1.5,1.5) (1.5,1.5)
In questo caso esistono 4 strategie razionali cooperative pure (piu' forse altre
miste
ovvero probabilistiche)
(1,3) (2,3) (3,1) (3,2)
In pratica uno dei due (master) vince sempre e l'altro (servant) perde sempre,
tanto poi
si spartiranno il bottino. Questo e' pero' il caso che .mau. voleva evitare.
-Sono Amici: fiducia limitata (non si spartiscono il bottino)
Per le ragioni descritte nel primo algoritmo questo caso , ovvero il gioco
proposto,
non ha soluzione razionale - ne ha un mucchio irrazionali sia chiaro che
potrebbero
cadere sotto il titolo "immolarsi per la patria" -
Si potrebbero trovare delle strategie cooperative facendo una piccola variazione
al
gioco per evitare la "strategia dominante".
Variazione sul tema.
Il gioco rimane quello di prima solo che nel caso (G:10, S:10) entrambi i
giocatori
perdono, diciamo, 1000 ovvero vincono -1000.
Bibl. (ovvero che libro mi sono riletto ieri :-)
Ken Binmore - Fun and Games
7o capitolo per le strategie cooperative.
Ciao, Roberto
Marco Coletti
m...@beatles.cselt.it (Maurizio Codogno) wrote:
>La Susi e il suo amico Gianni sono stati invitiati a partecipare a un gioco
>a premi del tipo "collaborativo", di svolgimento a loro sconosciuto.
>Vengono messi in due stanze distinte, senza nessuna possibilità di
>comunicazione con l'esterno, e gli viene chiesto di puntare su un numero da
>1 a 10. Chi avrà puntato sul numero più alto vince, e otterrà 1000 euro
>moltiplicati per il numero scelto (ad esempio, se il numero scelto è il 6
>vincerà 6000 euro). Se però entrambi puntano sullo stesso numero, nessuno
>vince.
>Ma Gianni e la Susi sono amiconi, e prima di iniziare hanno deciso di
>dividersi fraternamente la vincita. Inoltre, con tutti i quesiti che hanno
>dovuto risolvere per la Settimana Enigmistica, sanno entrambi trovare la
>migliore strategia dato il vincolo di operare alla cieca.
Assumo che a Susi e Gianni sia concessa una sola giocata oppure che non possano
esaminare il risultato delle giocate precedenti.
<SUSI>
Non so quanto sia intelligente Gianni, esso potrebbe fare un sacco di
ragionamenti diversi, più o meno corretti, quindi assumo che Gianni indicherà a
caso un numero da 1 a 10 (cioè Gianni indica un numero qualsiasi con
probabilità 1/10).
Se io indico il numero n, la vincita attesa (vincita media) è
sum_k{1..n-1} (1/10) 1000n + sum_k{n+1..10} (1/10) 1000k =
sum_k{1..n-1} 100n + sum_k{n+1..10} 100k =
sum_k{1..n} 100n - 100n + sum_k{n+1..10} 100k =
100n^2 - 100n + 100 (n+11)(10-n)/2 =
50n^2 - 150n + 5500
per cui mi conviene indicare il numero n=10 per massimizzare la vincita attesa,
la quale sarà in tal caso 9000.
D'altra parte anche Gianni farà lo stesso ragionamento e sceglierà 10, dunque
io devo scegliere un numero da 1 a 9 per massimizzare la vincita.
Dato che dopotutto potrebbe anche scegliere un numero da 1 a 9, sceglierò 9 per
massimizzare la vincita attesa (calcolo analogo al precedente).
Ma anche Gianni lo capirà e...
Basta! Qualunque ragionamento sensato io faccia, lo farà probabilmente anche
Gianni rendendo controproducente il ragionamento di entrambi.
Dunque mi affido al caso: se scelgo a caso un numero da 1 a 10 evito il
probabile conflitto di scelte razionali, e anche se Gianni giunge alla mia
stessa conclusione e si affida al caso non ci sarà conflitto deterministico.
Quale distribuzione di probabilità devo assegnare ai numeri da 1 a 10? Tenendo
presente che Gianni (in virtù del fatto che ragiona come me) sceglierà la mia
stessa distribuzione, vediamo qual'è la distribuzione di probabilità p(n) tale
che, se x e y sono due variabili aleatorie con tale distribuzione (che
rappresentano il numero scelto da me e il numero scelto da Gianni), la funzione
aleatoria che rappresenta la vincita
f(x,y) = 1000 max(x,y) se x!=y
f(x,y) = 0 se x=y
abbia aspettazione massima.
L'aspettazione E[f(x,y)] si può scrivere direttamente (senza calcolare la
distribuzione di probabilità di f(x,y)) in base a considerazioni "intuitive":
essa è la vincita 1000 moltiplicata per la probabilità che uno di noi due
scelga 1 e l'altro scelga un numero minore, più la vincita 2000 moltiplicata
per la probabilità che uno di noi due scelga 2 e l'altro scelga un numero
minore, più la vincita 3000 moltiplicata per la probabilità che uno di noi due
scelga 3 e l'altro scelga un numero minore, ... più la vincita 10000
moltiplicata per la probabilità che uno di noi due scelga 10 e l'altro scelga
un numero minore.
La probabilità che uno di noi due scelga n e l'altro scelga un numero minore è
uguale alla probabilità che io scelga n e Gianni scelga un numero minore più la
probabilità che Gianni scelga n e io scelga un numero minore, cioè (per
simmetria) è pari a due volte la probabilità che io scelga n e Gianni scelga un
numero minore.
La probabilità che io scelga n e Gianni scelga un numero minore (eventi
indipendenti) è pari al prodotto della probabilità che io scelga n per la
probabilità che Gianni scelga un numero minore; la probabilità che Gianni
scelga un numero minore di n è p(1)+p(2)+...p(n-1). Dunque la probabilità che
io scelga n e Gianni scelga un numero minore è:
p(n)[p(1)+p(2)+...p(n-1)]
In conclusione l'aspettazione di vincita è:
2000 2p(2)p(1) + 3000 2p(3)[p(1)+p(2)] +... 10000 2p(10)[p(1)+p(2)+...p(9)]
che con la notazione di sommatoria diventa:
sum_k{2..10} 1000k 2p(k) sum_i{1..k-1} p(i)
cioè:
2000 sum_k{2..10} k p(k) sum_i{1..k-1} p(i)
La distribuzione p(n) soddisfa per definizione alle condizioni:
0 <= p(n) <= 1
sum_n{1..10} p(n) = 1 (normalizzazione)
Dalla condizione di normalizzazione segue:
sum_i{1..k-1} p(i) = 1 - sum_i{k..10} p(i)
che sostituisco nell'espressione dell'aspettazione di vincita:
2000 sum_k{2..10} k p(k) [1 - sum_i{k..10} p(i)]
Col cambio di notazione x_j := p_(j+1) (per comodità), il problema diventa
dunque quello di massimizzare la funzione reale di 9 variabili reali x_1, x_2,
..., x_9:
f(x_1, x_2, ..., x_9) := sum_k{1..9} (k+1) x_k [1 - sum_i{k..9} x_i)]
nel dominio:
| 0 <= x_1 <= 1
| 0 <= x_2 <= 1
| ...
| 0 <= x_9 <= 1
| 0 <= x_1 + x_2 + ... x_9 <= 1
problema che si risolve cercando i punti x = (x_1, x_2, ... x_9) dove le
derivate parziali @f/@x_j si annullano tutte e controllando se ivi le derivate
parziali di ordine due @@f/@x_j@x_j sono tutte negative (il che significa che
abbiamo trovato un massimo relativo).
Si tratta cioè di risolvere il sistema:
@f/@x_j f(x_1, x_2, ..., x_9) == 0 j = 1..9
@f/@x_j f(x_1, x_2, ..., x_9) =
@f/@x_j sum_k{1..9} (k+1) x_k [1 - sum_i{k..9} x_i] =
@f/@x_j sum_k{1..j-1} (k+1) x_k [1 - sum_i{k..9} x_i] +
@f/@x_j (j+1)x_j [1 - sum_i{j..9} x_i] +
@f/@x_j sum_k{j+1..9} (k+1) x_k [1 - sum_i{k..9} x_i] =
- sum_k{1..j-1} (k+1) x_k + (j+1)(1 - 2x_j - sum_i{j+1..9} p_i) + 0 =
j+1 - sum_i{1..j-1} (i+1) x_i - 2(j+1)x_j - sum_i{j+1..9} (j+1) x_i =
j+1 - sum_i{1..9} [(i<=j)(i+1) + (i>=j)(j+1)] x_i
Il sistema da risolvere diventa dunque:
sum_i{1..9} [(i<=j)(i+1) + (i>=j)(j+1)] x_i == j+1 j = 1..9
Se poniamo
x := [x_1 x_2 ... x_9]trasposto
v := [2 3 4 5 6 7 8 9]trasposto
A := 4 2 2 2 2 2 2 2 2
2 6 3 3 3 3 3 3 3
2 3 8 4 4 4 4 4 4
2 3 4 10 5 5 5 5 5
2 3 4 5 12 6 6 6 6
2 3 4 5 6 14 7 7 7
2 3 4 5 6 7 16 8 8
2 3 4 5 6 7 8 18 9
2 3 4 5 6 7 8 9 20
il sistema, in notazione matriciale, diventa
A x == v
Esso si può risolvere abbastanza facilmente per sottrazioni di righe e
sostituzioni.
Ma io (Susi) tiro fuori dalla borsa il mio laptop con
Mathcad/Derive/Mathematica/Matlab/Maple e calcolo simbolicamente la matrice
inversa A^(-1) e il prodotto A^(-1) v.
La soluzione del sistema è:
x = A^(-1) v = 181440/6996581
241920/6996581
332640/6996581
453600/6996581
609840/6996581
808560/6996581
1058670/6996581
1370830/6996581
1757641/6996581
Le derivate parziali di secondo ordine valgono:
@@f/@x_j@x_j f(x_1, x_2, ..., x_9) =
@f/@x_j {j+1 - sum_i{1..9} [(i<=j)(i+1) + (i>=j)(j+1)] x_i} =
- @f/@p_j 2(j+1) x_j =
-2(j+1)
Esse sono negative ovunque, x compreso, dunque x è un massimo relativo.
Il punto x è all'interno del dominio dato, inoltre essendo unica la soluzione
del sistema visto, esso è l'unico massimo o minimo relativo e pertanto sulla
frontiera del dominio la funzione massimizzanda è minore.
In conclusione il punto x trovato è un punto di massimo assoluto nel dominio
dato.
Da x si ricavano p(n) = x_(n-1) per n=2..10, mentre p(1) si ricava dalla
condizione di normalizzazione, e infine:
p(1) = 181440/6996581
p(2) = 181440/6996581
p(3) = 241920/6996581
p(4) = 332640/6996581
p(5) = 453600/6996581
p(6) = 609840/6996581
p(7) = 808560/6996581
p(8) = 1058670/6996581
p(9) = 1370830/6996581
p(10) = 1757641/6996581
L'aspettazione di vincita in tal caso è
2000 sum_k{2..10} k p(k) sum_i{1..k-1} p(i) = 52389400000/6996581 =~ 7487.85
A questo punto ho il problema di costruire un esperimento fisico in cui la
probabilità di estrarre un numero da 1 a 10 sia quella trovata.
</SUSI>
Maurizio Codogno
In article <3801E34D...@ntboss.tesi.dsi.unimi.it>,
Roberto Corda <cor...@ntboss.tesi.dsi.unimi.it> wrote:
" Partiamo dal presupposto che Gianni e Susy si odino tra loro
" almeno quanto io li odio. :-)
" Il punto in cui le due opposte volonta in qualche modo
" (paradossale)
" coincidono e' il punto (10,10) dove entrambi non guadagnano nulla.
E questo e` ben noto.
" > Ma Gianni e la Susi sono amiconi, e prima di iniziare hanno deciso di
" > dividersi fraternamente la vincita. Inoltre, con tutti i quesiti che hanno
" > dovuto risolvere per la Settimana Enigmistica, sanno entrambi trovare la
" > migliore strategia dato il vincolo di operare alla cieca.
"
" Quanto alla cieca? Ovvero in quali di queste condizioni siamo?
"
" -i giocatori possono comunicare tramite una prima serie di giocate
" "protocollarii" in cui decidono come comportarsi in seguito.
No.
" - i giocatori hanno (o meno) ricordo delle giocate precedenti (vedi tit-4-tat
" usato per il dilemma del prigioniero)
No.
" - I giocatori hanno semplicemente deciso di dividersi la vincita in una fase
" extra-gioco (non credo che sia questa la possibilita')
E invece si`.
ciao, .mau.
Maurizio Codogno
In article <38033C3...@ntboss.tesi.dsi.unimi.it>,
Roberto Corda <cor...@ntboss.tesi.dsi.unimi.it> wrote:
" In pratica uno dei due (master) vince sempre e l'altro (servant) perde sempre,
" tanto poi si spartiranno il bottino. "
Ecco, vorrei evitare che uno faccia necessariamente il master.
Senno` e` troppo banale...
.mau.
Roberto Corda
Maurizio Codogno wrote:
Come dicevo esistono 4 strategia vincenti pure (in cui e' stabilito si dall'inizio
cosa fare)piu' altre miste, in cui probabilisticamente si adotta una strategia
piuttosto che un'altra.
Scrivo la sotto matrice delle scelte 9 e 10 del gioco originale in cui pero' i due
si
spartiscono il bottino.
G\S 9 10
9 (0,0) (5,5)
10 (5,5) (0,0)
Ovvero tutti e due decidono di giocare solo o 9 o 10. Se giocano lo stesso numero
perdono. Se giocano numeri diversi vincono.
Strategie da te vietate: uno vince sempre, dopo che il primo ha vinto vincono e
perdono
alternativamente (a causa della spartizione in realta' vincono sempre)
Strategia mista ovvero probabilistica di rango p:
ognuno dei due giocatori sceglie 9 con prob. p e 10 con prob 1-p
quindi ogni giocatore vince ad ogni turno(mediamente):
v = 5*p^2 + 5*(1-p)^2
con p=1/2 v = 2.5
con p=1 v = 5 ( master & servant: strategia vietata)
mi e' sorto un dubbio atroce, forse non ho capito un roba: ma Gianni e Susy
conoscono
la tabella (funzione giocata/vittoria) fin dall'inizio vero?
Ciao, Roberto
Roberto Corda
Marco Coletti wrote:
> m...@beatles.cselt.it (Maurizio Codogno) wrote:
>
> >La Susi e il suo amico Gianni sono stati invitiati a partecipare a un gioco
> >a premi del tipo "collaborativo"
>
> Assumo che a Susi e Gianni sia concessa una sola giocata oppure che non possano
> esaminare il risultato delle giocate precedenti.
>
> <SUSI>
> [altri ragionamenti inutili] quindi assumo che Gianni indicherà a
> caso un numero da 1 a 10
Non sono d'accordo, purtroppo il motivo e' piu' psicologico che matematico.
Io assumerei che il mio "compagno di merende" sia razionale
e che ragioni nello stesso modo in cui io ragionerei al suo posto.
Nel caso piu' semplice, come piu' volte detto, da .mau. per primo, un avversario
ostile
gioca semplicemente 10. Un finto-avversario come Gianni ragiona in questo modo:
e' bene che uno di noi due giochi 10 e l'altro giochi un numero minore quindi
scelgo il
punto dello spazio delle giocate (la coppia 10 e n<10) che massimizzi la vincita
media con
probabilita' di scelta del 10 p.
Ovvero algoritmo :
provo tutte le coppie (10,n) con n<10 e guardo quanto vinco mediamente se gioco
10 con probabilita' p, prendo il massimo di questa funzione. Ripeto l'operazione
per
tutti gli n. sino a trovare la coppia (_p,_n).
Quindi inizio a giocare 10 con probabilita' _p
e _n con probabilita' (1 - _p).
Questa e' , implicitamente, la soluzione cercata.
Ciao, Roberto
Marco Coletti
Roberto Corda <cor...@ntboss.tesi.dsi.unimi.it> wrote:
>> [altri ragionamenti inutili] quindi assumo che Gianni indicherà a
>> caso un numero da 1 a 10
>
>Non sono d'accordo, purtroppo il motivo e' piu' psicologico che matematico.
>Io assumerei che il mio "compagno di merende" sia razionale
>e che ragioni nello stesso modo in cui io ragionerei al suo posto.
Su cosa non sei d'accordo? Non si capisce.
Se hai letto tutto il mio intervento ti sarai accorto che Susi a un certo punto
assume che Gianni si comporterà esattamente come lei, proprio come dici tu.
>Un finto-avversario come Gianni ragiona in questo modo:
>e' bene che uno di noi due giochi 10 e l'altro giochi un numero minore quindi
>scelgo il
>punto dello spazio delle giocate (la coppia 10 e n<10) che massimizzi la vincita
>media con
>probabilita' di scelta del 10 p.
>
>Ovvero algoritmo :
>provo tutte le coppie (10,n) con n<10 e guardo quanto vinco mediamente se gioco
>10 con probabilita' p, prendo il massimo di questa funzione. Ripeto l'operazione
>per
>tutti gli n. sino a trovare la coppia (_p,_n).
>Quindi inizio a giocare 10 con probabilita' _p
>e _n con probabilita' (1 - _p).
Questa sarebbe la seguente distribuzione di probabilità:
p(1) = 0
p(2) = 0
...
p(_n-1) = 0
p(_n) = 1-_p
p(_n+1) = 0
...
p(10) = _p
Credo di aver già dimostrato che la distribuzione che massimizza la vincita
media è un'altra e precisamente:
p(1) = 181440/6996581
p(2) = 181440/6996581
p(3) = 241920/6996581
p(4) = 332640/6996581
p(5) = 453600/6996581
p(6) = 609840/6996581
p(7) = 808560/6996581
p(8) = 1058670/6996581
p(9) = 1370830/6996581
p(10) = 1757641/6996581
--
---------------------------------------------------------------------
Marco Coletti
Network Admin, Webmaster, Tuttologo :)
PGP public key:
http://www.trustcenter.de:11371/pks/lookup?search=0x96A79061&op=index
Fingerprint: 9F E5 80 61 F6 9F 05 2D EA 53 6F 2D 82 8B C7 C2
Certificate: http://www.trustcenter.de/cgi-bin/SearchCert.cgi
---------------------------------------------------------------------
Marco Coletti
Roberto Corda <cor...@ntboss.tesi.dsi.unimi.it> wrote:
>provo tutte le coppie (10,n) con n<10 e guardo quanto vinco mediamente se gioco
>10 con probabilita' p, prendo il massimo di questa funzione. Ripeto l'operazione
>per
>tutti gli n. sino a trovare la coppia (_p,_n).
>Quindi inizio a giocare 10 con probabilita' _p
>e _n con probabilita' (1 - _p).
Come dici anche tu, Susi deve assumere che Gianni arrivi esattamente alle
medesime conclusioni.
Tenendo conto di questa premessa, vediamo dove ci conduce la tua idea.
Susi gioca 10 con probabilità p e n (n<10) con probabilità 1-p.
Gianni fa lo stesso.
La vincita media è:
10000 {P[{Susi gioca 10 e Gianni n}] + P[{Susi gioca n e Gianni 10}]} +
0 {P[{Susi gioca 10 e Gianni 10}] + P[{Susi gioca n e Gianni n}]} =
Dato che Susi e Gianni non comunicano, i rispettivi eventi sono indipendenti,
dunque:
P[{Susi gioca 10 e Gianni n}] = P[{Susi gioca 10}]P[{Gianni gioca n}] =
p(1-p)
Inoltre, per simmetria:
P[{Susi gioca 10 e Gianni n}] = P[{Susi gioca n e Gianni 10}] = p(1-p)
Dunque la vincita media diventa:
10000 2p(1-p) = 20000 p(1-p)
Come era prevedibile, è irrilevante quale sia il numero n<10.
E' banale massimizzare p(1-p): il valore massimo 1/4 si ottiene per p=1/2.
Dunque la vincita media sarà 2500, ben al di sotto di quella derivante dall'uso
della p(k) che ho calcolato nella mia "soluzione" del problema, la quale è pari
a 7487.85.
Marco Coletti
marco....@ZZZeurofin.it (Marco Coletti) wrote:
>Dunque la vincita media diventa:
> 10000 2p(1-p) = 20000 p(1-p)
>E' banale massimizzare p(1-p): il valore massimo 1/4 si ottiene per p=1/2.
>
>Dunque la vincita media sarà 2500, ben al di sotto di quella derivante dall'uso
Ho dimenticato il 2.
La vincita media è 5000, comunque più bassa di quella da me ottenuta.
oha
On 14 Oct 1999 17:45:40 +0200, marco....@ZZZeurofin.it (Marco
Coletti) wrote:
| Susi gioca 10 con probabilità p e n (n<10) con probabilità 1-p.
| Gianni fa lo stesso.
se invece si scegliesse un numero a caso fra 10 e 9, anziche' solo 10?
le cose si complicano ma di poco.
in pratica nei casi in cui solo uno scelga 10 o 9 portano ad una
vincita inferiore del 5%, ma nei casi in cui non avrebbero vinto ci
sarebbe una probabilita' del 50% di vincere la quota massima
per non dimenticare nulla (almeno spero), la vincita che ci sarebbe se
entrambi optassero per un numero < 9 sarebbe inferiore, ma di poco
Oha
Marco Coletti
o...@gd8.com (oha) wrote:
>se invece si scegliesse un numero a caso fra 10 e 9, anziche' solo 10?
>
>le cose si complicano ma di poco.
E le cose migliorano, ma di poco.
Stiamo sempre considerando sottocasi del problema generale di determinare la
distribuzione di probabilità ottima sui numeri da 1 a 10. Problema che ho già
risolto in altro messaggio.
Marco Coletti
"Paolo Licheri" <paolo....@libero.it> wrote:
>Procedendo in modo analogo, trovo:
>
>range valore KEuro
>9-10 5
>8-10 6.44...
>7-10 7
>6-10 7.2
>5-10 7.22...
>4-10 7.14...
>3-10 7
>2-10 6.81...
>1-10 6
>
>quindi la strategia ottimale dovrebbe essere per entrambi la scelta casuale
>nel range 5-10.
Osservo che la tua ipotesi migliore, cioè la scelta di un numero da 5 a 10 con
equi-probabilità 1/6, equivale a scegliere un numero da 1 a 10 con probabilità:
1 0
2 0
3 0
4 0
5 1/6
6 1/6
7 1/6
8 1/6
9 1/6
10 1/6
Guarda caso questa mi pare la distribuzione di probabilità più simile a quella
da me ottenuta in un precedente messaggio, la quale è (io ritengo) la migliore
possibile e comporta una vincita media di 7.48785 KEuro.
Mi viene persino il dubbio che il mio msg non sia arrivato su certi
newsserver...
Marco Coletti
"Enrico Boni" <enric...@iol.it> wrote:
>Quindi l'unica possibile soluzione, in prima approssimazione (mi riservo di
>verificare meglio), e' puntare a caso. In questo modo, se i due usano
>algoritmi di generazione di numeri casuali diversi, possono sperare di
>vincere qualcosa essendo la probabilita' di collisione 1/10. In questo caso
Giocare "a caso" è la scelta giusta, ma non necessariamente con numeri
equiprobabili.
Forse il mio msg del 13.10.99 con la soluzione ottima era incomprensibile?
Roberto Corda
Marco Coletti wrote:
> Francesco Potorti` <F.Po...@cnuce.cnr.it> wrote:
> Adesso aspetto che qualcuno se ne esca con un'idea per una procedura
> ragionevole che realizzi fisicamente la distribuzione di probabilità:
> p(1) = 181440/6996581
> p(2) = 181440/6996581
> ...
un urna con 6996581 fogliettini di cui
181440 con scritto 1
181440 con scritto 2
ecc..
Ciao, Roberto
Roberto Corda
Marco Coletti wrote:
> m...@beatles.cselt.it (Maurizio Codogno) wrote:
>
> >La Susi e il suo amico Gianni sono stati invitiati a partecipare a un gioco
> >a premi del tipo "collaborativo", di svolgimento a loro sconosciuto.
>
> <SUSI>
> essa è la vincita 1000 moltiplicata per la probabilità che uno di noi due
> scelga 1 e l'altro scelga un numero minore
Non esiste la vincita mille: non esistono numeri minori di uno in questo
gioco.Conti a parte (che non ho controllato), ho cambiato idea :credo che la tua
sia la soluzione migliore.
In effetti quello proposto non e' un "gioco" ma un "problema di massimo"
esattamente
come tu l'hai affrontato.
Mi restano i dubbi relativi al comportamento di giocatori reali, ma questo credo
che esuli
dal problema.
Ciao, Roberto
Marco Coletti
Roberto Corda <cor...@ntboss.tesi.dsi.unimi.it> wrote:
>un urna con 6996581 fogliettini di cui
>181440 con scritto 1
>181440 con scritto 2
>
>ecc..
Lapalissiano... ;-)
Marco Coletti
Roberto Corda <cor...@ntboss.tesi.dsi.unimi.it> wrote:
>> <SUSI>
>> essa è la vincita 1000 moltiplicata per la probabilità che uno di noi due
>> scelga 1 e l'altro scelga un numero minore
>
>Non esiste la vincita mille: non esistono numeri minori di uno in questo
>gioco.Conti a parte (che non ho controllato),
E infatti la probabilità in questione è zero e così il termine relativo alla
vincita 1000 sparisce. Ne ho tenuto conto.
>ho cambiato idea :credo che la tua
>sia la soluzione migliore.
Grazie.
Ho vinto quàcchecòsa? ;-)
>Mi restano i dubbi relativi al comportamento di giocatori reali, ma questo credo
>che esuli
>dal problema.
Un giocatore reale probabilmente giocherebbe 1, confidando che l'altro (meno
intelligente) giochi 10. Oppure, resosi conto del conflitto potenziale,
giocherebbe il primo numero che gli passa per la testa (scelta a caso di 10
numeri equiprobabili).
Marco Coletti
Matteo Cortese <m.co...@libero.it> wrote:
>MC> Adesso aspetto che qualcuno se ne esca con un'idea per una procedura
>MC> ragionevole che realizzi fisicamente la distribuzione di probabilità:
>MC> p(1) = 181440/6996581
>MC> p(2) = 181440/6996581
>MC> p(3) = 241920/6996581
>MC> p(4) = 332640/6996581
>MC> p(5) = 453600/6996581
>MC> p(6) = 609840/6996581
>MC> p(7) = 808560/6996581
>MC> p(8) = 1058670/6996581
>MC> p(9) = 1370830/6996581
>MC> p(10) = 1757641/6996581
>
>Ma questo è banale. Susi lancia 7 volte un dado a 10 facce (da 0 a 9) e
>scrive le 7 cifre una affianco all'altra a formare un unico numero, che
>chiameremo x.
>Se x supera 6996580 ripete i 7 lanci.
E con ciò lo x ottenuto è una variabile aleatoria intera uniformemente
distribuita sul dominio {0, 1, 2, ...6996579, 6996580}.
Cioè:
P[{x=k}] = 1/6996581 k=0..6996580
>Adesso applica questa partizione: [uso la P maiuscola per indicare i valori
>non normalizzati, cioè P(i) = 6996581p(i)]
>
> se x < 181440 [cioè P(1)] allora gioca l'1
> altrimenti se x < 36288O [cioè P(1)+P(2)] allora gioca il 2
> altrimenti se x < 604800 [cioè P(1)+P(2)+P(3)] allora gioca il 3
> etc.
>
>Insomma, introducendo il concetto di "cumulata"
>
> S(k) = sum_{i=1..k} P(i)
>
>la regola è che Susi gioca il numero k se e solo se
>
> S(k-1) <= x < S(k)
>
>[naturalmente S(i) vale 0 per ogni i < 1]
Detta y la variabile aleatoria intera che vogliamo ottenere, cioè quella con la
distribuzione p() che vogliamo ottenere, la tua regola diventa
y = k se S(k-1) <= x < S(k)
con S(k) := 6996581 sum_{i=1..k} p(i)
In tal caso:
P[{y = k}] =
P[{S(k-1) <= x < S(k)}] =
sum_{j=S(k-1)...S(k)-1} P[{x = j}] =
sum_{j=S(k-1)...S(k)-1} 1/6996581 =
[S(k)-S(k-1)]/6996581 =
p(k)
Perfetto!
>Ovviamente se Susi non avesse un dado a 10 facce (ma chi non ce l'ha sempre
>on sé? :-D) può sempre improvvisare 10 bigliettini di carta ed estrarli da
>un sacchetto, oppure può costruire la rappresentazione binaria del numero x
>usando il lancio ripetuto di una sola moneta (ma ci vogliono 23 lanci).
Oppure si può rappresentare il vettore
[S(1),S(2),S(3),S(4),S(5),S(6),S(7),S(8),S(9),S(10)] =
[181440,362880,604800,937440,1391040,2000880,2809440,3868110,5238940,6996581]
in base 6 e usare un dado cubico standard (in cui si diminuisce di 1 il valore
di ciascuna faccia) per ottenere x.
La procedura diventerebbe (i numeri sono scritti in base 6, ho usato Derive):
Lancia il dado 9 volte; sia x il numero rappresentato in base 6 dalla sequenza
di cifre ricavata dai valori di ogni singolo lancio decrementati di 1.
se x >= 405543325 allora ricomincia
se x >= 304142204 allora y = 10 FINE
se x >= 214523530 allora y = 9 FINE
se x >= 140114400 allora y = 8 FINE
se x >= 110515200 allora y = 7 FINE
se x >= 45452000 allora y = 6 FINE
se x >= 32032000 allora y = 5 FINE
se x >= 20544000 allora y = 4 FINE
se x >= 11440000 allora y = 3 FINE
se x >= 3520000 allora y = 2 FINE
y = 1
Enrico Boni
Marco Coletti <marco....@ZZZeurofin.it> wrote in message
380c69b0...@news2.tin.it...
>
> Giocare "a caso" è la scelta giusta, ma non necessariamente con numeri
> equiprobabili.
>
> Forse il mio msg del 13.10.99 con la soluzione ottima era incomprensibile?
>
Tutt'altro. Il fatto e' che io avevo mandato la soluzione lo stesso giorno
in cui era stato postato il quesito, ma e' arrivata 10 giorni dopo....
M. Mercogliano
Salve,
chiedo scusa per il ritardo con cui intervengo in questo thread, ma il
motivo è che solo ora ho avuto modo di consultare il ng in questione.
Ho letto quasi tutte le risposte pervenute in merito al quesito, ma
non vi ho trovato alcuna risposta soddisfacente dal mio punto di
vista, così ho improvvisato un'altra soluzione.
Il problema lo pongo in questi termini: ognuno dei due individui (Susy
e Gianni) dispone di una propria distribuzione di probabilità con cui
decide quale numero tirar fuori; fortunatamente le due distribuzioni
sono indipendenti, poiché non c'é alcuna interazione tra i due
individui (sarebbe interessante notare il caso in cui i singoli
individui sappiano al termine di ciascuna giocata se hanno vinto o no,
nel qual caso dovrebbero "adattare" run-time i propri algoritmi
tenendo pur sempre in consideraione le possibili scelte dell'amico).
Nel nostro caso si hanno due distribuzioni che chiamero' f(x) e g(x),
dove x varia in un dominio discreto [1,10].
Vogliamo massimizzare il profitto P(f(x),g(x))
P(f(x),g(x)) =
sum_k{1..10}( g(k)*( sum_i{1..k-1}(k*f(i)*1000) +
sum_i{k+1..10}(i*f(i)1000) )
Le due distribuzioni non devono necessariamente coincidere, ma devono
garantire il massimo profitto medio; in pratica, suppondendo f(x)
diversa da g(x), dal momento che Susy non può conoscere la scelta
operata da Gianni e viceversa, si possono presentare 4 differenti
casi:
Susy -> f(x) , Gianni -> f(x)
Susy -> f(x) , Gianni -> g(x)
Susy -> g(x) , Gianni -> f(x) // uguale alla precedente
Susy -> g(x) , Gianni -> g(x)
Cio' che interessa e' garantire che nella media dei casi la scelta di
queste due funzioni porti il maggior profitto.
Le 4 possibilità sono equiprobabili, per cui bisogna solo più cercare
le due distribuzioni f(x) e g(x) per cui il profitto sia massimo,
ossia per cui sia massimo:
( P(f(x),g(x)) + P(f(x),f(x)) + P(g(x),f(x)) + P(g(x),g(x)) )/4
Non è infatti ancora detto che la scelta migliore consista
nell'adoperare una distribuzione uguale.
Ora mi appresto a fare un po' di conti su carta .....
..... mi sto rendendo conto che forse è possible solo adoperare
algoritmi a ricerca di ottimi locali, a meno di usare euristiche che
al momento non riesco a intravedere. Infatti ho imposto solo 3 vincoli
(sum_k f(x) = 1, sum_k g(x) = 1, max P(f(x),g(x))) pur avendo 20
variabili (gli f(X) e i g(x) per x in [1,10]), e diventa problematico
gestire i 17 gradi di libertà rimanenti; non è possibile adottare
derivate per ricerca di massimo assoluto.
Nel caso semplice prospettato da .mau. (x assume solo valori 1 e 2) ho
trovato che è possible risolvere il problema con qualsiasi accoppiata
del tipo
f(1)=k , f(2) =1-k
g(1)=1-k, g(2) = k
A questo punto nasce un ulteriore dilemma: nel caso di più accoppiate
ottimali quale scelta deve essere effettuata non sapendo quale
accoppiata sarà utilizzata dall'altra persona (ad es. Susy potrebbe in
questo banale caso pensare di adoperare l'accoppiata f(1)=g(1)=0.5,
mentre Gianni potrebbe usare f(1)=0.8,g(1)=0.2, non essendoci alcun
motivo per preferire l'una rispetto all'altra)?
Niente paura, basta estendere la media non solo alle due funzioni f(x)
e g(x) ma a tutte le funzioni che accoppiate consentono di ottenere
tale massimo; in tal caso bisogna quindi trovare la massima media
ottenibile considerando come elementi base la media di tutte le
funzioni che accoppiate possono raggiungere uno stesso profitto ( e il
discorso potrebbe ripresentarsi in forma sempre più annidata).
Vi sfido a trovare la soluzione al dilemma anche nel caso non poi così
semplice in cui x assuma solo più valori 1 e 2 (un problema solo
apparentemente semplice in fin dei conti).
Sono stato abbastanza enigmatico/confusionario in questa conclusione?
;-))
Per quanto riguarda il quesito iniziale, in cui x = [1..10], dovendo
comunque prendere una decisione, applico il caso appena analizzato con
x=[1..2] dove pero' utilizzo x=[9..10], cioè cerco di ottimizzare la
vincita adottando una scelta ottimale trovata per un caso più semplice
e applicata ad una caso più complesso (se conoscessi la soluzione
ottimale per x=[1..3] la riapplicherei a questo caso con x=[8..10], e
in ogni modo avrei approssimazioni soddisfacenti che potrebbero
migliorare sempre più con il migliorare delle prestazioni del mio
calcolatore (nel caso più generale dove x=[1..n]) )
Commenti in proposito?
Per .mau. : Il problema mi ricorda molto quello di ricerca di
soluzioni ottime nei modelli markoviani quando operavo in CSELT; non
credo esista una soluzione ottimale al problema che non preveda
l'analisi di tutti i casi possibili.
--------------------------------------------------
Per rispondere via E-mail correggere l'indirizzo