Επίλυση στοχαστικών παιγνίων με μεθόδους γραμμικού προγραμματισμού
Creators: name: Ζυγογιάννης, Κωνσταντίνος Δημητρίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2023
Subjects: Στοχαστικά παίγνια
Γραμμικός προγραμματισμός
Μαρκοβιανές διαδικασίες απόφασης
Stochastic games
Linear programming
Markov decision processes

description: Η παρούσα εργασία περιέχει κατ’ αρχήν μια ανασκόπηση με κεντρικό αντικείμενο τα Στοχαστικά Παίγνια. Το πρώτο κεφάλαιο αποτελεί μια εισαγωγή στις Μαρκοβιανές διαδικασίες απόφασης , ένα πολύ ισχυρό εργαλείο για την μελέτη των πιο «πολύπλοκων» στοχαστικών παιγνίων, τα οποία αποτελούν αντικείμενο μελέτης του δεύτερου κεφαλαίου. Σημαντικό μέρος της θεωρίας που αναπτύσσεται στα δύο πρώτα κεφάλαια αντλήθηκε από το βιβλίο των Jerzy Filar και Koos Vrieze με τίτλο Competitive Markov Decision Processes (1997). Το τρίτο κεφάλαιο βασίστηκε στην εργασία των S. Sinha και K. G. Bakshi με τίτλο Zero-Sum Two Person Perfect Information Semi-Markov Games: A Reduction (2022). Στην εργασία αναδεικνύεται ο ρόλος του Γραμμικού Προγραμματισμού, στην ανάλυση και επίλυση προβλημάτων που μοντελοποιούνται είτε ως διαδικασίες απόφασης είτε ως παίγνια. Όπως θα γίνει αντιληπτό, μελετώντας συγκεκριμένες κατηγορίες παιγνίων ως προς τη δομή τους, εν τέλει, ο υπολογισμός μιας βέλτιστης πολιτικής η οποία θα αποφέρει το μέγιστο αναμενόμενο κέρδος (ή την ελάχιστη ζημία) αποτελεί πρόβλημα που ισοδυναμεί με την επίλυση κατάλληλα κατασκευασμένων γραμμικών προγραμμάτων. Στο τρίτο κεφάλαιο γενικεύονται τα παίγνια που προαναφέρθηκαν, τα οποία πλέον θα καλούνται Ημιμαρκοβιανά Παίγνια. Πραγματοποιείται ανάλυση μιας συγκεκριμένης κλάσης αυτής της ιδιαίτερα ευρείας κατηγορίας παιγνίων, τα Ημιμαρκοβιανά Παίγνια Τέλειας Πληροφόρησης. Τέλος, γίνεται υλοποίηση του σχετικού αλγορίθμου επίλυσης τέτοιων παιγνίων με το λογισμικό MATLAB και παρατίθενται τα σχετικά αποτελέσματα.
description: The present paper initially includes a review with Stochastic Games as the main subject. Τhe first chapter is an introduction to Markov Decision Processes, a significant tool in order to study the more complicated case of Stochastic Games, which are going to be the subject of the next chapter. A big part of the theory developed in the first two chapters is due to the book Competitive Markov Decision Processes (1997), written by Jerzy Filar και Koos Vrieze. The third chapter is based on a research paper by S. Sinha και K. G. Bakshi, titled as Zero-Sum Two Person Perfect Information Semi-Markov Games: A Reduction (2022). Through this paper, the role of Linear Programming stands out in analyzing and solving problems which can be modelled as either decision processes or stochastic games. When analyzing specific subclasses of games regarding their structure, it is concluded that finding the policy that maximizes the expected profit (or minimizes the expected damage) is a problem equivalent to solving suitably constructed linear programs. In the third chapter, semi-Markov games, a generalization of the games mentioned so far, are being introduced. The main subject of this chapter is a specific category of semi-Markov games, called Perfect Information semi-Markov games. Finally, a specific algorithm regarding the solution of such games is implemented through the MATLAB software and its results are briefly discussed.