Search Mailing List Archives
[theory-seminar] Fw: [RAIN] RAIN Seminar Wednesday 10/18 12-1 PM at Y2E2 101: Michal Feldman on Prophet Inequalities
ofirgeri at stanford.edu
Tue Oct 17 20:00:50 PDT 2017
A talk of interest tomorrow at RAIN:
Michal Feldman from Tel-Aviv University is giving a talk on a cool new result regarding prophet inequalities from this week's FOCS.
---------- Forwarded message ----------
From: Anilesh K. Krishnaswamy <anilesh at stanford.edu<mailto:anilesh at stanford.edu>>
Date: Tue, Oct 17, 2017 at 2:30 AM
Subject: [RAIN] RAIN Seminar Wednesday 10/18 12-1 PM at Y2E2 101
To: internetalgs at lists.stanford.edu<mailto:internetalgs at lists.stanford.edu>
Michal Feldman from Tel-Aviv University is speaking at RAIN this Wednesday.
Venue: Y2E2 101
Time: 12 noon - 1 pm.
Details of her talk are below. If you would like to meet with her, please sign up in the following document: https://docs.google.com/spreadsheets/d/16BSjFVlts7JlTvLBwHhbaYyngQ--MqLmrlZyFsf3nl0/edit?usp=sharing
Hope to see you there!
Title: Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs
Speaker: Michal Feldman, Tel-Aviv University
Abstract: We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes prophet inequalities by constructing price-based online approximation algorithms, a natural extension of threshold algorithms for settings beyond binary selection. Our analysis takes the form of an extension theorem: we derive sufficient conditions on prices when all weights are known in advance, then prove that the resulting approximation guarantees extend directly to stochastic settings. Our framework unifies and simplifies much of the existing literature on prophet inequalities and posted price mechanisms, and is used to derive new and improved results for combinatorial markets (with and without complements), multi-dimensional matroids, and sparse packing problems. Finally, we highlight a surprising connection between the smoothness framework for bounding the price of anarchy of mechanisms and our framework, and show that many smooth mechanisms can be recast as posted price mechanisms with comparable performance guarantees.
Bio: Michal Feldman is a Professor of computer science in the Blavatnik School of Computer Science at Tel Aviv University and a researcher at Microsoft Research (MSR) Herzliya. Her research focuses on the intersection of computer science, game theory and microeconomics. She received her Ph.D. from the University of California at Berkeley in 2005, and did her postdoc at the Hebrew University (2005-07). She was a faculty member in the School of Business Administration and the Center for the study of rationality at the Hebrew University (2007-13), and a visiting professor at Harvard University and Microsoft Research New England (2011-13). She serves on the editorial board of various journals, including GEB, MOR, JCSS and ACM TEAC. She is the vice chair of ACM SIGEcom, and served as the PC chair of ACM Conference on Economics and Computation 2015. She is the recipient of various grants and fellowships, including ERC (European Research Council), Marie Curie IOF, Alon, and ISF. She is a member of the Israeli Young Academy and an alumna of the Global Young Academy.
Anilesh K. Krishnaswamy,
Department of Electrical Engineering,
internetalgs mailing list
internetalgs at lists.stanford.edu<mailto:internetalgs at lists.stanford.edu>
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar