1641.- Marche un Nobel para juegos...

Y por fin se dio: Shapley recibió el Nobel de Economía (junto con Al Roth)

Por fin se hizo justicia! En uno de los últimos posts decía "Shapley... pobre Shapley!", por la cantidad de cosas que hizo (juegos potenciales, indices de poder, y el tema por el que se lo dan, matching) sin que se lo dieran.

De matching conté algo hace un tiempo aquí (El lado oscuro de las matematicas), pero el que quiera el teorema posta y la demostración, se puede bajar este pdf que preparé hace un tiempo.

1637.- Teoria algoritmica de juegos (3)

(viene de aquí)

Self-fish routing

En el segundo ejemplo cambia la situación. Acá uno o más jugadores tratan de rutear un cierto volumen de datos/líquidos por una red y el costo será proporcional al tiempo que se tarda en recorrerla. Incluso con un solo jugador que dirige el tráfico hay problemas...

* * *

Segundo Ejemplo

El ejemplo lo propuso Pigou, en 1920:

La ruta A tarda 1 independiente del tráfico, mientras que la ruta B se congestiona cuando el tráfico se incrementa. Acá, el tráfico se puede considerar formado por
unidades muy pequeñas, que pueden ir por una ruta u otra (paquetes de información, gotas de agua).

Supongamos que tenemos que mandar 1 GB, y en B el costo es 1 segundo, c(1 GB)=1'. Entonces el equilibrio de Nash es mandar 1 GB por B, y nada por A. ¿Por qué? Porque si dividimos el giga de datos en paquetes, y mandamos p paquetes por A, y el resto por B, cualquiera de los paquetes que va por A tarda 1, y si se cambia a B llega antes (porque el total de datos en B con ese paquete extra sigue siendo menor a 1 GB, y tardarán menos de 1). En definitiva, el único equilibrio de Nash es mandar todo por B.

Ajá... ya tenemos el juego, las reglas, los costos, el equilibrio de Nash... ¿qué nos podría interesar optimizar? Bueno, una posibilidad es mejorar el tiempo promedio que tardan los paquetes en cruzar.

Si metemos 1 GB por B, llegan todos 1 segundo más tarde. Si lo metemos por A, también... pero si metemos mitad y mitad, la mitad que va por A tarda 1 seg, y la otra
solo medio segundo.

El tiempo promedio que tarda un paquete es 1.(1/2) + (1/2).(1/2) = 3/4, mejor que el tiempo del Nash que era 1.

El precio de la anarquía es igual al precio de la estabilidad, y es 1/(3/4)=4/3.

* * *

El peor de los mundos

Un gran resultado de Roughgarden y Tardos es que en toda red, sin importar su longitud, ni su complejidad, el precio es 4/3 si los costos de cada link son lineales en el tráfico.

Es decir, si cuando hay un flujo x por un link el costo es ax+b, con a y b fijos, entonces el precio de la anarquía es menor 4/3, y esto es independiente de la
topología de la red.

El ejemplo de Pigou, de 1920, resultó ser el peor de los mundos posibles.

* * *

El mejor de los mundos

¿Y si los costos no fueran lineales? ¿Cuadráticos, cúbicos, polinomiales, racionales...?

Bueno, Roughgarden atacó ese problema aquí (free). Por ejemplo, para polinomios de grado p, la clave es modificar el ejemplo de Pigou, y poner un costo a la ruta B de x^p. Una cuenta astuta, pero elemental, prueba que el precio es del orden de p/log(p). Tambien las cosas son independientes de la topología de la red, y del polinomio exacto involucrado.

Comparado, el ejemplo de Pigou es el mejor de los mundos posibles.

* * *

Qué falta?

Mucho, que reservo para la clase del jueves, e iré incluyendo según el ánimo/interés de aquí en más:

Una aplicación del ejemplo de Pigou de por qué podría interesarnos minimizar el tiempo promedio.

El ejemplo que da el peor precio de la estabilidad en problemas como el del primer ejemplo, donde cada jugador elige una ruta y comparten los costos quienes usan la misma. Es del orden del logaritmo de k, donde k es el número de jugadores.

La definición de juegos potenciales, o de congestión, que inluyen las dos grandes familias de juegos consideradas: jugadores eligiendo caminos en una red (atomic games), o envío de datos por una red (nonatomic games), donde se comparten los costos al usar un mismo camino, pero encareciéndolo por congestionarla.

Shapley... pobre Shapley!

Varios teoremas lindos: cotas para los precios de la estabilidad y de la anarquía en estos juegos, existencia de equilibrios de Nash puros,...

El precio de la Malicia: hay jugadores bizantinos cuyo único objetivo es cagarle la vida al resto... (ejmplos)

Otros ejemplos.

Más ejemplos.

La paradoja de Braess.

Problemas abiertos.

Diseño de mecanismos: ¿cómo reducir el precio de la anarquía/estabilidad?

* * *

Gran laburo el de esta gente, felicitaciones!

again, for the Carnival, now at Gaussianos

1636.- Teoría algorítmica de juegos (2)

(viene de Teoría algorítmica de juegos 1)

Ineficiencia


Consideren un juego, sus reglas, y los pagos y costos por participar. El problema principal que esta gente quiso resolver es el de analizar la ineficiencia asociada con la libertad que tienen los jugadores para elegir qué hacer. Claramente, si no hay restricciones, cada jugador actúa por su propio interés, pero el resultado al que se llega puede ser malo desde el punto de vista social o colectivo.

En Una mente brillante se dice que Nash refutó a Adam Smith, mostrando cómo todos podían beneficiarse, etcétera. Ni ahí. Hay equilibrios de Nash donde la mano invisible que elige las estrategias producen resultados desastrosos (de los cuales nadie quiere salir, porque empeora su situación), y hay ejemplos que lo muestran claramente.

