Σας προσκαλώ (και σας συνιστώ ιδιαίτερα) να παρακολουθήσετε την ομιλία του Καθ. Βασίλη Γκατζέλη, Drexel University, την ερχόμενη Πέμπτη 19/12, 13:00 - 14:30, στην αίθουσα Συνεδριάσεων της Σχολής, στο νέο κτήριο της ΣΗΜΜΥ. 

Η ομιλία περιγράφει πως σύγχρονες αλγοριθμικές τεχνικές μπορούν να εφαρμοστούν με επιτυχία σε προβλήματα σχεδιασμού μηχανισμών που απευθύνονται σε στρατηγικές και ιδιοτελείς οντότητες. Ακολουθούν ο τίτλος της ομιλίας, μια σύντομη περίληψη, και ένα σύντομο βιογραφικό του ομιλητή.  

Δ. Φωτάκης

Title: Truthful Cardinal Mechanisms for One-Sided Matching

Abstract: We revisit the well-studied problem of designing mechanisms for one-sided matching markets, where a set of n agents needs to be matched to a set of n heterogeneous items. Each agent i has a value v_{i,j} for each item j, and these values are private information that the agents may misreport if doing so leads to a preferred outcome. Ensuring that the agents have no incentive to misreport requires a careful design of the matching mechanism, and mechanisms proposed in the literature mitigate this issue by eliciting only the ordinal preferences of the agents, i.e., their ranking of the items from most to least preferred. However, the efficiency guarantees of these mechanisms are based only on weak measures that are oblivious to the underlying values. We achieve stronger performance guarantees by introducing a mechanism that truthfully elicits the full cardinal preferences of the agents, i.e., all of the v_{i,j} values. We evaluate the performance of this mechanism using the much more demanding Nash bargaining solution as a benchmark, and we prove that our mechanism significantly outperforms all ordinal mechanisms (even non-truthful ones). To prove our approximation bounds, we also study the population monotonicity of the Nash bargaining solution in the context of matching markets, providing both upper and lower bounds which are of independent interest.

Bio: Vasilis Gkatzelis is an Assistant Professor in Computer Science at Drexel University. He previously held positions as a postdoctoral scholar at the computer science departments of UC Berkeley and Stanford University, and as a research fellow at the Simons Institute for the Theory of Computing. He received his PhD from the Courant Institute of New York University and his research focuses on problems in algorithmic game theory and approximation algorithms.