Como funciona Internet

El sistema que permite el tráfico de datos por Internet se ha ido formando de manera evolutiva, siguiendo algunos criterios fundamentales tales como la compatibilidad hacia atrás, las instalaciones incrementales y los incentivos económicos. Es difícil determinar cuales de estos avances se han producido por una planificación deliberada y cuales han sido simplemente un legado de accidentes o casualidades históricas.

Una de las ideas fundamentales detrás de Internet es el packet switching, o transmisión conmutada de paquetes. Para entender esta idea es útil considerar su opuesto, el canal dedicado. Supongamos un antiguo sistema de teléfonos conectado por cables y con una operadora que hace las conexiones, en este caso tendríamos dos alternativas posibles, la más obvia sería que desde cada casa con teléfono salga un par de cables que la conecte con la central telefónica. Este sería un sistema muy confiable pero extremadamente ineficiente, porque la mayoría del tiempo los pares de cable pasarían sin ocuparse, porque las personas no están llamándose por teléfono las 24 horas del día. Este es el equivalente de líneas dedicadas (circuit switched) cuya ventaja es la confiabilidad y la desventaja su ineficiencia y alto costo.

Pero tenemos una alternativa que consiste en dividir las casas por sectores y tirar un solo par de cables compartidos para todo un bloque. Esto puede causar problemas cuando hay dos llamadas para teléfonos ubicados en el mismo bloque, pero estos problemas son improbables porque si el bloque de casas atendidas no es demasiado grande la probabilidad que existan colisiones es baja. ¿Y que pasa cuando existe una colisión? Simplemente se atiende al primero que llega y el segundo que trata de ocupar la línea compartida recibe el tono "ocupado", tendrá que esperar a que el otro termine su llamada. Si ambos llaman exactamente en el mismo instante, sin un milisegundo de diferencia, normalmente ambos reciben el tono "ocupado" aunque esta es una situación muy improbable. Esta es una idea análoga al packet switching cuya ventaja es la eficiencia y la desventaja en que es menos confiable porque está sujetas a colisiones y congestión (por ejemplo cuando después de un terremoto todos llaman al mismo tiempo).

Las líneas dedicadas tienen otro problema grave que no es tan evidente: resulta muy fácil cortarlas. Como existe un único circuito, basta que alguien corte ese circuito con un alicate para dejarlo definitivamente fuera de servicio.  Este problema alertó a los militares en USA, que durante los años de la guerra fría  vieron que las universidades, centros atómicos, etc. estaban conectando sus supercomputadores con líneas dedicadas, que eran muy confiables pero extremadamente vulnerables ante un ataque: alguien con un alicate cortante podía hacer más daño que muchas bombas.

Por eso a comienzos de 1960, la ARPA y otras instituciones ligadas a la defensa financiaron la investigación para desarrollar un sistema de comunicaciones que tuviera dos características principales: redundancia y eficiencia. La redundancia significaba que no hubiese un circuito único, si un camino se cortaba se debería poder usar otro de manera automática. La eficiencia implicaba no tener que hacer cientos de líneas dedicadas en paralelo así es como fue inventado el packet switching, consistente en cortar los mensajes en pequeños paquetes de un largo fijo para ser distribuidos por distintos caminos en una red de conexiones.

Mientras las líneas dedicadas tienen garantía de calidad, el packet switching no puede garantizar que no se perderán paquetes y no habrá congestión, trabajan en cambio bajo el concepto de "best effort" o sea haciendo todo lo posible para que la calidad de servicio sea aceptable, cosa que ocurre en términos estadísticos, tal como ocurría con las antiguas líneas telefónicas compartidas.

El modelo de capas

Otra idea fundamental en Internet consiste en aislar los distintos procesos en un modelo de capas, que actúen como cajas negras en el sentido que sus responsabilidades, entradas y salidas sean estandarizadas. Eso permite hacer muchos cambios y avances dentro de la caja negra, pero mantiene la compatibilidad hacia atrás porque las entradas y salidas son siempre las mismas. El modelo más conocido es de cuatro capas como muestra la figura:

Cada capa produce un servicio a la capa superior. La capa física se refiere a los medios de transporte, por ejemplo fibra óptica; cable de cobre; canal wifi; enlace satelital, etc. La capa de enlace (links) se refiere a las redes de área local como Ethernet por ejemplo.  La capa de red (network) está constituída por los routers y el sistema de enrutamiento  de los packet (capa IP). La capa de transporte (TCP) verifica el tráfico end-to-end juntando los packet para reconstruir los mensajes y enviando señales de control sobre la recepción. Finalmente la capa de aplicaciones es todo el software que usamos como los browsers, páginas web, Facebook, Blogger y todo eso.

Las capas de transporte y red (TCP/IP) casi no han cambiado desde el inicio de Internet, las demás capas en cambio han tenido cambios enormes. Por ejemplo la velocidad de transmisión en la capa física ha aumentado 30.000 veces, una cifra difícil de imaginar.

El enrutamiento de los packets es una de las partes más complicadas de Internet y se pueden encontrar bibliotecas sobre esto. El principio general es que cada router tiene tablas de corto alcance, con los mejores caminos para llegar a cierta dirección: Ningún router tiene una visión global de las conexiones, solo conoce a sus vecinos más próximos y esto permite conectar cualquier par de direcciones a través de los trillones de caminos posibles en un promedio entre 12 -18 saltos.

Tarifado en Internet

La economía en Internet es interesante porque las interacciones que se producen entre tecnología y economía son bidirecionales: las fuerzas económicas modelan la evolución de la tecnología, pero por otra parte las nuevas tecnologías disruptivas llevan a reescribir el balance de las ecuaciones económicas. Este campo de estudios también presenta un desafío por la falta de datos públicos de las estructuras de costo de los proveedores de Internet y la dificultad de obtener datos de consumobien calibrados.
(M. Chiang)

Los nuevos patrones de consumo creados por innovaciones tecnológicas como los teléfonos 3G-$G y las tablet, así como el aumento de consumo de video han hecho aparecer la necesidad de crear nuevos esquemas de tarifas. Uno de estos nuevos esquemas es el "smart data pricing" que trata de ajustar las tarifas de acuerdo al consumo de los usuarios. Algunas de estas estrategias son por ejemplo cobrar según el número de horas de uso; según la capacidad esperada de cada sesión; por servicio prioritario;  cobrar tanto a los creadores como a los consumidores de contenidos; etc.

La idea es que un sistema de precios diferenciados beneficiará a los usuarios en su conjunto, porque la tarifa plata tiende a penalizar a los que consumen menos y beneficiar a los que consumen más. El tarifado también puede ser dependiente de la hora considerando que hay horas de congestión y otras de bajo tráfico.

En general en estos sistemas de tarifa diferenciada existe un compromiso entre el nivel de retardo aceptable para el usuario y el precio, por lo que los usuarios dispuestos a aceptar mayor retardo deben pagar menos y viceversa.

Tarifa plana versus medida

Muchos años atrás, la conexión a Internet era con un modem por vía telefónica, uno discaba el número y los datos, transformados en sonido, eran enviados por teléfono a 300 bits/seg. La compañía telefónica cobraba igual que una llamada de voz, que en esos tiempos era bastante cara. El hecho es que Internet se pagaba por minuto de uso: mientras más minutos, más pagabas. Como imaginarán eso costaba un ojo de la cara además de ser insoportablemente lento, eran los años de la "Internet a galena" como la llamó la escritora Marta Blanco.

 Cuando aparecieron los primeros sistemas ISDN de 64 y 128 Mb/s las compañías optaron por cobrar tarifa plana mensual: todos pagan lo mismo independiente de cuanto usen Internet. En ese tiempo toda la gente estaba feliz porque no le cobrarían según el uso. Casi todos, recuerdo que leí a alguien argumentar que con la tarifa plana los usuarios normales terminaríamos subsidiando a los que hacen descargas y subidas masivas de datos. No recuerdo si fue Miguel Farah o Eduardo Kaftansky quien escribió eso, pero fue profético.

 Era obvio pero en su momento pocos lo pensaron, las compañías proveedoras de Internet (ISP) debían ser rentables y el precio que pagamos debe corresponder a los costos más la rentabilidad. Podemos pensar que los proveedores de Internet tienen como una tubería de diámetro fijo y el ancho de banda es como el caudal de agua -la analogía es bien adecuada- esos proveedores nos reparten a la casa en cañerías más pequeñas que nosotros usamos para descargar o subir datos. La economía de Internet tiene muchas similitudes con la economía del agua, algunas son complicadas y la mayoría de la gente no entiende, solo reclama.