* * *

Primer Ejemplo

El primer ejemplo NO es el dilema del prisionero. Ahí no hay opción: el juego tiene un solo equilibrio, así que no tienen chances de hacer nada. En cualquier situación, confesar es mejor que quedarse callado, y si bien se llega a un resultado no deseado, es clarísimo que no hay alternativas.

El primer ejemplo es una red con dos caminos A y B para ir de s a t. Pero A cuesta K y B cuesta 1+E, con E muy pequeño. Tenemos también K jugadores, que deben elegir ruta, y compartirán el costo de una ruta aquellos jugadores que la elijan.

Observemos que si todos van por el camino B, cada uno paga (1+E)/K, muy poco, y a nadie le conviene desviarse porque pagaría K, muchísimo.

Pero resulta que hay otro equilibrio de Nash, muy ineficiente, y es que todos elijan la ruta A: cada uno paga 1, y si un jugador se desvía, pagaría 1+E. Resultado: se quedan todos en la ruta A, pagando en total K.

Bienvenidos a la ineficiencia de la mano invisible de Nash.

* * *

Antes de otro ejemplo, veamos que buscaron resolver los seis ganadores del Godel de este año. Para analizar la ineficiencia de un juego hay que contestar las siguientes preguntas:

1.- ¿Cuáles son los pagos?

El problema se simplifica si hay un valor monetario (se paga o cobra cierta cantidad según qué hacen todos), pero también se puede considerar el tiempo que lleva una tarea (si bien time = money, hay situaciones donde el presupuesto no importa con tal de minimizar el tiempo).

2.- ¿Cómo comparar los distintos resultados del juego?

Si bien 1.- sugiere minimizar costos ó tiempos, o maximizar ganancias, hay que distinguir entre dos enfoques:

-Utilitario: buscamos minimizar el costo (o tiempo) general, tal vez a costa de matar a algún jugador, que corre con todo el costo.

-Igualitario: se quiere reducir el costo máximo de los jugadores.

Según el contexto, habrá que ver cuál conviene, definir la función correspondiente, y se busca el valor óptimo.

3.- ¿Qué quiere decir 'casi óptimo'?

La solución que eligieron es dividir el valor óptimo y el valor de la función en un equlibrio. Si esa razón está cerca de uno, podemos pensar que el equilibrio es casi óptimo. Y es fácil comparar, diciendo que es un tanto por ciento peor, o que cuesta el triple, etc. Además, como dicen en el libro: casi todos usan ese parámetro...

En la elección de cómo comparar, se llegó a un equilibrio ¿será cercano a un óptimo? :-)

4.- ¿Qué equilibrios se considerarán?

Acá no hay mucha vuelta: son los equlibrios de Nash, preferentemente los equilibrios en estrategias puras, y se mira cuánto valen para la función del punto 2.-

5.- ¿Qué pasa si hay más de un equilibrio?

Ahí vienen las dos definiciones importantes:

Precio de la Anarquía: es la razón (definida en 3.-) entre el peor valor de la función evaluada en los equilibrios (4.-) y el valor óptimo (2.-).

Precio de la Estabilidad: es la razón (definida en 3.-) entre el mejor valor de la función evaluada en los equilibrios (4.-) y el valor óptimo (2.-).

En el ejemplo de la red de dos caminos, el óptimo (utilitario e igualitario) es que todos vayan por B, que era un equilibrio de Nash. Como ese equilibrio coincide con el óptimo, el precio de la estabilidad es 1. Pero hay un equilibrio cuyo costo es K, con lo cual el precio de la anarquía es

(valor del equilibrio)/óptimo = K / (1+E) ~ K.

* * *

Precio de la estabilidad

Recordemos que en un equilibrio de Nash nadie tiene motivos para desviarse, lo cual estabiliza una situación: si todos estamos haciendo algo, y nadie gana más por desviarse unilateralmente, entonces seguiremos haciendo todos lo mismo.

En cualquier elección de estrategias que no sea un Nash, habrá un jugador que tiene incentivos por desviarse, con lo cual es difícil lograr que todos se coordinen en una situación (por ejemplo, la que da el valor óptimo) si esta no es un Nash. El precio de la estabilidad es lo mínimo que tenemos que sacrificar para tener un Nash.

* * *

Precio de la anarquía

El precio de la anarquía, en cambio, es el peor caso que puede darse. Nos alejamos del óptimo, y nadie tiene incentivos para cambiarse. Cuando hay un único equilibrio, mala suerte, coincide con el precio de la estabilidad y no hay mucho más para decir.

El problema más grave es cuando hay varios equilibrios y justo ese es fácil de descubrir, o es el que se implementa fácil o rápido por razones dinámicas. Veamos el ejemplo inicial con otra óptica.

Vivir en el centro de Buenos Aires es una locura, y si bien muchísima gente trabaja en el centro, prefiere vivir en Pilar, o Tigre, zonas alejadas desde las que sólo se llega en auto. Si K personas viven en Pilar, salen a las 8hs y vuelven a las 18hs, cada una pagando el costo de un auto, unas 8-10 podrían pagar mucho menos y mantener una combi que los lleve/traigo más o menos en el mismo tiempo. El tema es que cuando un country comienza a formarse, como los habitantes son pocos, la única solución es que cada uno resuelva su problema de transporte con su propio auto.

La formación de una villa sigue una dinámica similar: cada familia ocupa parcelas de un terreno, hasta cubrir por completo el área disponible. Abrir luego caminos internos (para circular con más comodidad o seguridad, llevar luz o agua, etc) termina siendo imposible, porque es necesario desplazar algunas familias, y en ocasiones ya no hay donde ubicarlas a menos que sea en otra parte.

