Ανάλυση τιμήματος της αναρχίας σε συνδυαστικές δημοπρασίες - Λάζος, Φίλιππος (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, 2015)
Το Τίμημα της Αναρχίας ορίζεται ως ο λόγος του κόστους της χειρότερης ισορροπίας Nash προς την καλύτερη δυνατή έκβαση του στρατηγικού παιγνίου και χρησιμοποιεί- ται για την μοντελοποίηση της απόδοσης ενός παιγνίου. Σε πολλά περιβάλοντα έχουν βρεθεί άνω και κάτω φράγματα για το Τίμημα της Αναρχίας. Θα παρουσιάσουμε μια θεώρια η οποία χαρακτηρίζει παίγνια με κάποια ευρωστία στη δομή τους, η οποία επι- τρέπει τον υπολογισμό τέτοιων φραγμάτων (κάποιες φορές με ακρίβεια) με πιο χαλαρές προυποθέσεις ως προς τον ορισμό της ισορροπίας στην οποία θα φτάσουν οι παίχτες . Στη συνέχεια, θα δείξουμε πως εφαρμόζεται αυτή η θεωρία στις Δημοπρασίες, ε- πιτρέποντας μας να κάνουμε προβλέψεις άνω φραγμάτων σε καταστάσεις που οι ίδιοι παίχτες συμμετέχουν σε πολλές δημοπρασίες ταυτόχρονα. Τέλος θα παρουσιάσουμε και μια θεωρία η οποία χρησιμοποιεί αποτελέσματα από Computational Complexity και Communication Complexity για να δώσει κάτω φράγματα στο Τίμημα της Αναρχίας, συμπληρώνοντας την ανάλυση που έγινε για τα άνω φράγματα.