Σχεδιασμός μηχανισμών για προβλήματα ανάθεσης αγαθών: αλγόριθμοι και αρνητικά αποτελέσματα
Περίληψη
Το επίκεντρο αυτής της διατριβής είναι η μελέτη προβλημάτων ανάθεσης αγαθών τόσο από την αλγοριθμική όσο και από την παίγνιο-θεωρητική πλευρά. Συγκεκριμένα, μας ενδιαφέρουν οι εξής δύο τομείς: 1) Η δίκαιη ανάθεση αδιαίρετων αγαθών, όπου ο στόχος είναι η παραγωγή αναθέσεων που ικανοποιούν ένα συγκεκριμένο κριτήριο δικαιοσύνης 2) Τα προβλήματα διαμοιρασμού κόστους πολλών αντικειμένων, όπου ο στόχος είναι η παραγωγή αναθέσεων και μεθόδων διαμοιρασμού κόστους, που επιτυγχάνουν το κριτήριο της κοινωνικής ωφέλειας, υπό τον περιορισμό της κάλυψης του κόστους.Και για τα δυο αυτά είδη προβλημάτων, παρέχουμε αλγορίθμους που επιτυγχάνουν βέλτιστους ή σχεδόν βέλτιστους προσεγγιστικούς παράγοντες ως προς τα κριτήρια που ανά περίπτωση μας ενδιαφέρουν, δίνοντας έτσι μια ολοκληρωμένη εικόνα του τι είναι δυνατό σε αυτά τα δυο πεδία.
Περίληψη σε άλλη γλώσσα
The focus of this thesis is the study of resource allocation problems from both an algorithmic and a game theoretic point of view. In particular, we are interested in the following two areas within algorithmic game theory: 1) Fair division of indivisible items, where the goal is to produce allocations that satisfy a certain fairness criterion 2) Multi-item cost sharing problems, where the goal is to provide allocations and cost-sharing methods that achieve economic efficiency, under the constraint of covering the incurred cost. The first part of the thesis regards the domain of computational fair division where the objective is to allocate a set of indivisible resources to a set of agents, when there are no monetary transfers, and in a way that leaves everyone satisfied. We are interested in the connection between the exact and the approximate versions of several recently introduced relaxations of envy-freeness and proportionality. We establish several tight, or almost tight, results c ...
περισσότερα
Κατεβάστε τη διατριβή σε μορφή PDF (2.18 MB)
(Η υπηρεσία είναι διαθέσιμη μετά από δωρεάν εγγραφή)
|
Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.
|
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στους συνδεδεμένους στο σύστημα χρήστες οι οποίοι έχουν αλληλεπιδράσει με τη διδακτορική διατριβή. Ως επί το πλείστον, αφορά τις μεταφορτώσεις.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.