Στα πλαίσια της διατριβής αναπτύξαμε δύο από τους πρώτους αλγορίθμους υπολογισμού μιας ε-προσεγγιστικής ισορροπίας Nash για την περίπτωση όπου το ε είναι κάποια σταθερά. Οι προσεγγίσεις που επιτυγχάνουν οι αλγόριθμοί μας είναι ε=3/4 και ε=(2+λ)/4 αντίστοιχα, όπου λ είναι το ελάχιστο, μεταξύ όλων των ισορροπιών Nash, κέρδος για έναν παίκτη. Επιπλέον, μελετήσαμε μια ευρεία κλάση τυχαίων παιγνίων δύο παικτών, για την οποία υπολογίσαμε μια πολύ καλή ε-προσεγγιστική ισορροπία Nash, με το ε να τείνει στο 0 καθώς το πλήθος των διαθέσιμων στρατηγικών των παικτών τείνει στο άπειρο. Οι αρχές της θεωρίας παιγνίων είναι χρήσιμες στην ανάλυση της επίδρασης που έχει στην καθολική απόδοση ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του. Προς την κατεύθυνση αυτή, εστιάσαμε στο πρόβλημα της εξισορρόπησης φορτίου. Μελετήσαμε διάφορα μοντέλα πληροφόρησης (π.χ. όταν όλα τα φορτία είναι άγνωστα ή όταν κάθε παίκτης γνωρίζει το μέγεθος του δικού του φορτίου) και αναλύσαμε για το καθένα το σύνολο και τις ιδιότητες των ισορροπιών Nash. Yπολογίσαμε επίσης φράγματα στο λόγο απόκλισης, ο οποίος εκφράζει την επίδραση που έχει στην απόδοση του συστήματος η εγωιστική συμπεριφορά των χρηστών του. Εκτός από τα υπολογιστικά θέματα που σχετίζονται με τη θεωρία παιγνίων, έχει ενδιαφέρον να μελετηθεί κατά πόσο μπορεί η θεωρία παιγνίων να βοηθήσει στην ανάπτυξη και ανάλυση αλγορίθμων για υπολογιστικά δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης. Προς αυτήν την κατεύθυνση, μελετήσαμε από παιγνιοθεωρητική σκοπιά το πρόβλημα χρωματισμού των κορυφών ενός γραφήματος. Ορίσαμε κατάλληλα το παίγνιο χρωματισμού γραφήματος και αποδείξαμε ότι κάθε παίγνιο χρωματισμού γραφήματος έχει πάντα μια αγνή ισορροπία Nash, και ότι κάθε αγνή ισορροπία Nash αντιστοιχεί σε ορθό χρωματισμό του γραφήματος. Δείξαμε επίσης ότι υπάρχει πάντα μια αγνή ισορροπία Nash που χρησιμοποιεί βέλτιστο αριθμό χρωμάτων, δηλαδή ίσο με το χρωματικό αριθμό του γραφήματος. Επιπλέον, περιγράψαμε και αναλύσαμε έναν πολυωνυμικό αλγόριθμο που υπολογίζει μια αγνή ισορροπία Nash για ένα οποιοδήποτε παίγνιο χρωματισμού γραφήματος και χρησιμοποιεί συνολικά ένα πλήθος χρωμάτων που ικανοποιεί ταυτόχρονα τα περισσότερα κλασικά γνωστά φράγματα στο χρωματικό αριθμό. / We developed two algorithms for computing an e-approximate Nash equilibrium for the case where e is an absolute constant. The approximations achieved by our algorithms are e=3/4 and e=(2+l)/4 respectively, where $\lambda$ is the minimum, among all Nash equilibria, payoff of either player. Furthermore, we studied a wide class of random two player games, for which we showed how to compute an e-approximate Nash equilibrium, where e tends to zero as the number of strategies of the players tends to infinity. Game theoretic concepts are useful in determining the impact that selfish behavior plays on the global performance of a system involving selfish entities. Towards this direction, we focused on the problem of load balancing. We studied the case where the agents are not necessarily fully informed about the exact values of their loads. We focused on several models of information (e.g. when all agents know nothing about the loads, or when each agents knows her own load) and, for each model, we characterized the set of Nash equilibria and analyzed their properties. Moreover, we bounded the coordination ratio, a measure which captures the impact that selfish behavior has to the global performance of the system, in contrast to the performance achieved by an optimum centralized algorithm. Besides the computational issues related to game theory, it is interesting to investigate whether game theory can help us in developing and analyzing algorithms for computationally difficult combinatorial optimization problems. Towards this direction, we studied from a game theoretic point of view the problem of vertex coloring. In particular, we properly defined the graph coloring game and we proved that every graph coloring game has a pure Nash equilibrium, and each pure Nash equilibrium corresponds to a proper coloring of the graph. We also showed that there exists a pure Nash equilibrium that uses an optimum number of colors, i.e. equal to the chromatic number. Furthermore, we developed and analyzed a polynomial time algorithm that computes a pure Nash equilibrium for any graph coloring game, using a number of colors satisfying most of the known classical bounds on the chromatic number.