El problema se ve también en las partes más viejas de las ciudades, donde la estructura antigua tiene calles intransitables para la modernidá, e invitan a carnicerías históricas, tales como en el centro de Buenos Aires, cuando se demolió parte del Cabildo para facilitar el tránsito. Bueno, también a Vieytes se le ocurre instalar su jabonería justo donde hoy (25 de Mayo, pero 202 años después) tenía que pasar la Avenida 9 de Julio...

* * *

Continuará.

(y esta vez, el Carnaval está en Gaussianos.)

1635.-. Teoria algoritmica de juegos

Al paso que voy, casi no posteo en este Carnaval. Pero quiero preparar una clase para el 31/5, y su contenido me viene bien para acá. O el Carnaval me viene bien para prepararla... no se. Allá vamos.

* * *

Introducción

La semana pasada, la ACM entregó el premio Godel, destinado a avances en lógica o fundamentos de la computación, y los ganadores fueron seis personas por tres papers que escribieron en parejas:

Elias Koutsoupias and Christos H. Papadimitriou, Worst-case Equilibira (2009).

Tim Roughgarden and Eva Tardos, How Bad Is Selfish Routing? (2002)

Noam Nisan and Amir Ronen, Algorithmic Mechanism Design (2001).

De paso, los tres primeros escriben en el blog Turing's invisible hand (agtb.worpress.com, por algorithmic game theory blog).

Más info sobre la teoría de juegos algorítmica se puede encontrar en el libro de Vazirani, Nisan, Roughgarden, y Tardos, Algorithmic Game Theory, Cambridge University Press, 2007. Se baja
gratis un pdf (non-printable, je!) de la editorial o las páginas de los autores.


* * *

El trabajo que hicieron se aplica a problemas interesantísimos de redes (incluyendo tráfico, no solo internet o redes de comunicaciones), y pienso desarrollar lo básico en los próximos posts.




Problema relacionado: hallar una localidad y las rutas adecuadas para que se junten a festejar, si deben viajar desde Stanford, Cornell, Berkeley, Atenas, Jerusalem y Haifa con los (apenas) 5000 U$S de premio...




(y esta vez, el Carnaval está en Gaussianos.)

1634.- Y que el diablo se lleve al último

Hablemos de matemáticas:


* * *

En Escocia, o tal vez en Salamanca, cuando los estudiantes progresaban en sus estudios místicos, eran obligados a correr por una galería subterránea, y el último de ellos era atrapado por el diablo.

Mas o menos así explica Ebenezer Brewer en su Dictionary of phrase and fable (de 1890, disponible sin problemas de copyright por aquí), el origen de la frase

Let the devil take the hindmost

* * *

La frase aparece en el siglo XVI, y era habitual en las retiradas militares: Every man for himself, and devil take the hindmost. Pero su origen es muy anterior, si contamos a Horacio y su Epístola a los Pisones, donde se lee

occupet extremum scabies.

El último cola'e perro, podríamos traducir, o el último es un huevo podrido, si nos guiamos por Discovery Kids o Disney Channel... sepan disculparme la imprecisión. Y si no me la disculpan, vayan a explorar los doctos refraneros latinos, donde encontrarán diferentes variantes. Por ejemplo,

—Ningún socorro a nadie —decía éste—. Cada cual para sí, y puto el último.

—El último somos nosotros —recordó, oportuno, el sargento Quemado. Urdemalas lo fulminó con la mirada.

—Era una frase, pardiez. Sin socorrernos unos a otros, y apretando boga, cabe la posibilidad de que alguno escape

como podemos leer en Corsarios de Levante, de Arturo Perez-Reverte.


* * *

Consideremos una función U(c,s), donde U es tres veces diferenciables, cóncava, con derivadas parciales positivas, U_cc y U_ss negativas, y U_cs positiva, que mide la preferencia entre el nivel de consumo (variable c), y el status (variable s):

De un paper, ajeno, del 2011. En definitiva, la condición "que el diablo se lleve al último" es que la derivada parcial de U respecto a s tienda a infinito cuando s tiende a cero, y que la derivada parcial de U respecto a c esté acotada inferiormente.

* * *

(Para una nueva edición del Carnaval, esta vez en DesEquiLIBROS)

1597.- Loterias, seguros, alarmas y mantenimiento - CdM X

No pensaba postear este Carnaval (que por acá son vacaciones!) pero me decidió la cantidad de posts que vi el mes pasado sobre las loterías, y el tema se multiplicó en las redes, comentarios, linkeos, buzzeos.... Algunos llegaron a ser ofensivos: que el juego es el impuesto al idiota, que es para los imbéciles... llegando a perder de vista que deberíamos, si pretendemos hacer alguna clase de divulgación, tratarlo lo más científicamente posible. Gaussianos fue la excepción: ni él ni sus comentaristas agregan estos juicios de valor, y se limitan a las cuentas puras y duras.

Lo más triste es que esta misma gente que dice lo que dice no tiene reparos en asegurar su automóvil, ponerle alarmas de robo, revisarlo con un mecánico antes de un viaje, contratar coberturas médicas o hacerse chequeos...; y hasta se ofenderían si se los trata de idiotas por esto. Pero las motivaciones atrás de unas y otras conductas son las mismas, así que nones: somos todos una manga de boludos.

Bien, así que vamos entonces a defender, no el juego ni mucho menos al jugador patológico, sino a la conducta completamente racional de jugarse un numerito de vez en cuando, o un billete una vez al año a la lotería.

* * *

Un concepto clave para acercarse al tema es la utilidad esperada: se supone que uno analiza los valores esperados de las decisiones que estamos por tomar, y elige la de mayor esperanza en el sentido probabilístico.

