Para auxiliar os gestores das organizações em seu processo decisório, o emprego de métodos de apoio à tomada de decisão é utilizado desde o século passado, a partir da década de 1950, havendo forte ênfase nas questões econômico-financeiras e operacionais das alternativas. Atualmente, o uso de métodos que consideram as questões relativas à sustentabilidade ambiental das alternativas é um assunto que tem despertado interesse, conforme se observa na literatura recente, ainda que relativamente escassa. Contudo, a práxis da maioria dos métodos multicritério existentes tem embasamento no tomador de decisão como um indivíduo ao invés de um grupo e a ampla diferença entre o comportamento de um indivíduo e de um grupo é negligenciado. Neste novo tipo de abordagem, soluções para resolver os conflitos que inevitavelmente surgem da necessidade de atender os diferentes critérios dos agentes envolvidos devem ser propostas. Para estes casos, a Teoria dos Jogos é reconhecidamente uma abordagem que permite a resolução de conflitos por meio da avaliação de diferentes cenários com diferentes alternativas. Neste sentido, a presente pesquisa apresenta um método multicriterial, baseado em indicadores de sustentabilidade em conjunto com a Teoria dos Jogos e o equilíbrio de Nash, para que seja uma das ferramentas de apoio na escolha do sistema de tratamento de esgoto sanitário para municípios. Para tornar possível a metodologia proposta, indicadores de sustentabilidade foram selecionados para serem usados como critérios na avaliação de alternativas de sistema de tratamento de esgoto. Além disto, vetores de pesos para os critérios foram definidos para representar perfis de jogadores. A partir disto, foi proposta uma função de pagamentos e um exemplo foi gerado a partir da definição do jogo e seus jogadores, tendo sido o software Gambit utilizado para encontrar o equilíbrio de Nash do jogo. Como resultado, a aplicação da metodologia proposta permite tratar o processo de escolha de ETE como um processo de escolha em grupo, ao invés de uma escolha individual, e visa contribuir para quebrar o paradigma da busca pela eficiência baseada nos critérios formados pelo binômio técnico e econômico na escolha de sistemas de tratamento de esgoto. Desta forma, a aplicação do novo método visa proporcionar meios para se enxergar o mesmo problema sobre diferentes focos e, com a utilização de diferentes critérios, poderia facilitar o processo da tomada de decisão para a escolha da alternativa técnica, econômica, ambiental e socialmente mais adequada. / To assist the managers of organizations in their decision making, the use of methods to support the decision are used since the last century, from the 1950s, with a strong emphasis on economic issues, financial and operational details of the treatment plants sewage. Currently, the use of methods to consider issues relating to the environmental sustainability of wastewater treatment plants is a subject that has attracted attention, as shown in recent studies, although relatively scarce. However, the practice of most existing methods are based on multicriteria decision-maker as an individual instead of a group and the wide difference between the behavior of an individual and a group is neglected. In this new approach, solutions to resolve the conflicts that inevitably arise from the need to meet the various criteria of the parties involved must be proposed. For these cases, game theory is admittedly an approach that allows the resolution of conflicts through the evaluation of different scenarios with different alternatives. With this research we sought to develop a measurement methodology based on indicators of sustainability in conjunction with game theory and Nash equilibrium, that is one of tools to support the choice of system of sewage treatment for a particular municipality . For the proposed new methodology, sustainability indicators were selected to be used as criteria in the evaluation of alternative system of sewage treatment and weight vectors for the criteria were defined as profiles of players. From this, we choose a function of reward and an example was generated from the definition of the game and its players, the software Gambit was used to find the Nash equilibrium of the game. The proposed methodology allows us to treat the process of choosing ETE as a selection process in group, rather than an individual choice, and aims to deconstruct the paradigm of the quest for efficiency based on criteria formed the duo in the technical and economic choice of systems for wastewater treatment. Thus, applying the new method aims at providing means to see the same problem on different sides, and with the use of different criteria, could facilitate the process of decision making for the choice of alternative technical, economic, environmental and socially suitable.

Orientador: Prof. Dr. Sinuê Dayan Barbero Lodovici / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional - PROFMAT, 2014. / Os jogos encantam a humanidade desde os tempos mais remotos. Especialmente, os jogos abstratos (ou matemáticos) atraíram a atenção de matemáticos ilustres como Bernoulli, dentre tantos. E esta atração deu origem a novas áreas da matemática, em destaque, surgiu também a Teoria dos Jogos. Esta teoria trás a beleza de transformar interações humanas em jogos, modelando fenômenos que podem ser observados quando dois ou mais "agentes de decisão" interagem entre si com conflitos e/ou cooperação. O estudo da Teoria dos Jogos utiliza recursos da modelagem matemática equacionando diferentes situações de diferentes campos de estudo e é esta característica interdisciplinar que inspirou este trabalho. A Teoria dos Jogos vem sendo utilizada em várias áreas, como economia, biologia, sociologia, etc. Neste trabalho pretende-se passar as noções básicas da Teoria dos Jogos para professores do ensino básico como uma possível ferramenta para fomentar entre os educandos o interesse pela matemática aplicada além deles serem beneficiados pelo desenvolvimento do pensamento estratégico, da atenção, raciocínio lógico, planejamento de ação e sequenciamento, habilidades muito úteis na competência de resolver problemas. Almeja-se que aconteça a construção do conhecimento dos alunos de uma forma mais atraente / The games enchanted mankind since ancient times. Especially, abstract games (or mathematical) attracted the attention of illustrious mathematicians like Bernoulli, among many. And this attraction gave rise to new areas of mathematics, highlighted, also appeared to Game Theory. The theory behind the beauty of transforming human interactions in games, modeling phenomena that can be observed when two or more "decision-makers" interact with conflict and / or cooperation. The study of Game¿s Theory uses mathematical modeling resources equating different situations of different fields of study and this interdisciplinary characteristic that inspired this work. The Game¿s Theory has been used in various areas, such as economics, biology, sociology, etc. This paper intends spending the basics of Game¿s Theory to elementary school teachers as a possible tool to foster among the students, the interest in applied mathematics and these be benefited by the development of strategic thinking, attention, logical reasoning, planning action and sequencing, very useful skills in problemsolving competence. It¿s desire to happen the construction of students¿ knowledge in a more attractive way.

