Matroid prophet inequalities and Bayesian mechanism design
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2013
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/78473 |
| _version_ | 1826211028733526016 |
|---|---|
| author | Weinberg, S. Matthew (Seth Matthew) |
| author2 | Constantinos Daskalakis. |
| author_facet | Constantinos Daskalakis. Weinberg, S. Matthew (Seth Matthew) |
| author_sort | Weinberg, S. Matthew (Seth Matthew) |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012. |
| first_indexed | 2024-09-23T14:59:45Z |
| format | Thesis |
| id | mit-1721.1/78473 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T14:59:45Z |
| publishDate | 2013 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/784732019-04-10T13:08:50Z Matroid prophet inequalities and Bayesian mechanism design Weinberg, S. Matthew (Seth Matthew) Constantinos Daskalakis. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012. Cataloged from PDF version of thesis. Includes bibliographical references (p. 42-44). Consider a gambler who observes a sequence of independent, non-negative random numbers and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The famous prophet inequality of Krengel, Sucheston, and Garling asserts that a gambler who knows the distribution of each random variable can achieve at least half as much reward, in expectation, as a "prophet" who knows the sampled values of each random variable and can choose the largest one. We generalize this result to the setting in which the gambler and the prophet are allowed to make more than one selection, subject to a matroid constraint. We show that the gambler can still achieve at least half as much reward as the prophet; this result is the best possible, since it is known that the ratio cannot be improved even in the original prophet inequality, which corresponds to the special case of rank-one matroids. Generalizing the result still further, we show that under an intersection of p matroid constraints, the prophet's reward exceeds the gambler's by a factor of at most 0(p), and this factor is also tight. Beyond their interest as theorems about pure online algoritms or optimal stopping rules, these results also have applications to mechanism design. Our results imply improved bounds on the ability of sequential posted-price mechanisms to approximate optimal mechanisms in both single-parameter and multi-parameter Bayesian settings. In particular, our results imply the first efficiently computable constant-factor approximations to the Bayesian optimal revenue in certain multi-parameter settings. This work was done in collaboration with Robert Kleinberg. by S. Matthew Weinberg. S.M. 2013-04-12T19:27:29Z 2013-04-12T19:27:29Z 2012 2012 Thesis http://hdl.handle.net/1721.1/78473 834094903 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 44 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Weinberg, S. Matthew (Seth Matthew) Matroid prophet inequalities and Bayesian mechanism design |
| title | Matroid prophet inequalities and Bayesian mechanism design |
| title_full | Matroid prophet inequalities and Bayesian mechanism design |
| title_fullStr | Matroid prophet inequalities and Bayesian mechanism design |
| title_full_unstemmed | Matroid prophet inequalities and Bayesian mechanism design |
| title_short | Matroid prophet inequalities and Bayesian mechanism design |
| title_sort | matroid prophet inequalities and bayesian mechanism design |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/78473 |
| work_keys_str_mv | AT weinbergsmatthewsethmatthew matroidprophetinequalitiesandbayesianmechanismdesign |