| Abstract : | The last decades, auctions played a significant role in the allocation of both public and private goods. Companies like Google implement auctions to allocate advertisement slots while platforms such as eBay also use them for online sales.Auctions are applicable in various cases such as spectrum allocation, airspace system allocation and allocation of financial products. Therefore, their popularity and their extensive use by governments as well as businesses made research around auctions imperative. The research focuses on studying characteristics of auctions such as transparency, truthfulness and maximization of social welfare and revenue.Combinatorial auctions are a type of auctions, which allows the participants to place package bids i.e. to submit bids on combinations of items and not just on individual items. Research around combinatorial auctions has been popular during the last fifteen years as there have been numerous applications such as truckload transportation, bus routes and radio spectrum allocation. Nevertheless, combinatorial auctions come with their challenges, because computing the allocation and the payments to the bidders are computationally hard problems in general.The purpose of this thesis is to focus mainly on the class of knapsack auctions and compare VCG and the so-called ”core-selecting auctions” performance in that setting. On the one hand, the celebrated VCG mechanism is an extension of the second-price sealed-bid auction or Vickrey auction. On the other hand, core-selecting auctions select an allocation and a pricing rule in a way that no coalition of participants, including the auctioneer, have incentives to deviate and achieve a better outcome. Furthermore, the concern about computational tractability remains unresolved in some scenarios. Hence, our focus is on evaluating the performance of VCG and core-selecting auctions in the knapsack setting by simulations, with respect to criteria such as generated revenue, computational complexity and social welfare.
Τις τελευταίες δεκαετίες, οι δημοπρασίες διαδραμάτισαν σημαντικό ρόλο σε αγοραπωλησίες τόσο δημόσιων όσο και ιδιωτικών αγαθών. Εταιρείες όπως η Google υλοποιούν δημοπρασίες για να διαθέσουν διαφημιστικό χώρο ενώ πλατφόρμες όπως το eBay τις χρησιμοποιούν για διαδικτυακές πωλήσεις. Οι δημοπρασίες έχουν εφαρμογή σε διάφορες περιπτώσεις, όπως στην διαχείριση εφοδιαστικής αλυσίδας και στα δρομολόγια των λεωφορείων. Η εκτεταμένη χρήση τους από κυβερνήσεις καθώς και από επιχειρήσεις κατέστησε την έρευνα γύρω από τις δημοπρασίες επιτακτική. Η έρευνα επικεντρώνεται στη μελέτη χαρακτηριστικών των δημοπρασιών όπως η διαφάνεια, η φιλαλήθεια και η μεγιστοποίηση του κοινωνικού οφέλους και των εσόδων.Οι συνδυαστικές δημοπρασίες είναι ένας τύπος δημοπρασιών, ο οποίος επιτρέπει στους συμμετέχοντες να καταθέσουν προσφορές για συνδυασμούς προϊόντων και όχι μόνο για μεμονωμένα προϊόντα. Η έρευνα γύρω από τις συνδυαστικές δημοπρασίες είναι δημοφιλής τα τελευταία δεκαπέντε χρόνια, καθώς έχουν πολυάριθμες εφαρμογές. Ωστόσο, οι συνδυαστικές δημοπρασίες συνοδεύονται από προκλήσεις, επειδή ο υπολογισμός της ανάθεσης και των πληρωμών συνιστά δύσκολο υπολογιστικά πρόβλημα. Σκοπός αυτής της εργασίας είναι να μελετηθεί κυρίως η κατηγορία των knapsack δημοπρασιών και να συγκριθεί η απόδοση του VCG με τις "core-selecting" δημοπρασίες. Από τη μία πλευρά, ο μηχανισμός VCG αποτελεί επέκταση της δημοπρασίας δεύτερης τιμής (Vickrey). Από την άλλη πλευρά, οι core-selecting δημοπρασίες υπολογίζουν την ανάθεση και τις πληρωμές με τέτοιο τρόπο ώστε καμία ομάδα από τους συμμετέχοντες να μην έχει κίνητρο να αποκλίνει για να επιτύχει καλύτερα αποτελέσματα. Επομένως, η παρούσα διπλωματική εργασία εστιάζει στην αξιολόγηση της απόδοσης των VCG και core-selecting δημοπρασιών στην περίπτωση των knapsack δημοπρασιών με κριτήρια όπως τα συνολικά έσοδα, η υπολογιστική πολυπλοκότητα και το κοινωνικό όφελος.
|
|---|
Copyright © 2013 Library AUEB. All rights reserved.