Les défis auxquels sont confrontés les différents secteurs de l’économie, répondent à l'évolution et à la spécialisation des consommateurs et des producteurs, dont les besoins sont de plus en plus complexes. À cet égard, au cours des 5 dernières années, les marchés de l'électricité ont subi un processus évolutif qui vise à répondre aux besoins de tous les intervenants dans des scénarios de développement durable.Aussi les agents impliqués dans les marchés de l'électricité, exposés à des risques opérationnels, juridiques, éthiques, financiers, entre autres, doivent‐ils se spécialiser pour s'approprier notamment de nouvelles technologies. Cette recherche porte principalement sur l'étude du risque financier tout à s'attachant à prendre en compte les nombreuses spécificités des marchés de l'électricité dans le but d'assurer le bon fonctionnement du marché et de ses participants.Dans les développements antérieurs, certains modèles se sont concentrés sur les phénomènes de pannes de courant électrique, d'instabilité du réseau, de variations de puissance, de réseaux intelligents, entre autres. D'autres études ont abordé la question de la prédiction de variables comme le prix et la stratégie d'entreprise, dans le but d'accroître les profits des participants. Ce projet de thèse propose un modèle financier complexe, qui se traduit par le calcul d'un équilibre de marché à partir des conditions initiales et des contraintes de risque. En utilisant la théorie des jeux, nous expliquons l'instabilité de l’équilibre. Nous montrons, en dépit de la complexité, qu'il est possible de trouver un scénario optimal en termes de rentabilité pour le système et les agents.Ce travail est structuré de la façon suivante. Dans le premier chapitre, une revue des études antérieures est présentée afin d’établir le contexte de la recherche. Le chapitre 2 décrit le marché de l'électricité colombienne avec ses particularités. Dans le chapitre 3, les indicateurs de risque (KRI) sont définis. Ils constitueront une partie fondamentale du modèle complet présenté dans le chapitre 4. Enfin, le chapitre 5, d'une part, présente les résultats obtenus et, d'autre part, discute de différentes voies d'approfondissement. / The challenges faced by different sectors of the economy, respond to the evolution and specialization of consumers and producers, where the needs are becoming more complex. In this sense, during the last 5 years the electricity markets have undergone an evolutionary pro- cess that aims to meet the needs of all stakeholders in the midst of sustainability scenarios.Thus, the agents involved in the electricity market, present a num- ber of exhibitions of operational nature, legal, ethical, financial, among others, which require a specialization allowing the entry of new tech- nologies. This research project focuses on the study of financial risk, which despite being so specific, consider many elements with the aim of ensuring the functioning of the market and its participants.In previous studies, some models have concentrated on the in- vestigation of blackouts phenomena, the stability of the network, the dynamic power system, and Smart grids, among others. Mean- while other investigations have addressed the problem of forecasting different variables like the spot price and corporate strategy, with the aim of increasing the profitability of the participants. Now, this project presents the proposal of a complex financial model, which results in calculating a market equilibrium considering initial condi- tions and risk constraints. Using game theory it demonstrates equi- librium instability and that through complexity it is possible to find an optimal scenario in terms of profitability for the system and the agents.In chapter 1 it carried out a review of previous studies in order to justify the investigation, then Chapter 2 includes a description of the Colombian electricity market, with different specifications. In chap- ter 3 the KRI are defined, and they will be integrated in Chapter 4 as a fundamental part of the comprehensive model. Finally, Chapter 5 includes the results of the study ending with some possible further studies and additional considerations.

Esta dissertação aborda a teoria dos jogos diferenciais em sua estreita relação com a teoria das equações de Hamilton-Jacobi (HJ). Inicialmente, uma revisão da noção de solução em teoria dos jogos é empreendida. Discutem-se nesta ocasião as idéias de equilíbrio de Nash e alguns de seus refinamentos. Em seguida, tem lugar uma introdução à teoria dos jogos diferenciais, onde noções de solução como a função de valor de Isaacs e de Friedman são discutidas. É nesta altura do trabalho que fica evidente a conexão entre este conceito de solução e a teoria das equações de Hamilton-Jacobi. Por ocasião desta conexão, é explorada a noção de solução clássica e é exposta uma demonstração do fato de que se um jogo diferencial possuir uma função de valor pelo menos continuamente diferenciável, esta será uma solução da equação de Hamilton-Jacobi associada ao jogo. Este resultado faz uso do princípio da programação dinâmica, devido a Bellman, e cuja demonstração está presente no texto. No entanto, quando a função de valor do jogo é apenas contínua, então embora esta não seja uma solução clássica da equação HJ associada a jogo, vemos que ela será uma solução viscosa, ou solução no sentido da viscosidade - e a esta altura são discutidos os elementos e propriedades desta classe de soluções, um teorema de existência e unicidade e alguns exemplos. Por fim, retomamos o estudo dos jogos diferenciais à luz das soluções viscosas da equação de Hamilton-Jacobi e, assim, expomos uma demonstração de existência da função de valor e do princípio da programação dinâmica a partir das noções da viscosidade / This dissertation aims to address the topic of Differential Game Theory in its connection with the Hamilton-Jacobi (HJ) equations framework. Firstly we introduce the idea of solution for a game, through the discussion of Nash equilibria and its refinements. Secondly, the solution concept is then translated to the context of Differential Games and the idea of value function is introduced in its Isaacs\'s as well as Friedman\'s version. As the value function is discussed, its relationship with the Hamilton-Jacobi equations theory becomes self-evident. Due to such relation, we investigate the HJ equation from two distinct points of view. First of all, we discuss a statement according to which if a differential game has a continuously differentiable value function, then such function is a classical solution of the HJ equation associated to the game. This result strongly relies on Bellman\'s Dynamic Programming Principle - and this is the reason why we devote an entire chapter to this theme. Furthermore, HJ is still at our sight from the PDE point of view. Our motivation is simple: under some lack of regularity - a value function which is continuous, but not continuously differentiable - a game may still have a value function represented as a solution of the associated HJ equation. In this case such a solution will be called a solution in the viscosity sense. We then discuss the properties of viscosity solutions as well as provide an existence and uniqueness theorem. Finally we turn our attention back to the theory of games and - through the notion of viscosity - establish the existence and uniqueness of value functions for a differential game within viscosity solution theory.