Otro, es que nuestra función de utilidad (resumiendo, mide el valor que le damos a una cantidad de dinero), no debería ser lineal, sino cóncava, como raíz de x o el logaritmo: deberíamos valorar más que nuestro capital aumente 1 peso cuando tenemos poco que cuando tenemos mucho.

Y eso nos tira de cabeza en la aversión al riesgo: con una utilidad cóncava, valoramos más un peso que apostarlo a una lotería cuya esperanza de pago también es un peso... ni hablar entonces de jugar si el pago es menor, como bien calcularon Gaussianos o Tito!

Si tomamos estas tres cosas como axiomas inamovibles, usual en la teoría de juegos, no deberíamos jamás apostar a menos que la esperanza matemática sea positiva.

* * *

Pero. Porque la cosa tiene su pero.

Para empezar, esto aplicado al hombre común asume que sabe proba y que puede hacer todas las cuentas... una suposición fallida por donde se la mire. Y no es cuestión de llamarle tarado al ignorante, que ahí ya hay un error, cometido desde la soberbia del que sabe.

Por otra parte, asumimos que sólo la cuestión monetaria afecta la función de utilidad y que sólo juega para maximizar su riqueza: que no está comprando el boleto por tradición, o con unos amigos o compañeros de oficina como parte de una camaradería que aún perdiendo se fortalece, o que la esperanza (no la matemática, la de ganar) tampoco vale nada. Y al llamarlo idiota por eso ya hay otro error, despreciar el valor de lo humano, cometido desde la pedantería de creerse tan frío como las matemáticas que uno sabe.

Y por último, creer que la utilidad la elegimos racionalmente nosotros, y que decidimos si es cóncava o convexa a voluntad, y no algo intrínseco a nuestra naturaleza, que difícilmente cambiemos por mucha matemática que aprendamos. Y ahí también ya hay otro error, porque ya estamos hablando de algo que no entendemos del todo, y se relaciona con la diversidad de nuestros gustos, un error que se comete desde la ilusión de que todo es medible con una única escala de valores posible, algo que debería detectarse como falso por poca matemática que se sepa.

* * *

Y mientras voy empezando, ya terminé, así que dejo para una segunda parte el resto: la relación con los seguros y las alarmas y el mantenimiento.

Me voy a hacer una quiniela y sigo tipeando.

1594.- El lado oscuro de las matematicas - CdM VIII

Si ayer no me iniciaron juicio académico para echarme de la universidad, tuve mucha suerte. Y es que en la clase demostré tres resultaditos pesados:

Demostré que con el matrimonio gay pueden no formarse parejas estables.

Dí un algoritmo (machista) para conseguir pareja.

Probé que la única consitución -o sistema electoral- justo es la dictadura.

Bienvenidos al lado oscuro de las matemáticas...

* * *

Los dos primeros items se pueden ver en el clásico paper de Gale y Shapley, College Admissions and the Stability of Marriage, American Mathematical Monthly 69, 9-14, 1962 (de algunos links se puede bajar gratis).

El algoritmo resuelve el problema de los matrimonios estables: dados dos conjuntos, de Varones y Mujeres (de igual cardinal, pero no es problema), donde cada varón tiene una lista de las mujeres ordenadas según a cuál prefiere más (y cada mujer tiene una lista con los varones), existe una biyección tal que no queden v y m que prefieran estar en pareja entre sí antes que con sus respectivos compañeros. Una situación así llevaría a divorciar la pareja y por eso la asignación no sería estable.

Hay una variante maquiavélica, donde algunos de los V pueden mentir, no revelando sus preferencias verdaderas. Si hay un solo mentiroso, le va peor, pero si son varios, puede ser que algunos mejoren y el resto no quede peor!

* * *

Con el matrimonio gay, el problema se conoce como el roommate problem, pero no hay caso: puede no existir ninguna asignación estable. El mejor ejemplo se tiene con cuatro participantes a, b, c, y d y sus preferencias son las siguientes:

a los ordena: b > c > d

b los ordena: c > a > d

c los ordena: a > b > d

d los ordena: a > b > c

Armen dos parejas cualesquiera, y verán que el resultado no es estable. Por ejemplo, si agrupamos (a, d) y (b, c), tenemos que c preferiría estar con a antes que con su actual pareja b; y a preferiría estar con c antes que con su actual pareja d. Luego, tienden a divorciarse y formar la pareja (a,c)

Pero esta también tiene el mismo problema, como pueden verificar muy rápido.

* * *

Finalmente, el último resultado es el nunca bien ponderado Teorema de Arrow. La demostración que dí es prácticamente la de Geanakoplos (con ligeros cambios, se puede ver en la Wikipedia).

Como se dijo en 1972, cuando le dieron el Nobel:

En su tesis doctoral, publicada en 1951, Arrow planteó la siguiente cuestión. Supongamos que en una sociedad uno tiene un número de alternativas entre las que elegir, y que cada individuo de la sociedad ordena las alternativas en el orden que las prefiere. ¿Es posible, en ese caso, hallar una regla democrática y éticamente aceptable que produzca un ranking colectivo (o social) de las distintas alternativas? Arrow mostró que la respuesta es negativa. En principio, es imposible hallar una regla semejante.

Existen distintas extensiones de este teorema, entre ellas la de Nakamura, o la más impactante de Gibbard y Satterthwaite: ni siquiera se puede elegir un único ganador, entre los distintos candidatos, a menos que:

haya un dictador;

haya un candidato proscripto;

se puede votar tácticamente para perjudicar candidatos.

Según cómo siga la semana, tal vez demuestre aquí el Teorema de Arrow, pero tengo que resolver cómo hacer dibujitos, que con un par la demostración queda más clara.