El hecho es que hasta el año 2007 el ancho de banda se consideró como un recurso prácticamente infinito, igual que el agua y se pronosticó que llegaría el momento en que tendríamos "Internet gratis y de calidad para todos". Pero a partir del 2007 se empezó a popularizar el Iphone, así como la costumbre de ir en el bus viendo una película.

A medida que fueron apareciendo equipos con mayor resolución la demanda por ancho de banda para esas aplicaciones ha venido creciendo exponencialmente, y se está llegando a un punto que los ISP ya no podrán seguir con el esquema de tarifa plana. Entonces las principales alternativas que enfrentan son:

 1.-Subir el precio de la tarifa plana
2.-Bajar los anchos de banda en la práctica, haciendo Internet más lenta
3.-Volver a medir el uso y cobrar más al que más usa y viceversa.

 Un usuario como yo está lejos de consumir 1 Gb/s mensual, en cambio otros, adictos a Youtube y los juegos en línea consumen mucho más que eso ¿por que debería subsidiar yo a los grandes consumidores, especialmente si usan Internet para puras estupideces? En Estados Unidos Verizon y AT&T están empezando a cobrar US$ 10 por Gb/s consumido, yo pago US$ 40 mensuales y consumo menos de 1 GB/s. Eso definitivamente no es justo ni tampoco eficiente.

¿Existe el Talón de Aquiles de Internet?

En el año 2000 apareció un artículo en la revista Nature The Internet's Achilles' Heel: Error and attack tolerance of complex networks que tuvo miles de citas, los autores Albert, Jeong y Barabasi se hicieron famosos de manera instantánea con su paper que decía en el resumen: "En este paper demostraremos que la tolerancia a errores no es una propiedad de todos los sistemas redundantes sino solo por cierta clase de redes inomogeneas llamadas scale-free networks (...) sin embargo esta tolerancia a los errores tiene un alto precio, estas redes son extremadamente vulnerables a los ataques, por ejemplo a algunos nodos seleccionados".

 El artículo completo es de solo siete páginas y se puede bajar de la página que aparece en el link anterior. Ser publicado en una cover story de Nature es el sueño de muchos intelectuales, en esa revista apareció el artículo de La Tragedia de los Comunes, o Vox Populi de Francis Galton. Muchas de las ideas fundamentales del pensamiento científico han aparecido en esa revista. La cosa es que el artículo de Albert y los otros estaba completamente pifiado: equivocado de principio a fin. La idea sin embargo era lo suficientemente interesante como para llegar a la portada de Nature. Si pensamos en Internet -o más exactamente en las conexiones físicas de cientos de millones de routers que dirigen los packets- lo podemos caracterizar como un enorme grafo donde los routers serían los nodos y las conexiones físicas (fibra óptica, cobre, enlaces satelitales, radioenlaces, etc.) serían los links que los vinculan.

Despojandolo de la demostración matemática, la teoría de los autores era que como el crecimniento de Internet es espontáneo y más o menos al azar (no existe en ningún lugar del mundo un "mapa" con todas las conexiones de Internet, ni tampoco regulaciones o requisitos para conectarse) entonces se debería producir el efecto "rich gets richer" ¿En que consiste esto? En que las conexiones se empiezan a aglomerar de manera natural en los nodos que -por su localización geográfica o por ser los primeros- llegan a estar colocados en "el centro de Internet" topologicamente hablando.

La teoría era entonces que habían uno pocos nodos de gran centralidad, que bastaba con "sacarlos" con el ataque de un virus o destruirlos físicamente por ejemplo y toda la Internet se derrumbaría al quedar segmentada en millones de partes. Ese era lo que llamaron el talón de Aquiles de Internet. ¿En que se equivocaron entonces? En todo, menos en su demostración científica que es impecable.

Lo que pasa es que las conexiones de Internet no se crean completamente al azar como suponían, en ese caso Internet efectivamente tendría un talón de Aquiles, pero existen fuerzas económicas que determinan el patrón de conexiones. Por ejemplo los usuarios de Internet tienen la típica distribución de "cola larga" de Pareto donde un 20% usa gran parte de de los recursos y el otro 80% usa el residuo, mientras que si las conexiones fuesen solo al azar se produciría una distribución normal, cosa que no ocurre.

 Por eso no existe un "centro" de Internet y no existen nodos "ricos que se hacen cada vez más ricos", por el contrario la distribución real de las conexiones de Interet es vacía en el centro y muy densa en la periferia. Es muy curioso como la economía de redes se parece a muchos otros fenómenos humanos regidos por la ley del 80-20, igual que en la economía común y corriente: siempre habrán pocos ricos y muchísimos pobres, pero los ricos no se enriquecen más y más indefinidamente. Hay ricos pero no son los mismos, igual que en los nodos de Internet.

Small World (6 grados de separación)

En el año 1969 se realizó famoso experimento llamado "seis grados de separación", no lo voy a comentar sino que mejor copio lo que aparece en Wikipedia:

 La teoría de los seis grados de separación es una hipótesis que intenta probar que cualquiera en la Tierra puede estar conectado a cualquier otra persona del planeta a través de una cadena de conocidos que no tiene más de cinco intermediarios (conectando a ambas personas con sólo seis enlaces), algo que se ve representado en la popular frase "el mundo es un pañuelo". 

La teoría fue inicialmente propuesta en 1930 por el escritor húngaro Frigyes Karinthy en un cuento llamado Chains. El concepto está basado en la idea de que el número de conocidos crece exponencialmente con el número de enlaces en la cadena, y sólo un pequeño número de enlaces son necesarios para que el conjunto de conocidos se convierta en la población humana entera. Recogida también en el libro "Six Degrees: The Science of a Connected Age” del sociólogo Duncan Watts, y que asegura que es posible acceder a cualquier persona del planeta en tan sólo seis “saltos”.

Este fenómeno de pocos grados de separación en se observa en muchísimas redes enormes. No significa que todos estés separados por 6 nodos sino que en promedio, una gran cantidad de nodos se presenta ese fenómeno. Existen dos mecanismos por los que el Small World opera:

a) Estructural: existen caminos cortos en las redes
b) Algorítmico: con muy poca información local se puede encontrar la ruta más corta cuando la red es grande

Y mientras más grande es la red más crecen las posibilidades de encontrar el camino entre dos puntos en menos saltos.  Se dice que en Facebook por ejemplo -una red enorme- los saltos necesarios en promedio son solo 4.74.

Veamos primero lo de los caminos cortos (explicación estructural). Intuitivamente parece algo asombroso, pero no es tan raro, una persona bien poco sociable puede tener unos 20 amigos, y si cada uno de estos tiene otros 20, en 6 saltos su red tendría acceso a 20^6, o sea 64 millones de personas solo en el segundo nivel (amigos de los amigos). Claro que en la práctica son muchos menos porque existen muchos amigos comunes y los contactos repetidos, la gente parecida tiende a aglomerarse (homofilia), pero igual los caminos son suficientes para que en una red grande se pueda llegar de un punto a otro solo con un promedio de pocos saltos.

