Can I read Prophet Inequality with Correlated Arrival Probabilities, with Application to Two Sided Matchings on EtoBox?

Prophet Inequality with Correlated Arrival Probabilities, with Application to Two Sided Matchings by Truong, Van-Anh; Wang, Xinshang is a scholarly article available to read on EtoBox.

What is Prophet Inequality with Correlated Arrival Probabilities, with Application to Two Sided Matchings about?

The classical Prophet Inequality arises from a fundamental problem in optimal-stopping theory. In this problem, a gambler sees a finite sequence of independent, non-negative random variables. If he stops the sequence at any time, he collects a reward equal to the most recent observation. The Prophet Inequality states that, knowing the distribution of each random variable, the gambler can achieve at least half as much reward in expectation, as a prophet who knows the entire sample path of random variables (Krengel and Sucheston 1978). In this paper, we prove a corresponding bound for correlated non-negative random variables. We analyze two methods for proving the bound, a constructive approach, which produces a worst-case instance, and a reductive approach, which characterizes a certain submartingale arising from the reward process of our online algorithm. We apply this new prophet inequality to the design of algorithms for a class of two-sided bipartite matching problems that underlie online task assignment problems. In these problems, demand units of various types arrive randomly and sequentially over time according to some stochastic process. Tasks, or supply units, arrive accord

Author

Truong, Van-Anh; Wang, Xinshang

Published

2019

Language

EN