Teoria de jocs algorítmica

La Teoria de Jocs Algorímica (AGT en anglès) és l'àrea d'intersecció entre la teoria dels jocs i les ciències de la computació. Aquesta té com a objectiu la comprensió i el disseny d'algorismes en un entorn estratègic qualsevol.^[1]

Fonaments i conceptes bàsics

Equilibri de Nash

L'equilibri de Nash és un “concepte de solució” per a jocs amb dos o més jugadors el qual hem de començar assumint que cada jugador coneix la seva millor estratègia i tothom coneix les estratègies dels altres. D’aquesta manera, l'equilibri de Nash consisteix en el fet que tots els jugadors tenen les estratègies que més probabilitat tenen de guanyar.

Cal destacar que un equilibri de Nash no implica que s’aconsegueixi el millor resultat del conjunt per a tots els participants, sinó que només el millor resultat per a cadascun d'ells considerats individualment. És perfectament possible que el resultat fossi millor per a tots si els jugadors coordinessin la seva acció d'alguna manera. Tot això pot ser més fàcil d'entendre amb un exemple,^[2] es tracta del dilema del presoner. Suposem que hi ha dos presoners A i B que han comès un assalt a mà armada però la policia necessita més informació per a posar-los a la presó. Per a obtenir-ne aquesta informació, els han posat en cel·les separades per a que no es puguin comunicar entre ells i els presenten les següents condicions:

Si confessa un i l'altre presoner no, el que confessa tindrà la llibertat mentre que l'altre haurà d'estar 10 anys a la presó.
Si els dos confessen, cadascun haurà d'estar 5 anys a la presó.
Si cap dels dos confessen, cadascun estarà 1 any a la presó.

En aquest exemple, l'equilibri de Nash estaria en que ambdós confessessin ja que cap dels dos s’arriscaran a que el seu company confessi i ell no. De totes maneres, els dos preferirien estar en un altre equilibri, en el qual cap dels dos confessessin ja que només haurien d'estar 1 any cadascun a la presó i no 5. Per això, amb l'equilibri obtingut (que els dos confessin) no s’aconsegueix el millor resultat del conjunt pels dos presoners però sí que és la millor estratègia individual ja que al confessar tens la possibilitat de no haver d'estar cap any a la presó.

Teoria dels jocs

La teoria de jocs és una branca de les matemàtiques aplicades que proporciona eines per a analitzar situacions en els jugadors, prenent decisions que són interdependents. Aquesta interdependència fa que cada jugador consideri les possibles decisions o estratègies de l'altre jugador al formular l'estratègia. Una solució a un joc descriu les decisions òptimes dels jugadors, que poden tenir interessos similars, oposats o mixtos, i els resultats poden sortir d'aquestes decisions.^[3]

Història

L'aparició d'Internet ha motivat l'estudi dels fenòmens de competència i cooperació en grans xarxes, i és l'origen de la teoria de jocs algorísmics. Aquest camp és relativament recent i podem situar el seu desenvolupament als anys 2000 .

L'any 2012 el comité del Premi Gödel va reconèixer “tres articles que posen les bases del creixement en la teoria de jocs algorítmics”.^[4]

Nisan-Ronen: un nou marc per estudiar algorismes

Un dels articles reconeguts va ser el document de Nisan i Ronen escrit l'any 1999 que va encunyar el terme disseny de mecanismes algorítmics. Aquest afirma a l'abstract:

<<Considerem problemes algorítmics en un entorn distribuït on no es pot suposar que els participants segueixen l'algorisme sinó el seu propi interès. Com que aquests participants, anomenats agents, són capaços de manipular l'algoritme, el dissenyador de l'algoritme hauria d'assegurar-se amb antelació que els interessos dels agents es compleixen millor si es comporten correctament. Seguint nocions del camp del disseny de mecanismes, proposem un marc per estudiar aquests algorismes. En aquest model, la solució algorítmica està adornada amb pagaments als participants i s'anomena mecanisme. Els pagaments s'han d'escollir amb cura per motivar tots els participants a actuar com el dissenyador de l'algoritme desitja. Apliquem les eines estàndard de disseny de mecanismes a problemes algorítmics i en particular al problema del camí més curt.>>

Price of Anarchy

