The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


             Walmart Lecture Series in Cryptography and Complexity

                     Lecture Hall, Room 1, Ziskind Building
                            on Sunday, June 26, 2011
                                    at 11:00





                                Nicole Immorlica
                            Northwestern University


                                 will speak on


                     Optimal Auctions over Social Networks

Abstract:
We consider the problem of selling a digital good, like a Facebook App, in a
social network.  We focus on goods that exhibit ``tennis racket externalities"
-- i.e., goods that have value only when used in conjunction with other users.
In a social network, this means that the digital good has no value to a user
unless at least one of his friends in the network also owns the good.  This
severely complicates the problem of selling the digital good as a user's value,
and hence the price we can charge, depends not only on his own situation, but
on the situation of his friends as well.  In this talk, we develop auctions for
selling such goods in a social network.  Our auctions provably extract a
constant fraction of the optimal revenue.

Joint work with N. Haghpanah, V. Mirrokni, and K. Munagala.