Παιγνιοθεωρητική ανάλυση δικτύων

Abstract

Algorithmic mechanism design is an important area between computer science and economics. One of the most fundamental problems in this area is the problem of scheduling unrelated machines to minimize the makespan. The machines behave like selfish players: they have to get paid in order to process the tasks, and would lie about their processing times if they could increase their utility in this way. The problem was proposed and studied in the seminal paper of Nisan and Ronen, where it was shown that the approximation ratio of mechanisms is between 2 and n. In this thesis, we present some recent improvements of the lower bound to 1 + ?2 for three or more machines and to 1 + φ for many machines. Since the gap between the lower bound of 2.618 and the upper bound of n is huge, we also propose an alternative approach to the problem, which first attempts to characterize all truthful mechanisms and then study their approximation ratio. Towards this goal, we show that the class of truthful mechanisms for two players (regardless of approximation ratio) is very limited: tasks can be partitioned in groups allocated by affine minimizers (a natural generalization of the wellknown VCG mechanism) and groups allocated by threshold mechanisms. Finally we generalize a tool we have used in the proof of the 1 + ?2 lower bound: we give a geometrical characterization of truthfulness for the case of three tasks, which we believe that might be useful for proving improved lower bounds and which provides a more complete understanding of truthfulness.

Η Αλγοριθμική Σχεδίαση Μηχανισμών είναι μια σημαντική περιοχή μεταξύ της επιστήμης των υπολογιστών και της οικονομικής θεωρίας. ΄Ενα από τα σημαν- τικότερα προβλήματα της περιοχής αυτής είναι το πρόβλημα του χρονοπρογραμ- ματισμού ασυσχέτιστων μηχανών με σκοπό την ελαχιστοποίηση του χρόνου που δουλεύει η μηχανή που τελειώνει τελευταία. Οι μηχανές συμπεριφέρονται σαν εγ- ωιστές παίκτες : θέλουν να πληρωθούν για να εκτελέσουν τις εργασίες και είναι δι- ατεθημένες να δηλώσουν ψευδείς χρόνους εκτέλεσης εάν με αυτό τον τρόπο μπορούν να αυξήσουν την ωφέλειά τους. Το πρόβλημα αυτό προτάθηκε και μελετήθηκε στην πολύ σημαντική δημοσίευση των Nisan και Ronen, που θεμελίωσε τον κλάδο της Αλγοριθμικής Σχεδίασης Μηχανισμών, όπου έδειξαν ότι ο λόγος προσέγγισης για το πρόβλημα είναι μεταξύ 2 και n. Στην παρούσα διατριβή παρουσιάζουμε βελτιώσεις του κάτω φράγματος σε 1+?2 για την περίπτωση των τριών μηχανών και σε 1 + φ για πολλές μηχανές. Dεδομένου ότι το χάσμα ανάμεσα στο κάτω φράγμα 2.618 και το άνω φράγμα n είναι τεράστιο προτείνουμε μία εναλλακτική προσέγγιση στο πρόβλημα, να χαρακ- τηρίσουμε πρώτα όλους τους δυνατούς μηχανισμούς και κατόπιν να μελετήσουμε τον λόγο προσέγγισής τους. Προς αυτό τον στόχο δείχνουμε ότι η κλάση των φιλαλήθων μηχανισμών για την περίπτωση των δύο παικτών είναι πολύ περιορισμένη: οι εργασίες μπορούν να χωριστούν σε ομάδες που ανατείθονται από αφφινικούς μεγιστοποιητές (που αποτελούν γενίκευση των γνωστών μηχανισμών VCG) και ομάδες που ανατείθονται από μηχανισμούς κατωφλίου. Τέλος γενικεύουμε ένα από τα εργαλεία που χρησιμοποιήσαμε για την απόδειξη του κάτω φράγματος 1+?2 δίνοντας ένα γεωμετρικό χαρακτηρισμό της φιλαλήθειας για την περίπτωση των τριών εργασιών, ο οποίος πιστεύουμε ότι θα είναι χρήσιμος για την απόδειξη νέων κάτω φραγμάτων και που σαφώς οδηγεί σε μια πιο πλήρη κατανόηση της φιλαλήθειας.