• Regret
• mu-calculus
• Modal Logic
• Iterated regret minimization algorithm
• Game Theory
• Dynamic Epistemic Logic
• Traveler's Dilemma

(For english, see below)
L’equilibrio di Nash non è sempre la migliore soluzione concettuale per descrivere un gioco strategico.
Il Dilemma del Viaggiatore ne è un esempio: una compagnia aerea perde le valigie di due viaggiatori, il cui valore è il medesimo. Un manager della compagnia è disposto a rimborsare a ciascuno dei viaggiatori una cifra compresa tra 2$ e 100$. Il manager chiede ai due viaggiatori di valutare il bagaglio perduto senza dar loro la possibilità di confrontarsi; i viaggiatori saranno rimborsati per il valore più basso assegnato tra i due, inoltre il viaggiatore che ha assegnato il valore più alto alla sua valigia, si vedrà decurtare altri 2$ che verranno assegnati all’altro viaggiatore.
L’unico equilibrio di Nash in questo gioco è il profilo strategico (2,2), ma risultati sperimentali (Becker, Carter et al. 2005) hanno mostrato che la soluzione del gioco è il profilo strategico (97,97).
Il concetto di rimorso influenza le decisioni che prendiamo ed, in una certa misura, ci aiuta a “razionalizzare” le emozioni. In Teoria dei Giochi viene definito rimorso del giocatore i in un profilo strategico s la differenza tra la best response e la strategia s_i. Il rimorso di una strategia a Re_i(a) del giocatore i è il massimo rimorso di tutti i profili strategici la cui i-esima strategia è a. Diciamo che per il giocatore i la strategia a domina debolmente la strategia b se Re(a)<Re(b).
Halpern e Pass nel loro articolo (2012) introducono l’algoritmo Iterated Regret Minimization (IRM): ad ogni iterazione l’IRM cancella le strategie debolmente dominate. Gli autori hanno dimostrato che applicando l’IRM al Dilemma del Viaggiatore la soluzione ottenuta è il profilo strategico (97,97).
Nello stesso articolo Halpern e Pass forniscono una caratterizzazione epistemica dell’IRM basata sull’assunzione di common knowledge of rationality (conoscenza comune di razionalità). Ma gli autori hanno avuto difficoltà nel costruire un modello che tenga traccia di un cambiamento nelle informazioni possedute dai due giocatori. Ad esempio, se uno dei due giocatori sa che l’avversario gioca la strategia 97, allora dovrebbe scegliere la strategia 96, non 97.
Nella mia tesi fornisco un modello che riesce a risolvere questo problema.
L’Epistemologia è lo studio della conoscenza; fin dai tempi dell’antica Grecia si usava la Logica per avere una visione più ricca e chiara dell’investigazione epistemologica. In tempi più recenti i modelli di Kripke costituiscono, nella maggior parte dei casi, la base logico-matematica più diffusa per descrivere le intuizioni dell’Epistemologia.
Teorici dei giochi quali Brandeburger (1991) e Board (2004), tra gli altri, hanno contribuito alla creazione di modelli lessicografici per descrivere il Belief (o credenza) dei giocatori. Su questa traccia, Baltag e Smets (2006) hanno proposto dei modelli (di Kripke) di plausibilità, che sono forniti di ordini lessicografici sensibili ad un cambiamento delle informazioni.
Grazie a questo modello, vedremo una proposta di soluzione al problema sopra citato. Nello specifico, viene fornita una caratterizzazione dell’IRM attraverso il radical upgrade, che è un operatore della Logica Proposizionale Dinamica spesso usato per descrivere un cambiamento delle informazioni. Inoltre diamo una definizione proposizionale di razionalità del rimorso nel linguaggio della Logica Dinamica Epistemica.
Per esempio, se l’informazione che il giocatore 2 pensa di voler giocare 97 è conoscenza comune tra i giocatori, a seguito di un punto fisso ottenuto tramite un’iterazione di radical upgrade di razionalità del rimorso, allora sarà ugualmente una credenza comune il fatto che anche il giocatore 1 gioca 97. In questo caso la credenza comune che entrambi i giocatori pensano di giocare 97 è il risultato della procedura di plausibilità dell’IRM, ed in questo modo entrambi i giocatori continuano a voler scegliere 97.
D’altra parte, se il giocatore 1, prima di implementare l’IRM, viene a sapere (correttamente) che il giocatore 2 vuole giocare la strategia 97, allora è ragionevole che il giocatore 1 scelga di giocare 96, e anche questo fenomeno è correttamente descritto dalla caratterizzazione di plausibilità dell’IRM.
Infine, oggigiorno il µ-calcolo è il linguaggio più studiato per descrivere gli automi e ha forti legami con la Logica Modale. Nella tesi viene anche fornita una caratterizzazione dell’algoritmo IRM attraverso il linguaggio del µ-calcolo modale.
La struttura della tesi è la seguente:
Capitolo 1: presento un’introduzione essenziale della Logica Modale; definisco la logica modale normale minimale K e introduco il concetto chiave di bisimulazione. Dopodiché studio la decidibilità e la complessità di alcuni problemi classici. Infine enuncio il Teorema di van Benthem che dimostra che la Logica Modale è il frammento della Logica del Primo Ordine invariante per bisimulazione.
Capitolo 2: introduco il modello di plausibilità di Baltag e Smets e ne mostro la completa assiomatizzazione. Poi introduco la Logica Proposizionale Dinamica che mi permette di definire operatori come il radical upgrade, che sarà cruciale nell’ultimo capitolo. Concludo il capitolo presentando un teorema chiave di Baltag e Smets sul punto fisso di un iterated radical upgrade, questo risultato sarà utile per il teorema centrale dell’ultimo capitolo.
Capitolo 3: presento alcuni elementi essenziali della Teoria dei Giochi: l’equilibrio di Nash e il Teorema di Nash. Inoltre presento un’osservazione circa i legami tra la Logica e la Teoria dei Giochi: vi è la logica dei giochi e vi è la Logica in forma di giochi. La Logica in forma di giochi è lo studio della Logica che usa idee proprie della Teoria dei Giochi, ad esempio i giochi di valutazione. La logica dei giochi è lo studio della Teoria dei Giochi per mezzo della Logica (l’argomento dell’ultimo capitolo della tesi).
Capitolo 4: introduco brevemente il µ-calcolo modale e ne dò la semantica usando un gioco di valutazione.
Capitolo 5: nell’ultimo capitolo propongo il modello di gioco di plausibilità e una definizione in forma proposizionale della razionalità del rimorso che userò per caratterizzare l’IRM. Presento anche i teoremi che dimostrano:
1) L’esistenza, in ogni modello di gioco di plausibilità, di profili strategici che soddisfano la definizione proposizionale della razionalità del rimorso.
2) Il fatto che i modelli di gioco di plausibilità soddisfano la proprietà Positive introspection of Belief di razionalità del rimorso.
3) La correttezza della caratterizzazione tramite i radical upgrade dell’algoritmo IRM.
Dopodiché applico la nuova caratterizzazione dell’IRM al Dilemma del Viaggiatore e mostro che il modello di gioco di plausibilità è in grado di fornire una soluzione al sopracitato problema di informazione.
Infine presento un teorema che introduce una formula del µ-calcolo modale che caratterizza l’IRM.
L’ultima sezione riguarda le ipotesi di lavoro futuro.