La otra explicación (algorítmica) es que en una red grande con muy poca información local se puede navegar de manera muy eficiente. De hecho así es como se enrutan los packets de datos que viajan por Internet, cuya red tiene miles de millones de nodos y sin embargo lo usual es que se llegue de un punto a potro en no más de 12 saltos en promedio.

Facebook: infección y contagio

Una característica típica en las redes es la llamada "influencia" donde un determinado usuario de Facebook o Twitter (por ejemplo)  influyen de cierta manera en los demás usuarios. Para estudiar este efecto el profesor Chiang usa un modelo de dependencia topológica, es decir considera a los usuarios como nodos conectados por medio de links y según la forma en que estos se encuentran conectados y la facilidad para establecer nuevas conexiones determina la influencia de cada cual.

En números Facebook tiene alrededor de 900 millones de usuarios y Twitter cerca de 500 millones, en cifras de 2012, esa es la cantidad de nodos de las respectivas redes. Ambos sistemas usan links direccionales donde seguir a alguien no implica que esa persona nos siga de vuelta. El valor económico de la influencia es importante por ejemplo en las campañas de marketing viral, donde se plantan algunos nodos "semilla".

La idea es que ciertos nodos -por su ubicación- dan mayor probabilidad que la semilla produzca un contagio, por eso es impoetante estudiar la topología de la red. Un ejemplo de como influye la topología es la influencia de la familia Medici, cuyo arbol genealogico muestra claramente que estaban en un nodo privilegiado por sus relaciones familiares.

Las topologías de red se pueden representar en grafos y matrices -igual que al calcular el Pagerank de Google- existen grafos con enlaces direccionales y bi direccionales. De la misma manera los patrones de conectividad de un grafo se pueden representar en una matriz, lo que permite manipularlos con operaciones algebraicas. Así se puede construir una matriz donde cada valor Aij será 1 si hay un link entre i-j y 0 si no hay un link entre estos nodos.

Para estudiar como se propaga la influencia según la topología de una red se pueden usar dos enfoques tomados de la medicina: los modelos de contagio  y los modelos de  infección.

Los modelos de contagio se dan por condiciones de conexión que los hacen accesibles a otros, de manera similar a la familia Medicis.  En estos casos es importante que los nodos se aglomeran en clusters y algunos tiene una posición privilegiada para contagíar bien sea por su centralidad o por el alcance de sus links. Esta propiedad llamada closeness centrality del nodo i se denota por Ci.

También existe la betweeness centrality, que es cuando un nodo está en medio del camino más corto entre otros nodos esto se denota por Bi. La importancia de un nodo se llama centrality y en cierto modo refleja que tiene alguna clase de acceso privilegiado o superior a los demás por su topología. Una de las medidad de centralidad o importancia es la que usa Google en el Pagerank calculando el eigenvector y el eigenvalor para clasificar las páginas web. Otras dos medidad de importancia de un nodo son la cercanía (o sea cuantos links cercanos lo unen con otros nodos) y el diámetro, que por el contrario es la cualidad de conectarse con cluster lejanos.

Así para modelos de contagio existen cuatro posibles métricas, según que clase de características estamos más interesados, todas basadas en la posición del nodo dentro de la topología de la red.

Los modelos de infección en cambio, estudian la transición de un estado a otro en el tiempo, son continuos y se tratan usando ecuaciones diferenciales. Se dice que estos son modelos basados en la población. Para la infección se definen tres estados: (S)usceptible, (I)nfectado y (R)epuesto/inmunizado. Que en redes corresponderían a un usuario que no ha sido influenciado, que está siendo influenciado y que ya fue influenciado por otro usuario, pero se "recuperó". Beta es la tasa en que un nodo se infecta y gama la tasa en que se recupera. La ecuación de este modelo de infección es:

dS(t)/dt=-BetaS(t)I(t) y su solución es:

I(t)=(I(0)e^Betat)/(S(0)+I(0)e^Betat), graficamente es logarítmica creciente

Esto en el caso sencillo que todos se infectaran y nadie se recupere. La curva llena es de los suseptibles S(t) y la punteada de los infectados I(t). Lo interesante de estas curvas logarítmicas es que parten cóncavas y en cierto punto cambian de sentido transformándose en convexas, donde ambas curvas se juntan es el punto de inflexión. En las curvas reales, conciderando la recuperación tenemos que S(t) cae y R(t) sube hasta que todos se recuperan (o mueren) en el intermedio los infectados I(t) suben a un máximo y a partir de cierto punto comienzan a caer.

El contagio es un cambio binario, alguien se contagia o no por la influencia de otro, la infección en cambio es un continuo en el tiempo donde alguien que es suceptible se infecta y eventualmente se recupera quedando o no inmunizado. 

El modelo de infección resuelto con ecuaciones diferenciales no considera la topología de la red porque se trata de como ocurre la infeción solo entre dos nodos, incluír la topología de toda la red complica bastante las cosas porque se deben estudiar probabilidades de ser infectado, con esto el modelo se hace intratable y hay que usar distintas aproximaciones, después de sucesivas aproximaciones se llega a una ecuación diferencial con matrices matemáticamente tratable como uestra la figura

Claro que estos modelos super simplificados presentan una utilidad limitada y existe una gran brecha entre la teoría y la práctica, pero sirven para hacerse una idea de como funcionan los mecanismos de contagio e infección en toda clase de redes.

Youtube y la formación de cascadas

Existen varios efectos de red -externalidades- que pueden ser positivos o negativos, la interferencia entre teléfonos móviles es un efecto negativo y la formación de cascadas o avalanchas de decisión es normalmente un efecto deseado. Youtube es uno de los servicios donde este efecto de cascada se ve claramente, donde se ha visto el caso de un video visto por casi 500 millones de personas a causa de este efecto.

En general las cascadas se producen por dependencia de la información entre los que toman una decisión, al contrario de la independencia requerida en "la sabiduría de las multitudes". Es muy difícil modelar excatamente estos fenómenos porque la gente en la vida real no actúa solo guiados por criterios racionales. Pero se puede demostrar que incluso si los actores que toman una decisión conociendo las decisiones que antes han tomado los demás siguen solo criterios racionales tenderán a aparecer estos fenómenos de cascada.

Un modelo simple para mostrar este efecto es el de toma de decisiones secuenciales, que se puede mostrar con el siguiente experimento imaginario: supongamos que colocamos a una serie de personas en fila frente a una pizarra, que deben adivinar el valor de un número que puede ser uno o cero.

Para hacer su estimación, cada uno recibe una "señal privada" que no es exacta, pero tiene una probabilidad mayor del 50% de ser el número correcto, a la señal privada que recibe la persona i la llamaremos xi. Tengan en cuenta que la señal privada puede ser 1 o 0, pero hay más probabilidades que el 50% que sea la correcta.. O sea las personas en ausencia de otra información, deberían escoger siempre la señal privada.

Entonces la primera persona recibe la señal privada x1 y la escribe en el pizarrón como su "acción pública" y1, que todos los que vienen después pueden ver. Es lógico (racional) que el primero siempre escribirá la señal privada. La segunda persona recibe su señal privada que puede ser igual o distinta a la que aparece en la pizarra, si x2 es igual a y1, las probabilidades de que sea el número correcto son mayores así es que coloca el mismo número y2=y1. Si son distintas no tiene mayor información y puede colocar cualquiera de los dos valores.

La tercera persona es la que puede iniciar la cascada porque si ve que y1=y2 y ese número coincide con su señal privada x3, colocará el mismo número y tendremos y1=y2=y3, el inicio de la cascada. De no ser así puede colocar cualquiera de los dos números, por ejemplo su propia señal privada. Sin embargo al calcular la probabilidad con la fórmula de Bayes resulta que la probabilidad de seguir los dos datos anteriores es mayor que el 50%.

