From: Rosa Teorell (rosat@microsoft.com)
Date: Fri Jan 30 2004 - 12:36:28 PST
You are invited to attend...
*****************************************************************************************************
WHO: Mohammad Mahdian
AFFILIATION: MIT
TITLE: Marriage, Honesty, and Stability
WHEN: Tue 2/3/2004
WHERE: 113/1159 Research Lecture Room, Microsoft Research
TIME: 10:30AM - 12:00PM
HOST: Jennifer Chayes
******************************************************************************************************
ABSTRACT:
I will begin by giving a short overview of my PhD research including my work on approximation algorithms and algorithmic game theory, and then will focus on a recent joint work with Nicole Immorlica on incentive issues in stable marriage.
Many centralized two-sided markets, such as the medical residency market, form a matching between participants by running a stable marriage algorithm. It is a well-known fact that no matching mechanism based on a stable marriage algorithm can guarantee truthfulness as a dominant strategy for participants. However, as we will show in this talk, in a certain probabilistic setting, truthfulness is (in some sense) the best strategy for the participants.
We show this by proving that in our setting the set of stable marriages is small. We derive several corollaries of this result. First, we show that, with high probability, in a stable marriage mechanism, the truthful strategy is the best response for a given player when the other players are truthful. Then we analyze equilibria of the deferred acceptance stable marriage game. We show that the game with complete information has an equilibrium in which a $(1-o(1))$ fraction of the strategies are truthful in expectation. In the more realistic setting of a game of incomplete information, we will show that the set of truthful strategies form a $(1+o(1))$-approximate Bayesian-Nash equilibrium. Our results have implications in many practical settings and were inspired by experimental observations in a paper of Roth and Peranson (1999) concerning the National Residency Matching Program.
BIO:
Mohammad Mahdian is a fourth year Ph.D. student in theoretical computer science at the Massachusetts Institute of Technology. He has a Bachelor degree in Computer Engineering from Sharif University of Technology, and a Masters degree in Computer Science from the University of Toronto. His main research interests include approximation algorithms and algorithmic aspects of game theory and economics, but he enjoys working on interesting problems in other areas of theoretical computer science and combinatorics as well.
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Fri Jan 30 2004 - 12:37:37 PST