Σε έναν μεγάλο αριθμό βιομηχανικών διεργασιών απαιτείται η διαδικασία της μίξης δύο ή περισσοτέρων υλικών για την παρασκευή του τελικού προιόντος.Ο πιο συνηθισμένος τρόπος μίξης είναι η ανάδευση ενός ή περισσοτέρων υλικών σε μια δεξαμενή. Η δεξαμενή καθώς και ο υπόλοιπος απαραίτητος εξοπλισμός όπως το στροφείο που πραγματοποιεί την ανάδευση, πρέπει να είναι με τέτοιο τρόπο σχεδιασμένος ώστε να είναι σε θέση αφ’ενός να φέρει εις πέρας την διαδικασία της μίξης και την παραγωγή του τελικού αποτελέσματος, τηρώντας κάποιες προδιαγραφές, αφ’εταίρου να είναι μηχανικά ευσταθής και ασφαλής. Λόγω διαφόρων αναγκών κατά την παραγωγική διαδικασία είναι απαραίτητη η αντικατάσταση των σωληνώσεων για την μεταφορά ενός υγρού από μια δεξαμενή επεξεργασίας ή αποθήκευσης σε άλλη, με την χρησιμοποίηση συστημάτων μεταφοράς της δεξαμενής. Άλλοι λόγοι επιβάλλουν την ταυτόχρονη μεταφορά και ανάδευση υλικών σε μια δεξαμενή, ή η δεξαμενή ανάδευσης να είναι στερεωμένη σε μεταλλικά ικριώματα ή να είναι στερεωμένη πάνω σε μεταλλικούς δοκούς. Έτσι, στην περίπτωση του συστήματος μεταφοράς μιας δεξαμενής από ένα σημείο σε κάποιο άλλο πρέπει κανείς να εξετάσει τις διαταραχές που υφίσταται το υγρό που περιέχει η δεξαμενή για παράδειγμα, εξαιτίας της κίνησης της δεξαμενής, για την αποφυγή υπερχείλισης του υγρού. Επιπλέον στην περίπτωση όπου τα υλικά που περιέχει μια δεξαμενή αναδεύονται κατά την μεταφορά της ή αυτή είναι στερεωμένη σε μεταλλικά ικριώματα, πρέπει να εξετάσει κανείς τις επιδράσεις της ανάδευσης στην σταθερότητα της δεξαμενής, και συνεπώς και στο σύστημα στήριξης ή μεταφοράς της ώστε να παρέχεται η αξιοπιστία και η ασφάλεια του συστήματος. Στην παρούσα εργασία χρησιμοποιήθηκε μια δεξαμενή ανάδευσης που περιείχε νερό, και μελετήσαμε τις επιδράσεις που είχε η ανάδευση του νερού, στην ισορροπία της δεξαμενής, καταγράφοντας την κατανομή του βάρους της. Στο πρώτο κεφάλαιο δίνονται διάφοροι ορισμοί και εξισώσεις που περιγράφουν ένα ρευστό και την κίνησή του. Στο δεύτερο κεφάλαιο περιγράφονται οι μονάδες που απαρτίζουν ένα σύστημα ανάδευσης, και στο τρίτο τα αποτελέσματα των φορτίσεων της δεξαμενής κατά την ανάδευσή της, στην πειραματική διάταξη που πραγματοποιήθηκε. / In a large number of industrial processes the mixing of two or more materials is necessary for the production of a final product. The most common form of mixing is the stirring of one or more materials in a mixing tank. The tank as well as the rest of the necessary equipment, for example the impeller which is responsible for the stirring process, must be designed in such a way that it is able to successfully complete the mixing process and produce the final product, according to certain specifications, while keeping mechanical stability and safety. Different needs may arise during the production of a final product. One of these may be the need to replace the pipes which are responsible for transferring one liquid material placed in a tank to another tank, with the use of a transferring system for the tank. Another need may be the simultaneous transfer and stirring of materials in a tank or the stirring tank may need to be stabilized on metal beams. In all these cases, one must evaluate the disturbances and the vibrations which effect the liquid and the tank, in order to ensure the efficiency, stability and safety of the mixing and transfer systems. In the present experimental thesis paper, a stirring tank was used that contained water, and the effects of the stirring of the water on the stability of the tank were studied and analyzed, through the recording of the distribution of the weight during the mixing. The first chapter contains definitions and equations that describe the motion of a fluid. The next chapter describes the parts that comprise a stirring system. Lastly, the third chapter contains the results, the analysis, and the conclusions of the experimental process.