Mi colaboración para el Carnaval de Matemáticas, esta vez a cargo de Los Matemáticos no son gente seria.

1590.- Charla de Juegos

El lunes 18, a las 15 hs hay una charla de Teoría de Juegos, aula 11 del Pabellón II (paradojicamente, el II es el 1ro de los pabellones grandes), Ciudad Universitaria, Bs. As., Arg.

Se supone que está dirigida a alumnos y docentes del secundario y/o público general, así que debería entenderse. Debería, vaya uno a saber qué hará el irresponsable a cargo de darla.

¿De qué hablará? Hasta donde sé, NO va a hablar del dilema del prisionero (porque es lo primero que manotea cualquier imbécil, aunque no sepa de qué se trata; siempre se intenta versear desde la falsa lógica con ese tema sin mirar los números con cuidado). Posiblemente sean aplicaciones sociales:

Regímenes legales de tránsito: cómo afecta al manejo el tipo de leyes sobre responsabilidad civil. Por ejemplo: si el automovilista siempre tiene la culpa, ¿significa que manejará con más cuidado?

(se supone que ahí va a explicar las matrices de pago, para el auto y el peatón, cómo eliminar estrategias dominadas)

Aparición de normas y convenciones: ¿conviene circular por la izquierda o por la derecha de una ruta?

(esto sirve para introducir el eq. de Nash; por lo menos en teoría)

Paradoja de Braess: aumentando nuestras opciones para circular, el viaje puede resultar más lento!

(similitud con la tragedia de los bienes comunes, la ventaja es que la matemática necesaria para explicarla es más simple: en vez de maximizar una función, alcanza con sumar números)

Si quedara tiempo (o si surgiera la pregunta), un tema interesante pero desconectado de lo anterior es el

Alfa-Beta Pruning: el algoritmo que usan las computadoras para jugar al ajedrez.

En general, dado que hay muchas opciones, y no se ven las consecuencias inmediatas de las acciones, uno debe explorar el árbol de opciones hasta cierta profundidad, y elegir el futuro que parece más promisorio. Esto es jugar medianamente 'a ciegas', y el costo de evaluar el árbol se reduce extraordinariamente con este algoritmo: uno logra duplicar la profundidad de análisis, al costo de no mirar todas las opciones.

1584.- Not-A-Journal y referatos

Cuando creo haberlo visto todo en materia de journals y publicaciones, descubro que hay aún más cosas en ese submundo que las que mi filosofía creía abarcar. Y, de paso, verifico que todavía soy capaz de creerme algo imposible antes del desayuno.

Me explico: antes del tercer mate (de mate, yerba con agua caliente, no de matemáticas) decido aceptar un referato que me habían encargado. Generosamente propongo como fecha el 30/10/10... y me rebota diciendo que debe ser "before 09/21/10".

Como mes 21 no conozco, deduzco que me piden que lo haga en menos de un mes... Bueno, todo sea por la sensia...

* * *





Por otra parte, me encuentro con un journal que no es un journal: NAJ Economics (link)!

Bue, esto no fue antes del desayuno, lo ví hace un tiempo, pero tiene tantas características novedosas que no me decidía a postearlo:

1. Un prestigioso Editorial Board (comparen con los de otros journals del área, la intersección no es vacía).



2. Los editores hacen los referatos y los publican.



3. El NAJ no publica los papers (sólo los referatos).



4. No hay submissions: los editores encuentran un paper en la red, lo leen, y si lo consideran suitable, publican su referato con un link al preprint.

Suficiente por hoy, voy a salir a la calle a ver si me despierto o estoy soñando.

1580.- Gran Blog

Les recomiendo The Leisure of the Theory Class si se quieren divertir un rato y leer sobre teoría de juegos. Es ácido el chabón cuando quiere, y tiene unas cuantas perlas en mitad de los posts como:

About Canadians. Dan, like many famous Americans is, in fact, Canadian. Lones Smith, Jeroen Swinkels and Phil Reny are other examples. Insufficiently famous? John K. Galbraith, Michael J. Fox, Wayne Gretzky and Captain James Tiberius Kirk. Indeed, it is impossible for Canadians to be famous as Canadians unless they are named Pierre and have wives who sleep with Mick Jagger.

Oddly enough, something of the same is true of English writers. Most famous English writers, dramatists and poets are not English. Wilde and Shaw were Irish. Burns and Doyle were Scotch. Conrad a Pole, Stoppard a Czech, Mikes a Hungarian, Naipaul a West Indian Indian.

(Ok, todavía lo podía agregar a Kipling, pero es lo de menos. Borges también clasificaba si se hubiera muerto allá y no en Ginebra).

Hay alguna frase que estoy por robarle, dejémoslo para otro post. Pero el post que quería recomendarles es: http://theoryclass.wordpress.com/2010/01/14/back-to-anonymity/.

* * *

Créanlo o no, dejé de leer y me fui a hacer un referato, y eso que no me habían apurado todavía, me había llegado a fines de abril.

Y no sólo me fui a hacerlo: lo hice! Ya está enviado y todo, el primero positivo en lo que va del año.

Ahora no se si seguir leyendo el blog, a ver si se pone a dar consejos de cómo dar clases de Teoría de Juegos y me paso la noche trabajando...

(btw... 101??? ni las teóricas de Análisis 1 tienen tanta gente!)

1579.- (i)racionalidad

A fin de cuentas, no se puede decir que los insectos piensen y, por tanto, la racionalidad no puede ser tan crucial cuando la teoría de juegos se las apaña para predecir su comportamiento en condiciones adecuadas.

Al mismo tiempo, con la llegada de la economía experimental caímos en la cuenta de que los seres humanos tampoco son gran cosa pensando. Cuando hallan el equilibrio de un juego, lo suelen hacer utilizando métodos de prueba y error.

