<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 12pt; color: #000000'><b>How to Design Simple Efficient Mechanisms that are also Composable</b>
<br>
<b><a href="http://www.cs.cornell.edu/people/eva/eva.html">Eva Tardos</a></b>, <a href="http://www.cornell.edu/">Cornell University</a><br><b><a name="2012-11-19">Monday, November 19, 2012</a>, 4:30 PM - 5:30 PM<br>Computer Science 105</b><br>
<br>
E-commerce applications require simple, and well-designed systems, and
systems that work well even if users participate in multiple mechanisms
(and the value of each player overall is a complex function of their
outcomes). Traditional mechanism design has considered such mechanisms
only in isolation, and the mechanisms it proposes tend to be complex and
impractical. In contrast, players typically participate in various
mechanisms, mechanisms that are run by different principals (e.g.
different sellers on eBay or different ad-exchange platforms) and
coordinating them to run a single combined mechanism is infeasible or
impractical. Even the simple and elegant Vickrey auction loses some of
its appeal when not in isolation: when the overall value of each player
is a complex function of their outcomes, the global mechanism is no
longer truthful.<br><br><p>
In this talk we initiate the study of efficient mechanism design with
guaranteed good properties even when players participate in multiple
different mechanisms either simultaneously or sequentially. Over the
last decade, computer scientists and game theorists have developed good
understanding of the impact of strategic user behavior on system
performance in environments that include selfish traffic routing,
service location, and bandwidth sharing. We will consider simple
mechanisms from this perspective. We define smooth mechanisms (that can
be thought of as mechanisms that generate approximately market clearing
prices), and show that smooth mechanisms are approximately efficient,
and the efficiency guarantees for smooth mechanisms (when studied in
isolation) carry over to the same or approximately the same guarantees
for a market composed of such mechanisms. Joint work with Vasilis
Syrgkanis. <br></p><p><br></p>
Eva Tardos is a Jacob Gould Schurman Professor of Computer Science at
Cornell University, is Senior Associate Dean of Computing and
Information Science, and was department chair 2006-2010. She received
her PhD from Eotvos University in Budapest. She has been elected to the
National Academy of Engineering and the American Academy of Arts and
Sciences, and is the recipient of some fellowships and awards, including
the Packard Fellowship, the Fulkerson Prize and the Dantzig prize. She
was editor in chief of SIAM Journal of Computing 2003-09, and is editor
of several other journals, including the Journal of the ACM, and
Combinatorica. Her research interest is algorithms and algorithmic game
theory, the subarea theory of designing systems and algorithms for
selfish users.
</div></body></html>