Cette thèse propose d'étudier la robustesse des commandes issues de la théorie des jeux adaptée aux systèmes multientrées, multiobjectifs. De façon générale les stratégies avec une structure d'information en boucle ouverte présentent des propriétés faibles de robustesse et ne peuvent être déterminées qu'a posteriori. Des exemples exhibent certaines limites. Les stratégies avec une structure d'information en boucle fermée sont beaucoup plus ardues à déterminer. Dans le cas d'une stratégie de Nash, un nouvel algorithme utilisant le manque de confiance est présenté pour résoudre les équations couplées algébriques de type Riccati. Pour une stratégie de Stackelberg avec une structure d'information en boucle fermée les conditions nécessaires et suffisantes sont déterminées et appliquées au problème de commande mixte H2 / Hinf. Enfin une extension à des systèmes comportant des incertitudes paramétrées mène à la résolution itérative d'une association non convexe de problèmes d'optimisation.

Η παρούσα διπλωματική εργασία πραγματεύεται την θεωρία παιγνίων και το πώς αυτή εφαρμόζεται στην οικονομική επιστήμη. Συγκεκριμένα, στόχος μας είναι να απαντήσουμε στο ερώτημα: «Πως αποφασίζονται οι τελικές στρατηγικές που θα επικρατήσουν σε ένα παίγνιο με την πάροδο του χρόνου;». Η εργασία είναι χωρισμένη σε δύο μέρη. Αρχικά αναφερόμαστε στην κλασσική θεωρία παιγνίων και αναλύουμε τα βασικά της στοιχεία και στη συνέχεια περνάμε στην ανάλυση της εξελικτικής θεωρίας παιγνίων. Στο 1ο μέρος της παρούσας εργασίας, λοιπόν, αναφέρουμε τα όσα είναι σχετικά με την κλασσικά θεωρία παιγνίων. Συγκεκριμένα, στο πρώτο κεφάλαιο γίνεται μία σύντομη ιστορική αναδρομή της θεωρίας αυτής και στο δεύτερο κεφάλαιο την ορίζουμε ως την επίσημη μελέτη που εξετάζει την ορθολογικότητα σε ένα επιχειρηματικό περιβάλλον και παρουσιάζουμε τα βασικά στοιχεία ενός παιγνίου. Αναφέρουμε τα δύο επίπεδα περιγραφής των παιγνίων, δηλαδή τα παίγνια συνεργασίας και μη-συνεργασίας, καθώς και τους δύο τρόπους αναπαράστασής τους που είναι η στρατηγική ή αλλιώς κανονική μορφή (μήτρες) και η εκτεταμένη ή αλλιώς αναλυτική μορφή (δέντρα παιγνίων). Στο τρίτο κεφάλαιο ορίζονται οι κυρίαρχες στρατηγικές και η αντίστοιχη ισορροπία κυρίαρχης στρατηγικής και στο τέταρτο κεφάλαιο ορίζεται η Ισορροπία Nash, η οποία αποτελεί τη στάνταρ έννοια της ισορροπίας στα οικονομικά. Στα δύο αυτά κεφάλαια (3 και 4) υπάρχουν παραδείγματα εφαρμογής που στοχεύουν στην καλύτερη κατανόηση, και αναλύεται και το Δίλημμα του Φυλακισμένου που αποτελεί το πιο κλασσικό παράδειγμα στη θεωρία παιγνίων. Στην περίπτωση, τώρα, όπου δεν υπάρχει Ισορροπία Nash (κάτι το οποίο συμβαίνει σε παίγνια στρατηγικής μορφής) το παίγνιο λύνεται με τη βοήθεια των μικτών στρατηγικών οι οποίες αναλύονται στο πέμπτο κεφάλαιο. Συνεχίζουμε με το έκτο κεφάλαιο, όπου παρουσιάζονται τα εκτεταμένα παίγνια πλήρους πληροφόρησης και αναλύεται η μέθοδος της προς τα πίσω επαγωγής (αναδίπλωση). Στο έβδομο κεφάλαιο παρουσιάζονται τα παίγνια ελλιπούς πληροφόρησης και στο όγδοο κεφάλαιο αναφέρονται τα παίγνια μηδενικού αθροίσματος (π.χ. σκάκι) και το πώς μπορούν να χρησιμοποιηθούν μαζί με τους τυχαιοποιημένους αλγόριθμους για την ανάλυση προβλημάτων στον απευθείας σύνδεσης υπολογισμό. Το 1ο μέρος κλείνει με ένα παράδειγμα εφαρμογής της θεωρίας παιγνίων, τις δημοπρασίες. Τι γίνεται όμως όταν ένα παίγνιο επαναλαμβάνεται και παίζεται περισσότερες από μία φορές; Το ερώτημα αυτό έρχεται να μας το απαντήσει η εξελικτική θεωρία παιγνίων στο 2ο μέρος της παρούσας διπλωματικής εργασίας. Στα δύο πρώτα κεφάλαια, του μέρους αυτού, ορίζονται τα εξελικτικά παίγνια, γίνεται αναφορά για το που μπορούν να βρουν εφαρμογή καθώς και στους λόγους που δεν είναι ακόμη γνωστές οι οικονομικές εφαρμογές τους. Το τρίτο και το πέμπτο κεφάλαιο αποτελούν τα πιο σημαντικά κεφάλαιο του 2ου μέρους. Στο τρίτο κεφάλαιο παρουσιάζεται αναλυτικά το μοντέλο των εξελικτικών παιγνίων και τα στοιχεία που το αποτελούν (αναμενόμενες ανταμοιβές, πληθυσμός, καταστάσεις). Περιγράφεται το στάδιο παιγνίου το οποίο ορίζεται από μία συνάρτηση καταλληλότητας και δίνεται έμφαση στις δύο γραμμικές προδιαγραφές που έχουν οι συναρτήσεις αυτές. Στη συνέχεια, αναλύεται πλήρως το πιο αντιπροσωπευτικό παράδειγμα της εξελικτικής θεωρίας παιγνίων, το παίγνιο Hawk-Dove, που αποτελεί ένα γενικό μοντέλο καταστάσεων με επιθετικές και αμυντικές αγορές. Το παίγνιο αυτό έχει δύο ειδών παίκτες, αυτοί που επιλέγουν να είναι επιθετικοί (Hawk) και αυτοί που επιλέγουν να είναι αμυντικοί (Dove), και ερευνάται το ποιο είδος παικτών θα επικρατήσει τελικά. Μέσα από την διαφορική εξίσωση που αναλύεται στο πέμπτο κεφάλαιο, στις δυναμικές, φαίνεται πως το αποτέλεσμα εξαρτάται από τρεις παραμέτρους: από τον αρχικό πληθυσμό, από την πιθανότητα να παιχτεί η καθεμία στρατηγική και από τον πίνακα με τις ανταμοιβές των παικτών. Έτσι απαντάται το αρχικό μας ερώτημα και προκύπτει η στρατηγική που τελικά θα επικρατήσει, που ονομάζεται εξελικτική στρατηγική (evolutionary stable strategy-ESS). Στο τέταρτο κεφάλαιο ορίζεται η Ισορροπία Nash (I.N.), η Εξελικτική Σταθερή Στρατηγική (ESS) και η Εξελικτική Ισορροπία (E.E.) και στο έκτο κεφάλαιο αναφέρουμε την τοπική κατάταξη συστημάτων με χαμηλές διαστάσεις και συγκεκριμένα τα γραμμικά παίγνια μίας-διάστασης, τα συστήματα δύο μεταβλητών και άλλα συστήματα δύο-διαστάσεων και μη-γραμμικά. Κλείνοντας το 2ο μέρος και γενικά την παρούσα εργασία, παρουσιάζουμε τρία παραδείγματα στα οποία φαίνεται η εφαρμοσιμότητα των όσων αναφέραμε. Συγκεκριμένα αναλύονται τρία γνωστά παίγνια τα οποία χρησιμοποιήθηκαν από την πολιτική και παραλληλίστηκαν με καταστάσεις που είχαν να αντιμετωπίσουν εκείνη τη στιγμή. / This thesis deals with the evolutionary game theory and how it applies to economics. First of all, it is necessary to refer the original game theory and to analyze the key elements and then move to the analysis of evolutionary game theory. In the first part of this study, therefore, we indicate what is on game theory. Specifically, in the first chapter is a brief history of game theory and the second chapter defined game theory as a formal study examining the rationality in a business environment and presents the basics elements of a game. Also, at this chapter i reffer to the description of games, namely, games of cooperation and non-cooperation, and the two ways of representing their strategy, the normal form (matrix) and the extensive form (game tree). The third chapter sets out the dominant strategy and the corresponding dominant strategy equilibrium and in the fourth chapter we define the Nash Equilimbrium, which is the standard notion of equilibrium in economics. In these two chapters (third and fourth) there are examples of the application for better understanding, and we analyze the prisoner's dilemma, which is the most classic example of game theory. If there is no Nash Equilimbrium (this could happen at narmal strategy games) the game is solved by mixed strategies, which are analyzed in the fifth chapter. Continuing, at the sixth chapter we can see the extensive games with perfect information and we analyze the method of backward induction. In the seventh chapter, we can see the extensive games with imperfect information and the eighth chapter refers to the zero-sum games and how they can be used together with randomized algorithms for the analysis of problems on-line calculation. Finally, the first part closes with an example application of game theory, the auctions. The question is “What happens when a game is played more than once?” The answer comes from the second part of this thesis in which we analyse the evolutionary game theory. In the first two chapters of this part we define evolutionary games, we refere where evolutionary games might be applicable and why economic application aren’t common already. The third and fourth chapter are the most important chapters of the second part. At the third chapter we present the model of the evolutionary game and its elements (expected payoffs, population, states). We describe the stage game which is defined by a fitness function and we emphasize at its two linear specifications. Then we make a full analysis one of the most representative example of evolutionary game theory, the Hawk-Dove game. This game has two types of players, aggressive (Hawk) and defensive (Dove), which reflects the situation where there is a competitive and an uncompetitive business, and the point is to find which of the two types will eventually prevail. Based on a differential equation, we conclude that the result depends on three parameters: the initial population, the probability with which each strategy is played and the payoff matrix. All this leads in a strategy which is known as evolutionary stable (ESS). In chapter five, we define the Nash Equilibrium, the Evolutionary Stable Strategy (ESS) and Evolutionary Equilibrium (EE) and in chapter six we analyze the local classification of low dimensions systems. To make clear the applicability of all those we mention at this thesis, we are closing with three examples. More specific we analyze three well-known games which were used by the political and paralleled with situations they had to face with.