Στην παρούσα μεταπτυχιακή διπλωματική εργασία χρησιμοποιούμε έννοιες και εργαλεία της Θεωρίας Παιγνίων με σκοπό να μελετήσουμε την απόδοση μηχανισμών κατανομής διαιρέσιμων πόρων εστιάζοντας κυρίως στον μηχανισμό αναλογικής κατανομής. Σύμφωνα με αυτόν τον μηχανισμό, ένα σύνολο χρηστών ανταγωνίζονται για ένα διαιρέσιμο πόρο -- όπως το εύρος ζώνης ενός τηλεπικοινωνιακού καναλιού -- υποβάλλοντας προσφορές. Ο μηχανισμός κατανέμει σε κάθε χρήστη ένα μέρος του πόρου το οποίο είναι ανάλογο της προσφοράς του και συλλέγει ένα ποσό ίσο με την προσφορά αυτή ως πληρωμή. Οι χρήστες στοχεύουν στη μεγιστοποίηση της ωφέλειας τους και συμπεριφέρονται στρατηγικά αλλάζοντας τις προσφορές τους με σκοπό να το πετύχουν. Έτσι, ο μηχανισμός ορίζει ένα παιχνίδι αναλογικής κατανομής. Παρουσιάζουμε γνωστά αποτελέσματα από τη σχετική βιβλιογραφία καθώς και νέα βελτιωμένα φράγματα για το κόστος της αναρχίας ως προς το κοινωνικό όφελος για συσχετιζόμενες ισορροπίες στο μοντέλο πλήρους πληροφόρησης και για ισορροπίες κατά Bayes-Nash στο μοντέλο ελλιπούς πληροφόρησης. Πιο συγκεκριμένα, παρουσιάζουμε ένα κάτω φράγμα 1/2 για το κόστος της αναρχίας ως προς τις προαναφερθείσες έννοιες ισορροπίας, βελτιώνοντας σημαντικά το προηγούμενο καλύτερο κάτω φράγμα 26.8% που πρόσφατα απέδειξαν οι Syrgkanis και Tardos (STOC 2013). Επίσης, μελετάμε για πρώτη φορά τη περίπτωση όπου οι χρήστες διαθέτουν περιορισμένους προϋπολογισμούς και παρουσιάζουμε ένα κάτω φράγμα περίπου 36% και ένα άνω φράγμα 50% για το κόστος της αναρχίας χρησιμοποιώντας ως αντικειμενική συνάρτηση το αποτελεσματικό όφελος το οποίο λαμβάνει υπόψη προϋπολογισμούς. / In this thesis, we use notions and techniques from Game Theory in order to analyze the performance of divisible resource allocation mechanisms focusing mainly on the proportional allocation mechanism. According to this mechanism, a set of users are competing for a divisible resource -- such as bandwidth of a communication link -- by submitting bids. The mechanism allocates to each user a fraction of the resource that is proportional to the user's bid and collects an amount equal to the bid as payment. Users aim to maximize their individual utility and act strategically in order to achieve their goal. Hence, the mechanism defines a proportional allocation game. We cover previously known results from the related literature and present new bounds on the price of anarchy with respect to the social welfare over coarse-correlated and Bayes-Nash equilibria in the full and incomplete information settings, respectively. In particular, we prove a lower bound of $1/2$ for the price of anarchy over both equilibrium concepts, significantly improving the previously best known lower bound, presented by Syrgkanis and Tardos (STOC 2013). Furthermore, we study for the first time the scenario where users have budget constraints and present lower bounds on the price of anarchy using the effective welfare (which takes budgets into account) as an objective function.