Θεωρία παιγνίων και προβλήματα βελτιστοποίησης

Abstract

Η Θεωρία Παιγνίων είναι ένα σύνολο μοντέλων που χρησιμοποιείται σαν βασικό εργαλείο για την κατανόηση, ανάλυση, εξήγηση και μοντελοποίηση καταστάσεων, καταστάσεις στις οποίες αλληλεπιδρούν νοήμονες οντότητες προκειμένου να πάρουν μια απόφαση δράσης η οποία μεγιστοποιεί την ωφέλειά τους. Η αφαιρετικότητά τους, επιτρέπει να χρησιμοποιηθούν για τη μελέτη ενός ευρέος φάσματος φαινομένων. Η επιθυμητή έκβαση των καταστάσεων αυτών είναι μια τελική κατάσταση ισορροπίας (Ισορροπία Nash) όπου κανένας από τους εμπλεκόμενους (παίχτες) στην αλληλεπίδραση δεν έχει κίνητρο να αλλάξει την απόφαση δράσης του. Η Εξελικτική Θεωρία Παιγνίων βασίζεται στις αρχές της εξέλιξης της Δαρβινικής Θεωρίας και μελετά την έκβαση του παιγνίου μέσω της εξέλιξής του καθώς παίζεται σε βάθος χρόνου μέσα από πολλές γενεές. Πρωταγωνιστές δεν είναι πλέον οι ορθολογικοί παίχτες αλλά οι ίδιες οι στρατηγικές, οι οποίες περνούν στις επόμενες γενεές ή πεθαίνουν ανάλογα με το πόσο καλές είναι. Η στρατηγική η οποία θα επιβιώσει μέσα από τη διαδικασία εξέλιξης είναι η Εξελικτικά Σταθερή Στρατηγική δηλαδή η επιθυμητή τελική κατάσταση. Η Θεωρία Παιγνίων μπορεί να χρησιμοποιηθεί εξίσου, για τη μοντελοποίηση δύσκολων προβλημάτων συνδυαστικής βελτιστοποίησης, προβλημάτων που η δυσκολία τους έγκειται στο ότι ανήκουν στην κλάση NP. Το πρόβλημα του Περιοδεύοντος Πωλητή είναι ένα από τα πιο διάσημα προβλήματα συνδυαστικής βελτιστοποίησης καθώς, η εύρεση της συντομότερης διαδρομής που θα κάνει ο πωλητής προκειμένου να επισκεφθεί μια ακριβώς φορά την κάθε πόλη αρμοδιότητάς του, και να επιστρέψει στην πόλη αφετηρίας, απαιτεί εκθετικό χρόνο καθώς αυξάνονται οι πόλεις. Στην εργασία αυτή προσεγγίζεται το πρόβλημα του Περιοδεύοντος Πωλητή από τη σκοπιά της Θεωρίας Παιγνίων και μελετάται κατά πόσον μπορούν να εφαρμοστούν οι αρχές της. Ορίζεται το παίγνιο μέσω της Εξελικτικής Θεωρίας Παιγνίων,και παρουσιάζεται το εξελικτικό παίγνιο του προβλήματος του Περιοδεύοντος Πωλητή.