Παίγνια Και Ιδιοτελής Συμπεριφορά Σε Δίκτυα

Abstract

Το αντικείμενο της παρούσας διπλωματικής εργασίας είναι η μελέτη καταστάσεων στις οποίες πολλοί χρήστες αλληλεπιδρούν μεταξύ τους, υπό την απουσία κάποιας εξωτερικής ρυθμιστικής αρχής, με μόνο γνώμονα ο καθένας το προσωπικό του όφελος. Τέτοιες καταστάσεις είναι συνηθισμένες σε μεγάλα, κατανεμημένα συστήματα και δίκτυα, με χαρακτηριστικότερο παράδειγμα αυτό του Internet. Τα συστήματα αυτά, που χαρακτηρίζονται από ιδιοτελή συμπεριφορά χρηστών, αποτελούν παραδοσιακά αντικείμενο μελέτης της Θεωρίας Παιγνίων. Στη διπλωματική αυτή παρουσιάζουμε κάποιες βασικές έννοιες της Θεωρίας Παιγνίων και στη συνέχεια προχωράμε στη μελέτη τριών μοντέλων που έχουν προταθεί για την αναπαράσταση των συστημάτων αυτών. Τα μοντέλα αυτά είναι: πρώτον, το δίκτυο παράλληλων ακμών που πρωτομελετήθηκε στο [KP99] και ακολουθήθηκε από μία σειρά από άλλες δημοσιεύσεις που επέλυσαν διάφορα ανοιχτά προβλήματα. Δεύτερον, το μοντέλο των παιγνίων συμφόρησης, το οποίο έχει μελετηθεί ανεξάρτητα από το προηγούμενο μοντέλο (που αποτελεί υποπερίπτωση παιγνίου συμφόρησης) και το οποίο μπορεί να μοντελοποιήσει καταστάσεις δρομολόγησης κίνησης μέσα σε δίκτυα χρηστών ή καταστάσεις όπου οι χρήστες δεσμεύουν τους πόρους κάποιου συστήματος. Τέλος, το τρίτο μοντέλο είναι ένα μοντέλο απειροστής ροής, που έχει μελετηθεί κυρίως από τους Roughgarden και Tardos, ως η μη-ατομική επέκταση των παιγνίων συμφόρησης. Για κάθε μοντέλο που μελετάμε, εξετάζουμε δύο βασικά θέματα: αυτό της ύπαρξης και της υπολογισιμότητας των ισορροπιών Nash και αυτό των φραγμάτων για το τίμημα της αναρχίας, που ουσιαστικά ποσοτικοποιεί τις απώλειες που έχουμε λόγω της ιδιοτελούς συμπεριφοράς των χρηστών.