Nash ισορροπίες σε Voronoi παίγνια
Creators: name: Πεγιά, Μαρία-Ειρήνη Αυγερινού
Publisher: name: Aristotle University of Thessaloniki
Year: 2017
Subjects: αμιγής Nash ισορροπία
Voronoi παίγνιο
παίγνιο Απομόνωσης
pure Nash equilibrium
Voronoi game
Isolation game

description: Η παρούσα εργασία ασχολείται με τη μελέτη των Voronoi παιγνίων. Διαισθητικά ένα Voronoi παίγνιο είναι ένα παίγνιο στο οποίο παίζουν δύο παίκτες. Κάθε παίκτης έχει από n το πλήθος σημεία. Οι παίκτες τοποθετούν διαδοχικά τα σημεία τους σε ένα μετρικό χώρο, ο οποίος αποτελεί την αρένα του παιγνίου. Κάθε παίκτης τοποθετεί ένα σημείο σε κάθε γύρο στην αρένα του παιγνίου. Το παίγνιο τελειώνει όταν έχουν τοποθετηθεί και τα 2n σημεία. Στη συνέχεια δίνεται η ωφέλεια του κάθε παίκτη. Η ωφέλεια του κάθε παίκτη μεταφράζεται ως το εμβαδόν της περιοχής που κατέχει. Ο κάθε παίκτης κατέχει την περιοχή, η οποία σχηματίζεται από τα σημεία που απέχουν κοντινότερη απόσταση από τα δικά του. Σημεία που απέχουν εξίσου από τους παίκτες μοιράζονται ισάξια. Σκοπός του κάθε παίκτη είναι να μεγιστοποιήσει την ωφέλειά του, ή ισοδύναμα την περιοχή του. Πρόκειται για ένα μη συνεργατικό, δυναμικό, και τέλειας πληροφόρησης παίγνιο. Το κέρδος του ενός παίκτη αποτελεί ζημία για τον άλλον παίκτη. Οι παίκτες έχουν πλήρη γνώση της ιστορίας του παιγνίου, δηλαδή της εξέλιξης σε κάθε γύρο του παιγνίου και οι παίκτες δεν κάνουν τις επιλογές τους ταυτόχρονα, αλλά στη διάρκεια του χρόνου. Θα μελετήσουμε αυτό το παίγνιο με χρήση εργαλείων από τη Θεωρία Παιγνίων. Θα εξετάσουμε την ύπαρξη Nash ισορροπίας σε αυτό το παίγνιο, δηλαδή αν υπάρχει μια σταθερή κατάσταση στην οποία δεν μπορεί κάποιος παίκτης να καλυτερεύσει μέσω μιας αλλαγής στρατηγικής, όταν όλοι οι άλλοι διατηρούν τη στρατηγική τους. Πιο συγκεκριμένα στο Κεφάλαιο 1 θα δώσουμε τις προαπαιτούμενες έννοιες που θα χρειαστούμε από τη Θεωρία Παιγνίων. Θα ορίσουμε το παίγνιο, τη Nash ισορροπία, το κοινωνικό κόστος διαφωνίας καθώς και την τιμή αναρχίας και τιμή ευστάθειας, που αποτελούν μέτρα της μη αποδοτικότητας της ισορροπίας Nash. Κατόπιν στο Κεφάλαιο 2 θα εισάγουμε τα Voronoi παίγνια. Θα χρειαστούμε βασικά στοιχεία και ιδιότητες των Voronoi διαγραμμάτων της υπολογιστικής γεωμετρίας έτσι ώστε να παρέχουμε στη συνέχεια τον ορισμό αυτού του είδους παιγνίου, αλλά και να διακρίνουμε τα συνεχή και διακριτά παίγνια ανάλογα αν ο χώρος στον οποίο παίζεται το παίγνιο είναι συνεχής ή διακριτός. Στο Κεφάλαιο 3 θα εστιάσουμε στην έρευνα που έχει γίνει στα συνεχή Voronoi παίγνια. Θα δούμε την περίπτωση όπου η αρένα είναι κύκλος ή ευθύγραμμο τμήμα καθώς και ξένες ανοιχτές καμπύλες. Στην περίπτωση που η αρένα είναι ευθύγραμμο τμήμα θα μελετήσουμε την ύπαρξη Nash ισορροπίας σε σχέση με το πλήθος των παικτών. Θα δούμε και την περίπτωση του ενός γύρου Voronoi παιγνίου, στο οποίο ο κάθε παίκτης στο γύρο του τοποθετεί με τη μία όλα τα σημεία του. Θα παρατηρήσουμε αλλού να υπάρχει νικηφόρα στρατηγική για τον πρώτο παίκτη, αλλού για τον δεύτερο, αλλού να υπάρχει Nash ισορροπία και αλλού να είναι NP-hard ή NP-complete ο προσδιορισμός της. Στο τέλος αυτού του κεφαλαίου δίνονται και επεκτάσεις αυτού του παιγνίου, όπως είναι τα Voronoi παίγνια επιλογής. Θα δούμε ότι αυτά τα παίγνια συνδέονται με στοχαστικές διεργασίες και πώς με αυτό τον τρόπο εμπεριέχουν τυχαιότητα. Στο Κεφάλαιο 4 θα εστιάσουμε στα διακριτά Voronoi παίγνια, στα οποία έχει γίνει μικρότερη έρευνα συγκριτικά με την έρευνα στη συνεχή περίπτωση. Με τον όρο διακριτά Voronoi παίγνια αναφερόμαστε σε γραφήματα. Θα δούμε την περίπτωση όπου η αρένα του παιγνίου είναι κυκλικό γράφημα, μεταβατικό γράφημα, μονοπάτι, πλέγμα. Στην περίπτωση που είναι πλήρες δυαδικό δένδρο ή τυχαίο δένδρο θα εξετάσουμε την ύπαρξη Nash ισορροπίας σε σχέση με το πλήθος των παικτών. Στο τέλος και αυτού του κεφαλαίου θα δώσουμε επεκτάσεις αυτού του παιγνίου. Θα εξετάσουμε τόσο τις νικηφόρες στρατηγικές, τις ισορροπίες (αν υπάρχουν) και το πλήθος αυτών όπου μπορεί να προσδιοριστεί. Στο Κεφάλαιο 5 θα ασχοληθούμε με το παίγνιο Απομόνωσης ένα διαφορετικό είδος παιγνίου που φαίνεται να είναι το συμπληρωματικό του Voronoi παιγνίου. Στο Voronoi παίγνιο ο στόχος του κάθε παίκτη είναι να μεγιστοποιήσει το εμβαδόν της Voronoi περιοχής του. Αντίθετα στο παίγνιο Απομόνωσης κάθε παίκτης έχει στόχο να τοποθετήσει τον εαυτό του όσο μακριά γίνεται από τους υπόλοιπους παίκτες σε ένα φραγμένο χώρο. Θα ορίσουμε το παίγνιο και θα μελετήσουμε τις Nash ισορροπίες (αν υπάρχουν) τόσο στη συνεχή όσο και στη διακριτή περίπτωση. Θα δούμε την τιμή αναρχίας και τιμή ευστάθειας και σε αυτό το είδος παιγνίου. Στο Κεφάλαιο 6 θα αναφέρουμε μερικά ανοικτά προβλήματα για τα Voronoi παίγνια και παίγνια Απομόνωσης, για τα οποία ακόμα δεν έχει σχηματίσει κάποιο πόρισμα η επιστημονική κοινότητα. Μετά από αυτό το κεφάλαιο ακολουθεί ένα παράρτημα με τη βασική ορολογία που χρησιμοποιήσαμε και τέλος ακολουθεί η βιβλιογραφία. Στόχος αυτής της εργασίας ήταν αρχικά η κατανόηση της περιοχής και έπειτα η ανίχνευση και καταγραφή των ανοιχτών προβλημάτων
description: This paper deals with the study of Voronoi games. Intuitively a Voronoi game is a game in which play two players. Each player has $n$ points. Players place their points in a metric space, which is the arena of the game. Each player places a point on each round in the game arena. The game ends when the 2$n$ points are placed. Then the utility of each player is given. The utility of each player is translated as the area of the region he owns. Each player possesses the area, which is formed by the points closest to his or her own. Points that are equally distant to the players, they divided equally. The goal of each player is to maximize his or her area, respectively. This is a non-cooperative, dynamic, and perfect information game. One player's gain is a damage to the other player. Players have a complete knowledge of the history of the game, i.e., its evolution in each round of the game and the players do not make their choices at the same time, but over time. We will study this game using tools from Game Theory. We will look at the existence of a Nash equilibrium in this game, that is, if there is a stable situation in which a player can not improve his or her utility through a change of his or her strategy, when everyone else keeps their strategy. In particular, in Chapter 1 we will give the preconditions that we will need from Game Theory. We will define the game, the Nash equilibrium, the social cost of discrepancy as well as the price of anarchy and price of stability, which are measures of the inefficiency of Nash equilibrium. Then, in Chapter 2 we will introduce the Voronoi games. We will need basic elements and attributes of the Voronoi diagrams of computational geometry so that we then provide the definition of this type of game, but also to distinguish between continuous and discrete games depending on whether the area in which the game is played is continuous or discrete, respectively. In Chapter 3 we will focus on the research that has been made on the continuous Voronoi games. We will look at the case where the arena is a circle or a segment as well as disjoint open curves. In the case in which the arena is a segment we will study the existence of a Nash equilibrium in relation to the number of players. We will look at the case of one-round Voronoi game, in which each player in his or her round places all his or her points at once. We will observe elsewhere that there is a winning strategy for the first player, elsewhere for the second player, elsewhere there is a Nash equilibrium and elsewhere to be NP-hard or NP-complete the existence of a Nash equilibrium. At the end of this chapter, there are also extensions to this game, such as Voronoi choice games. We will see that these games are connected with stochastic processes and how they are random in this way. In Chapter 4 we will focus on discrete Voronoi games, in which has been done less study than the continuous case. By the term discrete Voronoi games we refer to graphs. We will look at the case where the game arena is a cycle graph, a transition graph, a path, a grid. In the case of a full binary tree or a random tree we will look at the existence of a Nash equilibrium in relation to the number of players. At the end of this chapter, we'll give extensions to this game. We will look at the winning strategies, the Nash equilibria (if they exist) and the number of them, where it can be determined. In Chapter 5 we will deal with Isolation game, a different kind of game, that seems to be the complement of the Voronoi game. In the Voronoi game the goal of each player is to maximize the area of his or her Voronoi region. In contrast, in the Isolation game each player aims to place himself or herself as far as possible from the rest of the players in a bounded space. We will define the game and study the Nash equilibria in both the continuous and the discrete case. We will see the price of anarchy and the price of stability in this type of game. In Chapter 6 we will mention a few open problems for Voronoi games and for Isolation games, for which the scientific community has not yet formed a conclusion. After this chapter follows an appendix with the basic terminology we used, followed by the bibliography. The aim of this paper was initially to understand the area and then to detect and record the open problems