IPM:
Sat April 5th (Farvardin 17) 10--12
Mon April 7th (Farvardin 19) 10--12
Wed April 9th (Farvardin 21) 10--12


Sharif Math:
Tues. April 8th (Farvardin 20) 9--10

Sharif CE:
Tues. April 8th (Farvardin 20) 12--13

Bio:
Nicole Immorlica received her Ph.D. in June 2005 from MIT. From 2005-2007,
she was a postdoctoral researcher at the Theory Group in Microsoft Research.
She is currently visiting Centruum voor Wiskunde en Informatica (CWI) in
Amsterdam, the Netherlands before beginning a faculty position at
Northwestern University in September 2008. Her research interests lie in
applying techniques from the field of theoretical computer science to
problems at the forefront of economics and computer science. Her recent
research has focused on auction design, particularly sponsored search
auctions; matching markets such as the National Residency Matching Program
(NRMP); and the formation and diffusion of information in social networks.


For IPM:

Mini-Course on Algorithmic Game Theory


Since its inception in the 1980s, the popularity of the Internet has been
growing exponentially, resulting in a mass of shared knowledge and fast,
cheap communication. Hand-in-hand with these developments, we have seen the
birth of a plethora of new systems for facilitating interaction among
economic agents from marketplaces like eBay and Google's AdWords to online
networking services like MySpace and Match.com. These systems give rise to
numerous opportunities for scientific exploration, and such studies are
fundamental to the future economic and social success of these systems.

Algorithmic game theory is a new paradigm for studying such systems. The
goal in this field is to understand the behavior of autonomous selfish
agents, and to define rules that encourage them to collectively act in a way
that optimizes some system objective such as social welfare or revenue. This
course offers a broad overview of hot topics in algorithmic game theory.
Each day highlights a different subfield. On the first day, we will discuss
basic concepts in game theory including various equilibrium notions, and
learn about the complexity of computing equilibria. On the second day, we
will consider an important application of algorithmic game theory, namely
auction design. In this section of the course, we will discuss generic
techniques for revenue and welfare maximization and then study the design of
a real-world marketplace, the sponsored-search auctions of Google,
Microsoft, and Yahoo! On the third day, we will discuss the emerging field
of social networks, with a particular emphasis on predicting how information
and technologies diffuse over these networks.

Familiarity with basic concepts in probability and computer science is
assumed.


For Sharif Math:

Secretary Problems and Online Auction Design


This talk considers the problem of online auction design, or auctions for
bidders who arrive and depart over time (e.g. Priceline.com). Maximizing
welfare in such auctions is complicated by the fact that bids must be
accepted or rejected at the moment they are submitted. It is known how the
classic secretary problem introduced by Dynkin in 1963 can be used to design
approximately welfare-maximizing auctions in a simple multi-unit auction
setting. We show how the classic secretary problem can be generalized to a
combinatorial setting, and use this generalization to build mechanisms for a
class of online combinatorial auctions.

Parts of this talk are based on joint work with Moshe Babaioff, David Kempe,
and Bobby Kleinberg.



For Sharif CE:

Derandomization of Auctions


The focus of the talk will be based on a framework introduced by Goldberg et
al. for maximizing revenue in auctions for a good of unlimited supply (this
framework will be introduced in the Mini-Course on Algorithmic Game Theory
at IPM on Monday). Earlier work of Goldberg et al. introduced randomized
auction mechanisms that, in the worst case, achieve close to the optimal
revenue. We investigate the feasibility of high revenue deterministic
auctions. In the process, we give an exponential-space construction for
converting any randomized auction to a deterministic one with approximately
the same revenue properties. We do so by first proving the existence of a
deterministic solution to a related problem, the 'hat coloring problem', in
which everyone at a party attempts to guess the color of his own hat by just
observing the colors of his friends' hats. Our proof draws upon a seemingly
unrelated set of techniques from the literature on network flows. We also
present a polynomial-time deterministic construction of an auction with good
revenue properties, using parity arguments. Our work bypasses an
impossibility result of Goldberg et al. for deterministic symmetric auctions
by introducing asymmetry into the allocation and pricing scheme, suggesting
that in this setting asymmetry is essentially as powerful as randomness.

This talk is based on joint work with Gaggan Aggarwal, Amos Fiat, Andrew
Goldberg, Jason Hartline, and Madhu Sudan.