Teoría de Juegos Algorítmica

Usted está aquí

Créditos
6
Tipos
Complementaria de especialidad (Computación Avanzada)
Requisitos
Esta asignatura no tiene requisitos, pero tiene capacidades previas
Departamento
CS
Mientras que las Ciencias de la Computación se esfuerzan por comprender Internet y sus capacidades, los informáticos están incorporando conceptos y metodologías de Economía y Teoría de Juegos en su disciplina. En la última década, ha habido un enorme crecimiento en la investigación, centrada en torno a las siguientes preguntas: ¿qué herramientas de la teoría de juegos son aplicables a los sistemas informáticos? ¿Hasta qué punto el rendimiento de un sistema de optimización está influenciado por el conflicto de intereses de sus usuarios y administradores? ¿Cómo podemos diseñar un sistema cuyo funcionamiento sea robusto con respecto a los conflicto de intereses propios del sistema?

El curso pretende abordar algunos de los problemas fundamentales en la interfaz de la Informática y de la teoría de juegos, con un énfasis en los algoritmos y la complejidad computacional. Nuestro enfoque principal será en algoritmos de equilibrio, la complejidad computacional de la búsqueda de equilibrios, las herramientas algorítmicas en el diseño del mecanismo de subastas, los modelos de comportamiento Stategic para grandes redes, y el precio de la anarquía. Incorporando también algunas nociones de la teoría de juegos cooperativos.

Profesores

Responsable

  • Maria Jose Serna Iglesias ( )

Otros

  • Maria del Carme Alvarez Faura ( )

Horas semanales

Teoría
2.5
Problemas
1.5
Laboratorio
0
Aprendizaje dirigido
0.5
Aprendizaje autónomo
8

Competencias

Competencias Técnicas de cada especialidad

Advanced computing

  • CEE3.1 - Capacidad para identificar barreras computacionales y analizar la complejidad de problemas computacionales en diversos ámbitos de la ciencia y la tecnología; así como para representar problemas de alta complejidad en estructuras matemáticas que puedan ser tratadas eficientemente con esquemas algorítmicos.
  • CEE3.2 - Capacidad para utilizar un espectro amplio y variado de recursos algorítmicos para resolver problemas de alta dificultad algorítmica.
  • CEE3.3 - Capacidad para entender las necesidades computacionales de problemas de disciplinas distintas de la informática y efectuar contribuciones significativas en equipos multidisciplinares que usen la computación.

Competencias Técnicas Genéricas

Genéricas

  • CG1 - Capacidad para aplicar el método científico en el estudio y análisis de fenómenos y sistemas en cualquier ámbito de la Informática, así como en la concepción, diseño e implantación de soluciones informáticas innovadoras y originales.
  • CG3 - Capacidad para el modelado matemático, cálculo y diseño experimental en centros tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación e innovación en todos los ámbitos de la Informática.
  • CG5 - Capacidad para aplicar soluciones innovadoras y realizar avances en el conocimiento que exploten los nuevos paradigmas de la Informática, particularmente en entornos distribuidos.

Competencias Transversales

Razonamiento

  • CTR6 - Capacidad de razonamiento crítico, lógico y matemático. Capacidad para resolver problemas dentro de su área de estudio. Capacidad de abstracción: capacidad de crear y utilizar modelos que reflejen situaciones reales. Capacidad de diseñar y realizar experimentos sencillos, y analizar e interpretar sus resultados. Capacidad de análisis, síntesis y evaluación.

Básicas

  • CB6 - Que los estudiantes sepan aplicar los conocimientos adquiridos y su capacidad de resolución de problemas en entornos nuevos o poco conocidos dentro de contextos más amplios (o multidisciplinares) relacionados con su área de estudio.
  • CB8 - Que los estudiantes sepan comunicar sus conclusiones y los conocimientos y razones últimas que las sustentan a públicos especializados y no especializados de un modo claro y sin ambigüedades.
  • CB9 - Que los estudiantes posean las habilidades de aprendizaje que les permitan continuar estudiando de un modo que habrá de ser en gran medida autodirigido o autónomo.

Objetivos

  1. Conocer las principales técnicas y problemas en el dominio de la teoría de juegos algorítmica e identificar sus propiedades principales.
    Competencias relacionadas: CG1, CEE3.1, CEE3.2, CB8, CB9, CTR6,
  2. Examinar las condiciones bajo las cuales aparecen la cooperación y el antagonismo. Realizar un análisis y extraer las propiedades fundamentales de los problemas de diferentes dominios con el fin de evaluar la idoneidad de un análisis teórico de juegos y sus limitaciones
    Competencias relacionadas: CG1, CG3, CEE3.1, CEE3.2, CEE3.3, CB6, CB9, CTR6, CG5,

Contenidos

  1. Introducción a la teoría de juegos algorítmica
    Decisiones centralizadas y descentralizadas. Juegos e Internet. Tipos de juegos, estrategias y equilibrios.
  2. Juegos estratégicos y aspectos computacionales de los equilibrios de Nash
    Juegos estratégicos, estrategias puras y mixtas. El concepto de solución de un juego. Equilibrio de Nash puro, la complejidad de su computación. Equilibrios de Nash puros frente a óptimos locales: potential games. Estrategias mixtas y equilibrios de Nash. La complejidad de la computación de equilibrios de Nash.
  3. El precio de la anarquía y el de la estabilidad
    Definiciones. Coste social. Mejores y peores equilibrios de Nash. Juegos de Red: asignación de recursos basado en la utilidad. Juegos de Red: asignación de recursos basado en la utilidad. Encaminamiento egoísta y juegos de congestión. Juegos de creación de redes. Otros ejemplos.
  4. Teoría de juegos cooperativos
    Juegos cooperativos y simples. Tipos de coaliciones. Índices de poder. Ejemplos: juegos de votación, juegos combinatóricos y juegos de influencia en las redes sociales.
  5. Elección social computacional
    El problema de la agregación de preferencias. Reglas de votación. Manipulación, control y soborno en votaciones.

