Μελέτη της απόδοσης μηχανισμών κατανομής διαιρέσιμων πόρων

dc.contributor.advisorΚαραγιάννης, Ιωάννης
dc.contributor.authorΒουδούρης, Αλέξανδρος Ανδρέας
dc.contributor.committeeΚαραγιάννης, Ιωάννης
dc.contributor.committeeΚακλαμάνης, Χρήστος
dc.contributor.committeeΝικολετσέας, Σωτήριος
dc.contributor.otherVoudouris, Alexandros Andreas
dc.date.accessioned2015-03-12T10:33:21Z
dc.date.available2015-03-12T10:33:21Z
dc.date.copyright2014-12-16
dc.date.issued2015-03-12
dc.degreeΜεταπτυχιακή Εργασίαel
dc.description.abstractΣτην παρούσα μεταπτυχιακή διπλωματική εργασία χρησιμοποιούμε έννοιες και εργαλεία της Θεωρίας Παιγνίων με σκοπό να μελετήσουμε την απόδοση μηχανισμών κατανομής διαιρέσιμων πόρων εστιάζοντας κυρίως στον μηχανισμό αναλογικής κατανομής. Σύμφωνα με αυτόν τον μηχανισμό, ένα σύνολο χρηστών ανταγωνίζονται για ένα διαιρέσιμο πόρο -- όπως το εύρος ζώνης ενός τηλεπικοινωνιακού καναλιού -- υποβάλλοντας προσφορές. Ο μηχανισμός κατανέμει σε κάθε χρήστη ένα μέρος του πόρου το οποίο είναι ανάλογο της προσφοράς του και συλλέγει ένα ποσό ίσο με την προσφορά αυτή ως πληρωμή. Οι χρήστες στοχεύουν στη μεγιστοποίηση της ωφέλειας τους και συμπεριφέρονται στρατηγικά αλλάζοντας τις προσφορές τους με σκοπό να το πετύχουν. Έτσι, ο μηχανισμός ορίζει ένα παιχνίδι αναλογικής κατανομής. Παρουσιάζουμε γνωστά αποτελέσματα από τη σχετική βιβλιογραφία καθώς και νέα βελτιωμένα φράγματα για το κόστος της αναρχίας ως προς το κοινωνικό όφελος για συσχετιζόμενες ισορροπίες στο μοντέλο πλήρους πληροφόρησης και για ισορροπίες κατά Bayes-Nash στο μοντέλο ελλιπούς πληροφόρησης. Πιο συγκεκριμένα, παρουσιάζουμε ένα κάτω φράγμα 1/2 για το κόστος της αναρχίας ως προς τις προαναφερθείσες έννοιες ισορροπίας, βελτιώνοντας σημαντικά το προηγούμενο καλύτερο κάτω φράγμα 26.8% που πρόσφατα απέδειξαν οι Syrgkanis και Tardos (STOC 2013). Επίσης, μελετάμε για πρώτη φορά τη περίπτωση όπου οι χρήστες διαθέτουν περιορισμένους προϋπολογισμούς και παρουσιάζουμε ένα κάτω φράγμα περίπου 36% και ένα άνω φράγμα 50% για το κόστος της αναρχίας χρησιμοποιώντας ως αντικειμενική συνάρτηση το αποτελεσματικό όφελος το οποίο λαμβάνει υπόψη προϋπολογισμούς.el
dc.description.translatedabstractIn this thesis, we use notions and techniques from Game Theory in order to analyze the performance of divisible resource allocation mechanisms focusing mainly on the proportional allocation mechanism. According to this mechanism, a set of users are competing for a divisible resource -- such as bandwidth of a communication link -- by submitting bids. The mechanism allocates to each user a fraction of the resource that is proportional to the user's bid and collects an amount equal to the bid as payment. Users aim to maximize their individual utility and act strategically in order to achieve their goal. Hence, the mechanism defines a proportional allocation game. We cover previously known results from the related literature and present new bounds on the price of anarchy with respect to the social welfare over coarse-correlated and Bayes-Nash equilibria in the full and incomplete information settings, respectively. In particular, we prove a lower bound of $1/2$ for the price of anarchy over both equilibrium concepts, significantly improving the previously best known lower bound, presented by Syrgkanis and Tardos (STOC 2013). Furthermore, we study for the first time the scenario where users have budget constraints and present lower bounds on the price of anarchy using the effective welfare (which takes budgets into account) as an objective function.el
dc.identifier.urihttp://hdl.handle.net/10889/8413
dc.language.isogrel
dc.rights0el
dc.subjectΜηχανισμός αναλογικής κατανομήςel
dc.subjectΣυσχετιζόμενη ισορροπίαel
dc.subjectΙσορροπία κατά Bayes-Nashel
dc.subjectΜοντέλο ελλιπούς πληροφόρησηςel
dc.subjectΚόστος της Αναρχίαςel
dc.subject.alternativeProportional allocation mechanismel
dc.subject.alternativeCoarce-correlated equilibriumel
dc.subject.alternativeBayes-Nash equilibriumel
dc.subject.alternativeIncomplete information settingel
dc.subject.alternativePrice of Anarchyel
dc.subject.ddc519.3
dc.titleΜελέτη της απόδοσης μηχανισμών κατανομής διαιρέσιμων πόρωνel
dc.title.alternativeOn the efficiency of divisible resource allocation mechanismsel
dc.typeThesisel
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_voudouris.pdf
Size:
250.87 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
5.05 KB
Format:
Item-specific license agreed upon to submission
Description: