Teoria de Jocs Algorísmica

Esteu aquí

Crèdits
6
Tipus
Complementària d'especialitat (Computació Avançada)
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
CS
Mentres que les Ciències de la Computació s'esforçan per comprendre l'Internet i les seves capacitats, els informàtics estan incorporant conceptes i metodologies de l'economia i de la teoria de jocs en la seva disciplina. En les últimes dècades, hi ha hagut un enorme creixement en la investigació, centrada al voltant de les següents preguntes: ¿Quines eines de la teoria de jocs són aplicables als sistemes informàtics? ¿Fins a quin punt el desviament del rendiment d'un sistema, amb respecte de l'òptim, és degut al conflicte d'interessos dels seus usuaris i administradors? ¿Com podem dissenyar un sistema en el que el seu funcionament és robust respecte al possible conflicte d'interessos dins del sistema?

El curs pretén abordar alguns dels problemes fonamentals en la interfície de la Informàtica i de la teoria de jocs, amb un èmfasi en els algorismes i la complexitat computacional. El nostre enfocament principal serà en algoritmes d'equilibri, la complexitat computacional de la recerca d'equilibris, les eines algorítmiques en el disseny del mecanisme de subhastes, els models de comportament estratègic per a grans xarxes, i el preu de l'anarquia. Incorporant també algunes nocions de la teoria de jocs cooperatius.

Professors

Responsable

  • Maria Jose Serna Iglesias ( )

Altres

  • Maria del Carme Alvarez Faura ( )

Hores setmanals

Teoria
2.5
Problemes
1.5
Laboratori
0
Aprenentatge dirigit
0.5
Aprenentatge autònom
8

Competències

Competències Tècniques de cada especialitat

Computació avançada

  • CEE3.1 - Capacitat per a identificar barreres computacionals i analitzar la complexitat de problemes computacionals en diversos àmbits de la ciència i la tecnologia; així com per representar problemes d'alta complexitat en estructures matemàtiques que puguin ser tractades eficientment amb esquemes algorítmics.
  • CEE3.2 - Capacitat per utilitzar un espectre ampli i variat de recursos algorítmics per resoldre problemes d'alta dificultat algorísmica.
  • CEE3.3 - Capacitat per entendre les necessitats computacionals de problemes de disciplines diferents de la informàtica i efectuar contribucions significatives en equips multidisciplinaris que facin servir la computació.

Competències Tècniques Generals

Genèriques

  • CG1 - Capacitat per aplicar el mètode científic en l'estudi i anàlisi de fenòmens i sistemes en qualsevol àmbit de la Informàtica, així com en la concepció, disseny i implantació de solucions informàtiques innovadores i originals.
  • CG3 - Capacitat per al modelatge matemàtic, càlcul i disseny experimental en centres tecnològics i d'enginyeria d'empresa, particularment en tasques de recerca i innovació en tots els àmbits de la Informàtica.
  • CG5 - Capacitat per aplicar solucions innovadores i realitzar avenços en el coneixement que explotin els nous paradigmes de la Informàtica, particularment en entorns distribuïts.

Competències Transversals

Raonament

  • CTR6 - Capacitat de raonament crític, lògic i matemàtic. Capacitat de resoldre problemes en la seva àrea d'estudi. Capacitat d'abstracció: capacitat de crear i utilitzar models que reflecteixin situacions reals. Capacitat de dissenyar i realitzar experiments senzills, i analitzar-ne i interpretar-ne els resultats. Capacitat d'anàlisi, de síntesi i d'avaluació.

Bàsiques

  • CB6 - Que els estudiants sàpiguen aplicar els coneixements adquirits y la seva capacitat de resolució de problemes en entorns nous o poc coneguts dins de contexts més amplis (o multidisciplinaris) relacionats amb la seva àrea d'estudi.
  • CB8 - Que els estudiants sàpiguen comunicar les seves conclusions i els coneixements i raons darreres que les sustenten- a públics especialitzats i no especialitzats d'una manera clara i sense ambigüitats.
  • CB9 - Que els estudiants posseeixin les habilitats d'aprenentatge que els permetin continuar estudiant d'una manera que haurà de ser en gran mesura autodirigida o autònoma.

Objectius

  1. Conéixer les principals tècniques i problemes en el domini de la teoria de jocs algorísmica i identificar les propietats principals.
    Competències relacionades: CB8, CB9, CTR6, CEE3.1, CEE3.2, CG1,
  2. Examinar les condicions sota les quals apareixen la cooperació i l'antagonisme. Realitzar una anàlisi i extreure les propietats fonamentals dels problemes de diferents dominis per tal d'avaluar la idoneïtat d'un anàlisi teòrica de jocs i les seves limitacions
    Competències relacionades: CB9, CTR6, CEE3.1, CEE3.2, CEE3.3, CG5, CG1, CG3, CB6,

