Παιγνιοθεωρητικές πτυχές του παιγνίου - αστυνόμοι και ληστής - και παραλλαγών αυτού

Στην παρούσα διατριβή εισάγουμε ορισμένες παραλλαγές του παιγνίου «Αστυνόμοι και Ληστής» (CR) και κατόπιν αναλύουμε παιγνιοθεωρητικά, τόσο το πρωτότυπο παίγνιο, όσο και αυτές τις παραλλαγές, στο πλαίσιο των στοχαστικών παιγνίων. Το CR είναι ένα παίγνιο καταδίωξης σε γράφημα, μεταξύ ενός παίκτη που ελέγχει ένα αριθμό αστυνόμων και ενός ληστή. Δεδομένου γραφήματος τα κεντρικά ερωτήματα τότε είναι: (α) ποιος είναι ο ελάχιστος αριθμός αστυνόμων που εγγυάται σύλληψη, ποσότητα που ονομάζουμε «αστυνομικό αριθμό του γραφήματος» και (β) ποιες είναι οι βέλτιστες στρατηγικές των παικτών. Τα παίγνια που εισάγουμε είναι: (α) το «Σύγχρονο Παίγνιο» (CCR) όπου σε αντίθεση με το πρωτότυπο οι παίκτες κινούνται ταυτοχρόνως (και όχι εναλλάξ), (β) το παίγνιο «Ιδιοτελείς Αστυνόμοι και Παθητικός Ληστής» (SCPR) όπου δύο παίκτες, οι αστυνόμοι, καταδιώκουν ανεξάρτητα ο ένας από τον άλλο ένα παθητικό Ληστή, και (γ) το παίγνιο «Ιδιοτελείς Αστυνόμοι και Ενεργητικός Ληστής» (SCAR) όπου ένας αριθμός αστυνόμων καταδιώκουν, ανεξάρτητα ο ένας από τον άλλο, ένα ληστή που επιχειρεί να διαφύγει. Τα CR, CCR και SCPR τα μορφοποιούμε ως στοχαστικά (2-παικτών) παίγνια μηδενικού αθροίσματος και δείχνουμε σε κάθε περίπτωση την ύπαρξη αξίας και βέλτιστων θεσιακών στρατηγικών, ενώ παρουσιάζουμε και αλγόριθμους υπολογισμού αυτών. Στο CCR ορίζουμε επιπλέον τον «σύγχρονο αστυνομικό αριθμό γραφήματος», αναλόγως με τον κλασικό ορισμό και δείχνουμε ότι ισούται πάντα προς τον κλασικό αστυνομικό αριθμό. Το SCAR το μορφοποιούμε ως ένα στοχαστικό, Ν-παικτών παίγνιο μεταξύ, Ν-1 αστυνόμων και ενός ληστή και δείχνουμε ότι δέχεται πάντα σημεία ισορροπίας κατά Nash σε θεσιακές και μη θεσιακές στρατηγικές. Επιπλέον δείχνουμε μία σειρά αποτελεσμάτων που συνδέουν τον αστυνομικό αριθμό με τη συλληψιμότητα και, αφού πρώτα ορίσουμε τον «ιδιοτελή αστυνομικό αριθμό γραφήματος», δείχνουμε κατόπιν ότι ισούται πάντα προς τον κλασικό αστυνομικό αριθμό.