Els altres dos articles citats al Premi Gödel 2012 per les contribucions fonamentals a la Teoria de Jocs Algorítmics van introduir i desenvolupar el concepte de "Preu de l'anarquia". En el seu article de 1999 "Worst-case Equilibria", Koutsoupias i Papadimitriou van proposar una nova mesura de la degradació de l'eficiència del sistema a causa del comportament egoista dels seus agents (el que es coneix actualment com “preu de l'anarquia”): la relació entre l'eficiència del sistema en una configuració òptima i la seva eficiència en el pitjor equilibri de Nash. (El terme "Preu de l'anarquia" només va aparèixer un parell d'anys després).

Internet com a catalitzador

Un altre factor clau en el desenvolupament de la teoria de jocs algorítmics és Internet. Internet va crear una nova economia, tant com a base per a l'intercanvi i el comerç, com per drets propis. La naturalesa computacional d'Internet va permetre l'ús d'eines computacionals en aquesta nova economia emergent. D'altra banda, el mateix Internet és el resultat d'accions de molts individus. Això va causar un nou enfocament envers l'enfocament clàssic de la computació que s’havia mantingut fins aleshores. Així, la teoria de jocs és una manera natural de veure Internet i les interaccions que hi ha al seu interior, tant humanes com mecàniques.

