Back to search

National and Kapodistrian University of Athens

Inefficiency of Ordinal One-Sided Matching Mechanisms

Abstract

dc:description

Αυτή η διπλωματική εργασία εξετάζει μηχανισμούς μονομερούς αντιστοίχισης με βάση τις διατακτικές προτιμήσεις παικτών, οι οποίοι κατανέμουν αδιαίρετους πόρους. Επικεντρωνόμαστε σε δύο σημαντικούς μηχανισμούς: τον Random Priority και τον Probabilistic Serial. Ο Random Priority είναι ασφαλής από χειραγώγηση από τους παίκτες (truthful), αλλά συχνά οδηγεί σε υποβέλτιστα δίκαια αποτελέσματα, ενώ ο Probabilistic Serial παράγει δίκαια αποτελέσματα, αλλά είναι ευάλωτος σε χειραγώγηση. Εξετάζουμε αρκετές έννοιες, όπως την κοινωνική ευημερία, την αποδοτικότητα, την ασφάλεια στην χειραγώγηση και αναλύουμε την απόδοση αυτών των μηχανισμών. Μελετούμε το Approximation Ratio, το οποίο ποσοτικοποιεί πόσο κοντά βρίσκεται το αποτέλεσμα ενός μηχανισμού στην ιδανική λύση από την άποψη της κοινωνικής ευημερίας· το Τίμημα της Αναρχίας (Price of Anarchy), που μετρά πώς η στρατηγική συμπεριφορά των παικτών επηρεάζει την αποδοτικότητα του μηχανισμού· το Incentive Ratio, το οποίο εκφράζει το μέγιστο όφελος που μπορεί να κερδίσει ένας παίκτης με την αλλαγή των προτιμήσεων σε σύγκριση με την αληθινή του αναφορά. Τέλος, παραθέτουμε πειραματικά αποτελέσματα και συζητούμε μια νέα μετρική, για να εκτιμηθεί πώς η στρατηγική συμπεριφορά των πρακτόρων επηρεάζει το κοινωνικό όφελος του μηχανισμού, σε σχέση με την έκβαση του, αν όλοι έλεγαν την αλήθεια.

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Σταμάτης Βασίλειος
  • Stamatis Vasileios

Subjects

dc:subject × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:3417298

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Σταμάτης Βασίλειος; Stamatis Vasileios. Inefficiency of Ordinal One-Sided Matching Mechanisms. 2024. https://pergamos.lib.uoa.gr/uoa/dl/object/3417298