Αλγοριθμική & εξελικτική θεωρία παιγνίων

Αθανασίου - Σιούλας, Αθανάσιος Φ.

Master Thesis

Author

Αθανασίου - Σιούλας, Αθανάσιος Φ.

Date

2012-10-24

Abstract

Initially are presented certain historical elements, in order to be clear the scientific frame of the season of foundation of Game Theory and are explained certain basic concepts, essential for understanding later on. Then it follows the explanation of minimax theorem and the analysis of the game “The Prisoner‘s Dilemma”. The first one is the reason why economists started dealing with games of two players, while the second one is the most represented game of Game Theory in terms of structure, equilibrium and comprehension. Afterwards there is an extensive report in the classic Game Theory, where are presented the amazing ideas of perhaps the founding father of Game Theory, John F. Nash, his theorem and more important of all Nash Equilibrium, which constitutes until today the solution or the conclusion of each problem or game respectively. It follows a report in the development or refinement in some basic ideas and problems that Nash placed, in theoretical but also algorithmic level. In the next two chapters are presented the Algorithmic and Evolutionary Game Theory. Firstly, are explained basic concepts and tools, like the Complexity of algorithms searching Nash Equilibrium and the Algorithmic Mechanism Design (AMD), which is considered nowadays essential for a better result of complicated networks or situations. Also there are presented the most important contemporary problems, which constitute a very important field of research, like the Graph Coloring, Internet Equilibrium and the Network Congestion. Finally is analyzed the evolutionary algorithms and the natural processes, which they imitate, with specific examples. The present study is completed with tangible examples and applications of Game Theory that we experience or can perceive in our day life. In addition to the conclusion section that follows, the present study aims at the glorification of importance of Game Theory and at the sensitization of each reader, so that any of us would be able to make its practices a reality, for a better and socially more human environment.