Sulla computazione della curva di Pareto nei giochi bimatrice

Pareto efficiency property characterizes solutions for multi-objective optimization problems. Searching for solutions with this property is, in the general case, computationally intractable, even in the case of approximate solutions. Most of the results in literature provide different methodologies to find approximate solutions. Pareto efficiency plays a central role even in the Game of Theory area, because it is a required property for many solution concepts both in cooperative and noncooperative theory. To the best of our knowledege, there are no computational complexity results in literature on the problem of searching the Pareto Curve (all of the Pareto efficient points) for non-cooperative games. This document aims to provide results for 2-players normal-form games. First we provide a classification of 2 × 2 bimatrix games with respect to the geometrical characteristics of the feasible outcomes set of the game. Then we derive an exhaustive catalog of the possibile Pareto Curve shape in this game, and we provide an algorithm to calculate it exactly. Finally, using a divide et impera approach, we extend the previous result to generic bimatrix games, with an arbitrary number of actions per-player, showing that it is possible to compute exactly the Pareto Curve in a polinomial time in the number of actions of the players, and that it is formed by a number of pieces that grows at most polinomially in the number of actions.

La proprietà di Pareto efficienza caratterizza soluzioni per problemi di ottimizzazione multi-obiettivo. Ricercare soluzioni con questa proprietà è nel caso generale computazionalmente intrattabile, anche ricercando soluzioni approssimate. La maggior parte dei risultati in letteratura forniscono differenti metodologie per ricercare soluzioni approssimate. La proprietà di Pareto efficienza è centrale anche nel campo della teoria dei giochi, in quanto è richiesta in svariati concetti di soluzione sia nella teoria cooperativa che non cooperativa. Non sono noti risultati di complessità computazionale per la ricerca della Curva di Pareto (tutti i punti pareto efficienti) per giochi non cooperativi. Questo documento ha l’obiettivo di fornire risultati per giochi in forma normale a 2 giocatori. Inizialmente viene fornita una classificazione dei giochi bimatrice 2 × 2 rispetto alle caratteristiche geometriche dell’insieme dei possibili outcome del gioco. Successivamente si deriva un catalogo esaustivo della forma che la Curva di Pareto può assumere per questi giochi, e si propone un algoritmo in grado di derivarla in modo esatto. Infine, utilizzando un approccio divide et impera, si estende il risultato al caso di giochi bimatrice con un numero arbitrario di mosse, dimostrando che è possibile calcolare esattamente la Curva di Pareto in un tempo polinomiale rispetto al numero di mosse dei giocatori, e che questa è formata da un numero di pezzi che cresce, al più, polinomialmente rispetto al numero delle mosse.