La teoria de jocs estudia els equilibris (com l'equilibri de Nash). Un equilibri es defineix generalment com un estat en què cap jugador té un incentiu per canviar la seva estratègia. Els equilibris es troben en diversos camps relacionats amb Internet, per exemple, les interaccions financeres i l'equilibri de càrrega de comunicació. La teoria de jocs proporciona eines per analitzar els equilibris, i un enfocament comú és llavors "trobar el joc", és a dir, formalitzar les interaccions específiques d'Internet com a joc i derivar els equilibris associats.

Reformular els problemes en termes de jocs permet l'anàlisi de les interaccions basades en Internet i la construcció de mecanismes per satisfer demandes específiques. Si es pot demostrar que existeix un equilibri, s'ha de respondre una altra pregunta: es pot trobar un equilibri, i en un temps raonable? Això condueix a l'anàlisi d'algorismes per trobar equilibris.

Àrees de Recerca

La Teoria de Jocs Algorítmica es divideix en dues vessants de coneixement que s’enfoquen en la seva respectiva etapa en el procés de creació d'un joc:

Anàlisi: donat un algorisme ja implementat, analitzar-lo utilitzant eines pertanyents a la Teoria de Jocs com, per exemple: calculant i demostrant propietats de l'Equilibri de Nash, el preu de l'anarquia o les dinàmiques de millor resposta.
Disseny: disseny de jocs amb bones propietats algorítmiques i teòriques del joc. En concret, aquesta àrea rep el nom de disseny de mecanismes algorítmics.

Aquesta àrea conta amb aplicacions pràctiques tan diveres com: l'estudi de les criptomonedes, el proveïment participatiu i economia col·laborativa.^[5] On destaquen els dos sectors següents:

Ineficiència de l'equilibri

Estudia el lligam entre el preu de l'anarquia i el preu de l'estabilitat. Aquest concepte va ser introduït per a representar la pèrdua de rendiment d'un sistema a causa dels comportaments egoístes dels participants.

Eleccions socials computacionals

Anàlisis de problemes que es formen en agregar preferències a un grup d'agents d'un sistema qualsevol des d'un punt de vista computacional. Particularment, se centra en la computació eficient dels resultats en sistemes electorals, tenint en compte la complexitat de les diverses formes de manipulació de vots útils i dificultats de representació en una configuració combinatòria.

Exemples d'algoritmes de joc

A*

L'a* (Hart, 1968) és un algoritme de cerca heurística que s’utilitza per a jocs unipersonals. Aquest algorisme expandeix primer els camins que van de l'estat inicial a l'estat final que estima com a òptims segons la funció f(n) = g(n) + h(n), on g(n) és la funció que calcula el cost acumulat fins al node “n”, i h(n) és la funció que calcula l'estimació del cost per arribar a l'objectiu des del node “n”.

L'algoritme té la forma següent:

def Cerca_A (NodeArrel, NodeObjectiu):
	Llista = [[NodeArrel]]
	while (Cap(Cap(Llista)) != NodeObjectiu o bé len(Llista) != 0):
		C = Cap(Llista)
 E = Expandir(C)
 E = Eliminar_Cicles(E)
 Llista = Inserció_ordenada_f (E, Cua(Llista))
 if (Llista != “buida”):
 return Cap(Llista)
 else:
 return print(“No existeix solució”)

on trobem les següents funcions:

Cap (L): retorna el primer element de la llista “L”
Expandir (N): retorna la llista dels camins resultants d'expandir el node de més profunditat del camí “N”
Eliminar_Cicles (C): retorna els camins de la llista “C” que no tenen cicles
Inserció_ordenada_f (E, L): insereix els elements de la llista “E” a la llista “L” de manera que els camins queden ordenats de menor a major segons el valor de la funció f(n).
len(L): retorna la longitud de la llista L.

MiniMax

El MiniMax és l'algoritme més conegut i utilitzat per jocs on hi ha dos jugadors que juguen alternativament un i altre jugador amb informació perfecta. Cada jugador escolleixi fer el millor moviment, suposant que el contrincant escollirà un moviment que el pugui perjudicar. Per veure quins són els possibles moviments a fer en cada torn, l'algorisme realitza un arbre de cerca amb tots els possibles moviments a partir de l'estat actual del joc.

L'arbre de joc té una profunditat màxima prefixada per explorar el conjunt de jugades, ja que no es pot fer una exploració exhaustiva de totes les jugades. Això limitarà el que veiem de l'espai de cerca, cosa que pot provocar que realitzem unes jugades que a la llarga siguin dolentes. Per tant, com més gran sigui millors seran les jugades, però a la vegada tindrem més costos.

Llavors l'algorisme del MiniMax s’executa cada vegada que sigui el torn d'un jugador, ja que així se li mostrarà quin és el millor moviment a fer. Com ja hem dit, el primer que fa l'algorisme és generar l'arbre de solucions complet fins a la profunditat màxima a partir de l'estat actual del joc. Llavors es calculen els valors de la funció per a cada node terminal (les fulles dels arbres). El que fa l'algorisme és anar calculant el valor dels nodes superiors a partir dels valors dels nodes inferiors. Alternativament s’elegiran els valors mínims en els nivells on es correspondria a moviments del jugador oponent, i els valors màxims quan corresponguin a moviments del jugador al que li toca moure de veritat (d'aquí el nom MiniMax). Finalment el jugador actual escull la jugada valorant els valors que han arribat al nivell superior.

A continuació hi ha un exemple de què faria l'algorisme del MiniMax en el joc del tres en ratlla a partir de l'estat del joc que s’indica a continuació si sabem que li toca jugar al jugador de les X’s, l'arbre té una profunditat màxima de 3 i la funció dona el valor 1 si en el node guanya el jugador de les X’s, 0 si hi ha empat i -1 si perd el jugador de les O’s.

Per tant, veiem que la millor jugada que pot fer el jugador actual és posar una X a la casella de baix a l'esquerra.

Referències

↑ Vitter, Jeffrey Scott. Proceedings of the thirty-first annual ACM symposium on Theory of computing.. New York, NY: ACM, 1999. ISBN 1-58113-067-8.
↑ «Equilibri de Nash».
↑ «Two-person constant-sum games; Britannica».
↑ «ACM SIGACT Presents Gödel Prize for Research that Illuminated Effects of Selfish Internet Use — Association for Computing Machinery», 18-07-2013. Arxivat de l'original el 2013-07-18. [Consulta: 11 gener 2022].
↑ Roughgarden, Tim. Vint lliçons sobre la teoria de jocs algorítmica. Cambridge University Press, 2016. ISBN 9781316624791.

[1] Vitter, Jeffrey Scott. Proceedings of the thirty-first annual ACM symposium on Theory of computing.. New York, NY: ACM, 1999. ISBN 1-58113-067-8.

[2] «Equilibri de Nash».

[3] «Two-person constant-sum games; Britannica».

[4] «ACM SIGACT Presents Gödel Prize for Research that Illuminated Effects of Selfish Internet Use — Association for Computing Machinery», 18-07-2013. Arxivat de l'original el 2013-07-18. [Consulta: 11 gener 2022].

[5] Roughgarden, Tim. Vint lliçons sobre la teoria de jocs algorítmica. Cambridge University Press, 2016. ISBN 9781316624791.

[1]

[2]

[3]

[4]

[5]