[Colloquium] REMINDER: 3/16 Talks at TTIC: S. Matthew Weinberg, MIT

[Mary Marre]

When:     Wednesday, March 16th at 11:00 am

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       S. Matthew Weinberg, MIT


Title:       Algorithms for Strategic Agents

Abstract: When real people interact with algorithms (e.g. in auctions,
crowdsourcing, Bitcoin, etc.), they impose additional desiderata beyond
simply that the algorithm is correct, fast, and uses little storage. People
strategize during these interactions, so algorithms deployed in these
settings must be robust against strategic manipulation. Additionally,
people prefer transparent interactions, so these algorithms must also be as
simple as possible. My research addresses these, and other novel challenges
that arise when algorithms interact with strategic agents.

In this talk, I will focus on robustness against strategic manipulation,
and present a new algorithmic framework for these settings. Specifically, I
will present a black-box reduction from solving any optimization problem in
strategic settings, where the input is held by selfish agents with
interests of their own, to solving a perturbed version of that same
optimization problem in traditional settings, where the input is directly
given. I will further apply this framework to resolve two longstanding open
problems: extending Myerson's celebrated characterization of optimal
single-item auctions to multiple items (Myerson 1981), and designing
truthful mechanisms for job scheduling on unrelated machines (Nisan and
Ronen 1999).

Finally, I will briefly show how strategic considerations motivate nice
questions in "traditional" areas of algorithm design as well, and present
some of my work in convex optimization, parallel algorithms, and prophet
inequalities.



Host: Yury Makarychev, yury at ttic.edu  <yury at ttic.edu>


Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160315/9ee6e2b4/attachment.htm