Σχεδιασμός μηχανισμών, κοινωνική επιλογή και υπολογισμός ισορροπιών σε περιορισμένα πεδία

Περίληψη

Η παρούσα διδακτορική διατριβή μελετάει αποδοτικά αλγοριθμικά πλαίσια για περιβάλλοντα στα οποία η πληροφορία δεν είναι άμεσα διαθέσιμη. Πιο συγκεκριμένα μελετάει περιορισμούς στην πρόσβαση στην πληροφορία από τρεις διαφορετικές γωνίες: (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 ...
περισσότερα

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/54559
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/54559
ND
54559
Εναλλακτικός τίτλος
Mechanism design, social choice and equilibrium computation in restricted domains
Συγγραφέας
Πατσιλινάκος, Παναγιώτης του Σωτήριος
Ημερομηνία
2023
Ίδρυμα
Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ). Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών. Εργαστήριο Λογικής και Επιστήμης Υπολογισμών
Εξεταστική επιτροπή
Φωτάκης Δημήτριος
Παγουρτζής Αριστείδης
Συμβώνης Αντώνιος
Χριστοδούλου Γεώργιος
Καραγιάννης Ιωάννης
Μαρκάκης Ευάγγελος
Βαρβαρίγος Εμμανουήλ
Επιστημονικό πεδίο
Επιστήμες Μηχανικού και ΤεχνολογίαΕπιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ ➨ Υπολογιστές, Υλικό (hardware) και Αρχιτεκτονική
Λέξεις-κλειδιά
Αλγοριθμική θεωρία παιγνίων; Αλγοριθμική κοινωνική επιλογή; Προσεγγιστικοί αλγόριθμοι; Υπολογιστική πολυπλοκότητα; Σχεδιασμός μηχανισμών; Σχεδιασμός αλγορίθμων; Μετρική παραμόρφωση; Υπολογισμός ισορροπιών; Πολυπλοκότητα επικοινωνίας; Ανάλυση πέραν της χειρότερης περίπτωσης
Χώρα
Ελλάδα
Γλώσσα
Αγγλικά
Άλλα στοιχεία
εικ., πιν., σχημ., γραφ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στους συνδεδεμένους στο σύστημα χρήστες οι οποίοι έχουν αλληλεπιδράσει με τη διδακτορική διατριβή. Ως επί το πλείστον, αφορά τις μεταφορτώσεις.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.