Please use this identifier to cite or link to this item:
Title: Μελέτη απλών και αποδοτικών μηχανισμών τιμολόγησης
Other Titles: Study of simple and effective posted pricing mechanisms
Authors: Κερεντζής, Απόστολος
Keywords: Σχεδίαση μηχανισμών
Κατανομή διαιρέσιμου αντικειμένου
Κάτω φράγμα
Κοινωνικός πλούτος
Τριγωνικές κατανομές εισοδήματος
Εκ των προτέρων χαλάρωση
Keywords (translated): Mechanism design
Divisible item allocation mechanism
Lower bound
Social welfare
Ex-ante relaxation
Trinagular distributions
Abstract: Η παρούσα Μεταπτυχιακή Διπλωματική Εργασία, αξιοποιώντας έννοιες και εργαλεία της Σχεδίασης Μηχανισμών, αποσκοπεί στην προσέγγιση ενός βασικού ερωτήματος, της οριοθέτησης της απόκλισης απλών και συνάμα αποδοτικών μηχανισμών, εν συγκρίσει με τους αντίστοιχους βέλτιστους. Η μελέτη εστιάζει στην απόδοση, ως προς το κοινωνικό όφελος και το εισόδημα, του μηχανισμού κατανομής ενός διαιρέσιμου πόρου και συγκεκριμένα ενός μηχανισμού με γραμμικό κανόνα πληρωμής. Βάσει αυτού, χρησιμοποιείται μια σταθερή τιμή p ανά μονάδα προϊόντος και n υποψήφιοι αγοραστές εκδηλώνουν σταδιακά την αποτίμηση τους. Στο μοντέλο ελλιπούς πληροφόρησης που περιγράφουμε, ο κάθε αγοραστής i επιλέγει την αποτίμηση του τυχαία και ανεξάρτητα από τους ανταγωνιστές του, από μια πιθανοτική κατανομή Fi πάνω σε συνεχείς, κοίλες, και μη φθίνουσες συναρτήσεις στο [0,1]. Η αλληλουχία με την οποίο ο μηχανισμός παίρνει στην είσοδο του τις αποτιμήσεις των αγοραστών είναι ουσιώδης για το κάτω φράγμα του κοινωνικού οφέλους, ενώ αντίθετα δεν λαμβάνεται υπόψη για τους υπολογισμούς του αντίστοιχου ορίου του εισοδήματος. Στο πλαίσιο της Εργασίας μελετήθηκαν και παρουσιάζονται μηχανισμοί πώλησης μη διαιρέσιμων αντικειμένων παραθέτοντας εκτενώς τεχνικές όπως η ανισότητα του Προφήτη και γνωστά αποτελέσματα από τη σχετική πλούσια βιβλιογραφία. Με κατάλληλες τροποποιήσεις εξάγονται (ενδεχομένως για πρώτη φορά) αντίστοιχα φράγματα μηχανισμών κατανομής και για το διαιρέσιμο αντικείμενο. Πιο συγκεκριμένα, παρουσιάζουμε ένα κάτω φράγμα 31,78% για τον κοινωνικό πλούτο, όριο το οποίο δύναται να αυξηθεί σε 41,9% με τυχαία αναδιάταξη των υποψήφιων αγοραστών. Όσον αφορά το εισόδημα, γίνεται αξιοποίηση των εννοιών της εκ των προτέρων χαλάρωσης του περιορισμού υλοποίησης (ως ένα ιδεατό φράγμα) που ορίζει πως θα διατεθεί το πολύ ένα αντικείμενο με βάση τις εκτιμώμενες αποτιμήσεις και ενός μαθηματικού προγράμματος, ανάλογου του προγράμματος των Alaei et al. [1]. Με το πρόγραμμα αυτό συγκρίνεται εν τέλει ο γραμμικός μηχανισμός τιμολόγησης με τον ex-ante βέλτιστο. Μέσα από μια σειρά Λημμάτων και ενός κατάλληλου παραδείγματος, καταλήγουμε τέλος ότι η απόκλιση των μηχανισμών εκτιμάται μεταξύ Ω(lnα) και O(α^2), όπου α ορίζεται ως ο λόγος v'(0)/v(1).
Abstract (translated): In this Master Thesis, using notions and techniques from Mechanism Design, we are trying to approach the answer of a fundamental question: How much revenue can the simple and efficient posted pricing mechanism guarantee, compared to the optimal yet complicated mechanism? Here, we analyze the performance, subject to social welfare and revenue, of a special case of divisible resource mechanisms, the one with linear pricing rule. According to this model, a static price per unit p is used and n agents with ordering π gradually, one after the other, reveal their valuation function for the item. In the incomplete information setting we describe, every agent i draws, independently from other agents, from a publicly known distribution Fi, her valuation function vi : [0,1] -> R≥0, which is continuous, concave and monotone non-decreasing. The order that agents act seems to be of importance for the computation of the lower bound of the social welfare, while it is insubstantial for the corresponding bound in the case of revenue calculation. We cover previously known results from the rich literature related to non-divisible items, as well as present useful techniques like the prophet inequalities which are tight connected with posted pricing Mechanisms. In addition to that, with the right readjustments, we proove, for the first time in our knowledge, new lower bounds for the case of the divisible item. Specifically, in terms of the social welfare, a lower bound equal to 31.78% for the order-oblivious posted pricing model is presented. This bound can get further improoved, by agents’ random rearrangement, to 41.9%. As far as revenue is concerned, we make use the ex-ante relaxation, which relaxes the feasibility constraint to bind in expectation over the random values of the agents (rather than on the values that are realized ex post), which for our case implies that the total amount of units sold must be at most one. Finally, using a mathematical program analogous to the approach of Alaei et al [1], we conclude that the revenue gap between the ex-ante optimal mechanism and the proposed one, is between Ω(ln α) and O(α^2), where α is defined v'(0)/v(1), i.e a measure of curvature of the valuation function agents have.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΜΔΕ)

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