Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17391
Title: Παιγνιοθεωρητικά Μοντέλα για Προβλήματα Προσανατολισμού
Authors: Τριανταφύλλου, Στυλιανός
Φωτάκης Δημήτριος
Keywords: Orienteering Problem
Game Theory
Congestion Games
Selfish Routing
Atomic Games
Non-atomic Games
C-secure Games
Series Parallel Networks
Extension Parallel Networks
Convex Optimization
Fixed Point Theorems
Issue Date: 21-Oct-2019
Abstract: Σε αυτή την διπλωματική εργασία εισάγουμε μια νέα παιγνιοθεωρητική προσέγγιση του Orienteering Problem (OP) και ονομάζεται Multi-agent Orienteering Problem (MOP). Σε αντίθεση με την κλασική μορφή του OP, που ασχολείται με την κατανομή ενός συνόλου παικτών στα μονοπάτια ενός δικτύου, μέσω κεντρικής διαχείρισης, το MOP θεωρεί ότι ο κάθε παίκτης πλέον αποφασίζει για τον εαυτό του και κοιτά αποκλειστικά και μόνο το προσωπικό του συμφέρον. Θεωρείται επίσης ότι ο κάθε παίκτης παίρνει λογικές αποφάσεις και άρα το MOP εμπίπτει στην κατηγορία των non-cooperative games. Δεδομένου ενός δικτύου και δύο κόμβων του s και t, οι παίκτες του παιχνιδιού καλούνται να επιλέξουν το μονοπάτι που θα ακολουθήσουν για να πάνε από τον κόμβο s στον κόμβο t. Κάθε κόμβος του δικτύου χαρακτηρίζεται από ένα σταθερό κέρδος και μια αύξουσα συνάρτηση καθυστέρησης, η οποία εξαρτάται από το πόσοι παίκτες έχουν επιλέξει μονοπάτι που περιέχει αυτό τον κόμβο. Ο χρόνος που θα πάρει σε κάποιον παίκτη για να μετακινηθεί από τον κόμβο s στον κόμβο t είναι ίσος με τη συνολική καθυστέρηση που θα του επιβληθεί από όλους τους κόμβους, που ανήκουν στο μονοπάτι που έχει αποφασίσει να ακολουθήσει. Επίσης το κέρδος που θα προσκομίσει κάποιος παίκτης, είναι ίσο με το άθροισμα των κερδών όλων των κόμβων του μονοπατιού του. Στόχος κάθε παίκτη είναι να επιλέξει ένα s-t μονοπάτι με το οποίο θα μεγιστοποιήσει το κέρδος του και ταυτόχρονα δεν θα ξεπεράσει ένα συγκεκριμένο χρονικό όριο. Θεωρούμε ότι όλοι οι παίκτες κοιτάνε αποκλειστικά και μόνο το προσωπικό τους συμφέρον, χωρίς να τους ενδιαφέρει να βοηθήσουν ή να υπονομεύσουν κάποιον άλλον παίκτη (selfish agents). Είναι προφανές ότι η “επιτυχία” κάθε παίκτη εξαρτάται σε μεγάλο βαθμό από τις επιλογές που έχουν κάνει οι υπόλοιποι παίκτες, για παράδειγμα αν όλοι οι παίκτες αποφασίσουν να ακολουθήσουν το πιο κερδοφόρο μονοπάτι, τότε είναι πολύ πιθανό να βγουν όλοι εκτός χρόνου. Το βασικό ερώτημα είναι εάν το συγκεκριμένο παιχνίδι έχει ισορροπία Nash ή όχι, δηλαδή αν υπάρχει κατανομή των παικτών σε s-t μονοπάτια, τέτοια ώστε κανένας παίκτης να μη μπορεί να βελτιώσει το κέρδος του, αλλάζοντας ατομικά το μονοπάτι που ακολουθεί. Αν αποδειχθεί ότι υπάρχει μια τέτοια κατανομή, τότε το επόμενο βήμα είναι η αναζήτηση κάποιου αλγόριθμου που να την υπολογίζει αποδοτικά, αλλά και η εκτίμηση του πόσο χειρότερο μπορεί να είναι το συνολικό κέρδος που θα αποκομίσουν οι παίκτες αν την ακολουθήσουν, σε σχέση με αυτό της βέλτιστης λύσης. Αρχικά ορίζουμε την atomic παραλλαγή του προβλήματος (AMOP), σύμφωνα με την οποία κάθε παίκτης θεωρείται μη αμελητέα ποσότητα. Δείχνουμε ότι υπάρχει NE σε κάθε στιγμιότυπο του AMOP, που ανήκει στην singleton περίπτωση ή που αποτελείται από δίκτυο με δύο ενδιάμεσους κόμβους. Παρουσιάζουμε δύο στιγμιότυπα του AMOP με δύο μόνο παίκτες, ενός εκ των οποίων μάλιστα το δίκτυο είναι extension parallel, για τα οποία δεν υπάρχει NE. Επιπλέον δείχνουμε ότι το πρόβλημα του να αποφασίσουμε αν ένα στιγμιότυπο του AMOP έχει NE ή όχι, είναι NP-complete. Στην συνέχεια ορίζουμε τη non-atomic παραλλαγή του προβλήματος (NMOP), σύμφωνα με την οποία κάθε παίκτης θεωρείται μη υπολογίσιμη ποσότητα. Δείχνουμε ότι το Price of Anarchy (PoA) του NMOP είναι unbounded. Περιγράφουμε και ορίζουμε τον χώρο των feasible λύσεων του προβλήματος και παρουσιάζουμε τις δυσκολίες που προκαλεί στην απόδειξη ύπαρξης NE, όταν κάνουμε χρήση των fixed point theorems ή του convex optimization. Καταλήγουμε ότι για κάθε στιγμιότυπο του NMOP υπάρχει NE, δείχνοντας ότι είναι C-Secure σε κάθε κατανομή των παικτών, που δεν αποτελεί NE του. Δείχνουμε έναν άπληστο αλγόριθμο εύρεσης NE, για στιγμιότυπα του NMOP, με se ries parallel δίκτυα και αποδεικνύουμε την ορθότητα του. Τέλος παρουσιάζουμε μερικά αποτελέσματακαισυμπεράσματα, σχετικάμετηνσυμπεριφοράενόςδικτύου, κατατημεταφορά παικτών ανάμεσα σε δύο μονοπάτια του.
URI: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17391
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
Στέλιος Τριανταφύλλου-Διπλωματική Εργασία.pdfΣτέλιος Τριανταφύλλου816.93 kBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.