Μηχανισμοί χωροθέτησης κτιρίου με κλασματικές προτιμήσεις

Στη συγκεκριμένη μεταπτυχιακή διπλωματική εργασία σχεδιάζουμε μηχανισμούς σχετικά με το πρόβλημα χωροθέτησης κτιρίου. Συγκεκριμένα, εξετάζουμε το μοντέλο όπου όλοι οι παίκτες βρίσκονται σε μια γραμμή και τους ενδιαφέρει να μεγιστοποιήσουν το όφελός τους, το οποίο εξαρτάται από την απόστασή τους από...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριος συγγραφέας: Παναγιωτοπούλου, Ασημίνα
Άλλοι συγγραφείς: Κακλαμάνης, Χρήστος
Μορφή: Thesis
Γλώσσα:Greek
Έκδοση: 2020
Θέματα:
Διαθέσιμο Online:http://hdl.handle.net/10889/13338
id nemertes-10889-13338
record_format dspace
spelling nemertes-10889-133382022-09-05T20:48:51Z Μηχανισμοί χωροθέτησης κτιρίου με κλασματικές προτιμήσεις Mechanism design for facility location game with fractional preferences Παναγιωτοπούλου, Ασημίνα Κακλαμάνης, Χρήστος Καραγιάννης, Ιωάννης Παπαϊωάννου, Εύη Panagiotopolulou, Asimina Χωροθέτηση κτιρίου Θεωρία παιγνίων Facility location Game theory Στη συγκεκριμένη μεταπτυχιακή διπλωματική εργασία σχεδιάζουμε μηχανισμούς σχετικά με το πρόβλημα χωροθέτησης κτιρίου. Συγκεκριμένα, εξετάζουμε το μοντέλο όπου όλοι οι παίκτες βρίσκονται σε μια γραμμή και τους ενδιαφέρει να μεγιστοποιήσουν το όφελός τους, το οποίο εξαρτάται από την απόστασή τους από τα κτίρια. Οι παίκτες έχουν τη δυνατότητα να παραπλανήσουν σχετικά με την τοποθεσία τους και τις προτιμήσεις τους. Ανάλογα με την περίπτωση, σχεδιάζουμε φιλαλήθεις μηχανισμούς. Ειδικότερα, όταν μας ενδιαφέρει η βελτιστοποίηση του συνολικού οφέλους, όταν οι παίκτες έχουν τη δυνατότητα να παραπλανήσουν σχετικά με την τοποθεσία τους ενώ γνωρίζουμε τις προτιμήσεις τους, παρουσιάζουμε έναν -προσεγγιστικό φιλαλήθη μηχανισμό. Για την περίπτωση που οι παίκτες έχουν τη δυνατότητα παραπλάνησης σχετικά με τις προτιμήσεις τους, παρουσιάζουμε έναν -προσεγγιστικό μηχανισμό, με παίκτες μόνο στα άκρα του διαστήματος. Ενώ για την ειδική περίπτωση με μόνο δύο παίκτες στα άκρα αναλύουμε έναν βελτιωμένο –προσεγγιστικό φιλαλήθη μηχανισμό. Τέλος, για τη βελτιστοποίηση του ελάχιστου κέρδους, όταν υπάρχει μόνο ένα κτίριο, παρουσιάζουμε έναν μηχανισμό που επιτυγχάνει λόγο προσέγγισης. We aim to design mechanisms relating to the problem of Facility Location. In particular, we are going to examine the model where all players exist on a line and they are interested in maximizing their utility, which depends on their distance to the facilities. Players have the option to misreport their location and preferences. When we care about optimizing the social welfare, where players have the option to lie about their location, while we know their true preferences, we design a truthful -approximation mechanism. In the case where players lie about preferences and are located at the endpoints, we design a truthful approximation mechanism, and an improved -approximation mechanism for the case of two players. Finally, when there is only one facility, we analyze a mechanism with approximation ratio for the optimization of the minimum utility. 2020-03-13T21:51:22Z 2020-03-13T21:51:22Z 2019-11-19 Thesis http://hdl.handle.net/10889/13338 gr 0 application/pdf
institution UPatras
collection Nemertes
language Greek
topic Χωροθέτηση κτιρίου
Θεωρία παιγνίων
Facility location
Game theory
spellingShingle Χωροθέτηση κτιρίου
Θεωρία παιγνίων
Facility location
Game theory
Παναγιωτοπούλου, Ασημίνα
Μηχανισμοί χωροθέτησης κτιρίου με κλασματικές προτιμήσεις
description Στη συγκεκριμένη μεταπτυχιακή διπλωματική εργασία σχεδιάζουμε μηχανισμούς σχετικά με το πρόβλημα χωροθέτησης κτιρίου. Συγκεκριμένα, εξετάζουμε το μοντέλο όπου όλοι οι παίκτες βρίσκονται σε μια γραμμή και τους ενδιαφέρει να μεγιστοποιήσουν το όφελός τους, το οποίο εξαρτάται από την απόστασή τους από τα κτίρια. Οι παίκτες έχουν τη δυνατότητα να παραπλανήσουν σχετικά με την τοποθεσία τους και τις προτιμήσεις τους. Ανάλογα με την περίπτωση, σχεδιάζουμε φιλαλήθεις μηχανισμούς. Ειδικότερα, όταν μας ενδιαφέρει η βελτιστοποίηση του συνολικού οφέλους, όταν οι παίκτες έχουν τη δυνατότητα να παραπλανήσουν σχετικά με την τοποθεσία τους ενώ γνωρίζουμε τις προτιμήσεις τους, παρουσιάζουμε έναν -προσεγγιστικό φιλαλήθη μηχανισμό. Για την περίπτωση που οι παίκτες έχουν τη δυνατότητα παραπλάνησης σχετικά με τις προτιμήσεις τους, παρουσιάζουμε έναν -προσεγγιστικό μηχανισμό, με παίκτες μόνο στα άκρα του διαστήματος. Ενώ για την ειδική περίπτωση με μόνο δύο παίκτες στα άκρα αναλύουμε έναν βελτιωμένο –προσεγγιστικό φιλαλήθη μηχανισμό. Τέλος, για τη βελτιστοποίηση του ελάχιστου κέρδους, όταν υπάρχει μόνο ένα κτίριο, παρουσιάζουμε έναν μηχανισμό που επιτυγχάνει λόγο προσέγγισης.
author2 Κακλαμάνης, Χρήστος
author_facet Κακλαμάνης, Χρήστος
Παναγιωτοπούλου, Ασημίνα
format Thesis
author Παναγιωτοπούλου, Ασημίνα
author_sort Παναγιωτοπούλου, Ασημίνα
title Μηχανισμοί χωροθέτησης κτιρίου με κλασματικές προτιμήσεις
title_short Μηχανισμοί χωροθέτησης κτιρίου με κλασματικές προτιμήσεις
title_full Μηχανισμοί χωροθέτησης κτιρίου με κλασματικές προτιμήσεις
title_fullStr Μηχανισμοί χωροθέτησης κτιρίου με κλασματικές προτιμήσεις
title_full_unstemmed Μηχανισμοί χωροθέτησης κτιρίου με κλασματικές προτιμήσεις
title_sort μηχανισμοί χωροθέτησης κτιρίου με κλασματικές προτιμήσεις
publishDate 2020
url http://hdl.handle.net/10889/13338
work_keys_str_mv AT panagiōtopoulouasēmina mēchanismoichōrothetēsēsktirioumeklasmatikesprotimēseis
AT panagiōtopoulouasēmina mechanismdesignforfacilitylocationgamewithfractionalpreferences
_version_ 1771297316604477441