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

Abstract

Αρχικά παρουσιάζονται κάποια ιστορικά στοιχεία, ώστε να γίνει αντιληπτό το επιστημονικό πλαίσιο της εποχής της θεμελίωσης της Θεωρίας Παιγνίων και διασαφηνίζονται ορισμένες βασικές έννοιες, απαραίτητες για την περεταίρω κατανόησή της. Έπειτα ακολουθεί η επεξήγηση του θεωρήματος minimax και η ανάλυση του παιχνιδιού «Το Δίλημμα του Κρατουμένου». Το πρώτο αποτελεί τον θεμέλιο λίθο ενασχόλησης των οικονομολόγων με παιχνίδια δύο παιχτών, ενώ το δεύτερο είναι το αντιπροσωπευτικότερο παιχνίδι της θεωρίας σε επίπεδο δομής, ισορροπίας και κατανόησής της. Στη συνέχεια γίνεται μια εκτενή αναφορά στην κλασική Θεωρία Παιγνίων, όπου παρουσιάζονται οι εκπληκτικές ιδέες του θεμελιωτή της Θεωρίας Παιγνίων John F. Nash, το Θεώρημα και το σπουδαιότερο όλων την Ισορροπία Nash, η οποία αποτελεί ως σήμερα τη λύση ή την κατάληξη των εκάστοτε προβλημάτων ή παιχνιδιών αντίστοιχα. Ακολουθεί αναφορά στην εξέλιξη ή εκλέπτυνση που είχαν κάποιες από τις βασικές ιδέες και προβλήματα που έθεσε ο Nash, σε θεωρητικό αλλά και αλγοριθμικό επίπεδο. Στα επόμενα δύο κεφάλαια παρουσιάζονται η Αλγοριθμική και η Εξελικτική Θεωρία Παιγνίων. Όσον αφορά την πρώτη, επεξηγούνται βασικές έννοιες και εργαλεία, όπως η Πολυπλοκότητα των αλγορίθμων αναζήτησης ισορροπιών Nash, και ο Αλγοριθμικός Σχεδιασμός Μηχανισμών (AMD), ο οποίος κρίνεται πλέον απαραίτητος για την καλύτερη απόδοση και έκβαση πολύπλοκων δικτύων και καταστάσεων. Παρουσιάζονται επίσης τα σημαντικότερα σύγχρονα προβλήματα, τα οποία αποτελούν πολύ σημαντικό πεδίο έρευνας, όπως ο Χρωματισμός Γραφημάτων, η Διαδικτυακή Ισορροπία και η Συμφόρηση Δικτύου. Τέλος αναλύονται οι εξελικτικοί αλγόριθμοι και οι φυσικές διαδικασίες, τις οποίες μιμούνται, με συγκεκριμένα παραδείγματα. Η παρούσα μελέτη ολοκληρώνεται με απτά παραδείγματα και εφαρμογές της Θεωρίας Παιγνίων που βιώνουμε ή μπορούμε να αντιληφθούμε όλοι στη καθημερινότητά μας. Με τον τρόπο αυτό και με τα συμπεράσματα που ακολουθούν, η παρούσα διατριβή αποβλέπει στην εξύμνηση της σπουδαιότητας της Θεωρίας Παιγνίων και στην ευαισθητοποίηση του εκάστοτε αναγνώστη, ώστε να γίνει πραγματικότητα η πρακτική ενασχόληση όλων μας με την εν λόγω θεωρία για ένα καλύτερο και κοινωνικά πιο ανθρώπινο περιβάλλον.