Στην παρούσα μεταπτυχιακή διπλωματική εργασία χρησιμοποιούμε έννοιες και εργαλεία της Θεωρίας Παιγνίων με σκοπό να μελετήσουμε την απόδοση μηχανισμών κατανομής διαιρέσιμων πόρων εστιάζοντας κυρίως στον μηχανισμό αναλογικής κατανομής. Σύμφωνα με αυτόν τον μηχανισμό, ένα σύνολο χρηστών ανταγωνίζονται για ένα διαιρέσιμο πόρο -- όπως το εύρος ζώνης ενός τηλεπικοινωνιακού καναλιού -- υποβάλλοντας προσφορές. Ο μηχανισμός κατανέμει σε κάθε χρήστη ένα μέρος του πόρου το οποίο είναι ανάλογο της προσφοράς του και συλλέγει ένα ποσό ίσο με την προσφορά αυτή ως πληρωμή. Οι χρήστες στοχεύουν στη μεγιστοποίηση της ωφέλειας τους και συμπεριφέρονται στρατηγικά αλλάζοντας τις προσφορές τους με σκοπό να το πετύχουν. Έτσι, ο μηχανισμός ορίζει ένα παιχνίδι αναλογικής κατανομής. Παρουσιάζουμε γνωστά αποτελέσματα από τη σχετική βιβλιογραφία καθώς και νέα βελτιωμένα φράγματα για το κόστος της αναρχίας ως προς το κοινωνικό όφελος για συσχετιζόμενες ισορροπίες στο μοντέλο πλήρους πληροφόρησης και για ισορροπίες κατά 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.

Στον τομέα της κινητικής αποκατάστασης, η έννοια της βιοανάδρασης για τη βελτίωση του ταλάντευσης της στάσης του ανθρώπινου σώματος και του ελέγχου της ισορροπίας είναι αρκετά διαδεδομένη. Στις περισσότερες περιπτώσεις, το υποκείμενο προσπαθεί να ελέγξει τη θέση του με μια οπτική, προφορική ή αφής ανατροφοδότηση που παρέχεται από ένα ηλεκτρονικό σύστημα ή έναν νοσοκομειακό γιατρό. Πρόσφατες μελέτες αφορούν ασθενείς με κάποια νευρολογική ασθένεια που ελάμβαναν την οπτική ανατροφοδότηση στεκόμενοι σε μια δυναμοπλατφόρμα, ώστε να ελέγχουν την θέση του σημείου κεντρικής τους πίεσης (CoP). Στην έρευνά μας, καταγράφουμε τη κατανομή πίεσης κάτω από τα πόδια του υποκειμένου και παρέχουμε τις σχετικές ακουστικές πληροφορίες βιοανάδρασης (ABF) στην κατεύθυνση της βελτίωσης της ισορροπίας στάσης του. Με την παροχή αυτών των πρόσθετων ακουστικών πληροφοριών, στόχος μας είναι να διευκολύνουμε τη διαδικασία αντιστάθμησης της ελλείπουσας ή ανεπαρκούς αισθητήριας πληροφορίας από το κεντρικό νευρικό σύστημα (CNS). Έχουμε αναπτύξει και σε προκαταρκτικό στάδιο δοκιμάσει ένα σύστημα ακουστικής βιοανάδρασης βασιζόμενο σε μεσοσόλες με αισθητήρες πίεσης. Ο χρησιμοποιούμενος αλγόριθμος ABF έχει την ίδια βάση με αυτον που εφαρμόζεται σε ένα πρωτοτύπο ABF σύστημα, ήδη αναπτύγμενο και δοκιμασμένο, το οποίο ελέγχει τις μετακινήσεις επιτάχυνσης του σώματος. Οι μετρήσεις των τιμών πίεσης στα πόδια γίνονται μέσω ενός ζευγαριού εύκαμπτων μεσοσολών με 24 ειδικούς ενσωματωμένους αισθητήρες πίεζο-αντίστασης που περικλύονται σε κυτταρική δομή γεμάτη υγρό (Paromed). Η εφαρμογή ελέγχου αναπτύχθηκε σε περιβάλλον LabView και επιτρέπει τη συλλογή δεδομένων πίεσης σε 100Hz και την επεξεργασία αυτών σε πραγματικό χρόνο για τον υπολογισμό μιας εκτίμησης της τιμής του στιγμιαίου CoP. Η συμπεριφορά ταλάντευσης του CoP στα δυο επίπεδα, εμπρόσθια-οπίσθια AP και διάμεσα-πλευρικά ML, αποτυπώνεται σε ένα στερεοφωνικό ακουστικό σήμα που αλλάζει στο εύρος, τη συχνότητα και την ισορροπία L/R και μέσω των ακουστικών παρέχεται στο υποκείμενο. Το πειραματικό μας πρωτόκολλο περιέλαβε μια σειρά μετρήσεων με υγιείς εθελοντές εκτελώντας συγκεκριμένους στατικούς στόχους, με και χωρίς παρεχόμενο ABF. Κατά τη διάρκεια αυτών των στόχων προσπαθήσαμε να εξομοιώσουμε τις συνθήκες όπου η αισθητήρια πληροφορία είναι ελλείπουσα ή ανεπαρκής. Προκαταρκτικά αποτελέσματα στην ML κατεύθυνση, έδειξαν οτι με την ύπαρξη του ABF το ανθρώπινο σώμα ταλαντεύθηκε λιγότερο, γεγονός ενδεικτικό του ότι αυτό το νέο-αναπτυγμένο σύστημα βιοανάδρασης βασιζόμενο στις πίεζο-μεσοσόλες μπορεί να χρησιμοποιηθεί για να βελτιώσει την ισορροπία. Περισσότερα πειράματα και αναλυτική στατιστική ανάλυση πρέπει να ακολουθήσουν ώστε να γίνει κατανοητή η επιρροή αυτού του ABF στην ισορροπία του ανθρώπινου σώματος. / In the area of motor rehabilitation, the concept of biofeedback for improving postural sway and balance control is quite common. In most cases, the subject tries to control his position by a visual, oral or tactile feedback provided by an electronic system or a clinician. Recent studies involved patients with neurological disease that were receiving visual feedback as were standing in a force plate, for the monitoring of their centre of pressure (CoP) position. In our research, we record the pressure distribution beneath the subject's feet and provide related audio biofeedback (ABF) info in the direction of improving posture balance. By providing this extra audio information to the subject our aim is to facilitate the compensation process of the missing or inadequate sensory information by its central nervous system (CNS). We have developed and preliminary validated an insole pressure sensor-based, ABF system. The ABF concept followed is the same with the one applied in a prototype ABF system, already developed and validated, which monitors trunk acceleration movements. Foot pressure values were acquired through a pair of flexible insoles with 24 embedded discrete piezo-resistive sensors contained in a fluid-filled cell (Paromed). The control application was developed in LabView environment and permits pressure data collection in 100Hz and real-time processing for the calculation of an estimated value of the instant CoP. Swaying CoP behaviour in both AP and ML planes is mapped in a stereo audio signal changing in amplitude, frequency and L/R balance, which through the earphones is provided to the subject. Our experimental protocol involved a series of measurements with normal subjects performing specific static tasks, with and without ABF provided. During these tasks we tried to simulate conditions of missing or inadequate sensory information. Preliminary results about ML direction, shown that when ABF was provided the subject swayed less, suggesting that this new-developed biofeedback pressure-sensor insole-based system can be used to improve balance. More experiments and appropriate statistical analysis has to be done so as to understand the influence of this ABF on subject’ s balance.