Στα πλαίσια της διατριβής αναπτύξαμε δύο από τους πρώτους αλγορίθμους υπολογισμού μιας ε-προσεγγιστικής ισορροπίας Nash για την περίπτωση όπου το ε είναι κάποια σταθερά. Οι προσεγγίσεις που επιτυγχάνουν οι αλγόριθμοί μας είναι ε=3/4 και ε=(2+λ)/4 αντίστοιχα, όπου λ είναι το ελάχιστο, μεταξύ όλων των ισορροπιών Nash, κέρδος για έναν παίκτη. Επιπλέον, μελετήσαμε μια ευρεία κλάση τυχαίων παιγνίων δύο παικτών, για την οποία υπολογίσαμε μια πολύ καλή ε-προσεγγιστική ισορροπία Nash, με το ε να τείνει στο 0 καθώς το πλήθος των διαθέσιμων στρατηγικών των παικτών τείνει στο άπειρο. Οι αρχές της θεωρίας παιγνίων είναι χρήσιμες στην ανάλυση της επίδρασης που έχει στην καθολική απόδοση ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του. Προς την κατεύθυνση αυτή, εστιάσαμε στο πρόβλημα της εξισορρόπησης φορτίου. Μελετήσαμε διάφορα μοντέλα πληροφόρησης (π.χ. όταν όλα τα φορτία είναι άγνωστα ή όταν κάθε παίκτης γνωρίζει το μέγεθος του δικού του φορτίου) και αναλύσαμε για το καθένα το σύνολο και τις ιδιότητες των ισορροπιών Nash. Yπολογίσαμε επίσης φράγματα στο λόγο απόκλισης, ο οποίος εκφράζει την επίδραση που έχει στην απόδοση του συστήματος η εγωιστική συμπεριφορά των χρηστών του. Εκτός από τα υπολογιστικά θέματα που σχετίζονται με τη θεωρία παιγνίων, έχει ενδιαφέρον να μελετηθεί κατά πόσο μπορεί η θεωρία παιγνίων να βοηθήσει στην ανάπτυξη και ανάλυση αλγορίθμων για υπολογιστικά δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης. Προς αυτήν την κατεύθυνση, μελετήσαμε από παιγνιοθεωρητική σκοπιά το πρόβλημα χρωματισμού των κορυφών ενός γραφήματος. Ορίσαμε κατάλληλα το παίγνιο χρωματισμού γραφήματος και αποδείξαμε ότι κάθε παίγνιο χρωματισμού γραφήματος έχει πάντα μια αγνή ισορροπία Nash, και ότι κάθε αγνή ισορροπία Nash αντιστοιχεί σε ορθό χρωματισμό του γραφήματος. Δείξαμε επίσης ότι υπάρχει πάντα μια αγνή ισορροπία Nash που χρησιμοποιεί βέλτιστο αριθμό χρωμάτων, δηλαδή ίσο με το χρωματικό αριθμό του γραφήματος. Επιπλέον, περιγράψαμε και αναλύσαμε έναν πολυωνυμικό αλγόριθμο που υπολογίζει μια αγνή ισορροπία Nash για ένα οποιοδήποτε παίγνιο χρωματισμού γραφήματος και χρησιμοποιεί συνολικά ένα πλήθος χρωμάτων που ικανοποιεί ταυτόχρονα τα περισσότερα κλασικά γνωστά φράγματα στο χρωματικό αριθμό. / We developed two algorithms for computing an e-approximate Nash equilibrium for the case where e is an absolute constant. The approximations achieved by our algorithms are e=3/4 and e=(2+l)/4 respectively, where $\lambda$ is the minimum, among all Nash equilibria, payoff of either player. Furthermore, we studied a wide class of random two player games, for which we showed how to compute an e-approximate Nash equilibrium, where e tends to zero as the number of strategies of the players tends to infinity. Game theoretic concepts are useful in determining the impact that selfish behavior plays on the global performance of a system involving selfish entities. Towards this direction, we focused on the problem of load balancing. We studied the case where the agents are not necessarily fully informed about the exact values of their loads. We focused on several models of information (e.g. when all agents know nothing about the loads, or when each agents knows her own load) and, for each model, we characterized the set of Nash equilibria and analyzed their properties. Moreover, we bounded the coordination ratio, a measure which captures the impact that selfish behavior has to the global performance of the system, in contrast to the performance achieved by an optimum centralized algorithm. Besides the computational issues related to game theory, it is interesting to investigate whether game theory can help us in developing and analyzing algorithms for computationally difficult combinatorial optimization problems. Towards this direction, we studied from a game theoretic point of view the problem of vertex coloring. In particular, we properly defined the graph coloring game and we proved that every graph coloring game has a pure Nash equilibrium, and each pure Nash equilibrium corresponds to a proper coloring of the graph. We also showed that there exists a pure Nash equilibrium that uses an optimum number of colors, i.e. equal to the chromatic number. Furthermore, we developed and analyzed a polynomial time algorithm that computes a pure Nash equilibrium for any graph coloring game, using a number of colors satisfying most of the known classical bounds on the chromatic number.

Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη καταστάσεων ανταγωνισμού μεταξύ χρηστών, για τη χρησιμοποίηση ενός συνόλου κοινόχρηστων πόρων. Για την μοντελοποίηση και ανάλυση των καταστάσεων αυτών χρησιμοποιούμε ως εργαλεία, έννοιες από την θεωρία παιγνίων, όπως ισορροπίες Nash, παίγνια συμφόρησης και μηχανισμοί συντονισμού. Ο κάθε κοινόχρηστος πόρος χρεώνει κάποιο κόστος στους χρήστες που τον χρησιμοποιούν. Θεωρούμε ότι οι χρήστες των κοινόχρηστων πόρων είναι εγωιστικοί, δηλαδή μοναδική τους επιδίωξη είναι η μεγιστοποίηση της προσωπικής τους ωφέλειας. Μια ισορροπία Nash είναι μια κατάσταση όπου κανένας χρήστης δεν μπορεί να αυξήσει το εγωιστικό του όφελος αν αλλάξει μονομερώς την στρατηγική του. Πιο συγκεκριμένα ασχολούμαστε με το KP-μοντέλο γνωστό και ως μοντέλο παράλληλων ακμών και ιδιαίτερα με μεθόδους σύγκλισης σε αγνές ισορροπίες Nash, όπου δηλαδή οι στρατηγικές (ακμές) των χρηστών είναι ντετερμινιστικές. Γενικά, ένα παίγνιο (σύστημα) δεν έχει πάντα μια αγνή ισορροπία Nash. Ωστόσο, εμείς θα μελετήσουμε περιπτώσεις που εγγυημένα έχουν τουλάχιστον μια αγνή ισορροπία Nash. Ονομάζουμε πολιτική χρέωσης των ακμών τον τρόπο με τον οποίο υπολογίζεται το κόστος του κάθε χρήστη όταν χρησιμοποιεί μια ακμή. Μια μέθοδος σύγκλισης σε μια αγνή ισορροπία Nash, είναι να επιτραπεί στους χρήστες να αλλάζουν εγωιστικά τις στρατηγικές τους μέχρι να καταλήξουν σε μια αγνή ισορροπία Nash. Ενδιαφερόμαστε για την ταχύτητα σύγκλισης σε μια αγνή ισορροπία Nash, δηλαδή το πλήθος των εγωιστικών αλλαγών στρατηγικών μέχρι να καταλήξουμε σε ισορροπία. Αρχικά, χρησιμοποιείται η πολιτική χρέωσης συνολικού φορτίου (Makespan), όπου κάθε ακμή χρεώνει το συνολικό της φορτίο σε κάθε χρήστη που την χρησιμοποιεί. Στην πιο απλή περίπτωση, η όλη διαδικασία χωρίζεται σε βήματα. Σε κάθε βήμα επιλέγεται, από το σύνολο των χρηστών που έχουν όφελος να αλλάξουν στρατηγική, ένας χρήστης ο οποίος αλλάζει στρατηγική. Η επιλογή γίνεται με βάση κάποιον αλγόριθμο προτεραιότητας. Για το μοντέλο αυτό, που ονομάζεται ESS-μοντέλο, η ταχύτητα σύγκλισης είναι στη χειρότερη περίπτωση εκθετική στο πλήθος των χρηστών. Παρουσιάζουμε την επίδραση των αλγορίθμων προτεραιότητας στην ταχύτητα σύγκλισης καθώς και αποτελέσματα για τρεις διαφορετικές κατηγορίες ακμών. Μια άλλη προσέγγιση, με εφαρμογή στα κατανεμημένα συστήματα, είναι η παράλληλη αλλαγή στρατηγικών από τους χρήστες (rerouting), όπου περισσότεροι από έναν χρήστες μπορούν να αλλάξουν ταυτόχρονα τη στρατηγική τους. Το μοντέλο αυτό υπερτερεί του ESS στην ταχύτητα σύγκλισης καθώς και στο πλήθος των πραγματικών καταστάσεων που μοντελοποιεί. Στη γενικότερη περίπτωση, όπου οι χρήστες επιτρέπεται να συνάπτουν συνασπισμούς (coalitions) μεταξύ τους, χρησιμοποιούμε έννοιες από τη συνεργατική θεωρία παιγνίων. Οπότε έχουμε να αντιμετωπίσουμε ομάδες χρηστών που αλλάζουν εγωιστικά τις ομαδικές στρατηγικές τους. Παρουσιάζουμε ένα ψευδοπολυωνυμικό φράγμα στην ταχύτητα σύγκλισης για μια ειδική περίπτωση όπου οι ακμές είναι πανομοιότυπες και επιτρέπονται συνασπισμοί πλήθους το πολύ δύο χρηστών. Ένας άλλος τρόπος σύγκλισης σε μια αγνή ισορροπία Nash είναι η κατασκευή ενός αλγορίθμου που αναθέτει στρατηγικές στους χρήστες, όχι απαραίτητα με βάση τα εγωιστικά κριτήρια του καθενός, χωρίς να αυξάνει το κοινωνικό κόστος. Με τον όρο κοινωνικό κόστος αναφερόμαστε σε μια συνολική μετρική της απόδοσης του συστήματος σε συνάρτηση με τις στρατηγικές των χρηστών του συστήματος. Ο αλγόριθμος Nashify που παρουσιάζουμε, συγκλίνει σε μια αγνή ισορροπία Nash σε πολυωνυμικό πλήθος βημάτων, χωρίς να αυξάνει το κοινωνικό κόστος. Στη συνέχεια, εισάγουμε την έννοια των μηχανισμών συντονισμού. Οι μηχανισμοί συντονισμού είναι ένα σύνολο πολιτικών χρέωσης για τις ακμές, που έχουν ως στόχο την παροχή κινήτρων στους εγωιστικούς χρήστες έτσι ώστε οι εγωιστικές αλλαγές των στρατηγικών τους να συγκλίνουν σε αγνές ισορροπίες Nash με μειωμένο κοινωνικό κόστος. Στην παρούσα εργασία, μελετάμε την επίδραση των μηχανισμών συντονισμού στην ταχύτητα σύγκλισης των εγωιστικών χρηστών σε μια ισορροπία Nash. Εξετάζουμε εκτός από την πολιτική χρέωσης συνολικού φορτίου (makespan) και κάποιες διαφορετικές πολιτικές χρέωσης (SJF, LJF, FIFO) και μελετάμε την επίδραση των αλγορίθμων προτεραιότητας στην ταχύτητα σύγκλισης τους. Παρουσιάζουμε και αποδεικνύουμε φράγματα στην ταχύτητα σύγκλισης για τις SJF και LJF πολιτικές που χρεώνουν τους χρήστες με βάση το μέγεθος των βαρών τους. Τέλος αποδεικνύουμε για την πολιτική χρέωσης FIFO, ένα γραμμικό άνω φράγμα στην ταχύτητα σύγκλισης για την ειδική περίπτωση των πανομοιότυπων ακμών και ένα ψευδοπολυωνυμικό άνω φράγμα για την γενική περίπτωση των ακμών. Τελικά, αξιολογούμε πειραματικά την επίδραση των αλγορίθμων προτεραιότητας στις πολιτικές χρέωσης στο ESS μοντέλo με πανομοιότυπες ακμές. Ουσιαστικά, συγκρίνουμε τις πολιτικές χρέωσης συνολικού φορτίου, SJF, LJF και FIFO καθώς και το συνεργατικό με το μη συνεργατικό μοντέλο σχετικά με τη ταχύτητα σύγκλισης τους. Παρατηρούμε ότι για την συνολικού φορτίου, SJF, LJF και FIFO πολιτική χρέωσης τα πειραματικά αποτελέσματα επαληθεύουν τα θεωρητικά φράγματα. Δηλαδή η FIFO πολιτική παρουσιάζει ταχύτερη σύγκλιση από τις υπόλοιπες πολιτικές ανεξάρτητα του αλγόριθμου προτεραιότητας. Για την περίπτωση των συνασπισμών με πολιτική χρέωσης συνολικού φορτίου, παρατηρούμε ότι η ταχύτητα σύγκλισης είναι πολυωνυμική στο πλήθος των χρηστών ακόμα και στην χειρότερη επιλογή συνασπισμών. Το αποτέλεσμα αυτό υποδεικνύει ότι το ψευδοπολυωνυμικό θεωρητικό άνω φράγμα μπορεί να βελτιωθεί. / General goal of the current diploma thesis is the study of competitive situations among users of a set of global resources. In order to analyze and model these situations we use as tools, game theoretic elements, such as Nash equilibrium, congestion games and coordination mechanisms. Every global resource debit a cost value to its users. We assume that the users are selfish, that is their sole objective is the maximization of their personal benefit. An Nash equilibrium is a situation in which no user can increase his personal benefit by changing only his or her own strategy unilaterally. More specific, we are interested in the KP-model or parallel links model and we study convergence methods to pure Nash equilibrium, in which all the strategies a user can select are deterministic. Generally, a game has not always a pure Nash equilibrium. Although we are going to study cases in which there is always at least one Nash equilibrium. We define as cost policy of an edge the function which computes the cost of each user of this edge. A method of convergence in a pure Nash equilibrium is, starting from an initial configuration, to allow all users to selfishly change their strategies (one after the other) until they reach a pure Nash equilibrium. We are interested in the convergence time to pure Nash equilibrium, that is the number of these selfish moves. Firstly, we study the makespan cost policy, in which each edge debits its total load to everyone that use it. In the most simple case, the whole procedure is divided into several steps. At each step, the priority algorithm choose one user from the set of users that benefit by changing their current strategy. For this model, named ESS-model, the convergence time is at the worst case exponential to the number of users. We present the effect of several priority algorithms to the convergence time and results for the major different cases of edges (identical, related, unrelated). Another approach, with applications to distributed systems, is the concurrent change of strategies (rerouting) in which more than one users can change simultaneously their strategies. This model is more powerful than ESS because of its real life applications. Another model we study is that of coalitions, in which the users can contract alliances. This model comes from cooperative game theory. In this case we have to deal with groups of users changing selfishly their group strategies. We present a pseudo-polynomial bound to the convergence time in the identical machines model with coalitions of at most 2 users. Another model of convergence, a little different than the others stated above, is the construction of an algorithm that delegates strategies to the users unselfishly without increasing the social cost. Informally, social cost is a total metric of the system performance depending on the users strategies. This model is named nashification and the algorithm nashify that provides converge to a pure Nash equilibrium in polynomial number of steps without increasing the social cost. As far as the coordination mechanisms are concerned, they are a set of cost policies for the edges, that provides motives to the selfish users in order to converge to a pure Nash equilibrium with decreased social cost. In this thesis, we study the effect of coordination mechanisms in the convergence time. We examine, except from makespan, the sjf, ljf and fifo cost policies. Sjf and ljf policies debit the users concerning their weights. The thesis results are divided in two categories. On the one hand, we prove upper and lower bounds of convergence time for sjf, ljf and fifo policies. Especially for fifo we prove in identical machines case a tight linear bound which is independent from the priority algorithm and a pseudo-polynomial bound in unrelated machines case. On the other hand, we implement all the above mentioned models and analyze them experimentally. In our experiments there are 3 parameters: the priority algorithm, the cost policy, and the number of coalitions. In all cases the experimental results follows the theoretical with one exception which is the most interesting among the experiments. In the case of coalitions with at most 2 users the theoretical upper bound is pseudo-polynomial to the number of users but the experimental results shows that the convergence time is polynomial. These results force us to conjecture that there is a polynomial upper bound.

