Σχεδιασμός μηχανισμών, κοινωνική επιλογή και υπολογισμός ισορροπιών σε περιορισμένα πεδία
Περίληψη
Η παρούσα διδακτορική διατριβή μελετάει αποδοτικά αλγοριθμικά πλαίσια για περιβάλλοντα στα οποία η πληροφορία δεν είναι άμεσα διαθέσιμη. Πιο συγκεκριμένα μελετάει περιορισμούς στην πρόσβαση στην πληροφορία από τρεις διαφορετικές γωνίες: (1) Η πληροφορία είναι προσωπική (και ιδιωτική) σε στρατηγικούς παίκτες και χρειάζεται να αποκαλυφθεί στον αλγόριθμο μέσα από κατάλληλα σχεδιασμένα κίνητρα: Αυτή η περιοχή συνήθως αναφέρεται ως «αλγοριθμικός σχεδιασμός μηχανισμών». Η έρευνα στα πλαίσια της διατριβής επικεντρώνεται στην αντιμετώπιση ισχυρών αρνητικών αποτελεσμάτων περιορίζοντας την ανάλυση σε «φυσιολογικά» υποσύνολα στιγμιότυπων του προβλήματος, μια πρακτική από την περιοχή της ανάλυσης πέραν της χειρότερης περίπτωσης στη θεωρία αλγορίθμων. Συγκεκριμένα, αναλύεται η προσεγγισιμότητα του προβλήματος χωροθέτησης εγκαταστάσεων από φιλαλήθεις μηχανισμούς. (2) Η επικοινωνία είναι ακριβή: Μελετώντας αυτόν τον περιορισμό σε περιβάλλοντα με στρατηγικούς παίκτες αποδεικνύεται ότι απλοί μηχανισμοί ...
περισσότερα
Περίληψη σε άλλη γλώσσα
Abstract: The work in this thesis primarily revolves around efficient algorithmic frameworks for settings where information is not readily available. Specifically, we look at limitations of provided information from three main angles: (1) Information is difficult to quantify. In this line of work we focused on distortion in voting (JAIR ’22, AAAI ’22), which is the notion that quantifies the impact of being able to use only limited information on the social welfare of the outcome (i.e. in terms of approximation). Here 1 we study both the effects of various forms of limited information on metric distortion and also the distortion of a very popular mechanism, STV, in relation to the dimensionality of the underlying metric space. (2) Information is private to strategic agents and needs to be revealed to the algorithm through properly designed incentives. This area is commonly referred to as mechanism design and my related work focuses on fighting strong impossibility results by restrictin ...
περισσότερα
![]() | |
![]() | Κατεβάστε τη διατριβή σε μορφή PDF (2.35 MB)
(Η υπηρεσία είναι διαθέσιμη μετά από δωρεάν εγγραφή)
|
Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.
|
Στατιστικά χρήσης
![](/eadd/image/spinner.gif)
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
Πηγή: Google Analytics.
![](/eadd/image/spinner.gif)
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
Πηγή: Google Analytics.
![](/eadd/image/spinner.gif)
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
![](/eadd/image/spinner.gif)
ΧΡΗΣΤΕΣ
Αφορά στους συνδεδεμένους στο σύστημα χρήστες οι οποίοι έχουν αλληλεπιδράσει με τη διδακτορική διατριβή. Ως επί το πλείστον, αφορά τις μεταφορτώσεις.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.