Αναλυση Τιμηματος Της Αναρχιας Σε Συνδυαστικες Δημοπρασιες

Abstract

Το Τιμημα της Αναρχιας οριζεται ως ο λογος του κοστους της χειροτερης ισορροπιας Nash προς την καλυτερη δυνατη εκβαση του στρατηγικου παιγνιου και χρησιμοποιει- ται για την μοντελοποιηση της αποδοσης ενος παιγνιου. Σε πολλα περιβαλοντα εχουν βρεθει ανω και κατω φραγματα για το Τιμημα της Αναρχιας. Θα παρουσιασουμε μια θεωρια η οποια χαρακτηριζει παιγνια με καποια ευρωστια στη δομη τους, η οποια επι- τρεπει τον υπολογισμο τετοιων φραγματων (καποιες φορες με ακριβεια) με πιο χαλαρες προυποθεσεις ως προς τον ορισμο της ισορροπιας στην οποια θα φτασουν οι παιχτες . Στη συνεχεια, θα δειξουμε πως εφαρμοζεται αυτη η θεωρια στις Δημοπρασιες, ε- πιτρεποντας μας να κανουμε προβλεψεις ανω φραγματων σε καταστασεις που οι ιδιοι παιχτες συμμετεχουν σε πολλες δημοπρασιες ταυτοχρονα. Τελος θα παρουσιασουμε και μια θεωρια η οποια χρησιμοποιει αποτελεσματα απο Computational Complexity και Communication Complexity για να δωσει κατω φραγματα στο Τιμημα της Αναρχιας, συμπληρωνοντας την αναλυση που εγινε για τα ανω φραγματα.