Ken Binmore.

* * *

Binmore escribió el mejor libro de teoría de juegos (Playing for Real), con el peor índice de la historia de la matemática. Quienes crean que los cuatro tomos del Winning Ways de Berkelamp, Conway & Guy le ganan están equivocados.

El índice de PfR es apenas una lista de 21 "títulos", tan descriptivos como: Backing Up (el 2do); Keeping your Balance (8vo); Getting Together (seguido, dos capítulos después por Teaming UP); Just Playing?; o el último: Going, Going, Gone!

En general, la relación entre los capítulos y sus títulos es un chiste privado hasta que uno no los leyó. Después tienen sentido, pero seis meses después de leído el libro, no sirven de nada (lo digo por experiencia). Los que me conocen saben que memoria no me falta, pero me resulta imposible manejarme en las 630 páginas con esos 21 títulos.

Por ejemplo, los títulos de las secciones o subsecciones no están (gran diferencia con el BC&G). Incluso el índice al final por palabras claves es bastante parco.

* * *

Por otra parte, sigue siendo el mejor libro que encontré sobre el tema, y eso que hay otros muy buenos (el de Myerson, por ejemplo; o cualquier cosa que escriba Shubik). El Fudenberg & Tirole, más técnico y difícil, está en otra categoría, y no resulta comparable a los demás. Es muy sólido y completo respecto a las diferentes ramas de la teoría de juegos económica, y como Binmore dice, es el libro que hay que leer para publicar en Econométrica [no me queda claro, todavía, si eso es un elogio o una crítica].

Una cosa rara en Teoría de Juegos es cómo se discuten los axiomas considerados, y cómo los autores de cada libro 'pelean' justificando o defendiendo interpretaciones alternativas, que incluso contradicen lo que acaban de afirmar.

El caso extremo, creo, son los comentarios que intercalan en su libro Osborne y Rubinstein, porque muchas veces uno no coincide con lo que el otro afirma, y discuten en medio del texto!

* * *

Los textos de Binmore agregan una discusión extra, filosófica, muchas veces muy profunda (sólo Shubik llega más lejos, cuando habla de ciencias sociales). Creo que es mucho lo que se puede decir sobre el comportamiento humano vía la teoría de juegos, y es una rama fascinante que no necesita muchos conocimientos previos.

Prometo (y ya me pongo a tipear, que si no no llego, que esta semana agrego un ejemplo concreto).

1569.- Carnaval IV - Problem(it)a

Imaginen dos barcos de guerra, enemigos, buscándose en el océano. Imaginen que uno de los capitanes (digamos, Xérez) tiene un espía en un puerto neutral, y le pagará 1 dolar por cada dato útil que reciba sobre el otro barco.

Imaginen, ahora, que el otro capitán (sea Yérez) se comunica con un espía que tiene en el mismo puerto y le dice:

-Te pago 1 dolar por cada dato útil que tengas sobre el otro barco. Es urgente, porque tengo el radar roto.

Imaginen, por último, que Xérez y Yérez, sin saberlo, confiaron en el mismo espía.

* * *

¿Cuánto es el máximo que puede ganar el espía con estos capitanes?

* * *

Imaginen la situación durante un minuto, el primer minuto de Everybody Knows, de Leonard Cohen, si quieren. Tal vez les sugiera la respuesta.




* * *

No es difícil imaginar cómo actuará el espía para hacer fortuna:

Le avisa a Xérez que el radar de Yérez no funciona.

y luego

Le avisa a Yérez que Xérez sabe que el radar de Yérez no funciona.

y luego

Le avisa a Xérez que Yérez sabe que Xérez sabe que el radar de Yérez no funciona.

y luego...

* * *

La idea detrás de este problem(it)a es la de conocimiento común, una genialidad de Robert Aumann en los '70, y una de las razones por las cuales le dieron el Nobel.

De hecho, el conocimiento común es clave para su teorema conocido como "agreeing to disagree":

Si dos personas tienen la misma distribución de probabilidad a priori, y las consecuencias de un evento A son conocimiento común, tendrán la misma distribución de probabilidad a posteriori.

* * *

En fayerwayer posteaban el año pasado diez preguntas para trabajar en Google, y la segunda es un problema basado en la idea de conocimiento común. Cambiando 100 por cualquier otro número, se ve que no alcanza con k iteraciones en el "sabe que sabe que sabe...".

El problema inicial es de S Ambroszkiewicz.

Este post va de cabeza a la 4ta edición del Carnaval Matemático, ahora en manos de Zurditorium.

1544.- Aumann y el poker

El año pasado tuvimos una reunión extraña con Aumann: unos veinte profesores de económicas y exactas, y unos cincuenta agentes del mossad alrededor. Hubo una pregunta que no me animé a hacerle, y me imagino cuál habría sido su respuesta.



Más de cincuenta años atrás, la policía israelí cerró un garito en Jerusalem, donde se jugaba al poker por plata, y la defensa lo llamó a Aumann para testificar. ¿Testificar sobre qué? Que el poker no es un juego de azar, sino de habilidad, y por lo tanto, no estaba penado por la ley. Pero pese a su defensa matemática, el juez condenó a los timberos.

Contaba Kalai que luego Aumann se encontró con el juez, y le preguntó por su fallo. Su respuesta habría sido que en esos lugares la gente pierde todo, arruinando sus familias.

Kalai argumenta que el juez tiene razón. Reformulando su argumento, las leyes apuntan a un ideal, y los juegos de apuestas son perjudiciales para ese ideal social (también cita una variante del argumento, el juez debía descartar a Aumann, apelando a la Misnah: los jugadores no deben testimoniar pues no contribuyen a la creación del mundo!)

* * *

