[Colloquium] Reminder: Guest Speakers @ TTI-C Today (4/13/06)

[Katherine Cumming]

**********TTI-C Guest Speakers Today***********
                                 April 13, 2006
        Presented by:  Toyota Technological Institute at Chicago
 
Speaker:  Mohammad Mahdian, Microsoft Research Theory Group
Speaker's home page:  <http://research.microsoft.com/~mahdian/>
http://research.microsoft.com/~mahdian/
 
Date: Thursday, April 13, 2006 
Location: TTI-C Conference Room
Time:  10:00 am
 
Title:   Marriage, Honesty, and Stability
 
Abstract:  
 
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. 
 
Speaker:  Venkati Guruswami ,University of Washington
Speaker's home page: http://www.cs.washington.edu/homes/venkat/
Date: Thursday, April 13, 2006 
Location: TTI-C Conference Room
Time:  11:15 am
 
Title:   List Decoding: What, Why and How?
Abstract:
Suppose you want to communicate a message of k packets on a noisy
communication channel. So you judiciously encode it as a redundant
collection of n = ck packets and transmit these. What is the fewest number
of correct packets one needs to receive in order to have any hope of
recovering the message? Well, clearly one needs at least k correct packets.
In this talk, I will introduce and motivate a error-recovery model called
list decoding under which one can attain this information-theoretic limit.
Specifically, for any desired eps > 0, there is a coding scheme that enables
recovery of the message as long as at least k(1+eps) packets are received
intact. The location of the correct packets and the errors on the remaining
packets can be picked adversarially by the channel. Depending on time, I'll
give a peek into the algebraic ideas and constructions that lead to the
above result. The talk will be self-contained. 
----------------------------------------------------------------------------
------
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or  <mailto:kcumming at tti-c.org> kcumming at tti-c.org

For information on future TTI-C talks and events, please go to the TTI-C
Events page:  http://www.tti-c.org/events.html.  TTI-C (1427 East 60th
Street, Chicago, IL  60637)
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060413/3f37969f/attachment.htm