Correlation gap

In stochastic programming, the correlation gap is the worst-case ratio between the cost when the random variables are correlated to the cost when the random variables are independent.[1]

As an example,[1]:6 consider the following optimization problem. A teacher wants to know whether to come to class or not. There are n potential students. For each student, there is a probability of 1/n that the student will attend the class. If at least one student attends, then the teacher must come and his cost is 1. If no students attend, then the teacher can stay at home and his cost is 0. The goal of the teacher is to minimize his cost. This is a stochastic-programming problem, because the constraints are not known in advance – only their probabilities are known. Now, there are two cases regarding the correlation between the students:

  • Case #1: the students are uncorrelated: each student decides whether to come to class or not by tossing a coin with probability , independently of the others. The expected cost in this case is .
  • Case #2: the students are correlated: one student is selected at random and comes to class, while the others stay at home. Note that the probability of each student to come is still . However, now the cost is 1.

The correlation gap is the cost in case #2 divided by the cost in case #1, which is .

[1] prove that the correlation gap is bounded in several cases. For example, when the cost function is a submodular set function (as in the above example), the correlation gap is at most (so the above example is a worst-case).

An upper bound on the correlation gap implies an upper bound on the loss that results from ignoring the correlation. For example, suppose we have a stochastic programming problem with a submodular cost function. We know the marginal probabilities of the variables, but we do not know whether they are correlated or not. If we just ignore the correlation and solve the problem as if the variables are independent, the resulting solution is a -approximation to the optimal solution.

Applications

The correlation gap was used to bound the loss of revenue when using a Bayesian-optimal pricing instead of a Bayesian-optimal auction.[2]

gollark: It was refurbished and has a 7th gen processor. I got it for £140 and spent another £30 on an SSD and RAM.
gollark: Barrel jack power input, Ethernet, VGA, HDMI, USB-A and -C, a headphone jack, an SD card reader I can't use under Linux, a fingerprint sensor with the same problem, and a "smart card" reader which I have no use for.
gollark: I have an older business-grade laptop, which is pretty great.
gollark: Most people basically just want to use Facebook, email, an office suite, that sort of thing, so their phone would work fine with laptop-grade IO and tweaked software.
gollark: It's not good for power users, but many phones have video output and USB host capability, and docks are already a thing.

See also

References
  1. Agrawal, Shipra; Ding, Yichuan; Saberi, Amin; Ye, Yinyu (2010). "Correlation Robust Stochastic Optimization". Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1087. arXiv:0902.1792. doi:10.1137/1.9781611973075.88. ISBN 978-0-89871-701-3.
  2. Yan, Qiqi (2011). "Mechanism Design via Correlation Gap". Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. p. 710. arXiv:1008.1843. doi:10.1137/1.9781611973082.56. ISBN 978-0-89871-993-2.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.