Computational results for normal form coarse correlated equilibria

This works revolves around the computational complexity of the solution concept known as Coarse Correlated Equilibrium within the context of non cooperative game theory; we'll focus on optimal equilibria, which ensure the maximization of the cumulative expected utility of the players. The Coarse Correlated Equilibrium, as well as the Correlated Equilibrium, deserve attention since they are associated to stable states of game modeling situations, frequent in real life, where some kind of preplay coordination between the players is possible . Here we'll exploit a hybrid representation of the strategies of the players combining normal and sequence form in order to show how, from the constraint describing the CCE, it is possible t derive an optimization problem solvable in polynomial time. In particular, we'll show first how this is possible in the basic case of games with 2 players to analyze afterwards how linear programs and algorithms defined for the basic case can be extended to games with Nature or featuring 3 or more players. We also provide an implementation of the simplex algorithm suitable to identify solutions in practice.

Questo lavoro ha per tema la complessità computazionale del concetto di soluzione Coarse Correlated Equilibrium nel contesto della teoria dei giochi non cooperativa; ci concentreremo su equilibri ottimali, tali cioè da garantire la massimizzazione dell'utilità cumulata dei giocatori. Sia Coarse Correlated Equilibrium che Correlated Equilibrium meritano attenzione in quanto rappresentativi di una situazione di stabilità in giochi che modellino situazioni, frequenti nella realtà, dove sia possibile qualche forma di coordinamento strategico tra i giocatori prima che questi intraprendano azioni. Qui faremo uso di una rappresentazione ibrida delle strategie dei giocatori che combini forma normale e forma sequenza per mostrare come, partendo dal vincolo rappresentativo del Coarse Correlated Equilibrium, sia possibile definire un problema di ottimizzazione risolvibile in tempo polinomiale. In particolare, mostreremo dapprima come ciò sia possibile per il caso base di giochi con 2 giocatori per poi osservare come i programmi lineari e gli algoritmi definite per il caso base siano estendibili a giochi con 2 giocatori che includano Natura e a giochi con 3 o più giocatori. Proponiamo anche un'implementazione dell' algoritmo simplex adatta a identificare soluzioni nella pratica.