Por eso, a medida que se va creando una serie de números repetidos, las personas pensarán racionalmente que son muchos los que han recibido la misma señal privada, que tiene la probabilidad mayor a 50% y que ese número es más probable independiente de la señal privadas que reciban. Es el efecto del análisis bayesiano que supone que algo que se repite está entregando información útil para el futuro. Una cascada se inicia entonces -suponiendo comportamiento racional- con el tercer participante si los dos anteriores han elegido el mismo valor.

También se pueden calcular las probabilidades de que ocurra una cascada en un esquema de este tipo y resulta que a medida que N (el número de personas o estimaciones que se hacen) es más grande, la probabilidad de que aparezca una cascada se aproxima a uno, o sea pasado suficiente tiempo se puede esperar con bastante seguridad que las cascadas se producirán.

¿Cuanto dura una cascada? Podría ser indefinida, pero como hablamos de probabilidades cualquiera pordría apostar a romperla simplemente porque
Pero las señales privadas son solo probabilidades, y este comportamiento de seguir la serie también está afectado por las señales privadas. En el fondo lo que se elige es si le creen al pensamiento de los demás o a la señal privada recibida. Cuando alguien corta una cascada se lllama el efecto de "el Rey está desnudo" lo que podría inducir otra cascada en sentido inverso. Este efecto se puede ver cuando las ropas pasan de moda o cuando cae un régimen político y es sustituído por otro.

Este fenómeno de dependencia de la información es típico de las redes, donde las personas toman decisiónes en base a las acciones de otras personas ignorando la información propia que disponen, otros nombres son modelo de influencia social o cascada de información.

Ahora, la probabilidad de que en un número grande de participantes N se produzcan más cascadas correctas (con el verdadero resultado) se hace muy pequeña a medida que N crece. O sea las cascadas no son predictivas y no tienen mayor probabilidad de ser correctas. La demostración de estas probabilidades está en la conferencia Q7 Part D del módulo How do I viralize a Youtube video? Pero la explicación conceptual es que las cascadas son lo opuesto de la "sabiduría de las multitudes", donde las estimaciones son completamente independientes y los errores tienden a anularse. En una cascada la dependencia es completa, los errores tienden a aumentarse y -cuando hay dependencia de información- lo que se produce es algo así como "la estupidez de las multitudes".

Votaciones y formación de concensos

La otra manera de formar concensos es por medio de votaciones. Una votación es un proceso donde por un lado tenemos un grupo de personas (votantes) y por el otro un número de alternativas (candidatos). En un modelo general cada votante tiene una preferencia especial para ordenar la lista de alternativas, es decir se crea una matriz con los candidatos ordenados según las preferencias de cada votante. De todas esas listas ordenadas de manera diferente se debe sacar una sola con un orden que refleje el concenso de todos los votantes. De eso se trata la votación, es un proceso donde varias listas se comprimen en una sola -la ganadora- por lo que gran parte de la información se pierde en el proceso.

Las votaciones son un mecanismo muy importante en la formación de concensos donde hay intereses en conflicto y son fundamentales en la teoría de la Social Choice, que es la base de la economía del bienestar.  Votaciones justas son un gran problema por la imposibilidad axiomática de muchos sistemas conocidos.

Podemos pensar en la votación como una caja negra donde una de sus entrasas son todas las listas ordenadas según cada votante y la salida es la lista ganadora.  La votación de la salida debe ser transitiva o sea, en una lista de preferencias A,B,C  si A>B y B>C entonces A>C y no cíclica, no podría en el caso anterios ser C>A.

Hay muchos sistemas de votación y todos tienen problemas. El más conocido es el mayoritario (Kemeny), donde se escoge en orden descendente entre la suma de los votos que obtiene cada alternativa.

Otro sistema es el posicional, una generalización del mayoritario. Este sistema consiste en dar un puntaje según la posición que ocupe en la lista. Por ejemplo el primero en la lista puede obtener 1 punto y todos los demás 0. Luego se cuentan los puntajes. O sea si tenemos tres listas de votos ordenadas (A,C,B) (C,B,A)  (A,B,C), y el lugar 1 tiene 1 punto miwentras los demás tienen 0, los puntajes serían: A=2, C=1, B=0 y la lista resultante sería (A,C,B). Una variante de este es el Borda Count, donde para N votantes, el primer lugar de la lista recibe N-1 puntos, el segundo N-2... etc. hasta el último que recibe 0.

El sistema Condorcet consiste en comparar por pares, lo que hace más sencillo el conteo. Este sistema tiene algunos problemas por ejemplo si comparamos de a pares estar tres listas (A,B,C) (B,C,A) (C,A,B) nos resulta un orden ciclico que es inconsistente. No solo Condorcet sino que todos los sistemas de votación presentan algún problema de consistencia.

Un ejemplo simple muestra que exactamente la misma votación puede dar tres resultados diferentes según el sistema que se use. Supogamos que V1, V2 y V3 votan así por C(hocolate), V(ainilla) S(trawberry)
V1 =(C,V,S)
V2=(S,V,C)
V3=(V,S,C)
Según que sistema se use, después del conteo los resultados son:
Mayoritario (C,S,V)
Borda (V,SC) (S y C empatados)
Cordorcet (V,S,C)

Es un problema serio porque cada sistema de votación -y se supone que los tres son racionales- da resultados distintos para los mismos votos. Solo imaginen esto en una elección política y de hecho ocurre que los resultados de las elecciones están fuertemente determinados por el sistema.

En vista de esta paradoja y muchas otras es que apareció la necesidad de buscar un sistema axiomatico que elimine la posibilidad de que ocurran paradojas en los sistemas de votación. El intento más famoso es el sistema axiomático de Kenneth Arrow para un sistema de votación ideal. Los axiomas de Arrow son cinco:

1. Cada lista de entrada es completa y transitiva (no omite candidatos y lamanera en que están ordenados es consistente)
2. La lista de salida, o sea el resultado, es completo y transitivo (idem)
3. La salida no es idéntica a ninguna entrada (es decir no hay un dictador)
4. Pareto (por ej. si en todas las entradas A>B entonces en la lista de salida A>B)
5. Independencia de las alternativas irrelevantes (IIA), por ejemplo si A>B en todas las entradas, ese orden debe aparecer igual en la salida independiente de cualquier otra alternativa C, D, etc. en medio.

El resultado es el famoso Teorema de la Imposibilidad, no existe ningún sistema de votación -Arrow demostró que no puede existir- que cumpla con estos cinco axiomas para una cantidad de más de 3 candidatos o alternativas. Popularmente se le conoce también como el "teorema de imposibilidad de la democracia".

El axioma que hace imposible un sistema libre de paradojas es el 5, la independencia de las alternativas irrelevantes (IIA). En realidad no existen las alternativas irrelevantes ni la independencia entre más de 3 alternativas y las que se ubican entre dos alternativas cualquiera afectan el orden incluso si se conserva en todas las listas de votación originales.

Esto tiene gran relevancia y no significa que los sistemas de votación estén fallados sino que nuestra intuición, de que existe independencia en el orden relativo de dos candidatos con respecto a los demás no existe. Este problema de "interferencia" de las alternativas "entre medio" se ha tratado de superar cambiando el concepto de order por otro de intensidad, o sea ya no importa solo que A>B sino también cuan intensamente A es mejor que B.

El hecho es que en todos los procesos de votación se produce una compresión de la intención de los votantes: muchas preferencias se comprimen en una sola y en ese proceso inevitablemente se pierde información, lo que lleva a las paradojas en los distintos sistemas.

Wikipedia y la negociación

Wikipedia no fue el primer intento de enciclopedia cooperativa, hubo otros antes pero Wikipedia fue el primero exitoso. Estudiar por que funcionó ayuda a comprender un concepto muy importante de la economía de redes que es la formación espontanea de concensos.