Actividades

Actividad Acto evaluativo


Teoría
28h
Problemas
16h
Laboratorio
0h
Aprendizaje dirigido
4h
Aprendizaje autónomo
56h

Examen final

Preguntas de teoría y resolución de problemas
Objetivos: 1 2
Semana: 15 (Fuera de horario lectivo)
Tipo: examen final
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
2h
Aprendizaje autónomo
15h

Control 1

Control de problemes
Objetivos: 1 2
Semana: 6
Tipo: examen de problemas
Teoría
0h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
10h

Control 2

Control de problemas

Semana: 13
Tipo: examen de problemas
Teoría
0h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
10h

Presentació de un artículo de investigación

Activitat voluntaria. Presentación de un artículo de revista científica del área describiendo investigación en alguno de los temas tratados en el curso o en otros temas relacionados que sean de interés para el alumno.
Objetivos: 1 2
Contenidos:
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

Metodología docente

Habrá dos tipos de clases: sesiones teóricas y sesiones prácticas. Dos horas por semana se dedican a la teoría y dos más
para los ejercicios.

Las clases teóricas tienen la forma de clase magistral en la que el profesor propone nuevos conceptos o técnicas. Se complementan con ejemplos que ilustran los conceptos introducidos. Las sesiones consistirán en una presentación de los principales temas de cada contenido, basándose principalmente en trabajos de investigación originales.
 Se espera un alto nivel de participación de los estudiantes en cada sesión. Las líneas actuales de investigación en cada tema se discutirán al final de su presentación.

Las clases prácticas se utilizan para resolver los ejercicios en las que los estudiantes participan activamente. En general, los profesores establecen los ejercicios con anticipación. Se espera que los estudiantes resuelvan los ejercicios y los presenten con el objetivo de poder discutir las diversas soluciones / alternativas en clase.

Método de evaluación

Nota = 20%(C1+C2)/2 + 40% FW + 40% FT


C1, C2 = Controles de problema. Cada uno se califica de 0 a 10.

FW = Presentación de artículo (de 0 a 10) en el que se requiere que cada participante presente un artículo de investigación (previamente asignado por el profesor).
  La presentación consta de:
      3-5 minutos estado del arte sobre el tema del artículo, y la motivación.
     Visión general (1-3 minutos) de las ideas principales del documento.
     10 minutos de presentación incluyendo la mayoría de los detalles importantes.
     2-5 minutos de conclusiones y revisión de los problemas o direccions de investigación que se mencionan en el artículo.

FT = Prueba final (de 0 a 10) que incluye todo el contenido de AGT.

Bibliografía

Básica:

Complementaria:

Capacidades previas

Conocimientos básicos de los métodos de análisis de algoritmos (en particular, la complejidad asintótica).
Conocimientos básicos en algoritmos. Programación Lineal. Flujo máximo. Búsqueda locales. Algoritmos para problemas en grafos y redes.
Conocimientos básicos sobre razonamiento algebraico.
Conocimientos básicos sobre complejidad computacional, clases y reducciones.

Adenda

Contenidos

There are no modifications to the contents of the teaching guide. No hi ha modificacions respecte als continguts de la guia docent. No hay modificaciones respecto a los contenidos de la guía docente.

Metodología docente

There are no modifications to the methodology given in the teaching guide. The on-line classes will be complemented with voluntary activities that encourage participation in these classes and the assimilation of the topics of the course. No hi ha modificacions respecte a la metodologia de la guia docent. Les classes no presencial es complementaran amb activitats voluntàries que fomentin la participació en aquestes classes i l'assimilació dels continguts de l'assignatura. No hay modificaciones respecto a la metodología de la guía docente. Las clases no presenciales se complementarán con actividades voluntarias que fomenten la participación en estas clases y la asimilación de los contenidos de la asignatura.

Método de evaluación

There are no modifications to the evaluation method. No hi ha modificacions respecte al mètode d'avaluació. No hay modificaciones al método de evaluación.

Plan de contingencia

In case of cancellation of the face-to-face teaching, the classes will continue on-line, in the same schedule, and they will be reinforced with communication tools that allow to maintain contact between students and between students and teachers in an agile way. The exams will be held in person, with delivery through the Racó and/or Atenea En cas de cancel·lació de tota activitat lectiva presencial les classes es continuaran de forma no presencial en el mateix horari i és reforçaran amb eines de comunicació que permetin mantenir el contacte entre els estudiants i entre estudiants i professors de forma àgil. Els exàmens es realitzaran de forma no presencial, amb entrega a través del Racó i/o d'Atenea. En caso de cancelación de toda actividad lectiva presencial las clases continuarán de forma no presencial en el mismo horario y se reforzarán con herramientas de comunicación que permitan mantener el contacto entre los estudiantes y entre estudiantes y profesores de forma ágil. Los exámenes se realizarán de forma no presencial, con entrega a través del Racó y/o de Atenea.