Η ιδέα της «ισορροπίας της φύσης» αποτελεί μια μεταφορά που υπονοεί πως στη φύση υπάρχει σταθερότητα και τάξη, η οποία υπαγορεύεται από ένα «δημιουργό» ή την ίδια τη φύση, και άρα προβλεψιμότητα. Η «ισορροπία της φύσης» ξεκίνησε ιστορικά ως ένα στοιχείο του αρχαίου πολιτισμού που εντοπίζεται σε διάφορες κοσμοθεωρίες, αλλά ενσωματώθηκε και στην επιστήμη της οικολογίας και έφτασε να την επηρεάζει σε μεγάλο βαθμό από την εμφάνισή της ως νέας επιστήμης μέχρι και πριν μερικά χρόνια. Η ιδέα της «ισορροπίας της φύσης» έχει αναθεωρηθεί στο πλαίσιο της οικολογίας με τη διαμόρφωση νέων θεωριών και μοντέλων για τη λειτουργία της φύσης, αλλά εξακολουθεί να κυριαρχεί στην κοινωνία ως προς την περιβαλλοντική στάση και κουλτούρα της ως συνόλου, τη χάραξη στόχων και στρατηγικών από περιβαλλοντικές, μη κυβερνητικές οργανώσεις, αλλά και τη χάραξη των επίσημων πολιτικών διαχείρισης και προστασίας του περιβάλλοντος. Ακόμα, η ιδέα της «ισορροπίας της φύσης» κυριαρχεί στη σχολική επιστήμη όπου παρουσιάζεται στα σχολικά εγχειρίδια και στη σκέψη των παιδιών όλων των ηλικιών και των νεαρών ενηλίκων, όπως προκύπτει από έρευνες στο χώρο της διδακτικής της βιολογίας. Η κυριαρχία της ιδέας της «ισορροπίας της φύσης» στην εκπαιδευτική πραγματικότητα φαίνεται να δρα ως εμπόδιο στην οικοδόμηση της επιστημονικής γνώσης των παιδιών για τη φύση (δηλαδή στην προσέγγιση των σύγχρονων μοντέλων για τη λειτουργία της), αλλά και στην ανάπτυξη περιβαλλοντικά υπεύθυνης στάσης και συμπεριφοράς απέναντι σε αυτή. Υπαγορεύοντας ότι οι συνέπειες των παρεμβάσεών μας στη φύση είναι αναστρέψιμες, η ιδέα αυτή δημιουργεί την ψευδαίσθηση των «μαγικών» λύσεων, ενώ όπως έχει φανεί, η εφαρμογή της στις πολιτικές διαχείρισης της φύσης μπορεί να οδηγεί τα οικοσυστήματα σε αποτελέσματα που δεν είναι ούτε «κανονικά», ούτε «προβλέψιμα». Όπως προκύπτει από τα παραπάνω, είναι σκόπιμη μία συστηματική προσπάθεια αποσταθεροποίησης της ιδέας της «ισορροπίας της φύσης» στο πλαίσιο της εκπαίδευσης. Αυτή προϋποθέτει ασφαλώς το σχεδιασμό ενός κατάλληλου μαθησιακού περιβάλλοντος, ο οποίος με τη σειρά του προϋποθέτει την ανίχνευση των ιδεών των μαθητών, καθώς σύμφωνα με τον εποικοδομισμό, που έχει επικρατήσει έναντι πιο παραδοσιακών επιστημολογικών ή γνωστικών προσεγγίσεων, η προηγούμενη γνώση του υποκειμένου έχει καθοριστική σημασία στην οικοδόμηση νέας γνώσης από αυτό. Η έρευνα με τίτλο «η ιδέα της “ισορροπίας της φύσης” στη σκέψη φοιτητών επιστημών της εκπαίδευσης» ανιχνεύει τις αντιλήψεις που έχουν σε σχέση με την ιδέα της «ισορροπίας της φύσης», παιδιά που έχουν τελειώσει τη δευτεροβάθμια εκπαίδευση και έχουν εισαχθεί στην τριτοβάθμια, και διερευνά το πώς αυτές οι αντιλήψεις ενσωματώνονται στους συλλογισμούς που αυτά αναπτύσσουν για φυσικές διαταραχές ή ανθρώπινες παρεμβάσεις στη φύση. Τα αποτελέσματα της έρευνας δείχνουν πως η ιδέα της «ισορροπίας της φύσης» είναι καλά εδραιωμένη στον τρόπο με τον οποίο οι φοιτητές σκέφτονται για τη φύση. Για τους περισσότερους φοιτητές η «ισορροπία της φύσης» είναι μια πραγματικότητα και μέσα από αυτό το πρίσμα συζητούν και κάνουν προβλέψεις για τα οικοσυστήματα. Ακόμα, φαίνεται ότι οι φοιτητές θεωρούν πως ο άνθρωπος με τις ενέργειές του μπορεί να ενισχύσει και να προστατεύσει αυτή την «ισορροπία», και οι διαταραχές που προκαλούνται από ανθρώπινη δραστηριότητα θεωρούνται ιδιαίτερα κρίσιμες. Τα αποτελέσματα της έρευνας δείχνουν πως στην πλειοψηφία τους οι μαθητές των οποίων οι ιδέες διερευνήθηκαν σκέφτονται για τη λειτουργία της φύσης μέσα από το πρίσμα της ύπαρξης μιας «ισορροπίας», και προσφέρουν υλικό για το σχεδιασμό ενός μαθησιακού περιβάλλοντος το οποίο θα προωθεί τα νέα μοντέλα λειτουργίας της φύσης και θα επιχειρεί να αποσταθεροποιήσει την έννοια της «ισορροπίας» η οποία, όπως αναφέρθηκε, δρα ως εμπόδιο στην εκπαίδευση και στην κοινωνική πρακτική. / -