Desde el inicio fue una iniciativa muy cuestionada por el hecho que cualquiera podía publicar lo que hace que esté sujeta a tres problemas principales: desinformación, errores, información incompleta. Estos eran -en visión de los críticos- los problemas obvios de la falta de una autoridad y fuentes de conocimiento experto y reputable.

La idea de Wikipedia es formar un concenso básico sobre los temas a través de muchas versiones diferentes que cualquiera puede aportar, en lugar de la "opinión autorizada" de expertos sobre los mismos.  Bueno, el mecanismo casi todos lo conocemos a grandes rasgos pero hay algunas partes menos conocidas y es como trabajan los editores para facilitar el concenso, es decir, tratar de impedir que una visión sesgada o maliciosa se imponga por sobre la visión del concenso. Para esto los editores usan dos mecanismos: la negociación y la votación.

La negociación es una competencia entre dos o más actores contrapuestos que finalmente llegan a un acuerdo o punto de equilibrio. Hay dos visiones principales que son el elquilibrio axionatico de Nash y la oferta interactiva de Rubinstein. Podemos modelar la negociación para el equilibrio de Rubinstein con un ejemplo simple, por ejemplo A(lice) y B(ob) que se disputan como repartirse un dólar.

Digamos que A dice "repartamos así: 80% para mí y 20% para tí", entonces B podría contestar "no, mejor 10% para tí y 90% para mí", así comienza la negociación y el proceso sigue hasta que una parte dice "acepto tu oferta". Entonces A pretende, por ejemplo tener x para si y (1-x)  para B. Se podría pensar que este proceso dura para siempre pero no es así, en un tiempo T alguna de las partes termina aceptando la oferta contraria, esto porque a ambas partes les conviene llegar a un concenso, como por ejemplo en una compraventa, ambos quieren cerrar el negocio de la manera que mejor los favorezca pero prefieren un concenso a no hacer el negocio. Matemáticamente la función de utilidad es :

Ui=xie^(-rikT)

Donde Ui es utilidad de cada negociante i, xi es lo que propone, e es la constante de Napier, ri es el poder de negociación de i, k los intervalos de tiempo y T el tiempo total de la negociación. De esto se encuentran dos ecuaciones de equilibrio para cada uno de los negociadores con puntos de equilibrio x1* y x2* :

1-x2*=x1*e^-r1T
1-x1*=x2*e^-r2T

x1* es el punto donde A determina que le conviene aceptar la oferta de B y viceversa. Las soluciones para los puntos de equilibrio son:

x1*=(1-e^r2T)/(1-e^-(r1+r2)T) si T triende a cero r2/(r1+r2)
x2*=(1-e^r1T)/(1-e^-(r1+r2)T) si T tiende a cero r1/(r1+r2)

Lo que en buen cristiano significa que el óptimo para aceptar una oferta depende del poder de negociación de la parte contraria. Lo que es intuitivamente obvio por lo demás.

¿Y que es el poder de negociación? Es el que tiene la parte contraria y que hace caer nuestra función de utilidad más o menos rápido en el tiempo. Si a medida que pasa el tiempo -y se hacen más propuestas- nuestra utilidad cae de manera relativamente lenta es poder de negociación de la otra parte es débil y viceversa.

Es decir que si podemos trazar exactamente como decae nuestra curva de utilidad en el tiempo durante una negociación, podíamos calcular con esa simple fórmula el punto exacto donde nos conviene aceptar la otra oferta.

En los problemas de la vida real rara vez podemos trazar esta curva pero siempre la tenemos presente de manera inconsciente, intuitiva. En cada negociación que hacemos, incluso cuando regateamos el precio de una mercadería en una feria callejera.

Recomendaciones de Amazon

Las recomendaciones de la tienda online de Amazon se basan en un sistema de votación de clientes que hacen evaluaciones voluntarias de los productos, los evaluadores a su vez son evaluados por un sistema de votación en el que participa la comunidad de clientes. El sistema de Amazon no solo rankea por mayoría de votos sino que también registra el efecto llamado "sabiduría de las multitudes" y otros como los sesgos.

En el año 1906, en una granja de Plymouth, Inglaterra, Sir Francis Galton hizo un experimento muy simple pero de resultados importante para la estadística. El experimento de Galton consistió en juntar a 787 personas comunes y corrientes y pedirles que escribieran su estimación sobre el peso de un buey que estaba a la vista de todos. Cada persona miraba al buey, escribía en un papel su peso estimado y lo echaba en una urna.

 Entre los que estimaban el peso habían unos cuantos granjeros y carniceros, pero la gran mayoría eran personas comunes y corrientes que no tenían idea de como estimar el peso de un buey. Contra la intuición, el peso promedio estimado fue de 1187 libras, mientras que el peso real del buey eran 1198 libras, o sea una exactitud del 99.92%. Y esto no se debió a una coincidencia, porque el experimento se ha repetido innumerables veces desde entonces con resultados similares. Esto dio origen a un principio matemático llamado "la sabiduría de las multitudes". El paper original, Vox Populi, de Francis Galton en la revista Nature lo pueden leer aquí.

 Y tiene una explicación matemática, en palabras simples se puede decir que -si se cumplen ciertas condiciones- las estimaciones de una multitud ignorante serán más acertadas que las de expertos, porque los errores de sub estimación y sobre estimación tienden a compensarse convergiendo el promedio al valor correcto. Las condiciones que deben cumplirse para que esto ocurra son tres:

1.-Definición exacta de la pregunta (con una respuesta exacta, objetiva)
2.-Las estimaciones deben ser completamente independientes y sin sesgo (no deben haber influencias mutuas ni ideas preconcebidas)
 3.-Una cantidad de estimaciones independientes lo suficientemente grande (un problema importante es que significa exactamente "suficientemente grande")

Si las multitudes ignorantes son sabias porque los errores se compensan ¿por que entonces es tan malo el desempeño de las democracias? Creo que es obvio que la condición (2) no se cumple en ninguna de sus dos partes, eso explica por que la sabiduría de las multitudes no funciona en la política.

En este link por ejemplo aparece una página de Amazon con la cámara fotográfica de mis sueños, y al lado del producto se muestran las estrellas de recomendación y un número.

Esta cámara en particular ha obtenido 4 de 5 estrellas y ha sido revisada por 41 clientes. Todo eso es muy sencillo, las 4 estrellas son el puntaje promedio, redondeado, de los 41 puntajes. El problema es si yo quiero compararla con -digamos- la Nikon D3100, que tiene un precio similar, también tiene 4 de 5 estrellas pero la evaluaron 425 personas.

 Intuitivamente podemos pensar que un puntaje de 4 sobre 425 revisiones es mejor que el puntaje de 4 con 41 revisiones y mucho mejor que un puntaje de 4 con -digamos- 2 revisiones. ¿pero que hay de una cámara que tenga un puntaje de 3 pero con 10000 revisiones?. Es un problema de ranking análogo al que tiene Google para ordenar los resultados de búsqueda, no hay un solo criterio sino varios que se manejan siguiendo algún sofisticado análisis matemático.

En esta página, que hace un ranking de todas las cámaras fotograficas veremos que no están ordenadas simplemente por el puntaje obtenido sino por un algoritmo que considera el puntaje y la cantidad de evaluaciones además de otros factores.

Las estimaciones se pueden modelar con la siguiente fórmula:

yi(x)=x+Ei(x)

Donde yi(x) es la estimación, x el valor real y Ei(x) el error de cada estimación. Existe el promedio de los errores de quienes hacen las estimaciones que -usando el error cuadrático medio- se define por

