Καταστάσεις Ισορροπίας Σε Μοντέλα Παιγνίων Συμφόρησης: Ύπαρξη, Πολυπλοκότητα Και Απόδοση

Abstract

Το δεύτερο ερώτημα με το οποίο ασχολούμαστε είναι η πολυπλοκότητα υπολογισμού μιαςΑμιγούς Ισορροπίας \tl{NASH} σε Παίγνια Συμφόρησης. Παραθέτουμε,τα σημαντικότερααποτελέσματα των τελευταίων ετών στο πεδίο αυτό. Επιπλέον, εξάγουμε και κάποια νέααποτελέσματα πολυπλοκότητας, που υποδεικνύουν τη δυσκολία υπολογισμού αμιγούς ισορροπίας\tl{NASH} σε ένα μοντέλο παραπλήσιο με τα παίγνια συμφόρησης.Τέλος, εξετάζουμε την απόδοση της ισορροπίας \tl{NASH} υπό το πρίσμα κάποιας συνάρτησηςκοινωνικού κόστους. Παρουσιάζουμε, αποτελέσματα για το τίμημα της αναρχίας σε ορισμέναενδιαφέροντα μοντέλα παιγνίων συμφόρησης. Παράλληλα προτεί- νουμεένα νέο μοντέλο για την περιγραφή σνυθηκών ιδιοτελούς δρομολόγησης και ανάθεσης μηκώνκύματος σε πολυνηματικά οπτικά δίκτυα, για το οποίο υπολογίζουμε επακριβώς το τίμημα τηςαναρχίας για διαισθητικά χρήσιμες συναρτήσεις κοινωνικού κόστους.