Natural and efficient dynamics through convex optimization

Abstract

The subject of this thesis is the use of convex optimization techniques to study the dynamic behavior of the agents’ strategies and the Price of Anarchy in opinion formation games, as well as to design efficient algorithms in computational problems related to opinion selection in time-changing environments. More specifically, the contribution of the thesis is the following:Extension and generalization of the previous results concerning the convergence properties and the Anarchy Price in opinion formation games based on the Friedkin-Johnsen model. These extensions are carried out in two main directions. In the first direction, a generalization of the opinion formation games is examined in which the influences among the agents can be negative (some agents' opinions can be repulsive to others). It turns out that even in this case, the Anarchy Price is upper bounded by a constant independent on the number of the agents participating in the game. At the same time, it turns out that the best response dynamics converge to Nash equilibrium even in cases where the agents admit limited information about the other agents' strategies. In the second direction, we consider a random-payoff variant of the opinion formation games in which the disagreement cost of each agent is a random variable depending on the agent’ s random meetings. The goal of each agent is to appropriately select an opinion (strategy) that minimizes her expected disagreement cost. We present results concerning the convergence rate of the opinions to Nash equilibrium when all agents update their opinion according to the Follow the Leader algorithm. We also present lower bounds on the convergence rate of any update rule that ensures no-regret.We examine two generalizations of the Hegselmann-Krause model. In the first generalization, we consider an undirected graph in which the nodes represent the agents and the edges represent the social relationships among them. At each round, the agents update their opinions to the average of the opinions of their neighbors that are sufficiently close to their own opinion. The model proposed by Hegselmann and Krause is a special case of the above model, when any two agents are socially connected. We prove that that for any graph topology, the agents' opinions are stabilized after a finite number of rounds. In the second extension that we examine, each agent randomly selects a small subset of the other agents and updates her opinion to the average the opinions of the randomly-met agents that are close to her own opinion. We show that even in this case the system converges to a stable point with high probability.We present a polynomial time algorithm for the k-facility reallocation problem. This problem was proposed as a generalization of the classical k-median optimization problem, where the positions of the requests lie on the real line but may change over time. Our algorithm is based on rounding an optimal fractional solution of an appropriate linear program and runs in strongly polynomial time. Our result is a significant improvement over the previous known algorithm, which was exponential in the parameter k.

Το αντικείμενο της διατριβής είναι η χρήση τεχνικών κυρτής βελτιστοποίησης για την μελέτη της δυναμικής συμπεριφοράς των στρατηγικών και του Τιμήματος της Αναρχίας σε ανταγωνιστικά παίγνια διαμόρφωσης άποψης, καθώς και για το σχεδιασμό αποδοτικών αλγορίθμων σε υπολογιστικά προβλήματα που σχετίζονται με την επιλογή απόψεων σε χρονικώς μεταβαλλόμενα περιβάλλοντα. Πιο συγκεκριμένα, η συμβολή της διατριβής εντοπίζεται στα εξής:Επέκταση και γενίκευση γνωστών αποτελεσμάτων για τις ιδιότητες σύγκλισης σε ισορροπία Nash καθώς και των άνω φραγμάτων για το Τίμημα της Αναρχίας σε παίγνια διαμόρφωσης άποψης βασιζόμενα στο μοντέλο Friedkin-Johnsen. Οι επεκτάσεις αυτές πραγματοποιούνται σε δύο βασικές κατευθύνσεις. Στην πρώτη κατεύθυνση εισάγεται και μελετάται μία γενίκευση των παιγνίων διαμόρφωσης άποψης στην οποία οι επιδράσεις μεταξύ των παικτών μπορεί να αρνητικές (βλ. οι απόψεις κάποιων παικτών να λειτουργούν απωθητικά για τους υπόλοιπους). Αποδεικνύεται πως ακόμα και σε αυτή την περίπτωση, το Τίμημα της Αναρχίας φράσσεται άνω από μία σταθερά ανεξάρτητη του αριθμού των παικτών που συμμετέχουν στο παίγνιο. Παράλληλα αποδεικνύεται πως η best response δυναμική συγκλίνει σε ισορροπία Nash ακόμα και σε περιπτώσεις που οι παίκτες έχουν ελλιπή γνώση σχετικά με τις στρατηγικές των άλλων παικτών. Στην δεύτερη κατεύθυνση, εξετάζεται μια τυχαιοκρατική εκδοχή των παιγνίων διαμόρφωσης άποψης στην οποία το κόστος διαφωνίας κάθε παίκτη με τον κοινωνικό του περίγυρο δίνεται από μία τυχαία μεταβλητή εξαρτώμενη από τυχαίες συναντήσεις του με παίκτες που ανήκουν στον κοινωνικό του περίγυρο. Στόχος των παικτών είναι η επιλογή της στρατηγικής που ελαχιστοποιεί το αναμενόμενο κόστος διαφωνίας. Παρουσιάζονται αποτελέσματα σχετικά με την ταχύτητα σύγκλισης των απόψεων σε ισορροπία Nash, όταν οι παίκτες ανανεώνουν τις απόψεις τους βάσει του αλγορίθμου Follow the Leader. Παρουσιάζονται ακόμη κάτω φράγματα στην ταχύτητα σύγκλισης οποιασδήποτε δυναμικής που εξασφαλίζει no-regret.Εισάγονται και μελετώνται δύο γενικεύσεις του δυναμικού συστήματος Hegselmann-Krause. Στην πρώτη γενίκευση, θεωρούμε ένα μη κατευθυνόμενο δίκτυο του οποίου οι κόμβοι αναπαριστούν τους παίκτες και οι ακμές αναπαριστούν τις μεταξύ τους κοινωνικές σχέσεις. Σε κάθε γύρο, οι παίκτες ανανεώνουν τις απόψεις τους στο μέσο όρο των απόψεων των γειτόνων τους των οποίων η άποψη είναι κοντινή προς τη δική τους. Το μοντέλο που προτάθηκε από τους Hegselmann και Krause αποτελεί ειδική περίπτωση του παραπάνω μοντέλου, όταν όλοι οι παίκτες συνδέονται με όλους τους άλλους. Αποδεικνύεται πως για οποιαδήποτε τοπολογία δικτύου, οι απόψεις των παικτών σταθεροποιούνται μετά από πεπερασμένο αριθμό γύρων. Στη δεύτερη επέκταση, οι παίκτες διαλέγουν τυχαία ένα μικρό υποσύνολο άλλων παικτών και ανανεώνουν την άποψη τους στο μέσο όρο απόψεων των τυχαίων παικτών που έχουν άποψη είναι κοντινή προς τη δική τους. Αποδεικνύεται ότι το σύστημα συγκλίνει σε ισορροπία μετά από πεπερασμένο αριθμό βημάτων. Εξ’ όσων γνωρίζουμε, αυτή είναι η πρώτη απόδειξη σύγκλισης σε δυναμικά συστήματα διαμόρφωσης άποψης όπου θεωρούμε ότι το υποκείμενο δίκτυο είναι κατευθυνόμενο.Παρουσιάζεται αλγόριθμος πολυωνυμικού χρόνου για το πρόβλημα k-facility reallocation. Το πρόβλημα αυτό προτάθηκε ως γενίκευση του κλασσικού προβλήματος βελτιστοποίησης k-median, όταν οι θέσεις των πελατών βρίσκονται στην ευθεία αλλά εξελίσσονται στο χρόνο. Ο αλγόριθμος βασίζεται στην επίλυση ενός κατάλληλου γραμμικού προγράμματος και είναι ισχυρά πολυωνυμικός. Το αποτέλεσμα αποτελεί σημαντική βελτίωση σε σχέση με τον προηγούμενο καλύτερο γνωστό αλγόριθμο, ο οποίος ήταν εκθετικός στην παράμετρο k.