Cette thèse étudie l’évolution des marchés du gaz naturel en Europe jusqu’en 2035 en utilisant les outils de la modélisation. Le modèle proposé, intitulé GaMMES, repose sur une description oligopolistique des marchés et ses principaux avantages sont les suivants : un niveau de détail important de la structure économique de la chaîne gazière et une prise en compte endogène des contrats de long-terme en amont ainsi que de la substitution avec les produits pétroliers et le charbon, au niveau de la demande. Dans un premier temps, nous étudions la question de la sécurité d’approvisionnement en gaz en Europe et les conditions favorables à la régulation des marchés vulnérables au risque de rupture d’approvisionnement, notamment de la part de la Russie. Trois études de cas sont proposées selon le degré de dépendance et la nature de régulation en place : le marché allemand des années 1980 et les marchés actuels de la Bulgarie et de l’Espagne. Nous étudions en particulier l’évolution des caractéristiques des marchés en fonction du risque de rupture et le type de régulation à mettre en place afin d’assurer l’optimalité du bien-être social. Ensuite, nous proposons un modèle de type systèmes dynamiques afin de prendre en compte la substitution énergétique entre le charbon, le pétrole et le gaz naturel. Notre approche permet d’estimer une nouvelle forme fonctionnelle de la fonction de demande pour le gaz naturel, qui englobe à la fois la substitution énergétique et les inerties de consommation dues aux investissements des usagers finaux. Dans un troisième temps, nous utilisons cette fonction de demande dans un modèle d’équilibre partiel des marchés du gaz naturel en Europe. Le modèle GaMMES, écrit sous forme de problème de complémentarité, représente les principaux acteurs de l’industrie du gaz naturel en considérant leurs interactions stratégiques et les pouvoirs de marchés. Il a été appliqué au marché du gaz naturel en Europe du nord-est afin d’étudier l’évolution, jusqu’en 2035, de la consommation, des prix spot, des prix et volumes long-terme, de la production et de la dépendance par rapport aux imports étrangers. Finalement, nous proposons une extension stochastique du modèle GaMMES afin d’analyser l’impact de la forte fluctuation du prix du Brent sur les marchés gaziers. Une étude économétrique a été menée afin de calculer la loi de probabilité du prix du pétrole, lorsqu’il est modélisé en tant que variable aléatoire, dans le but de construire et pondérer l’arbre des scénarii. Les résultats permettent de comprendre comment l’aléa modifie les comportements stratégiques des acteurs, notamment au niveau des contrats de long-terme. Enfin, la valeur de la solution stochastique est calculée afin de quantifier l’importance de la prise en compte des fluctuations du prix du pétrole pour chaque acteur de la chaîne. / This thesis studies the evolution of the natural gas markets in Europe, until 2035, using optimization theory tools. The model we develop, named GaMMES, is based on an oligopolistic description of the markets. Its main advantages are the following: we consider an important level of detail in the economic structure of the gas chain and we endogenously take into account long-term contracts in the upstream as well as energy substitution between gas, oil, and coal in the demand. In the first part of this thesis, we study the issue of security of supply in Europe and the conditions under which it is necessary to regulate the gas markets that are strongly dependent on foreign imports. Three case studies are then presented, regarding the level of dependence and the markets' specificities: the German gas trade of the 1980s and the current Spanish and Bulgarian markets. We study in particular the evolution of the markets' outcome as a function of the supply disruption probability and the kind of regulation to implement in order to maximize the social welfare. In the second part, we develop a system dynamics model in order to capture fuel substitution between oil, coal, and natural gas. Our approach allows one to calculate a new functional form of the demand function for natural gas that contains energy substitution and consumption inertia effects due to end-users' investments. In the third part, we take advantage of our demand function and use it in a partial equilibrium model of natural gas markets in Europe. The GaMMES model, when written as a complementarity problem, describes the principal gas chain actors as well as their strategic interactions and market power. It was applied to the northwestern European gas trade to analyze the evolution of consumption, spot and long-term contract prices and volumes, production, and natural gas dependence, until 2035. In the last part, we present a stochastic extension of the GaMMES model in order to study the impact of the strong Brent price fluctuation on the gas markets. An econometric analysis allowed us to calculate the probability law of the oil price, when taken as a random variable, in order to construct the scenario tree and estimate its weights. Our results show how uncertainty changes the strategic behavior, in particular for the long-term contracting activity. Finally, the value of the stochastic solution is calculated to quantify the importance of taking into account randomness in the optimization programs of the gas chain actors.

