Please use this identifier to cite or link to this item:
Title: Μελέτη της απόδοσης μηχανισμών κατανομής διαιρέσιμων πόρων
Other Titles: On the efficiency of divisible resource allocation mechanisms
Authors: Βουδούρης, Αλέξανδρος Ανδρέας
Issue Date: 2015-03-12
Keywords: Μηχανισμός αναλογικής κατανομής
Συσχετιζόμενη ισορροπία
Ισορροπία κατά Bayes-Nash
Μοντέλο ελλιπούς πληροφόρησης
Κόστος της Αναρχίας
Keywords (translated): Proportional allocation mechanism
Coarce-correlated equilibrium
Bayes-Nash equilibrium
Incomplete information setting
Price of Anarchy
Abstract: Στην παρούσα μεταπτυχιακή διπλωματική εργασία χρησιμοποιούμε έννοιες και εργαλεία της Θεωρίας Παιγνίων με σκοπό να μελετήσουμε την απόδοση μηχανισμών κατανομής διαιρέσιμων πόρων εστιάζοντας κυρίως στον μηχανισμό αναλογικής κατανομής. Σύμφωνα με αυτόν τον μηχανισμό, ένα σύνολο χρηστών ανταγωνίζονται για ένα διαιρέσιμο πόρο -- όπως το εύρος ζώνης ενός τηλεπικοινωνιακού καναλιού -- υποβάλλοντας προσφορές. Ο μηχανισμός κατανέμει σε κάθε χρήστη ένα μέρος του πόρου το οποίο είναι ανάλογο της προσφοράς του και συλλέγει ένα ποσό ίσο με την προσφορά αυτή ως πληρωμή. Οι χρήστες στοχεύουν στη μεγιστοποίηση της ωφέλειας τους και συμπεριφέρονται στρατηγικά αλλάζοντας τις προσφορές τους με σκοπό να το πετύχουν. Έτσι, ο μηχανισμός ορίζει ένα παιχνίδι αναλογικής κατανομής. Παρουσιάζουμε γνωστά αποτελέσματα από τη σχετική βιβλιογραφία καθώς και νέα βελτιωμένα φράγματα για το κόστος της αναρχίας ως προς το κοινωνικό όφελος για συσχετιζόμενες ισορροπίες στο μοντέλο πλήρους πληροφόρησης και για ισορροπίες κατά Bayes-Nash στο μοντέλο ελλιπούς πληροφόρησης. Πιο συγκεκριμένα, παρουσιάζουμε ένα κάτω φράγμα 1/2 για το κόστος της αναρχίας ως προς τις προαναφερθείσες έννοιες ισορροπίας, βελτιώνοντας σημαντικά το προηγούμενο καλύτερο κάτω φράγμα 26.8% που πρόσφατα απέδειξαν οι Syrgkanis και Tardos (STOC 2013). Επίσης, μελετάμε για πρώτη φορά τη περίπτωση όπου οι χρήστες διαθέτουν περιορισμένους προϋπολογισμούς και παρουσιάζουμε ένα κάτω φράγμα περίπου 36% και ένα άνω φράγμα 50% για το κόστος της αναρχίας χρησιμοποιώντας ως αντικειμενική συνάρτηση το αποτελεσματικό όφελος το οποίο λαμβάνει υπόψη προϋπολογισμούς.
Abstract (translated): In 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.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
thesis_voudouris.pdf250.87 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.