Eae=1/N*(SUMi...n(Ex(Ei^2(x)))

o sea la suma de todos los errores al cuadrado dividido por las N estimaciones. Pero también existe el error del promedio, que después de alguna manipulación  algebraica resulta en Eea=1/N*(Eae) o sea el error anterior dividido por las estimaciones y que normalmente es mucho menor que el error promedio de las estimaciones individuales.

El factor (1/N) que relaciona los errores promedio con el promedio del error es la expresión matemática de la "sabiduría de las multitudes", como N es el número de personas que hacen la estimación, se puede ver que si N es muy grande el error promedio disminuye. A mayor N menor error promedio, asumiendo que las estimaciones son independientes y sin sesgo, por lo que los errores individuales estarán bien distribuídos.

Este concepto se usa para una controvertida rama de las estadísticas llamada "estimación Bayesiana", que asume que la historia pasada da información acerca del futuro, independiente del conocimiento que tengamos del fenómeno. Estas estimaciones bayesianas las hacemos todo el tiempo, Bayes continuó el trabajo de Laplace quien plenteó el siguiente problema "si durante los miles de años que se tiene registro, todos los días ha salido el sol ¿cual es la probabilidad que eso ocurra mañana?"

Desde la estadística clásica en estado de ignorancia, que un evento se haya repertido muchísimas veces no entrega información, bien podría no salir el sol mañana aunque haya salido durante cien millones de días. Ambas estimaciones tienen fundamentos conceptuales filosóficamente diferentes.

Según la estadística clásica si yo tengo una secuencia de n experimentos y s veces yo obtengo un cierto resultado, digamos "1" ¿cual es la probabbilidad de que en el siguiente obtenga 1? Según la estadística clásica la probabilidad sería exactamente s/n, pero el punto de vista bayesyano dice que también depende de cuantas veces se haya obtenido ese valor antes, y después de algo de cálculo integral se llega a una solución muy sencilla que incorpora esta "historia" y la estimación bayesiana quedaría  (s+1)/(n+2).

Se introduce un factor que hace que la probabilidad de que algo ocurra se mueva en una zona entre el valor de algo que nunca ha ocurrido antes hasta algo que ha ocurrido muchísimas veces. Así es como se incluye la sabiduría de las multitudes al cálculo de los rankings de Amazon.

Claro que el algoritmo exacto es un secreto de Amazon, pero mediante ingeniería reversa se ha podido determinar que se basa en el promedio de los puntajes, ajustado por una estimación Bayesiana, más unos bias dependientes de la calidad de los revisores y de las veces que se reporta que el artículo ha salido malo dentro de los primeros 30 días. Con algo de ingeniería reversa observando los rankings se encuentra que Amazon probablemente incorpora el factor bayesiano en una fórmula como esta:

BayesianoAmazon= (Nprom*R+ni*ri)/(Nprom+ri)

Para una estimación bayesiana el valor de N es el total de las observaciones pero también puede ser un Nmin, un Nmax o un Npromedio. Amazon usa un Nprom o Nmax. R es el promedio de todas las puntuaciones, ni es el promedio de estimaciones del item i y ri la puntuación promedio del item i.

Esto, como todas las demás cosas que hemos visto en el curso, no solo tiene que ver con el problema específico de Amazon, sino que con el problema general de construir rankings e incorporar la "sabiduría de las multitudes" a las estimaciones, ambas cosas fundamentales en muchos problemas de economía de redes.

Filtrado colaborativo 2

El método usado por Netflix para recomendar sus películas se basa en buscar similitudes. Como vimos en la entrada anterior han acumulado millones de evaluaciones hechas por usuarios. Con toda esa información se puede crear una matriz, por ejemplo, donde en las columnas estén las películas y en las filas todos los usuarios que han hecho evaluaciones. Es una matriz enorme que puede tener millones de usuarios y decenas de miles de películas, además no es una matriz cuadrada, tiene más filas que columnas.

En la celda correspondiente al par (usuario, película) se guarda la evaluación del usuario Ui para la película i. La idea general es que a usuarios similares probablemente les gustarán películas similares, el problema es como definir esa "similaridad" a partir de las evaluaciones. Intuitivamente podemos pensar que si un usuario da la misma calificación a dos películas, estas serían -para el- de calidad similar. Y si dos usuarios le dan la misma calificación a una película estos tienen gustos similares. Cuando hay esta similaridad se dice que existe una vecindad entre películas y usuarios. Como decíamos la idea es que a cierta clase de personas le gusta cierta clase de películas.

Matemáticamente una de las maneras de detectar estas vecindades y usarlas para predecir es el método de los mínimos cuadrados. Pero antes de eso se usan los modelos paramétricos, que son modelos matemáticos que en un comienzo tienen algunos datos que son variables en la etapa de entrenamiento, pero serán fijos en la etapa de predicción. Así los modelos paramétricos tienen dos etapas: entrenamiento y predicción.

Un buen ejemplo de esto son los sistemas de reconocimiento de voz de los computadores o teléfonos (marcadores de voz). En su etapa de entrenamiento el usuario ingresa algunas frases conocidas para que el sistema ajuste sus parámetros al tono y modulación de una voz en particular, estos son los datos de línea base. Luego que ha sido entrenado, el sistema ya puede interpretar la voz prediciendo que ciertos sonidos corresponden a ciertas palabras. En general el esquema es así:

Simplificando al extremo, en el caso de Netflix se tiene un gran registro histórico de calificaciones que sirven para crear la línea base  para entrenar al modelo paramétrico. El modelo parte con una suposición burda, por ejemplo tomando el simple puntaje de evaluación promedio de todo el conjunto de evaluaciones, a esta se le agrega un factor por el sesgo que puede tener cada película y el sesgo que puede tener cada espectador (por ejemplo, que prefiera las de acción alas de romance). Se hace una primera estimación para una película con puntaje conocido y se compara la predicción con el puntaje real, la diferencia entre el valor de la predicción real y el predecido es el error.

Entonces se usa el método de error de los mínimos cuadrados, que mide cuan alejada o cerca está la curva de predicciones respecto de la curva real. Ahora se trata de optimizar esta curva de errores mínimos cuadrados para que se acerque a la real, minimizar los errores cuadráticos medios.

En estos modelos se usa la palabra "sintonizar" para describir como van convergiendo las predicciones con la línea base en la etapa de entrenamiento. Para complicar las cosas existe en los modelos paramétricos un problema llamado "overfitting" que ocurre cuando algunas predicciones concuerdan demasiado con la línea bae en el período de entrenamiento el modelo se va haciendo rígido y pierde poder predictivo. Para esto se hace cierto ajuste matemático llamado regularización de mínimos cuadrados.

Como la función que deseamos optimizar es cuadrática (mínimos cuadrados) no podemos usar la programación lineal, lo que se usa es optimización convexa. Mientras la programación lineal se hace con un sistema de inecuaciones lineales más restricciones que definen un espacio de soluciones factibles en forma de polígono, con aristas bruscas, la optimización convexa también define un espacio convexo, sin quiebres bruscos.

Hay una definición gráfica interesante: un conjunto es convexo si cualquier par de puntos en el conjunto se pueden unir por un segmento de recta que no salga del conjunto, por ejemplo (a) es convexo y (b) no lo es

La propiedad geométrica más importante es que entre dos conjuntos convexos que no s etoquen siempre se puede trazar una recta entre ellos que no los toque, cosa que no ocurre si al menos uno no es convexo. Una función convexa es intuitivamente una que se curva hacia arriba, como (a) en la figura

Es resumen, la minimización de una función convexa en un conjunto convexo es la llamada optimización convexa. Y en el caso especial de los mínimos cuadrados se optimiza un función convexa no sujeta a ninguna restricción. A grandes rasgos el predictor de línea base para el adiestramiento funciona minimizando una función de error por mínimos cuadrados.

Pese a la complicada fundamentación matemática este método de optimización podría resumirse en una sola frase: se define una función objetivo con la suma de los errores al cuadrado, para cada punto de esta función su segunda derivada se iguala a cero (porque está en un "valle" o sea un óptimo convexo) esto da una ecuación lineal que al resolverse entrega la predición. Si estoy equivocado que alguien me corrija, pero así es como yo lo entendí.

Filtrado Colaborativo 1

El filtrado colaborativo es el método que usa la empresa Netflix que arrienda videos online para recomendar películas a sus clientes. Aunque la idea base es sencilla, el modelo matemático que se usa es bastante complicado. El método se basa en que los clientes hacen una evaluación de las películas después de verlas, asignando entre 1 a 5 estrellas.

No todos los clientes lo hacen por supuesto, esto es voluntario. La cosa es que basados en esas evaluaciones Netflix ha creado un algoritmo que "supone" que películas le gustarán a un cliente en base a la evaluación de otros clientes y la semejanza que el cliente que recibe la recomendación tendrá con ellos.

Para entender el modelo matemático que usan están las siguientes definiciones: User id=Ui Movie id=i Rating stars (1,2,3,4,5)=Rui Timing=Tui Estos datos entran a una "caja negra" cuya salida es una predicción de rating ^Rui que es la suposición del rating que le daría el usuario Ui a la película i ^Rui podría ser una fracción, por ejemplo 4.2, de ser así se sube a 5, si ^Rui predicho resulta mayor que 5 se deja en 5 y si es menor que 1 se deja en 1

Existen tres criterios posibles para construir esta métrica: la satisfacción del cliente que es el mejor criterio pero resulta inmanejable de calcular en la práctica, la efectividad de la predicción que también es muy difícil de calcular y finalmente el error de la predicción que es lo que se calcula mediante mediante la técnica conocida como L2 o media del mínimo valor cuadrado de los errores RMSE.

El error en cada punto sería `Rui-Rui (o sea valor predicho menos valor real) y la norma L2 se define como:

RMSE= Sqr(SUMui((`Rui-Rui)^2/C)

