Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/11806
Title: Design and analysis of algorithms for non-cooperative environments
Other Titles: Σχεδιασμός και ανάλυση αλγορίθμων για μη συνεργατικά περιβάλλοντα
Authors: Βουδούρης, Αλέξανδρος Ανδρέας
Keywords: Strategic games
Price of anarchy
Mechanism design
Approximation algorithms
Resource allocation
Opinion formation
Ownership transfer
Asymmetric information
Keywords (translated): Στρατηγικά παιχνίδια
Κόστος της αναρχίας
Σχεδιασμός φιλαληθών μηχανισμών
Προσεγγιστικοί αλγόριθμοι
Κατανομή πόρων
Διαμόρφωση απόψεων
Μεταφορά ιδιοκτησίας
Μη συμμετρική πληροφόρηση
Abstract: This thesis studies issues related to problems that arise in large-scale distributed environments with non-cooperative users, who act strategically and compete with each other to maximize their personal payoffs. For instance, imagine a scenario where a set of users compete over a resource, such as the bandwidth of a communication link or advertisement slots when keywords are queried in search engines on the Internet. A mechanism takes input from all participating users (which represents their preferences) and outputs an allocation of the resource to them (it distributes the bandwidth or assigns slots). Each user aims to select her input to the mechanism in order to satisfy her personal objectives (possibly by misreporting her true preferences), without caring about the social welfare which we would like to maximize as the designers of the mechanism. Therefore, this behavior induces a strategic game among the users who act as players and sequentially change their strategies until they reach an equilibrium state (if one exists) from which no one has any incentive to deviate. Due to the strategic behavior of the users, the equilibrium that is reached may be of low quality in terms of some objective function like the social welfare, compared to what could happen if a central authority dictated the strategies of the users. The price of anarchy and stability are two quantification measures of this kind of inefficiency at equilibrium. Our main goal in this thesis is to understand the advantages and constraints of the strategic games that arise in non-cooperative environments as means of computation. What can they compute and how well can they compute it? Is it possible to alter the rules of the game and incentivize the players to truthfully report their preferences? We answer to such questions related to equilibrium computation, price of anarchy and stability estimation, and truthful mechanism design for many interesting and important classes of problems. In particular, we study resource allocation with budget constraints, opinion formation, ownership transfer with expert advice, and revenue maximization in randomized combinatorial sales.
Abstract (translated): H παρούσα Διατριβή μελετά προβλήματα που προκύπτουν σε περιβάλλοντα μεγάλης κλίμακας με εγωκεντρικούς χρήστες, οι οποίοι συμπεριφέρονται στρατηγικά και ανταγωνίζονται μεταξύ τους με σκοπό να μεγιστοποιήσουν το ατομικό τους κέρδος. Για παράδειγμα, φανταστείτε ένα σύνολο από χρήστες που ανταγωνίζονται για έναν πόρο, όπως το εύρος ζώνης ενός τηλεπικοινωνιακού καναλιού ή θέσεις διαφήμισης σε αποτελέσματα αναζήτησης στο Διαδίκτυο. Ένας μηχανισμός δέχεται είσοδο από όλους τους χρήστες και παράγει ως έξοδο μια κατανομή του πόρου σε αυτούς. Κάθε χρήστης προσπαθεί να επιλέξει την είσοδο του έτσι ώστε να εξυπηρετήσει τα προσωπικά του συμφέροντα (ενδεχομένως αποκρύπτοντας τις αληθινές του προτιμήσεις), χωρίς να νοιάζεται για το κοινωνικό όφελος το οποίο εμείς επιθυμούμε να μεγιστοποιήσουμε ως σχεδιαστές τους μηχανισμού. Η συμπεριφορά αυτή ορίζει ένα στρατηγικό παιχνίδι μεταξύ των χρηστών οι οποίοι αλλάζουν στρατηγικές μέχρι το παιχνίδι να φτάσει σε κατάσταση ισορροπίας από την οποία κανείς δεν έχει κίνητρο να αποκλίνει. Η ισορροπία ενδέχεται να έχει μικρή απόδοση (σύμφωνα με κάποια αντικειμενική συνάρτηση όπως το κοινωνικό όφελος) σε σχέση με το τι θα μπορούσε να συμβεί αν κάποια κεντρική αρχή διέταζε τους χρήστες για το πως να συμπεριφερθούν. Το κόστος της αναρχίας και της ευστάθειας είναι δύο μετρικές που χρησιμοποιούνται για την ποσοτικοποίηση αυτής της μη-αποδοτικότητας. Κύριος στόχος μας είναι η κατανόηση των δυνατοτήτων καθώς και των περιορισμών των στρατηγικών παιχνιδιών ως μέσα υπολογισμού. Τι μπορούν να υπολογίσουν και πόσα καλά μπορούν να το υπολογίσουν; Είναι δυνατόν να μεταβάλλουμε τους κανόνες του παιχνιδιού έτσι ώστε οι παίκτες να έχουν κίνητρο να λένε πάντα την αλήθεια; Απαντάμε σε τέτοιου είδους ερωτήσεις μελετώντας ζητήματα υπολογισμού ισορροπιών, εκτίμησης κόστους αναρχίας και ευστάθειας, καθώς και σχεδίασης φιλαληθών μηχανισμών για ενδιαφέρουσες και σημαντικές κλάσεις προβλημάτων. Πιο συγκεκριμένα, ασχολούμαστε με προβλήματα ανάθεσης πόρων υπό περιορισμούς προϋπολογισμού, διαμόρφωσης απόψεων σε κοινωνικά δίκτυα, μεταφοράς ιδιοκτησίας, και μεγιστοποίησης εσόδων σε συνδυαστικές αγορές.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)

Files in This Item:
File Description SizeFormat 
phd.thesis.voudouris.pdfPhD thesis1.56 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons