Revenue maximization and prophet inequalities

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=E6c_JsETCLA


Duration: 42:52
298 views
4

Consider the problem faced by a seller desiring to maximize revenue with m items, in a market with n unit-demand buyers (interested in buying at most one item). The valuation of buyer i for item j is independently drawn from distribution F_{ij}. The design of revenue optimal mechanisms is well understood in the special case of m=1 item. However, the general problem had been open for long. In this talk, I will begin with the special case of 1 buyer and m items, and discuss the design and proof of an approximately revenue optimal mechanism. Emphasis will be on the proof and connection to prophet inequalities. I will discuss the extension to multiple buyers, and a recent generalization of prophet inequalities that has been used to approximate revenue maximization problems with matroidal feasibility constraints. The resulting mechanisms in all cases are simple posted price mechanisms. No prior knowledge of mechanism design will be assumed.



Other Videos By Microsoft Research


2016-07-26Frontiers of Accessibility: From the Body to the Mind, the Heart, and the Soul
2016-07-26Analyzing neurological disorders using functional and structural brain imaging data
2016-07-26Collaborative, Large-Scale Data Analytics and Visualization with Python
2016-07-26Gap Probabilities for Zeroes of Stationary Gaussian Functions
2016-07-26Random Walks on Groups and the Kaimanovich-Vershik Conjecture for Lamplighter Groups
2016-07-26Sensing without Sensors
2016-07-26Optimal Falsifications for Cyber-Physical Systems using Trajectory Splicing
2016-07-26A Sensor Fusion Approach towards Gesture Recognition on the Wearable Ring Form Factor
2016-07-26Digital Traces in Online Places: Methods, Software, and Applications for Social Behavioral Research
2016-07-26Stabilizer: Statistically Sound Performance Evaluation
2016-07-26Revenue maximization and prophet inequalities
2016-07-26On the Number of Matroids
2016-07-26RealTime Collaborative Analysis with (Almost) Pure SQL: A Case Study in Biogeochemical Oceanography
2016-07-26Who is Afraid of Vectors�Optimizing Cryptography Using SSE, AVX, NEON, and Co.
2016-07-26Programming with People: Integrating Human-Based and Digital Computation
2016-07-26ISHI Connects Us: Social Gaming with the Skype Team
2016-07-26Monitoring the Snowpack in Remote, Ungauged Mountains from Satellite and Computers
2016-07-26A Logical Revolution
2016-07-26Online Node-weighted Steiner Forest and Extensions
2016-07-26Optimal Pairings on Abelian Varieties with Theta Functions
2016-07-26Using Crowd Agents to Create Deployable Intelligent Systems


Tags:
microsoft research