English version:
Nash equilibrium is not always the best solution concept for describing a strategic game.
The Traveler's Dilemma is an example of such a game: an air company looses two travelers' suitcases, whose value is identical. A manager of the company estimates the value of the two suitcases between 2$ and 100$. The manager asks the two travelers to assign a value to the suitcase without consulting each other; they will be refunded the lowest value assigned between the two, and 2$ will be taken from the refund of the player who gave the higher value and will be given to the opponent.
The only Nash equilibrium of the game is the strategy profile (2,2), but experimental results (Becker, 2005) showed that the game solution is the strategy profile (97,97).
Regret has a strong influence on the decisions that we take and brings us to rationalize emotions to some extent. In Game Theory the regret re_a (s) of a player a associated to the strategy profile s=(s_a,s_{-a}) is the difference between the best response of player a to s_{-a} and s_a. We say that strategy s_a is regret-dominated by strategy s_a' if Re_a(s_a')<Re_a(s_a), where Re_a(s_a) is the maximum regret of all the strategy profiles whose a-th strategy is s_a.
In their paper (2012) Halpern and Pass introduced the Iterated Regret Minimization (IRM) Algorithm: at each round IRM deletes regret-dominated strategies. After one iteration of the IRM only the strategies 100-96 survive for both players, after a second iteration the only strategy profile that survives is (97,97)!
In their paper, Halpern and Pass also provide an epistemic characterization of the IRM based on the assumption of common knowledge of rationality. But they found a difficulty in giving a model that would keep track of a change in information, i.e. if one of the two players comes to know that the opponent is playing strategy 97, then she should play 96, not 97.
In this thesis we attempt to provide a solution to this problem.
Epistemology is the study of knowledge, since the times of ancient Greece, Logic was used to obtain a clearer and richer view of epistemological investigation. In more recent times Kripke models made a breakthrough in the description of most accredited Epistemological theories.
Game theorists like Brandeburger (1991) and Board (2004), among the others, provided lexicographic models to describe the Belief of the players. On this path Baltag and Smets (2006) proposed a (Kripke) plausibility model provided with lexicographic orders, which is susceptible to change in information.
Thanks to this model we will see a solution proposal to the aforementioned problem.
In particular, it is provided a plausibility characterization of the IRM through the radical upgrade, which is a Propositional Dynamic Logic operator used to describe a change in information.
For example, if the information that player 2 is believed to play 97 is obtained from the fixed-point of iterated radical upgrade of rationality, then it is also common belief that player 1 is playing 97 too. In this case the common belief that both players are playing 97 is the result of the IRM plausibility procedure, still, through this method, the two players choose to play 97.
On the other side if player 1, before implementing IRM, correctly comes to believe that player 2 is playing strategy 97, then it is reasonable that player 1 should play 96, and this fact is also correctly described by the IRM plausibility characterization.
Furthermore, nowadays, mu-calculus is the most studied language for describing automata and it has strong links to Modal Logic. We will also see a characterization of the IRM algorithm in the modal mu-calculus.
The structure of the thesis is as follows:
Chapter 1: it is given an essential introduction to Modal Logic, then it is defined the minimal normal modal logic K, it is introduced the key concept of bisimulation, we study the construction of the canonical model (a method to study completeness of normal modal logics), we study decidability and the complexity classes of some classical problems. In the end we state van Benthem Theorem which proves that Modal Logic is the First Order Logic fragment which is invariant under bisimulation.
Chapter 2: we introduce Baltag and Smets' plausibility models and see their complete axiomatization; then we introduce the Propositional Dynamic Logic which let us define model operators like radical upgrade which will be crucial in the last chapter. We conclude the chapter by proving a key theorem by Baltag and Smets about fixed-points of iterated radical upgrade, this result will be useful in the last chapter.
Chapter 3: we present some essentials of Game Theory: Nash Equilibrium, Nash Theorem. Then we present a key observation linking Logic to Game Theory: there is logic as games and there is logic of games. The first one is about using Game Theory to have a deeper comprehension of Logic (for instance we will see the valuation game), the second one is the use of Logic to understand and describe the structures and concepts of Game Theory (this will be the main topic of the last chapter).
Chapter 4: we briefly introduce the modal mu-calculus and provide its semantics by means of an evaluation game.
Chapter 5: in this last chapter we see the proposed plausibility game model and we will also see a propositional definition of regret-rationality that we will use to characterize the IRM. We present some theorems stating:
1) The existence, in any plausibility game model, of strategy profiles that satisfy the propositional definition of regret-rationality.
2) The fact that the plausibility game model satisfies Positive introspection of Belief of regret-rationality.
3) The correctness of the plausibility characterization of the IRM.
Then we will apply our IRM plausibility characterization to the Traveler's Dilemma and we see how our plausibility game model is able to provide a solution to the information problem.
Finally we present a theorem introducing a modal mu-calculus formula which characterizes the IRM.
The last section is about further work.