Rafael Pla López
Departament de Matemàtica Aplicada
Universitat de València, Spain
Resumen
Un enfocament estadístic al dilema del viatger, primer cercant els millors resultats a partir d'una distribució equiprobabilística de respostes, després fent un procés iteratiu, suposant que la frecuència de una resposta és proporcional al seu resultat (iteració genètica) i suposant que els persones seleccionen les millors respostes prèvies (iteració racional).
Introducció
Al número d'Agost de 2007
d'"Investigación y Ciencia" (l'edició espanyola de
"Scientific American") he llegit un article sobre el dilema del viatger
per Kaushik Basu (dos viatgers que han perdut el mateix objecte
reclamen una indemnització; la companyia els pregunta per
separat el seu preu, advertint-los que is diuen la mateixa quantitat,
entre 2 i 100
€, ambdós rebran aquesta quantitat, però si diuen
quantitats diferents, la companyia acceptarà la quantitat
més baixa, però donaran aquesta quantitat més 2
€ com a plus al viatger que ha dit la quantitat més baixa,
i aquesta quantitat menys 2 € com a penalització al
viatger que ha dit la quantitat més alta). El
professor Basy explica que l'únic equilibri de Nash,
corresponent a la Teoria de Jocs standard, tal que ningú puga
millorar els seus resultat per un canvi unilateral, és la
situació en la que ambdós viatgers responen 2
€. Tanmateix, aquesta resposta és molt ineficient i
inusual. I per tant la Teoria hauria de canviar per a resoldre aquesta
paradoxa.
Com estic en el meu mes de vacances, he pogut dedicar temps a aquest problema, llunyà del meu camp habitual d'investigació en modelització de l'evolució social. Vaig començar preguntant als membres de la meua família. Així, la meua esposa, una mestra, me va donar la resposta desconfiada estandard de Nash, 2 €. I el meu jove fill me va donar la resposta confiada intuitiva, 100 €. Així, vaig decidir abordar el problema amb una modelització estadística..
Com estic en el meu mes de vacances, he pogut dedicar temps a aquest problema, llunyà del meu camp habitual d'investigació en modelització de l'evolució social. Vaig començar preguntant als membres de la meua família. Així, la meua esposa, una mestra, me va donar la resposta desconfiada estandard de Nash, 2 €. I el meu jove fill me va donar la resposta confiada intuitiva, 100 €. Així, vaig decidir abordar el problema amb una modelització estadística..
Primera aproximació a partir d'equiprobabilitat
Supose que el primer viatger, A, es confronta amb altres 99 travelers, i cadascú d'ells dóna una resposta diferent x entre 2 i 100. Així, podem calcular el resultat mitjà de la resposta y del viatger A,
Supose que el primer viatger, A, es confronta amb altres 99 travelers, i cadascú d'ells dóna una resposta diferent x entre 2 i 100. Així, podem calcular el resultat mitjà de la resposta y del viatger A,
A1(y)
= [ SUM x=2:y-1 (x-2) + y + SUM
x=y+1:100 (y+2) ]/99 = [ (y-2)(0+y-3)/2 + y + (100-y)(y+2)
]/99 =
= (-y2 + 193y + 406)/198
= (-y2 + 193y + 406)/198
|
Es pot veure en la Figura
1 aquest resultat mitjà A1
com una funció de la resposta y.
Obtenim el resultat màxim resolent dA1/dy = (-2y+193)/198 = 0 el qual correspon a y=193/2=96.5 : els valors enters més pròxims y=96 i y=97 tenen el mateix resultat mitjà de 49.080808 |
 Figura 1
