research unit 1
 

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit Aigaion.nl.SourceForge.hetLogo

Publication

Type of publication:Phdthesis
Entered by:PNP
TitleAlgorithmic and Evolutionary Game Theory
Bibtex cite IDRACTI-RU1-2008-66
Year published 2008
Month November
School Computer Engineerings and Informatics Department, Patras University
Abstract
Η θεωρία παιγνίων προσφέρει μοντέλα και αναλυτικά εργαλεία για την κατανόηση φαινομένων που παρατηρούνται όταν κάποιες εγωιστικές οντότητες (παίκτες) με προσωπικές στρατηγικές και συμφέροντα αλληλεπιδρούν. Στόχος της διατριβής είναι η μελέτη προβλημάτων που συνδέονται τόσο με τη θεωρία παιγνίων όσο και με τη θεωρία υπολογισμού. Τα συγκεκριμένα θέματα με τα οποία ασχοληθήκαμε και τα αποτελέσματα της έρευνάς μας συνοψίζονται παρακάτω. Υπολογισμός Προσεγγιστικών Ισορροπιών Nash. Ένα από τα πλέον θεμελιώδη αλγοριθμικά προβλήματα της θεωρίας παιγνίων είναι το πρόβλημα υπολογισμού μιας ισορροπίας Nash ενός δοθέντος παιγνίου. Μια ισορροπία Nash είναι ένας συνδυασμός στρατηγικών, μία για κάθε παίκτη, τέτοια ώστε να μην υπάρχει παίκτης που να μπορεί να αυξήσει το κέρδος του αν αποκλίνει μονομερώς, αν αλλάξει δηλαδή τη στρατηγική του. Πρόσφατα όμως αποδείχθηκε ότι το πρόβλημα υπολογισμού μιας ισορροπίας Nash είναι πλήρες για την κλάση πολυπλοκότητας PPAD, γεγονός που έστρεψε την έρευνα προς την αναζήτηση ε-προσεγγιστικών ισορροπιών Nash, δηλαδή συνδυασμών στρατηγικών με την ιδιότητα ότι κανένας παίκτης δεν μπορεί να αυξήσει το κέρδος του περισσότερο από ε αν αποκλίνει μονομερώς. Στα πλαίσια της διατριβής αναπτύξαμε δύο από τους πρώτους αλγορίθμους υπολογισμού μιας ε-προσεγγιστικής ισορροπίας Nash για την περίπτωση όπου το ε είναι κάποια σταθερά. Οι προσεγγίσεις που επιτυγχάνουν οι αλγόριθμοί μας είναι ε=3/4 και ε=(2+λ)/4 αντίστοιχα, όπου λ είναι το ελάχιστο, μεταξύ όλων των ισορροπιών Nash, κέρδος για έναν παίκτη. Επιπλέον, μελετήσαμε μια ευρεία κλάση τυχαίων παιγνίων δύο παικτών, για την οποία υπολογίσαμε μια πολύ καλή ε-προσεγγιστική ισορροπία Nash, με το ε να τείνει στο 0 καθώς το πλήθος των διαθέσιμων στρατηγικών των παικτών τείνει στο άπειρο. Εξισορρόπηση Φορτίου και Ατελής Πληροφόρηση. Οι αρχές της θεωρίας παιγνίων είναι χρήσιμες στην ανάλυση της επίδρασης που έχει στην καθολική απόδοση ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του. Προς την κατεύθυνση αυτή, εστιάσαμε στο πρόβλημα της εξισορρόπησης φορτίου. Συγκεκριμένα, κάθε ένας από ένα σύνολο n χρηστών, με διαφορετικό φορτίο ο καθένας, καλείται να επιλέξει έναν από δύο διαθέσιμους εξυπηρετητές όπου θα αναθέσει το φορτίο του. Ο στόχος κάθε χρήστη είναι να ελαχιστοποιήσει το κόστος του, το οποίο ορίζεται ως το αναμενόμενο συνολικό φορτίο στον εξυπηρετητή που θα επιλέξει. Στην περίπτωση που κάθε χρήστης γνωρίζει τόσο το μέγεθος του φορτίου του όσο και τα μεγέθη των φορτίων των άλλων χρηστών, το επαγόμενο παίγνιο είναι ουσιαστικά ένα παίγνιο συμφόρησης με βάρη, ανήκει δηλαδή σε μια κατηγορία παιγνίων τα οποία έχουν μελετηθεί εκτενώς στην πρόσφατη βιβλιογραφία. Στα πλαίσια της διατριβής μελετήσαμε την περίπτωση όπου οι χρήστες έχουν ατελή πληροφόρηση σχετικά με τα ακριβή μεγέθη των φορτίων τους. Εστιάσαμε στις λεγόμενες κατωφλιακές στρατηγικές, δηλαδή σε στρατηγικές της μορφής.
Authors
Panagopoulou, Panagiota
Topics
BibTeXBibTeX
RISRIS
Attachments
phd.pdf (main file)
 
Publication ID528