Τεχνικές για Ανακατανομή του Φάσματος Ραδιοσυχνοτήτων

Abstract

Οι δημοπρασίες, είναι ένας μεγάλος τομέας οικονομίας και ένας τομέας έρευνας για πολλούς σπουδαίους οικονομολόγους και μηχανικούς. Συναντάμε δημοπρασίες σε απλές μορφές στον κόσμο εδώ και χιλιάδες χρόνια, ωστόσο πλέον είναι πολύ μεγάλο μέρος της οικονομίας καθώς “κυβερνούν” αποκλειστικά ορισμένες αγορές. Η αγορά ραδιοφάσματος είναι μία από αυτές τις αγορές. Από το 1994 το φάσμα κατανέμεται στις περισσότερες χώρες του κόσμου μέσω δημοπρασιών. Υπήρξαν πολλές δημοπρασίες φάσματος σε όλο τον κόσμο, διαφορετικών μορφών, κάποιες επιτυχημένες και άλλες αποτυχημένες. Η θεωρία των δημοπρασιών και ο σχεδιασμός μηχανισμών που τις υλοποιούν έχουν συνεισφέρει πολύ όσο αναφορά τις δημοπρασίες φάσματος, προκειμένου να κατανέμεται το φάσμα με τον “καλύτερο” δυνατό τρόπο. Η πιό συνηθισμένη μορφή δημοπρασίας μέχρι τώρα ήταν αυτή της δεύτερης-τιμής. Ωστόσο η τελευταία λέξη της τεχνολογίας σε ότι αφορά τις δημοπρασίες φάσματος, είναι της αναβαλλόμενης αποδοχής. Επειδή ο χώρος του φάσματος είναι πεπερασμένος, οι χώρες πρέπει να βρουν έναν τρόπο για να “δημιουργήσουν” περισσότερο χώρο για τις κορυφαίες τεχνολογίες του σήμερα. Ένας προφανής τρόπος είναι να πάρουν πίσω το χώρο που είχε δοθεί στο παρελθόν σε τηλεοπτικούς σταθμούς και να τον εκχωρήσουν ξανά σε ασύρματες υπηρεσίες. Αυτό μπορεί να ακούγεται εύκολο, αλλά είναι ακριβώς το αντίθετο στην πράξη. Όπως αναφέραμε παραπάνω, έχουν πραγματοποιηθεί πολλές δημοπρασίες φάσματος από το 1994. αλλά δεν υπήρξε ποτέ δημοπρασία φάσματος για την ανακατανομή αυτού, έως το 2016. Η δημοπρασία, Incentive Auction του FCC το 2016 ήταν η πρώτη και ακόμη μόνο δημοπρασία που πέτυχε αυτό το δύσκολο έργο. Η αποστολή της δημοπρασίας ήταν να αγοράστουν πρώτα τα δικαιώματα από τηλεοπτικούς σταθμούς που θέλουν να συμμετάσχουν, στη συνέχεια να γίνει η ανακατανομή των υπόλοιπων τηλεοπτικών σταθμών σε ένα “μικρότερο” χώρο στο φάσμα και, τέλος, να δημιουργηθούν και να πωληθούν νέες άδειες χρήσης στον χώρο που δημιουργήθηκε σε επιχειρήσεις ασύρματων υπηρεσιών. Η ανακατανομή των εναπομείναντων τηλεοπτικών σταθμών σε ”μικρότερο” χώρο στο φάσμα, είναι το Stations Repacking Problem, και είναι NP-Complete πρόβλημα, γενικεύοντας το Graph-Coloring που είναι επίσης NP-Complete. Έτσι, για να εφαρμοστεί επιτυχώς αυτή η δημοπρασία, υπήρχε επίσης ανάγκη να λυθεί αυτό το πρόβλημα βέλτιστα. Σε αυτή τη διπλωματική εργασία, θα εισάγουμε πρώτα κάποιες βασικές αρχές στη θεωρία των δημοπρασιών και το σχεδιασμό των κατάλληλων μηχανισμών. Το κάνουμε αυτό με σκοπό να κατανοήσουμε σε βάθος την ιδέα και την ακριβή διαδικασία της δημοπρασίας αυτής και της σύνδεσής της με το πρόβλημα της ανακατανομής των τηλεοπτικών σταθμών. Η συμβολή μας σε αυτή την εργασία, είναι να προσπαθήσουμε να δημιουργήσουμε το δικό μας εργαλείο επίλυσης του προβλήματος επανακατανομής των σταθμών χρησιμοποιώντας ένα framework της Google - το OR-TOOLS. Θα συγκρίνουμε το εργαλείο επίλυσης με το αρχικό που χρησιμοποιήθηκε, καθώς είναι ένα εργαλείο επίλυσης ανοιχτού κώδικα, και θα μελετήσουμε τη βελτιστοποίηση του και την επίπτωση αυτού του εργαλείου επίλυσης σε όλη τη διαδικασία της δημοπρασίας.