Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

An economic view of prophet inequalities

An economic view of prophet inequalities An Economic View of Prophet Inequalities BRENDAN LUCIER Microsoft Research Over the past decade, an exciting connection has developed between the theory of posted-price mechanisms and the prophet inequality, a result from the theory of optimal stopping. This survey provides an overview of this literature, covering extensions and applications of the prophet inequality through the lens of an economic proof of this classic result. We focus on highlighting ways in which the economic perspective drives new advances in the theory of online stochastic optimization, and vice versa. Categories and Subject Descriptors: J.4 [Social and Behavioral Science]: Economics General Terms: Economics, Theory Additional Key Words and Phrases: Prophet Inequalities, Pricing, Approximation 1. OVERVIEW We are tasked with dividing up and selling a pool of resources among rational applicants, and our goal is to make the allocation as e ƒcient (or, perhaps, as pro table) as possible. To what extent are optimal mechanisms approximated by simple sales protocols? This question stands at the forefront of algorithmic mechanism design, despite a lack of consensus on precisely what is meant by œsimple.  While it ™s admittedly di ƒcult to move past œI ™ll know it when I see it,  a http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM SIGecom Exchanges Association for Computing Machinery

An economic view of prophet inequalities

Lucier, Brendan
ACM SIGecom Exchanges , Volume 16 (1) – Sep 25, 2017
Download PDF
24 pages

Loading next page...
 
/lp/association-for-computing-machinery/an-economic-view-of-prophet-inequalities-NB0UCQa0Pj
Publisher
Association for Computing Machinery
Copyright
Copyright © 2017 by ACM Inc.
ISSN
1551-9031
DOI
10.1145/3144722.3144725
Publisher site
See Article on Publisher Site

Abstract

An Economic View of Prophet Inequalities BRENDAN LUCIER Microsoft Research Over the past decade, an exciting connection has developed between the theory of posted-price mechanisms and the prophet inequality, a result from the theory of optimal stopping. This survey provides an overview of this literature, covering extensions and applications of the prophet inequality through the lens of an economic proof of this classic result. We focus on highlighting ways in which the economic perspective drives new advances in the theory of online stochastic optimization, and vice versa. Categories and Subject Descriptors: J.4 [Social and Behavioral Science]: Economics General Terms: Economics, Theory Additional Key Words and Phrases: Prophet Inequalities, Pricing, Approximation 1. OVERVIEW We are tasked with dividing up and selling a pool of resources among rational applicants, and our goal is to make the allocation as e ƒcient (or, perhaps, as pro table) as possible. To what extent are optimal mechanisms approximated by simple sales protocols? This question stands at the forefront of algorithmic mechanism design, despite a lack of consensus on precisely what is meant by œsimple.  While it ™s admittedly di ƒcult to move past œI ™ll know it when I see it,  a

Journal

ACM SIGecom Exchanges – Association for Computing Machinery

Published: Sep 25, 2017

There are no references for this article.