Relaxing the Independence Assumption in Sequential Posted Pricing, Prophet Inequality, and Random Bipartite Matching

We reexamine three classical settings of optimization under uncertainty, which have been extensively studied in the past, assuming that the several random events involved are mutually independent. Here, we assume that such events are only pair-wise independent; this gives rise to a much richer space of instances. Our aim has been to explore whether positive results are possible even under the more general assumptions. We show that this is indeed the case.

Indicatively, we show that, when applied to pair-wise independent distributions of buyer values, sequential posted pricing mechanisms get at least \(\frac{1}{1.299}\) of the revenue they get from mutually independent distributions with the same marginals. We also adapt the well-known prophet inequality to pair-wise independent distributions of prize values to get a 1/3-approximation using a non-standard uniform threshold strategy. Finally, in a stochastic model of generating random bipartite graphs with pair-wise independence on the edges, we show that the expected size of the maximum matching is large but considerably smaller than in Erdős-Renyi random graph models where edges are selected independently. Our techniques include a technical lemma that might find applications in other interesting settings involving pair-wise independence.

1. 1.

   For example, if value of item B is always equal to the values of items A and C, then items A and C cannot be independent.

2. 2.

   We note that prophet inequalities for classes of prize distributions with limited correlation have been studied before. The survey of Hill and Kertz [11] discusses early related results in stopping theory while the papers [4, 8, 12] are representative of recent related work by the EconCS community. However, such results are rarely based on the use of simple threshold strategies as the one we use here.

3. 3.

   We remark that, while the expectation for the threshold strategy is taken in the worst case over any pair-wise independent distribution, the expectation for the prophet is taken in the best case over any distribution with the given marginals.

4. 4.

   If the distributions were continuous, we could choose the threshold \(\widehat{v}\) so that \(x=\frac{\sqrt{5}-1}{2}\). For this value of x we have \(\frac{x}{1+x} =1-x=\frac{3-\sqrt{5}}{2}=0.382\). Then, we could get a lower bound on \(\textsf {APX}_{}\) by combining (2) and (3) as follows:

   $$ \textsf {APX}_{}=\textsf {APX}_{1} + \textsf {APX}_{2} \ge 0.382 \left( \widehat{v}+ \sum _{i=1}^n \mathbf {E}\left[ {(v_i-\widehat{v})^+}\right] \right) \ge 0.382\cdot \textsf {REF}. $$

   In our proof, we assume that distributions can be discontinuous and, thus, we may not be able to set \(\widehat{v}\) to get a particular value of x.

5. 5.

   Our construction can be extended to cover the case of non-integer \(\varDelta \) with some minor adjustments.

We thank Yuan Zhou for helpful discussions on the expected size of maximum matchings in random bipartite graphs. This work was partially supported by Science and Technology Innovation 2030 - “New Generation of Artificial Intelligence” Major Project No. 2018AAA0100903; COST Action 16228 “European Network for Game Theory”; Innovation Program of Shanghai Municipal Education Commission; Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE) and the Fundamental Research Funds for the Central Universities; National Natural Science Foundation of China (Grant No. 61806121); Beijing Outstanding Young Scientist Program (No. BJJWZYJH012019100020098) Intelligent Social Governance Platform; Major Innovation & Planning Interdisciplinary Platform for the “Double-First Class” Initiative, Renmin University of China.

Authors and Affiliations

1. Department of Computer Science, Aarhus University, Aarhus, Denmark

   Ioannis Caragiannis

2. ITCS, Shanghai University of Finance and Economics, Shanghai, China

   Nick Gravin & Pinyan Lu

3. Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China

   Zihe Wang

Corresponding author

Correspondence to Ioannis Caragiannis .

Editors and Affiliations

1. Tel Aviv University, Tel Aviv, Israel

   Michal Feldman

2. Shanghai University of Finance and Economics, Shanghai, China

   Hu Fu

3. Technion – Israel Institute of Technology, Haifa, Israel

   Inbal Talgam-Cohen

Reprints and permissions

© 2022 Springer Nature Switzerland AG

Policies and ethics