Donde C es el número total de pares pelicula/usuario evaluados ui Para hacer esta predicción se usa un algoritmo de aprendizaje. Como vimos antes tenemos una "caja negra" a la que se le introducen los valores de (Ui, i, Rui, Tui) y entrega la predicción ^Rui. Esta caja negra se "entrena" con técnicas de optimización convexa que veremos en la próxima parte. Netflix estableció un premio de 1 millón de dólares a quien logre desarrollar un algoritmo que mejore en un 10% la efectividad de sus recomendaciones.

Matrices y Google Pagerank

Normalmente uno estudia las matemáticas como una aburrida y a veces absurda secuencia de cálculos, que cada vez se pone más enredada -solo piensen que los niños parten estudiando teoría de conjuntos que es lo más abstracto y complicado que existe- enseñada a veces por ganapanes que con suerte entienden la mitad de lo que dicen. No es raro que tanta gente las termine odiando.

Pero hay cosas tan lindas y tan interesantes que cuesta imaginarse. A veces uno no se da cuenta de eso hasta muchos años después que le enseñaron. Una de esas cuestiones asombrsas son las matrices, una forma de notación abreviada para representar y manipular información.

Sin saberlo trabajamos con matrices a cada rato: una hoja de cálculo Excel es exactamente una matriz, donde colocamos valores arreglados en filas y columnas y cada celda tiene un subíndice ij que nos permite localizarla A1,1; B3,5; etc.

La noción de matrices es una de las más antiguas en matemáticas, la conocían los chinos hace mucho más de 2000 años y les llamaban -apropiadamente- "cuadrados mágicos", porque cuando uno arregla los números de cierta forma aparecen propiedades que parecen de magia y ha tomado siglos entender por que funcionan.

El uso más conocido es la receta que nos enseñan en el colegio para resolver sistemas de ecuaciones lineales con matrices y sus determinantes. Lo más lindo de las matrices es que sus propiedades "mágicas" -que por ejemplo permiten resolver sistemas de ecuaciones- vienen de la forma y de la simetría, son propiedades que se pueden descubrir y usar por intuición, sin saber realmente por que funcionan, como se hizo durante muchos años.

Las matrices no solo sirven para resolver sistemas de ecuaciones lineales, también pueden representar muchas otras cosas como por ejemplo grafos, lo que facilita mucho su manipulación en una computadora. Un grafo con cientos o miles de nodos es muy difícil de interpretar, pero se puede representar por una matriz y gracias a las propiedades "mágicas" de las matrices se pueden calcular valores con más facilidad.

La relación entre la forma, la simetría y las propiedades de lo que representa una matriz es muy importante, las matrices más simétricas son las que tienen las propiedades más interesantes y asombrosas. 

Por ejemplo la matriz cuadrada, con las mismas filas que columnas representan un sistema de ecuaciones que tiene una única solución (hay tantas ecuaciones como variables). Cuando hay menos ecuaciones que variables la matriz es rectangular y la solución no es única, sino que hay un espacio, una zona dentro de la cual hay infinitas soluciones factibles, el borde de esa zona es normalmente donde están las soluciones óptimas en programación lineal.

En el curso de Networks: friends, money and bytes me entero que Google usa propiedades de las matrices para calcular el Page Rank, que ordena a las páginas web según su importancia. A grandes rasgos se considera un grafo donde cada página web es un nodo y se conecta con las demás por links que salen a otras páginas o que entran de ciertas páginas. Por ejemplo imaginemos la web con solo cuatro sitios web, podría ser algo así:
(Ignoren las rayas en rojo, que son del profesor) Esto se podría representar con la siguiente matriz:
0, 0, 1, 0
0, 0, 1, 0
0, 0, 0, 1
1, 1, 1, 0
Donde cada fila representa un nodo (web) y si envía un link se coloca un 1 y si no envía se coloca un 0. Cada columna indica también el nodo hacia donde se envía el link. Por ejemplo la web 1 envía solo un link a la web 3, etc. 

Luego esta matriz se "normaliza" es decir cada valor se divide por el total de links enviados, en los tres primeros casos solo envían uno y en el cuarto se envían tres, así es que queda:
0, 0, 1, 0
0, 0, 1, 0
0, 0, 0, 1
1/3, 1/3, 1/3, 0
Y así tenemos el grafo representado por una matriz ¿y para que sirve esto?, bueno, es una matriz cuadrada de 4x4 así es que tiene propiedades mágicas. Una de estas propiedades es el eigenvalor y eleigenvector, que son una especie de factor de escala, que mantiene propiedades fundamentales de la matriz al multiplicarla. Si nuestra matriz es H, el eigenvalor lambda y el eigenvector pi se definen por esta igualdad:

H multiplicado por pi=lambda multiplicado por pi 

Bueno, resulta que este eigenvector almacena los valores que usa Google para rankear cada web ¿Como llegaron en Google a esa conclusión? Sepa Moya, ya les dije que las matrices son mágicas, a mi me llega hasta allí nomás el brazo. El hecho es que este eigenvector almacena la solución del sistema de ecuaciones lineales que representan al grafo. Y si quieren ver como se calculan los eigen (valor y vector propio hablando en cristiano) pueden leerlo aquí.

Claro que esa es una simplificación nomás porque hay varias otras complicaciones: las matrices de todas las páginas relevantes son enormes así es que se deben calcular usando métodos numéricos (iterativos), y hay casos especiales que complican la representación de matrices, pero todo tiene su solución y después de varias piruetas algebraicas se llega a la gran matriz G que es la que usa Google para asignar el Page Rank.

Subastas

Las subastas son uno de los mecanismos fundamentales de la economía libre. Existen desde la época de los romanos y tal vez desde antes, cuando se subastaban esclavos y toda clase de cosas. Así pasaron muchos siglos sin que su mecanismo cambiara demasiado.

Una subasta pública es un mecanismo clásico del mercado, tal vez el más puro de todos porque es uno de los más difíciles de manipular. El problema consiste en que alguien tiene uno o varios bienes que desea vender, tiene una valuación personal (lo que el piensa que vale) pero no tiene idea de cuanto le puede sacar, o sea no conoce el precio final. Tampoco tiene idea quien se lo puede adjudicar, esas son las dos condiciones básicas del subastador: no sabe quien va a comprar ni el precio que va a obtener.