Η παρούσα διπλωματική εργασία πραγματεύεται την θεωρία παιγνίων και το πώς αυτή εφαρμόζεται στην οικονομική επιστήμη. Συγκεκριμένα, στόχος μας είναι να απαντήσουμε στο ερώτημα: «Πως αποφασίζονται οι τελικές στρατηγικές που θα επικρατήσουν σε ένα παίγνιο με την πάροδο του χρόνου;». Η εργασία είναι χωρισμένη σε δύο μέρη. Αρχικά αναφερόμαστε στην κλασσική θεωρία παιγνίων και αναλύουμε τα βασικά της στοιχεία και στη συνέχεια περνάμε στην ανάλυση της εξελικτικής θεωρίας παιγνίων. Στο 1ο μέρος της παρούσας εργασίας, λοιπόν, αναφέρουμε τα όσα είναι σχετικά με την κλασσικά θεωρία παιγνίων. Συγκεκριμένα, στο πρώτο κεφάλαιο γίνεται μία σύντομη ιστορική αναδρομή της θεωρίας αυτής και στο δεύτερο κεφάλαιο την ορίζουμε ως την επίσημη μελέτη που εξετάζει την ορθολογικότητα σε ένα επιχειρηματικό περιβάλλον και παρουσιάζουμε τα βασικά στοιχεία ενός παιγνίου. Αναφέρουμε τα δύο επίπεδα περιγραφής των παιγνίων, δηλαδή τα παίγνια συνεργασίας και μη-συνεργασίας, καθώς και τους δύο τρόπους αναπαράστασής τους που είναι η στρατηγική ή αλλιώς κανονική μορφή (μήτρες) και η εκτεταμένη ή αλλιώς αναλυτική μορφή (δέντρα παιγνίων). Στο τρίτο κεφάλαιο ορίζονται οι κυρίαρχες στρατηγικές και η αντίστοιχη ισορροπία κυρίαρχης στρατηγικής και στο τέταρτο κεφάλαιο ορίζεται η Ισορροπία Nash, η οποία αποτελεί τη στάνταρ έννοια της ισορροπίας στα οικονομικά. Στα δύο αυτά κεφάλαια (3 και 4) υπάρχουν παραδείγματα εφαρμογής που στοχεύουν στην καλύτερη κατανόηση, και αναλύεται και το Δίλημμα του Φυλακισμένου που αποτελεί το πιο κλασσικό παράδειγμα στη θεωρία παιγνίων. Στην περίπτωση, τώρα, όπου δεν υπάρχει Ισορροπία Nash (κάτι το οποίο συμβαίνει σε παίγνια στρατηγικής μορφής) το παίγνιο λύνεται με τη βοήθεια των μικτών στρατηγικών οι οποίες αναλύονται στο πέμπτο κεφάλαιο. Συνεχίζουμε με το έκτο κεφάλαιο, όπου παρουσιάζονται τα εκτεταμένα παίγνια πλήρους πληροφόρησης και αναλύεται η μέθοδος της προς τα πίσω επαγωγής (αναδίπλωση). Στο έβδομο κεφάλαιο παρουσιάζονται τα παίγνια ελλιπούς πληροφόρησης και στο όγδοο κεφάλαιο αναφέρονται τα παίγνια μηδενικού αθροίσματος (π.χ. σκάκι) και το πώς μπορούν να χρησιμοποιηθούν μαζί με τους τυχαιοποιημένους αλγόριθμους για την ανάλυση προβλημάτων στον απευθείας σύνδεσης υπολογισμό. Το 1ο μέρος κλείνει με ένα παράδειγμα εφαρμογής της θεωρίας παιγνίων, τις δημοπρασίες. Τι γίνεται όμως όταν ένα παίγνιο επαναλαμβάνεται και παίζεται περισσότερες από μία φορές; Το ερώτημα αυτό έρχεται να μας το απαντήσει η εξελικτική θεωρία παιγνίων στο 2ο μέρος της παρούσας διπλωματικής εργασίας. Στα δύο πρώτα κεφάλαια, του μέρους αυτού, ορίζονται τα εξελικτικά παίγνια, γίνεται αναφορά για το που μπορούν να βρουν εφαρμογή καθώς και στους λόγους που δεν είναι ακόμη γνωστές οι οικονομικές εφαρμογές τους. Το τρίτο και το πέμπτο κεφάλαιο αποτελούν τα πιο σημαντικά κεφάλαιο του 2ου μέρους. Στο τρίτο κεφάλαιο παρουσιάζεται αναλυτικά το μοντέλο των εξελικτικών παιγνίων και τα στοιχεία που το αποτελούν (αναμενόμενες ανταμοιβές, πληθυσμός, καταστάσεις). Περιγράφεται το στάδιο παιγνίου το οποίο ορίζεται από μία συνάρτηση καταλληλότητας και δίνεται έμφαση στις δύο γραμμικές προδιαγραφές που έχουν οι συναρτήσεις αυτές. Στη συνέχεια, αναλύεται πλήρως το πιο αντιπροσωπευτικό παράδειγμα της εξελικτικής θεωρίας παιγνίων, το παίγνιο Hawk-Dove, που αποτελεί ένα γενικό μοντέλο καταστάσεων με επιθετικές και αμυντικές αγορές. Το παίγνιο αυτό έχει δύο ειδών παίκτες, αυτοί που επιλέγουν να είναι επιθετικοί (Hawk) και αυτοί που επιλέγουν να είναι αμυντικοί (Dove), και ερευνάται το ποιο είδος παικτών θα επικρατήσει τελικά. Μέσα από την διαφορική εξίσωση που αναλύεται στο πέμπτο κεφάλαιο, στις δυναμικές, φαίνεται πως το αποτέλεσμα εξαρτάται από τρεις παραμέτρους: από τον αρχικό πληθυσμό, από την πιθανότητα να παιχτεί η καθεμία στρατηγική και από τον πίνακα με τις ανταμοιβές των παικτών. Έτσι απαντάται το αρχικό μας ερώτημα και προκύπτει η στρατηγική που τελικά θα επικρατήσει, που ονομάζεται εξελικτική στρατηγική (evolutionary stable strategy-ESS). Στο τέταρτο κεφάλαιο ορίζεται η Ισορροπία Nash (I.N.), η Εξελικτική Σταθερή Στρατηγική (ESS) και η Εξελικτική Ισορροπία (E.E.) και στο έκτο κεφάλαιο αναφέρουμε την τοπική κατάταξη συστημάτων με χαμηλές διαστάσεις και συγκεκριμένα τα γραμμικά παίγνια μίας-διάστασης, τα συστήματα δύο μεταβλητών και άλλα συστήματα δύο-διαστάσεων και μη-γραμμικά. Κλείνοντας το 2ο μέρος και γενικά την παρούσα εργασία, παρουσιάζουμε τρία παραδείγματα στα οποία φαίνεται η εφαρμοσιμότητα των όσων αναφέραμε. Συγκεκριμένα αναλύονται τρία γνωστά παίγνια τα οποία χρησιμοποιήθηκαν από την πολιτική και παραλληλίστηκαν με καταστάσεις που είχαν να αντιμετωπίσουν εκείνη τη στιγμή. / This thesis deals with the evolutionary game theory and how it applies to economics. First of all, it is necessary to refer the original game theory and to analyze the key elements and then move to the analysis of evolutionary game theory. In the first part of this study, therefore, we indicate what is on game theory. Specifically, in the first chapter is a brief history of game theory and the second chapter defined game theory as a formal study examining the rationality in a business environment and presents the basics elements of a game. Also, at this chapter i reffer to the description of games, namely, games of cooperation and non-cooperation, and the two ways of representing their strategy, the normal form (matrix) and the extensive form (game tree). The third chapter sets out the dominant strategy and the corresponding dominant strategy equilibrium and in the fourth chapter we define the Nash Equilimbrium, which is the standard notion of equilibrium in economics. In these two chapters (third and fourth) there are examples of the application for better understanding, and we analyze the prisoner's dilemma, which is the most classic example of game theory. If there is no Nash Equilimbrium (this could happen at narmal strategy games) the game is solved by mixed strategies, which are analyzed in the fifth chapter. Continuing, at the sixth chapter we can see the extensive games with perfect information and we analyze the method of backward induction. In the seventh chapter, we can see the extensive games with imperfect information and the eighth chapter refers to the zero-sum games and how they can be used together with randomized algorithms for the analysis of problems on-line calculation. Finally, the first part closes with an example application of game theory, the auctions. The question is “What happens when a game is played more than once?” The answer comes from the second part of this thesis in which we analyse the evolutionary game theory. In the first two chapters of this part we define evolutionary games, we refere where evolutionary games might be applicable and why economic application aren’t common already. The third and fourth chapter are the most important chapters of the second part. At the third chapter we present the model of the evolutionary game and its elements (expected payoffs, population, states). We describe the stage game which is defined by a fitness function and we emphasize at its two linear specifications. Then we make a full analysis one of the most representative example of evolutionary game theory, the Hawk-Dove game. This game has two types of players, aggressive (Hawk) and defensive (Dove), which reflects the situation where there is a competitive and an uncompetitive business, and the point is to find which of the two types will eventually prevail. Based on a differential equation, we conclude that the result depends on three parameters: the initial population, the probability with which each strategy is played and the payoff matrix. All this leads in a strategy which is known as evolutionary stable (ESS). In chapter five, we define the Nash Equilibrium, the Evolutionary Stable Strategy (ESS) and Evolutionary Equilibrium (EE) and in chapter six we analyze the local classification of low dimensions systems. To make clear the applicability of all those we mention at this thesis, we are closing with three examples. More specific we analyze three well-known games which were used by the political and paralleled with situations they had to face with.