Tenía en mente la historia, y el post que linkeo me recordaba algo que me pasó a principios de los '90. Vívía con unos amigos, éramos todos estudiantes, y comprábamos muchas cosas en una feria municipal que teníamos cerca (sobre Santa Fe, bajo el puente de Pacífico). En uno de los puestos, un par de viejos jugaba al ajedrez, y cuando iba hacía algún partido con ellos, según el tiempo que tuviese, o su clientela.

Pero un día, no hubo más tablero: aparecieron un día los inspectores municipales, y les dejaron un cartel que recordaba una vieja ordenanza que prohibía los juegos de azar...

* * *

No hubiera contado nunca esta anécdota, sospecho que Aumann todavía se estaría riendo de nosotros. No es un juego de azar, con lo cual la ley estricta no se aplica; ni tampoco había apuestas de por medio, lo cual descarta el ideal social tras la ley.

Pero dudé en preguntarle a Aumann si seguía pensando como pensaba antes: que el fallo era inaceptable, porque estos jueces no obedecían la ley, sino su visión personal de cómo debían ser las cosas. Sospecho que sí, porque esa sigue siendo su postura en contra de los salvatajes económicos (en el fondo, que se jodan los bancos que tomaron riesgos, sabían que podía pasar) lo cual muestra una sorprendente coherencia a lo largo del tiempo.

1543.- Tres teoremas sobre el agua y su falta de forma

Teor 1: Imagenemos un río, y pongamos una red hexagonal en una parte de la corriente de agua, entre las dos costas. Elegimos hexágonos al azar, y colocamos en ellos una columna de cemento (si dos son vecinas, se unen herméticamente).

Solo hay dos resultados posibles: o quedó abierto un curso de agua, o las columnas forman un dique. En definitiva, todo juego de Hex termina con la victoria de uno de los jugadores.

* * *

Teor 2. En un terreno llano colocamos columnas unas al lado de otra, herméticamente unidas la columna i con las i-1 e i+1 (y sólo con ellas), tal que la primera y la última también se peguen. Quedan dos regiones separadas, una acotada, que podemos llenar de agua sin que pase a la otra.

* * *

Teor 3: En un estanque cuadrado, agitamos el agua (suavemente) y al menos un punto no se moverá (o las aguas se abren).

Advertencia: los próximos párrafos contienen la demostración. Puede omitirse en una primera, segunda, tercera,... lectura. El simbolito √ delante de algunos números 2 se refiere a 'raíz'. El html no es math-friendly.

Veamos: si todo punto se desplazó al menos una distancia h, tapemos la superficie con una red de triángulos de diámetro d menor a h (diremos al final quiénes son h y d).

Pintemos los vértices de rojo si la coordenada x varió h/√2 o más. Si no, lo pintamos de verde (la coordenada y varió h/√2 o más).


el camino es sólo indicativo, podría ser cualquier otro

Quedará un camino de vértices rojos o uno de verdes (reemplace un triángulo por una columna si tiene al menos dos vértices rojos: tiene un dique, o pasa el agua). Supongamos que el camino es rojo, da igual. Comienza en a*, y la coordenada x aumentó al menos h/√2. Llega a b*, donde disminuyó al menos h/√2. Luego, en algún momento, se produjo un cambio de signos: en dos vértices de un mismo triángulo saltó al menos 2 h/√2 (que es mayor a h).


Ahora, necesitamos un poco de análisis para decir quiénes son h y d:

Si T es la transformación que agita el agua, y la norma euclídea de T(x,y)-(x,y) no se anula, es mayor a un h (pues es continua).

Las imágenes de dos puntos del cuadrado por T estarán a distancia menor que h si estaban a distancia menor a un d' (pues T uniformemente continua).

Luego, si d es menor a d', hay dos vértices de un mismo triángulo donde la función salta más de h. Ridículo!

* * *

Estos tres grandes teoremas son equivalentes entre sí. No es difícil demostrar alguna versión más o menos general una vez que uno tiene la idea.

Sobre ellos, digamos que el primero lo identifica a Jordan. Gauss lo utilizó varias décadas antes, sin demostrar, considerándolo 'evidente'.

Brouwer, intuicionista, rechazaba las matemáticas 'tradicionales', pero su teorema de punto fijo demostró ser de gran utilidad en la matemática clásica. Una aplicación que hizo fue generalizar el de Jordan a Rⁿ, cambiando curvas por hipersuperficies. Parece que Poincaré lo intuyó: su idea fue que si se echaba azucar en una taza de café y se revolvía, algún granito en la superficie no cambiaba de lugar (su teorema ergódico es una de las tantas ramificaciones de esa idea tan simple).

El Hex fue inventado por Nash (pocos años antes lo había inventado Piet Hein). La relación de este juego con el teorema de Jordan es evidente, no es difícil probar la equivalencia. Con Brouwer es más difícil, pero sale: la existencia de un equilibrio de Nash es consecuencia directa de este teorema (y le valió un Nobel). Para la otra implicación, sólo se debe revisar lo que hicimos arriba, una idea de David Gale.

* * *

La idea que los conecta es que el agua no tiene forma, pero nos revela la forma de los lugares que ocupa. Sirva de moraleja, o mejor que sirva de base para la demostración de algún otro teorema.

* * *

(especial para el Carnaval Matemático, organizado esta vez por Tito Eliatron)

1542.- Omerta

(vamos, carajo!! estoy volviendo: recién iba a poner negritas, y en vez del código html usual, apelé al téxico \textbf{})

* * *

(mmm... y ahora empecé \begin{center} antes de darme cuenta... tampoco es cuestión de no postear culpa de eso!!)

* * *

Ejercicio: analice el Dilema del Prisionero en el caso de que (al menos) uno de ellos pertenezca a la mafia^(*).