Por la teoría subjetiva del valor sabemos que cada persona le asigna un valor subjetivo a las cosas y mediante una negociación los compradores y vendedores se pone de acuerdo en un valor que es el precio de equilibrio: el máximo que acepta pagar el comprador y el mínimo que acepta recibir el vendedor, ese es el precio. Hay innumerables formas de crear este precio pero la subasta tiene básicamente dos formas: se parte con un precio mínimo que va subiendo hasta que no hay más ofertas, o -lo que es menos común- con un precio máximo que va bajando hasta que alguien acepta comprar.

La subasta es un juego donde los ofertantes compiten entre si y el vendedor compite contra todos los ofertantes. El juego lo gana el que adquiere el producto a un precio bajo su valoración personal o cuando el vendedor lo vende sobre su valoración personal: en ambos casos hay una utilidad, de los compradores al minimizar el precio y los vendedores al maximizarlo.

Las subastas tienen otras variantes como la propuesta a sobre cerrado donde, al revés de la subasta pública, puede haber un solo comprador (una municipalidad por ejemplo) y varios vendedores u ofertantes. También existe un sinnúmero de estrategias para lograr la mejor utilidad, como la del "sniper" (francotirador) en las subastas con límite de tiempo hacen su oferta en los últimos segundos.

Con los servicios de subasta por Internet como eBay y Mercado Libre, los sistemas se han sofisticado mucho. Google subasta sus espacios publicitarios de AdWords e introdujo la primera innovación en siglos al sistema cuando descubrió que la mejor forma de lograr subastas justas, o sea sin estrategias que distorsionen los precios es la siguiente: el artículo se lo lleva el que hace la mayor postura, pero no paga el precio que ofreció, sino que el segundo mejor precio (o sea el anterior). La explicación es matemática y más o menos enredada pero en el fondo se trata de desacoplar el precio del ganador de la subasta, con lo que se logran estrategias más limpias de manera que el precio se aproxime lo más posible a la evaluación del comprador. La ecuación para las subastas es:

Ui (b)= Vi-Pi(b) 

Donde Ui(b) es la utilidad del postor i, Vi la valuación subjetiva del artículo según i y Pi(b) el precio que finalmente paga i, b es un vector

Una subasta parece sencilla pero es todo un arte y ciencia, en todas las ciudades hay grupos de viciosos que van a todas las subastas son todos medio ludopatas porque la subasta es un típico juego de estrategia. Una sola vez en mi vida participé en una, cuando un amigo que remataba varias cosas me pidió que fuera de "palo blanco" o sea a ofertar en su nombre para hacer subir los precios artificialmente.   Ni que decir que fue un desastre, los otros tipos se dieron cuenta enseguida, yo me emocioné haciendo subir las posturas y mi amigo se tuvo que llevar todas sus cosas de vuelta para la casa ¡se las adjudicó el mismo! Mi amigo no me habló por un buen tiempo y yo me abstuve de meter mis narices a un remate hasta el día de hoy.

Control de potencia en los CDMA

Ya revisé la lección de la primera semana que se trata de como funcionan los teléfonos celulares, es interesantísima. Si se fijan en la imagen verán por que se llama telefonía "celular", resulta que las antenas están ubicadas en las puntas de hexágonos que cubren pequeñas áreas de terreno llamados "celdas" por su parecido a las celdas de un panal de abejas. Las antenas son muy direccionales, solo irradian hacia adelante cubriendo un ángulo de 270 grados con muy baja potencia, solo lo justo para cubrir la celda.

El funcionamiento de los celulares inteligentes (smartphones) es mucho más sofisticado de lo que la gente imagina ¿como pueden enviar y recibir una cantidad tan enorme de información si el espectro que pueden ocupar es limitado? ¿como hacen para que las señales no se interfieran y todo sea más lento?. La respuesta es el sistema CDMA, que usa comunicaciónes digitales y transmisión por paquetes que -como en Internet- permite usar de manera mucho más eficiente el espectro de frecuencias disponibles.

Pero eso no es todo, hay otros dos mecanismos muy sofisticados que son la reutilización de una misma frecuencia por distintos usuarios y la ecualización de las potencias a un mínimo.

El problema de la interferencia se puede visualizar con el modelo de "cocktail party". supongamos que estamos en una fiesta ruidosa tratando de hablar con alguien, pero no escuchamos solo lo que la persona con quien conversamos nos dice, sino las voces de todos los demás borrachos y gritones que no nos dejan entender lo que nos dicen ¿cual sería la solución? Obviamente que todos se pongan de acuerdo y usen un volumen de voz más bajo.

Justamente eso es lo que se hace con los teléfonos: transmitir y recibir con potencia mínima, pero ¿cuan mínima? Si la potencia es demasiado baja no alcanza a llegar a la antena o celular, si es demasiado alta causará interferencia. La potencia requerida depende de la distancia y como son móviles es distinta para cada aparato según su ubicación.

La telefonía celular es un buen ejemplo de como diferentes actores compiten dinámicamente por el uso de un recurso escaso, que es el ancho de banda asignado. Los que alguna vez hicieron radio de 11 metros (ham radio) recordarán el problema, cuando se instalaba un tipo con una "zapatilla" de potencia y tapaba a todos los demás, es un gran ejemplo de la Tragedia de los Comunes.

Pero en un sistema público de telefonía, como son los celulares, que uno tape a todos los demás subiendo la potencia no es una opción. Por el contrario, se debe buscar una solución socialmente óptima. O sea se debe alcanzar un óptimo de Pareto ¿recuerdan? Un punto a partir del cual la mejora de cualquiera solo se puede obtener empeorando a otro, esa es la frontera que no se puede sobrepasar.

La situación de muchos compitiendo de manera no-cooperativa por un recurso escaso (el espectro asignado de frecuencias) es un problema clásico de la economía que también se aplica a las redes y existen dos clases de soluciones: caóticas o planificadas. Comportamientos individuales dirigidos por el interés propio, agregados en un mecanismo justo y eficiente, ayudado por información que se realimenta: así funcionan las redes.

En el caso de los celulares primero se usa la optimización con programación lineal: el objetivo a minimizar es el consumo de potencia, la restricción es un cierto nivel de interferencia igual para todos y las constantes son los canales disponibles y el ruido. Con esto se obtiene la zona de soluciones factibles cuya frontera es el óptimo de Pareto.

Lo otro que se usa es la teoría de juegos que ve el control de la potencia como una competencia. Existen dos posibles modelos de juegos: los de cooperación (como el juego de coordinación) y los de competencia (como el dilema del prisionero), en este caso se usa un modelo de competencia que se va ajustando con la realimentación negativa de información a medida que la recibe tiene a converger hacia el estado óptimo. La ecuación que se usa es:

Pi (t+1)= (Gi/SIRi(t)) Pi(t)

Donde Pi(t+1) es el valor de la potencia ajustada, Gi es el nivel esperado, SIRi(t) es la relación señal/ruido en el momento t (la señal de realimentación) y Pi(t) el nivel de la potencia actual.

A estas alturas muchos pensarán "OK, todo esto es muy bonito pero ¿para que sirve saber como funcionan los celulares?". Resulta que no se trata de los celulares sino del concepto de la economía de redes, ese es el mecanismo como funcionan las redes y esas son las reglas: competencia, tragedia de los comunes,  optimización lograda por la convergencia, con información que llega realimentada. Si lo piensan bien así es como funcionan todos los mercados de lo que sea, es decir la economía de redes es un principio mucho más general de lo que parece.

Los 11 videos de la primera clase se pueden ver en este sitio de Youtube, están muy interesantes, especialmente los Q1: part C, part D y part E. Se los recomiendo.