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