Resultats mitjans confrontats amb respostes equiprobabilístiques |
Iteració genètica
Podem suposar que, en ocasions successives, les respostes que han obtingut els millors resultat ocorreran amb més frequència. Per tal de modelar aquest procés, suposarem que la frequència d'una resposta és propocional al seu previ resultat mitjà.
Així, tenim la següent relació iterativa:
An+1(y) = [SUM x=2:y-1 An(x)(x-2) + An(y)y + SUM x=y+1:100 An(x)(y+2)] / SUM x=2:100 An(x)
Es pot veure en la Figura 2 els darrers resultats mitjans d'A com a una funció de la seua resposta y a través d'aquesta iteració genètica, comparada amb l'aproximació inicial: y=96 es consolida com la millor resposata, amb un resultat mitjà que arriba al voltant de 61 €.
Observeu que els viatgers no necessiten conèixer el càlcul de la millor resposta a través d'aquesta iteració genètica: les millors respostes simplement s'estenen més àmpliament.
Podem suposar que, en ocasions successives, les respostes que han obtingut els millors resultat ocorreran amb més frequència. Per tal de modelar aquest procés, suposarem que la frequència d'una resposta és propocional al seu previ resultat mitjà.
Així, tenim la següent relació iterativa:
An+1(y) = [SUM x=2:y-1 An(x)(x-2) + An(y)y + SUM x=y+1:100 An(x)(y+2)] / SUM x=2:100 An(x)
He implementat aquesta iteració en llenguatge C (és pot obtindre el codi font en http://www.uv.es/pla/models/viajero/viajero.c) i obtingut els resultats màxims successius a partir de respostes enteres, els quals són: n= 1: A(96)=49.080807 A(97)=49.080807 n= 2: A(96)=59.993732 n= 3: A(96)=60.926846 n= 4: A(96)=61.021133 n= 5: A(96)=61.031261 n= 6: A(96)=61.032364 n= 7: A(96)=61.032497 n= 8: A(96)=61.032520 n= 9: A(96)=61.032509 n=10: A(96)=61.032516 n=11: A(96)=61.032509 n=12: A(96)=61.032513 n=13: A(96)=61.032524 n=14: A(96)=61.032513 n=15: A(96)=61.032524 (a partir de n=13 els resultats es repeteixen cíclicament) |
 Figur1 2
Resultats mitjans en el primer pas (verd) i en el pas 30é (blau) |
Es pot veure en la Figura 2 els darrers resultats mitjans d'A com a una funció de la seua resposta y a través d'aquesta iteració genètica, comparada amb l'aproximació inicial: y=96 es consolida com la millor resposata, amb un resultat mitjà que arriba al voltant de 61 €.
Observeu que els viatgers no necessiten conèixer el càlcul de la millor resposta a través d'aquesta iteració genètica: les millors respostes simplement s'estenen més àmpliament.
Iteració racional
Suposarem ara que els viatgers coneixen en cada pas el càlcul dels resultats mitjans, i escullen les millors respostes arrodonint a números enters tant respostes com resultats.
Així, en el primer pas 48.5 ≤ A1(y) < 49.5 si i solament si 86≤y≤100, i podem suposar que en el segon pas les úniques respostes dels altres viatgers són x=86:100, i per tant els resultats mitjans seran
A*2(y) = [ SUM x=86:y-1 (x-2) + y + SUM x=y+1:100 (y+2) ]/15 = [(y-86)(84+y-3)/2 + y + (100-y)(y+2)]/15 =
= (-y2 + 193y - 6566)/30
Resolent
dA*2/dy = (-2y+193)/30 = 0
obtenim el mateix valor y=193/2=96.5 per al resultat màxim (de fet, obtindriem el mateix valor sempre que les respostes x varien des de qualsevol número fins a 100), però ara el resultat mitjà per a y=96 i y=97 és 91.53333, el qual s'aproxima a 92, i qualsevol altra resposta obté un resultat mitjà menor que 91.5.
Així, en el tercer pas podem suposar que les respostes dels altres viatgers són x=96 o x=97. Podem repetir el càlcul, però amb solament dues respostes podem calcular directament els resultats mitjans:
A*3(96) = (96+98)/2 = 97
A*3(97) = (94+97)/2 = 95.5
Per tant, la millor resposta és inequívocament y=96. De fet, amb solament dues respostes y=96 és una opció dominant (obté el millor resultat amb independència de la reposta de l'altre viatger), i la previsió estadística coincideix amb l'equilibri de Nash.
Així, tant la iteració genètica com la iteració racional arriben a la mateixa conclusió: la millor resposta és 96 €. Tanmateix, la iteració racional obté un resultat major, 97 en front de 61.
Suposarem ara que els viatgers coneixen en cada pas el càlcul dels resultats mitjans, i escullen les millors respostes arrodonint a números enters tant respostes com resultats.
Així, en el primer pas 48.5 ≤ A1(y) < 49.5 si i solament si 86≤y≤100, i podem suposar que en el segon pas les úniques respostes dels altres viatgers són x=86:100, i per tant els resultats mitjans seran
A*2(y) = [ SUM x=86:y-1 (x-2) + y + SUM x=y+1:100 (y+2) ]/15 = [(y-86)(84+y-3)/2 + y + (100-y)(y+2)]/15 =
= (-y2 + 193y - 6566)/30
Resolent
dA*2/dy = (-2y+193)/30 = 0
obtenim el mateix valor y=193/2=96.5 per al resultat màxim (de fet, obtindriem el mateix valor sempre que les respostes x varien des de qualsevol número fins a 100), però ara el resultat mitjà per a y=96 i y=97 és 91.53333, el qual s'aproxima a 92, i qualsevol altra resposta obté un resultat mitjà menor que 91.5.
Així, en el tercer pas podem suposar que les respostes dels altres viatgers són x=96 o x=97. Podem repetir el càlcul, però amb solament dues respostes podem calcular directament els resultats mitjans:
A*3(96) = (96+98)/2 = 97
A*3(97) = (94+97)/2 = 95.5
Per tant, la millor resposta és inequívocament y=96. De fet, amb solament dues respostes y=96 és una opció dominant (obté el millor resultat amb independència de la reposta de l'altre viatger), i la previsió estadística coincideix amb l'equilibri de Nash.
Així, tant la iteració genètica com la iteració racional arriben a la mateixa conclusió: la millor resposta és 96 €. Tanmateix, la iteració racional obté un resultat major, 97 en front de 61.
Bibliografia
Kaushik Basu, "El dilema del viajero", Investigación y Ciencia, Agost 2007, pàgines 48-54
Aquest article pot ser reproduït i republicat lliurement, en conjunt o en part, donant la referència http://www.uv.es/pla/models/viajero
Kaushik Basu, "El dilema del viajero", Investigación y Ciencia, Agost 2007, pàgines 48-54
Aquest article pot ser reproduït i republicat lliurement, en conjunt o en part, donant la referència http://www.uv.es/pla/models/viajero