Στα πλαίσια της διατριβής αναπτύξαμε δύο από τους πρώτους αλγορίθμους υπολογισμού μιας ε-προσεγγιστικής ισορροπίας 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.

Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη καταστάσεων ανταγωνισμού μεταξύ χρηστών, για τη χρησιμοποίηση ενός συνόλου κοινόχρηστων πόρων. Για την μοντελοποίηση και ανάλυση των καταστάσεων αυτών χρησιμοποιούμε ως εργαλεία, έννοιες από την θεωρία παιγνίων, όπως ισορροπίες Nash, παίγνια συμφόρησης και μηχανισμοί συντονισμού. Ο κάθε κοινόχρηστος πόρος χρεώνει κάποιο κόστος στους χρήστες που τον χρησιμοποιούν. Θεωρούμε ότι οι χρήστες των κοινόχρηστων πόρων είναι εγωιστικοί, δηλαδή μοναδική τους επιδίωξη είναι η μεγιστοποίηση της προσωπικής τους ωφέλειας. Μια ισορροπία Nash είναι μια κατάσταση όπου κανένας χρήστης δεν μπορεί να αυξήσει το εγωιστικό του όφελος αν αλλάξει μονομερώς την στρατηγική του. Πιο συγκεκριμένα ασχολούμαστε με το KP-μοντέλο γνωστό και ως μοντέλο παράλληλων ακμών και ιδιαίτερα με μεθόδους σύγκλισης σε αγνές ισορροπίες Nash, όπου δηλαδή οι στρατηγικές (ακμές) των χρηστών είναι ντετερμινιστικές. Γενικά, ένα παίγνιο (σύστημα) δεν έχει πάντα μια αγνή ισορροπία Nash. Ωστόσο, εμείς θα μελετήσουμε περιπτώσεις που εγγυημένα έχουν τουλάχιστον μια αγνή ισορροπία Nash. Ονομάζουμε πολιτική χρέωσης των ακμών τον τρόπο με τον οποίο υπολογίζεται το κόστος του κάθε χρήστη όταν χρησιμοποιεί μια ακμή. Μια μέθοδος σύγκλισης σε μια αγνή ισορροπία Nash, είναι να επιτραπεί στους χρήστες να αλλάζουν εγωιστικά τις στρατηγικές τους μέχρι να καταλήξουν σε μια αγνή ισορροπία Nash. Ενδιαφερόμαστε για την ταχύτητα σύγκλισης σε μια αγνή ισορροπία Nash, δηλαδή το πλήθος των εγωιστικών αλλαγών στρατηγικών μέχρι να καταλήξουμε σε ισορροπία. Αρχικά, χρησιμοποιείται η πολιτική χρέωσης συνολικού φορτίου (Makespan), όπου κάθε ακμή χρεώνει το συνολικό της φορτίο σε κάθε χρήστη που την χρησιμοποιεί. Στην πιο απλή περίπτωση, η όλη διαδικασία χωρίζεται σε βήματα. Σε κάθε βήμα επιλέγεται, από το σύνολο των χρηστών που έχουν όφελος να αλλάξουν στρατηγική, ένας χρήστης ο οποίος αλλάζει στρατηγική. Η επιλογή γίνεται με βάση κάποιον αλγόριθμο προτεραιότητας. Για το μοντέλο αυτό, που ονομάζεται ESS-μοντέλο, η ταχύτητα σύγκλισης είναι στη χειρότερη περίπτωση εκθετική στο πλήθος των χρηστών. Παρουσιάζουμε την επίδραση των αλγορίθμων προτεραιότητας στην ταχύτητα σύγκλισης καθώς και αποτελέσματα για τρεις διαφορετικές κατηγορίες ακμών. Μια άλλη προσέγγιση, με εφαρμογή στα κατανεμημένα συστήματα, είναι η παράλληλη αλλαγή στρατηγικών από τους χρήστες (rerouting), όπου περισσότεροι από έναν χρήστες μπορούν να αλλάξουν ταυτόχρονα τη στρατηγική τους. Το μοντέλο αυτό υπερτερεί του ESS στην ταχύτητα σύγκλισης καθώς και στο πλήθος των πραγματικών καταστάσεων που μοντελοποιεί. Στη γενικότερη περίπτωση, όπου οι χρήστες επιτρέπεται να συνάπτουν συνασπισμούς (coalitions) μεταξύ τους, χρησιμοποιούμε έννοιες από τη συνεργατική θεωρία παιγνίων. Οπότε έχουμε να αντιμετωπίσουμε ομάδες χρηστών που αλλάζουν εγωιστικά τις ομαδικές στρατηγικές τους. Παρουσιάζουμε ένα ψευδοπολυωνυμικό φράγμα στην ταχύτητα σύγκλισης για μια ειδική περίπτωση όπου οι ακμές είναι πανομοιότυπες και επιτρέπονται συνασπισμοί πλήθους το πολύ δύο χρηστών. Ένας άλλος τρόπος σύγκλισης σε μια αγνή ισορροπία Nash είναι η κατασκευή ενός αλγορίθμου που αναθέτει στρατηγικές στους χρήστες, όχι απαραίτητα με βάση τα εγωιστικά κριτήρια του καθενός, χωρίς να αυξάνει το κοινωνικό κόστος. Με τον όρο κοινωνικό κόστος αναφερόμαστε σε μια συνολική μετρική της απόδοσης του συστήματος σε συνάρτηση με τις στρατηγικές των χρηστών του συστήματος. Ο αλγόριθμος Nashify που παρουσιάζουμε, συγκλίνει σε μια αγνή ισορροπία Nash σε πολυωνυμικό πλήθος βημάτων, χωρίς να αυξάνει το κοινωνικό κόστος. Στη συνέχεια, εισάγουμε την έννοια των μηχανισμών συντονισμού. Οι μηχανισμοί συντονισμού είναι ένα σύνολο πολιτικών χρέωσης για τις ακμές, που έχουν ως στόχο την παροχή κινήτρων στους εγωιστικούς χρήστες έτσι ώστε οι εγωιστικές αλλαγές των στρατηγικών τους να συγκλίνουν σε αγνές ισορροπίες Nash με μειωμένο κοινωνικό κόστος. Στην παρούσα εργασία, μελετάμε την επίδραση των μηχανισμών συντονισμού στην ταχύτητα σύγκλισης των εγωιστικών χρηστών σε μια ισορροπία Nash. Εξετάζουμε εκτός από την πολιτική χρέωσης συνολικού φορτίου (makespan) και κάποιες διαφορετικές πολιτικές χρέωσης (SJF, LJF, FIFO) και μελετάμε την επίδραση των αλγορίθμων προτεραιότητας στην ταχύτητα σύγκλισης τους. Παρουσιάζουμε και αποδεικνύουμε φράγματα στην ταχύτητα σύγκλισης για τις SJF και LJF πολιτικές που χρεώνουν τους χρήστες με βάση το μέγεθος των βαρών τους. Τέλος αποδεικνύουμε για την πολιτική χρέωσης FIFO, ένα γραμμικό άνω φράγμα στην ταχύτητα σύγκλισης για την ειδική περίπτωση των πανομοιότυπων ακμών και ένα ψευδοπολυωνυμικό άνω φράγμα για την γενική περίπτωση των ακμών. Τελικά, αξιολογούμε πειραματικά την επίδραση των αλγορίθμων προτεραιότητας στις πολιτικές χρέωσης στο ESS μοντέλo με πανομοιότυπες ακμές. Ουσιαστικά, συγκρίνουμε τις πολιτικές χρέωσης συνολικού φορτίου, SJF, LJF και FIFO καθώς και το συνεργατικό με το μη συνεργατικό μοντέλο σχετικά με τη ταχύτητα σύγκλισης τους. Παρατηρούμε ότι για την συνολικού φορτίου, SJF, LJF και FIFO πολιτική χρέωσης τα πειραματικά αποτελέσματα επαληθεύουν τα θεωρητικά φράγματα. Δηλαδή η FIFO πολιτική παρουσιάζει ταχύτερη σύγκλιση από τις υπόλοιπες πολιτικές ανεξάρτητα του αλγόριθμου προτεραιότητας. Για την περίπτωση των συνασπισμών με πολιτική χρέωσης συνολικού φορτίου, παρατηρούμε ότι η ταχύτητα σύγκλισης είναι πολυωνυμική στο πλήθος των χρηστών ακόμα και στην χειρότερη επιλογή συνασπισμών. Το αποτέλεσμα αυτό υποδεικνύει ότι το ψευδοπολυωνυμικό θεωρητικό άνω φράγμα μπορεί να βελτιωθεί. / General goal of the current diploma thesis is the study of competitive situations among users of a set of global resources. In order to analyze and model these situations we use as tools, game theoretic elements, such as Nash equilibrium, congestion games and coordination mechanisms. Every global resource debit a cost value to its users. We assume that the users are selfish, that is their sole objective is the maximization of their personal benefit. An Nash equilibrium is a situation in which no user can increase his personal benefit by changing only his or her own strategy unilaterally. More specific, we are interested in the KP-model or parallel links model and we study convergence methods to pure Nash equilibrium, in which all the strategies a user can select are deterministic. Generally, a game has not always a pure Nash equilibrium. Although we are going to study cases in which there is always at least one Nash equilibrium. We define as cost policy of an edge the function which computes the cost of each user of this edge. A method of convergence in a pure Nash equilibrium is, starting from an initial configuration, to allow all users to selfishly change their strategies (one after the other) until they reach a pure Nash equilibrium. We are interested in the convergence time to pure Nash equilibrium, that is the number of these selfish moves. Firstly, we study the makespan cost policy, in which each edge debits its total load to everyone that use it. In the most simple case, the whole procedure is divided into several steps. At each step, the priority algorithm choose one user from the set of users that benefit by changing their current strategy. For this model, named ESS-model, the convergence time is at the worst case exponential to the number of users. We present the effect of several priority algorithms to the convergence time and results for the major different cases of edges (identical, related, unrelated). Another approach, with applications to distributed systems, is the concurrent change of strategies (rerouting) in which more than one users can change simultaneously their strategies. This model is more powerful than ESS because of its real life applications. Another model we study is that of coalitions, in which the users can contract alliances. This model comes from cooperative game theory. In this case we have to deal with groups of users changing selfishly their group strategies. We present a pseudo-polynomial bound to the convergence time in the identical machines model with coalitions of at most 2 users. Another model of convergence, a little different than the others stated above, is the construction of an algorithm that delegates strategies to the users unselfishly without increasing the social cost. Informally, social cost is a total metric of the system performance depending on the users strategies. This model is named nashification and the algorithm nashify that provides converge to a pure Nash equilibrium in polynomial number of steps without increasing the social cost. As far as the coordination mechanisms are concerned, they are a set of cost policies for the edges, that provides motives to the selfish users in order to converge to a pure Nash equilibrium with decreased social cost. In this thesis, we study the effect of coordination mechanisms in the convergence time. We examine, except from makespan, the sjf, ljf and fifo cost policies. Sjf and ljf policies debit the users concerning their weights. The thesis results are divided in two categories. On the one hand, we prove upper and lower bounds of convergence time for sjf, ljf and fifo policies. Especially for fifo we prove in identical machines case a tight linear bound which is independent from the priority algorithm and a pseudo-polynomial bound in unrelated machines case. On the other hand, we implement all the above mentioned models and analyze them experimentally. In our experiments there are 3 parameters: the priority algorithm, the cost policy, and the number of coalitions. In all cases the experimental results follows the theoretical with one exception which is the most interesting among the experiments. In the case of coalitions with at most 2 users the theoretical upper bound is pseudo-polynomial to the number of users but the experimental results shows that the convergence time is polynomial. These results force us to conjecture that there is a polynomial upper bound.