Introducción a la Teoría Algorítmica de Juegos

Introducción a la Teoría Algorítmica de Juegos

• La teoría de juegos estudia las interacciones estratégicas entre agentes racionales.
• Su objetivo es predecir resultados y recomendar estrategias.
• El diseño de algoritmos se centra en crear algoritmos eficientes para problemas computacionales.
• Busca optimizar métricas de rendimiento como tiempo y espacio.
• La Teoría Algorítmica de Juegos (AGT) aplica el pensamiento algorítmico a los problemas de la teoría de juegos.
• Aborda los desafíos computacionales en los juegos y diseña juegos con propiedades deseables.

Enrutamiento egoísta

• Modelo que involucra una red de carreteras.
• El tráfico fluye entre un punto de origen y un destino.
• Cada conductor elige el camino más corto disponible.
• Se plantea cómo afecta el enrutamiento egoísta al tiempo total de viaje.
• La paradoja de Braess establece que agregar una carretera puede aumentar el tiempo de viaje para todos.
• Es un resultado anti-intuitivo con implicaciones significativas.

Ejemplo de la paradoja de Braess

• Red inicial :*
• Carretera A: Inicio a Fin, Costo: x
• Carretera B: Inicio a Fin, Costo: 1
• Flujo :*
• Tasa de tráfico: 1
• Cada conductor elige la carretera con el mínimo costo
• Equilibrio :*
• Todos los conductores toman la Carretera A: Costo $1+x$
• O todos los conductores toman la Carretera B: Costo $x+1$
• Costo total: 1
• Red modificada :*
• Carretera A: Inicio a Intersección, Costo: x
• Carretera B: Intersección a Fin, Costo: x
• Carretera C: Inicio a Fin, Costo: 1
• Carretera D: Inicio a Intersección, Costo: 0
• Carretera E: Intersección a Fin, Costo: 0

Debido a que las Carreteras D y E tienen costo 0 desde Inicio a Intersección a Fin, ahora todos los conductores toman el camino Inicio $\rightarrow$ Intersección $\rightarrow$ Fin. Entonces el costo se vuelve $x+x=2x$.

• Flujo :*
• Tasa de tráfico: 1
• Equilibrio :*
• Todos los conductores toman Inicio $\rightarrow$ Intersección $\rightarrow$ Fin : Costo x + x
• Costo total: 2
• Conclusión :*
• Agregar una carretera aumentó el costo de 1 a 2.

Diseño de mecanismo

• Su objetivo es diseñar las reglas de un juego para lograr un resultado deseado
• Los jugadores actúan estratégicamente en su propio interés.
• El diseñador del mecanismo tiene información limitada.
• Algunos ejemplos incluyen:
• Subastas: diseñar una subasta para maximizar los ingresos
• Votación: diseñar un sistema de votación para elegir al mejor candidato
• Emparejamiento: diseñar un algoritmo de emparejamiento para emparejar estudiantes y escuelas

Internet como un juego

• Los protocolos incluyen TCP/IP, BGP, DNS.
• Los jugadores son sistemas autónomos, proveedores de contenido, usuarios
• Las interacciones estratégicas son control de la congestión, enrutamiento, almacenamiento en caché
• Se incentiva maximizar el rendimiento, minimizar la latencia, aumentar los ingresos.

Direcciones futuras

• La IA se utiliza para aprender estrategias óptimas en juegos complejos.
• Se busca diseñar agentes de IA que puedan cooperar y competir eficazmente.
• Se enfoca en diseñar sistemas descentralizados seguros y justos.
• Se utiliza la teoría de juegos para analizar los incentivos de los validadores y mineros.
• Se comprende cómo las redes sociales influyen en el comportamiento.
• Se diseñan intervenciones para promover la cooperación y reducir los conflictos.

Conclusión

• La Teoría Algorítmica de Juegos es un campo dinámico que combina la informática y la economía
• Tiene aplicaciones en muchas áreas.
• Ofrece nuevas perspectivas sobre las interacciones estratégicas y los incentivos.