Continguts

  1. Introducció a la teoria de jocs algorísmica
    Decisions centralitzades i descentralitzades. Jocs i Internet. Tipus de jocs, estratègies i equilibris.
  2. Jocs estratègics i aspectes computacionals dels equilibris de Nash
    Jocs estratègics, estratègies pures i mixtes. El concepte de sol.lució del joc. Equilibri pur de Nash, la complexitat de la seva computació. Equilibris de Nash purs versus òptims locals: potential games. Estratègies mixtes i equilibris de Nash. La complexitat de la computació de equilibris de Nash.
  3. El preu de l'anarquia i el de l'estabilitat.
    Definicions. Coste social. Millors i pitjors equilibris de Nash. Jocs de Xarxa: assignació de recursos basat en la utilitat. Encaminament egoista i jocs de congestió. Jocs de formació de xarxa. Altres exemples.
  4. Teoria de jocs cooperatius
    Jocs cooperatius i simples. Tipus de coalicions. Índexs de poder. Exemples: jocs de votació, jocs combinatorics, jocs d'influència en les xarxes socials.
  5. Elecció social computacional
    El problema de l'agregació de preferències. Regles de vot. Manipulació, control i suborn en la votació.

Activitats

Activitat Acte avaluatiu


Teoria
28h
Problemes
16h
Laboratori
0h
Aprenentatge dirigit
4h
Aprenentatge autònom
56h

Examen final

Preguntes de teoria y resolució de problemes
Objectius: 1 2
Setmana: 15 (Fora d'horari lectiu)
Tipus: examen final
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2h
Aprenentatge autònom
15h

Control 1

Control de problemes
Objectius: 1 2
Setmana: 6
Tipus: examen de problemes
Teoria
0h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Control 2

Control de problemes

Setmana: 13
Tipus: examen de problemes
Teoria
0h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Presentació d'un article de recerca

Activitat voluntaria. Presentació d'un article de revista científica de l'àrea descrivint recerca en algun dels temes tractats en el curs o en altres temes relacionats que siguin d'interès per a l'alumne.
Objectius: 1 2
Continguts:
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h

Metodologia docent

Hi haurà dos tipus de classes: sessions teòriques i sessions pràctiques. Dues hores per setmana es dediquen a la teoria i dos més
per als exercicis.

Les classes teòriques tenen la forma de classe magistral en què el professor proposa nous conceptes o tècniques. Es complementen amb exemples que il·lustren els conceptes introduïts. Les sessions consistiran en una presentació dels principals temes de cadascú dels continguts i es basaran principalment en treballs de recerca originals seleccionats.
S'espera un alt nivell de participació dels estudiants en cada sessió. Les línies actuals d'investigació en cada tema es discutiran al final de la seva presentació.

Les classes pràctiques s'utilitzen per dur a resoldre els exercicis en elles els estudiants participen activament. En general, els professors estableixen els exercicis amb anticipació. S'espera que els estudiants resolguin els exercicis i els presentin amb l'objectiu de poder discutir les diverses solucions/alternatives a classe.

Mètode d'avaluació

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

C1, C2 = Controls de problemes. Cadascú qualificat entre 0 i 10.


FW = Presentació d'article (de 0 a 10) en el qual es requereix que cada participant presenti un article de recerca (prèviament assignat pel professor).
La presentació consta de:
3-5 minuts estat de l'art sobre el tema de l'article, i la motivació.
Visió general (1-3 minuts) de les idees principals del document.
10 minuts de presentació incloent la majoria dels detalls importants.
2-5 minuts de conclusions i revisió dels problemes oberts i línies de recerca que s'esmenten en l'article.

FT = Prova final (de 0 a 10) que inclou tot el contingut d'AGT.

Bibliografia

Bàsica:

Complementaria:

Capacitats prèvies

Coneixements bàsics dels mètodes d'anàlisi d'algorismes (en particular, la complexitat asimptòtica).
Coneixements bàsics en algoritmes. Programació Lineal. Flux màxim. Cerca locals. Algorismes per a problemes en grafs i xarxes.
Coneixements bàsics sobre raonament algebraic.
Coneixements bàsics sobre complexitat computacional, classes i reduccions.

Addenda

Continguts

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.

Metodologia docent

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ètode d'avaluació

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.

Pla de contingència

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.