Τα τελευταία χρόνια οι δημοπρασίες έχουν γίνει όλο και περισσότερο σημαντικές στον τομέα των multiagent συστημάτων ως χρήσιμοι μηχανισμοί για τη διανομή των πόρων, την ανάθεση καθηκόντων και το ηλεκτρονικό εμπόριο. Σε πολλές περιπτώσεις η δημοπρασία Vickrey (ασφαλής προσφορά δεύτερης τιμής) χρησιμοποιείται ως ένα πρωτόκολλο το οποίο καθορίζει πως οι διάφοροι ανεξάρτητοι αντιπρόσωποι (agents) πρέπει να αλληλεπιδράσουν με σκοπό να φτάσουν σε συμφωνία. Οι κύριοι λόγοι επιλογής του πλειστηριασμού Vickrey είναι η ύπαρξη μιας κυρίαρχης στρατηγικής ισορροπίας, το μικρό εύρος ζώνης και η κατανάλωση χρόνου εξαιτίας του μόλις ενός γύρου προσφοράς και της (θεωρητικής) μυστικότητας των προσφορών. Η παρούσα εργασία αναφέρει λεπτομερώς ιδιότητες οι οποίες είναι απαραίτητες για να διαβεβαιώσουν την ακριβή και μυστική εκτέλεση των πλειστηριασμών Vickrey και προβάλει μια κατηγοριοποίηση διαφορετικών μορφών συνομωσιών. Προσεγγίζουμε τις δύο σημαντικότερες δραστηριότητες του πλειστηριασμού Vickrey ως εξής: στην τρωτότητα ενός ψεύτη πλειστηριαστή και την απροθυμία αυτών που υποβάλλουν τις προσφορές (συμμετεχόντων στη δημοπρασία) να αποκαλύψουν την προσωπική τους εκτίμηση. Τότε, προτείνουμε μία καινούρια τεχνική η οποία επιτρέπει την εκπλήρωση με ασφάλεια δημοπρασιών δεύτερης τιμής (second-price). Κάτι τέτοιο επιτυγχάνεται με την αναγγελία κρυπτογραφημένων δυαδικών λιστών προσφορών σε έναν πίνακα. Τεχνικές αναζήτησης όπως top-down, bottom-up και δυαδική χρησιμοποιούνται για να βρεθεί βήμα-βήμα με αλληλεπίδραση η δεύτερη μεγαλύτερη προσφορά, χωρίς να αποκαλυφθούν περιττές πληροφορίες.
Η περιοχή των multiagent συστημάτων, η οποία αφορά συστήματα τα οποία αποτελούνται από τεχνικές οντότητες οι οποίες ονομάζονται agents και αλληλεπιδρούν και κατά μία έννοια μπορούμε να πούμε ότι είναι έξυπνες και αυτόνομες, τα τελευταία χρόνια έχει εγείρει την προσοχή όλο και περισσότερων ερευνητών. Το ηλεκτρονικό εμπόριο, η αυτόματη κατανομή των πόρων και η ανάθεση δραστηριοτήτων είναι θέματα με μεγάλο ενδιαφέρον στην κοινωνία των agent. Καθώς οι δημοπρασίες είναι πολύ ευέλικτα και αποτελεσματικά εργαλεία τα οποία μπορούν να χρησιμοποιηθούν για να δηλώσουν αυτά τα προβλήματα, αποτελεί κοινή πρακτική να χρησιμοποιούμε πολύ γνωστά αποτελέσματα και γνώσεις της θεωρίας πλειστηριασμών και πλήρως κατανοητά πρωτόκολλα δημοπρασίας όπως η αγγλική δημοπρασία, η εκπτωτική δημοπρασία και η δημοπρασία Vickrey. Μεταξύ των διαφόρων πρωτοκόλλων, η δημοπρασία Vickrey (αλλιώς γνωστή ως second-price δημοπρασία ασφαλούς προσφοράς) έχει αποσπάσει ιδιαίτερη προσοχή εντός της multiagent κοινωνίας εξαιτίας τριών κυρίως χαρακτηριστικών:
- Απαιτεί μικρό εύρος ζώνης και κατανάλωση χρόνου
- Κατέχει μία κυρίαρχη στρατηγική στην προσφορά της αληθινής αξιολόγησης κάποιου
- Αποτελεί δημοπρασία ασφαλούς προσφοράς, οι προσφορές (οι οποίες εκφράζουν ιδιωτικές τιμές) παραμένουν μυστικές
Αυτά τα χαρακτηριστικά κάνουν το Vickrey πρωτόκολλο δημοπρασίας να έχει ιδιαίτερη απήχηση από τη σκοπιά του αυτοματισμού. Η δημοπρασία Vickrey, στην αρχική της μορφή και όπως χρησιμοποιείται για την πώληση αγαθών ή την κατανομή των πόρων, δουλεύει ως εξής: κάθε ένας κάνει μια ασφαλή προσφορά εκφράζοντας το ποσό το οποίο είναι πρόθυμος να πληρώσει και αυτός που υποβάλλει τη μεγαλύτερη προσφορά κερδίζει τη δημοπρασία. Το ποσό το οποίο θα καταβληθεί από το νικητή είναι ίσο με τη δεύτερη μεγαλύτερη προσφορά. Σε σενάρια ανάθεσης δραστηριοτήτων, η Vickrey δημοπρασία δουλεύει ακριβώς αντίθετα (και γι’ αυτό το λόγο συχνά αναφέρεται ως ανάστροφη δημοπρασία Vickrey): καθένας που είναι πρόθυμος να φέρει σε πέρας μια δραστηριότητα υποβάλλει μια προσφορά εκφράζοντας το ποσό το οποίο επιθυμεί αυτός να πληρωθεί για την ολοκλήρωση της δραστηριότητας. Ο νικητής λαμβάνει ένα ποσό ίσο με τη δεύτερη χαμηλότερη προσφορά (και η πληρωμή του είναι η δεύτερη χαμηλότερη προσφορά μείον το βασικό κόστος για την ολοκλήρωση της δραστηριότητας). Αν υπάρχουν περισσότερες από μία νικήτριες προσφορές, ο τελικός νικητής ανακηρύσσεται τυχαία (ένας από αυτούς με τη χαμηλότερη προσφορά). Καθώς η τυπική και η ανάστροφη δημοπρασία είναι πλήρως αναλογικές, όλες οι παρουσιαζόμενες θεωρήσεις και τεχνικές αφορούν και τους δύο τύπους της Vickrey δημοπρασίας.
Παρ’ όλες τις εντυπωσιακές θεωρητικές της ιδιότητες, η Vickrey δημοπρασία σπανίως χρησιμοποιείται στην πράξη. Αυτό το πρόβλημα έχει παρουσιαστεί πολλές φορές και είναι αδιαφιλονίκητο γεγονός ότι η σπανιότητα χρήσης της Vickrey δημοπρασίας οφείλεται σε δύο βασικούς λόγους. Πρώτος λόγος είναι ότι η αξιοπρεπής εκτέλεση της Vickrey δημοπρασίας εξαρτάται από την τιμιότητα του πλειστηριαστή. Αυτός που υποβάλει τη μεγαλύτερη προσφορά πρέπει να εμπιστεύεται τον πλειστηριαστή όταν αυτός ανακοινώνει τη δεύτερη μεγαλύτερη προσφορά. Υπάρχει μεγάλος κίνδυνος ενός ανειλικρινούς πλειστηριαστή ο οποίος να μεγαλώνει τη δεύτερη μεγαλύτερη προσφορά με σκοπό να κερδίσει περισσότερα χρήματα (για τον εαυτό του ή για τον πελάτη του, τον πωλητή). Δεύτερος λόγος είναι ότι αυτοί που υποβάλλουν μια προσφορά είναι συνήθως απρόθυμοι να αποκαλύψουν τις αληθινές προσωπικές τιμές όπως απαιτείται από την κυρίαρχη στρατηγική. Σε πολλά σενάρια οι δημοπρασίες δεν είναι απομονωμένα γεγονότα, αλλά τμήματα μιας σειράς διαπραγματεύσεων. Η τιμολόγηση αγαθών ή δραστηριοτήτων είναι ευαίσθητες πληροφορίες τις οποίες οι agents σκοπεύουν να κρατήσουν ιδιωτικές. Ακόμα και αν η μεταφορά ασφαλών προσφορών είναι πλήρως προστατευμένη με τεχνικές κρυπτογραφίας, παραμένει άγνωστο πως ο πλειστηριαστής μεταχειρίζεται αυτές τις εμπιστευτικές πληροφορίες. Η μυστικότητα ασφαλών προσφορών είναι επίσης σημαντικό θέμα στους κανονικούς πλειστηριασμούς πρώτης τιμής (first-price), αλλά πολλές φορές είναι περισσότερο σημαντικό στους πλειστηριασμούς δεύτερης τιμής (second-price) αφού οι προσφορές αναπαριστούν μη εναλλακτικές ιδιωτικές τιμές. Η συγκεκριμένη εργασία παρουσιάζει επίσης την κρίσιμη αδυναμία της δημοπρασίας Vickrey. Παρουσιάζουμε μια τεχνική η οποία βεβαιώνει την αδυναμία του πλειστηριαστή να διαχειριστεί την κατάληξη της δημοπρασίας και επεξηγούμε μεθόδους οι οποίες μειώνουν στο ελάχιστο τη γνώση του πλειστηριαστή σχετικά με τις προσφορές με σκοπό να αδυνατίσουν τη θέση του για συνωμοτικές συμφωνίες.
Η παρούσα εργασία δομείται ως εξής: Το τμήμα 2 συνοψίζει τις υπάρχουσες προσπάθειες στον τομέα των ασφαλών Vickrey δημοπρασιών και εξηγεί γιατί περιορίζουμε τους εαυτούς μας σε έναν μοναδικό πλειστηριαστή. Το τμήμα 3 ερμηνεύει ζωτικά χαρακτηριστικά τα οποία βεβαιώνουν μια ομαλή διαδικασία πλειστηριασμού και καθορίζει σημαντικούς τύπους συνωμοσιών. Η θεμελίωση του νέου πρωτοκόλλου ασφαλούς πλειστηριασμού παρουσιάζεται στο τμήμα 4 και το τμήμα 5 παρουσιάζει και αναλύει τρεις μεθόδους οι οποίες κρύβουν πληροφορίες τις οποίες δεν χρειάζεται ο πλειστηριαστής. Τέλος, στο τμήμα 6 παρουσιάζονται τα πλεονεκτήματα και τα μειονεκτήματα της προτεινόμενης μεθόδου.
Link me
Follow me
Join me