* * *

Por si no conoce el DdelP, dos ciudadanos son detenidos y aislados hasta confesar un crimen e incriminar al otro. Si no lo hacen, van presos 3 años c/u. Si los dos lo hacen, van presos 10 años c/u. Si uno lo hace y el otro no, el que habla sale libre y el otro va 15 años preso.

* * *

Omerta viene, créase o no, de hombredad, prudentemente reemplazada en nuestro idioma por hombría.

* * *

(*) Por si hace falta aclararlo, la Omerta es la prohibición categórica^(**) de cooperar con las autoridades policiales, aún habiendo sido víctima de un crimen.

* * *

(**) Con flechas y todo!

* * *

Ejercicio avanzado: en una población de N personas, pN son de la mafia (p entre 0 y 1). La policía elige un par al azar y juegan al DdelP. ¿Cómo se comporta el porcentaje de mafiosos después de k juegos? (suponga que se realizan antes de que nadie quede libre)

(si alguien quiere prenderse, escribimos algo)

1540.- Jueguitos

Les recomiendo que prueben el chat noir. En este juego hay un elemento random, que sumado a un tablero limitado, altera la teoría conocida para el juego del Angel.

Sobre este otro juego, podemos decir que está casi liquidado: cuatro demostraciones dicen que el ángel gana si se le permite al ángel dar dos pasitos. Pero si el ángel mueve de a uno, como un rey en un tablero de Ajedrez, está cocinado. Muy buen resumen de las demostraciones y links a los papers, acá.


Y, para relajar la mente, un rompecabezas abstracto, sencillito, sin imágenes que distraigan.

1528.- Benjamin

Lo siguiente es parte del libro GAM3R 7H30RY, de McKenzie Wark. Se puede leer online aquí (un párrafo aparte merecería el sitio future of the book).

* * *

Benjamin se levanta por la mañana. Va al baño. Deja levantada la tabla del inodoro. Se baña y desayuna. Lee el diario. Encuentra un trabajo -como sujeto de experimentos- que comienza mañana. No es mucho, pero son tiempos duros. Lee un libro, y luego otro. Almuerza, sestea, lee otra vez. Se va a dormir. Se levanta. Va a trabajar. Vuelve a su casa, se prepara la comida. Habla un poco con su compañero de cuarto Bert. Aparece Hannah. Flirtea un poco con ella. Se va a la cama, se levanta, todo comienza otra vez.

Pasan los días sin muchos cambios. Cocina mejor. Hace nuevos amigos -Ted, Gersholm, Asja. A veces aparecen; otras los visita él. Hay muebles nuevos. Esto lo hace un poco más feliz, pero no mucho. Lo ascienden a Asistente del laboratorio. Es el turno noche, pero la paga es mejor. Luego pasa a Investigador y vuelve a trabajar en horarios diurnos. Más adelante se transforma en un académico. Aspira a ser un teórico. La paga es mejor. Y el horario. Sueña con yates y un gran televisor.

Benjamin es un Sim, un personaje del juego The Sims. Están perdonados por imaginar que era la vida de alguien.


* * *

In The Sims, you create characters like Benjamin, build and furnish homes for them, find them jobs and friends. All in a world without a sky. Perhaps a game like The Sims could be a parody of everyday life in ‘consumer society’. Benjamin and his friends dream of things. Things make them happy. They find a nice sofa so much more relaxing than a cheap one.


* * *

Imagina que Benjamin, nuestro personaje en The Sims, llega al penúltimo nivel y se transforma en un teórico. Tal vez le compres una computadora, porque parece aburrido de leer. ¿Qué haría con ella? Jugar The Sims, por supuesto!

1524.- Irracionalidad

No, no vamos a hablar de pi, ni e, ni raíz de dos.

El post trata del siguiente experimento:

disponemos de 50 clicks

hay N puertas (cerradas), y podemos abrir una con un click

con el siguiente click podemos abrir otra (y se cierra la 1ra) o clickear en la abierta

si clickeamos en la abierta, recibimos una cierta cantidad de puntos aleatoria (cada puerta tiene una distribución propia fija), y la puerta no se cierra

podemos seguir clickeando en la misma o cambiar a otra

si pasan 10 clicks sin que hayamos clickeado en una puerta, ésta desaparece

Bien, ¿se lo imagina sin necesidad de hacerlo?



¿Qué pasa si ahora las puertas no desaparecen porque no clickea? ¿Cambiaría en algo su estrategia?

* * *

Como bien me señala Hernán, así es demasiado general. Se lo puede jugar aquí.

1520.- 1ra clase de teoria de juegos

Sea A un subconjunto de un espacio métrico completo y separable.

Sea M(A) el conjunto de todas las medidas borelianas de probabilidad sobre A.

Sea U el espacio de funciones continuas f(a, m) que van de M(A)xA en los reales, U = C[M(A)xA].

Sea V una función del intervalo [0,1] en U, medible Lebesgue.

Lo anterior (A, M(A), U, V) define un juego continuo G, y un equilibrio será una medida de probabilidad boreliana p sobre UxA, es decir,

 p \in M(C[M(A)\times A]\times A)

¿Se marearon con medidas definidas en espacios de funciones que están definidas a su vez en otros espacios de medidas, como yo? Y eso que no les dije que A es un compacto (débil estrella) en el dual de algún espacio de Banach X, con lo cual sus propios puntos ya son funciones...

No importa, son tecnicismos, la cosa realmente empieza a ponerse difícil en la 2da clase.

1519.- Tactica y estrategia

"La táctica es saber qué hay que hacer cuando hay que hacer algo; la estrategia consiste en saber qué hacer cuando no hay que hacer nada".

Genialidad del gran maestro polaco Savielly Tartakower, guía muy útil.