Teoria de Jocs Algorísmica

• Hores setmanals
• Competències
• Objectius
• Continguts
• Activitats
• Metodologia docent
• Mètode d'avaluació
• Bibliografia
• Capacitats prèvies

Professorat

Responsable

• Maria Jose Serna Iglesias ( )

Hores setmanals

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: CB6, CB9, CTR6, CEE3.1, CEE3.2, CEE3.3, CG1, CG3, CG5,

Continguts

1. Introducció a la teoria de jocs algorísmica
   Decisions centralitzades i descentralitzades. Jocs i Internet. Tipus de jocs, conceptes de solució, estratègies i equilibris. Eleccions socials.
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. Jocs ponderats de votació
   Definició i exemples. Poder i pes. Dimensió i codimensió

Activitats

Activitat Acte avaluatiu

Metodologia docent

Mètode d'avaluació

Bibliografia

Bàsica:

• Algorithmic game theory - Nisan, N. [et al.] (eds.), Cambridge University Press, 2007. ISBN: 978-0521872829
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003321009706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• An introduction to game theory - Osborne, M.J, Oxford University Press, 2009. ISBN: 9780195322484
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003942069706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Computational aspects of cooperative game theory - Chalkiadakis, G.; Elkind, E.; Wooldridge, M.J, Morgan & Claypool, 2012. ISBN: 9781608456529
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003903969706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Mathematics and politics: strategy, voting, power and proof - Taylor, A.D.; Pacelli, A.M, Springer, 2008. ISBN: 9780387776439
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003693179706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementaria:

• Handbook of computational social choice - Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; Procaccia, A.D, Cambridge University Press , 2016. ISBN: 9781107060432
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004132859706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Economics and computation : an introduction to algorithmic game theory, computational social choice, and fair division - Rothe, Jörg, Springer , [2016]. ISBN: 9783662479032
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004193409706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Capacitats prèvies