Submitted by Diego Piotto (dpiotto@gmail.com) on 2017-08-28T18:15:31Z No. of bitstreams: 1 Diego Piotto_Final.pdf: 1609250 bytes, checksum: 9c276b0e7f775c9cb47d057087a1da5a (MD5) / Approved for entry into archive by Joana Martorini (joana.martorini@fgv.br) on 2017-08-28T18:21:48Z (GMT) No. of bitstreams: 1 Diego Piotto_Final.pdf: 1609250 bytes, checksum: 9c276b0e7f775c9cb47d057087a1da5a (MD5) / Made available in DSpace on 2017-08-29T12:42:11Z (GMT). No. of bitstreams: 1 Diego Piotto_Final.pdf: 1609250 bytes, checksum: 9c276b0e7f775c9cb47d057087a1da5a (MD5) Previous issue date: 2017-08-14 / O sistema elétrico brasileiro sofreu grandes mudanças em sua regulação nas últimas décadas no intuito de aumentar a eficiência de mercado baseando-se no incentivo a competição entre os agentes. O incentivo a entrada de geradores privados tem gerado resultados significativos a competição e tem provocado uma reestruturação que tem modificado a operação antes totalmente centralizada para modelos descentralizados que estimulam a competição entre agentes. O objetivo deste trabalho é, partir do artigo de Barroso Et al. (2001), onde é obtido a ação de poder de mercado em sistemas hidrotérmicos para ambiente competitivo e de mínimo custo tanto para modelo estático como modelo dinâmico, desenvolver o modelo de comportamento dos agentes para situações de colusão entre agentes price makers tanto para o modelo estático como para o dinâmico. Além disso obter as taxas de juros limites para o desvio da colusão. Será demostrado que em mercados com poucos agentes, o benefício de se desviar da colusão somente ocorre para altas taxas de desconto. Com a inclusão de maior quantidade de agentes, identifica-se que o incentivo ao desvio da colusão possui taxas descrentes. Será apresentado que para modelos acoplados no tempo o comportamento de um possível conluio fará com que os agentes sustentem o preço spot mais elevado, mesmo em períodos de baixa afluência. / The Brazilian electrical system has undergone great changes in its regulation in the last decades in order to increase the efficiency of the market based on the incentive to the competition among the agents. The incentive to the entry of private generators has generated significant results the competition and has caused a restructuring that has modified the operation before totally centralized to decentralized models that stimulate the competition between agents. The objective of this work is to analyze the market power in hydrothermal systems that is, based on thermal and hydroelectric generation, using low cost models for centralized systems and Nash Cournot model for decentralized systems both decoupled in time in order to obtain the dispatch great. The analysis extends to the strategic behavior of the agents for time coupled systems using low cost models for centralized systems and Nash Cournot model using stochastic programming resources to determine the optimal dispatch of the agents of the market. It has been shown that in markets with few agents, the benefit of diverting from collusion only occurs at high discount rates. With the inclusion of a greater number of agents, it is identified that the incentive to the deviation of collusion has unbelievable rates. It will be shown that for time-coupled models the behavior of a possible collusion will cause the agents to sustain the higher spot price, even in periods of low affluence.