Prophet Inequality for Bipartite Matching: Merits of Being Simple and Nonadaptive

References

• [1] Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1253–1264.Google Scholar
• [2] Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
• [3] Alaei S, Hajiaghayi M, Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation. Proc. 13th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 18–35.Google Scholar
• [4] Alaei S, Hajiaghayi M, Liaghat V (2013) The online stochastic generalized assignment problem. Raghavendra P, Raskhodnikova S, Jansen K, Rolim JDP, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science, vol. 8096 (Springer, Berlin), 11–25.Google Scholar
• [5] Ashlagi I, Burq M, Jaillet P, Saberi A (2018) Maximizing efficiency in dynamic matching markets. Preprint, submitted March 4, http://arxiv.org/abs/1803.01285.Google Scholar
• [6] Azar P, Kleinberg R, Weinberg M (2014) Prophet inequalities with limited information. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1358–1377.Google Scholar
• [7] Buchbinder N, Jain K, Naor J (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Proc. 15th Annual Eur. Sympos. Algorithms (Springer, Berlin), 253–264.Google Scholar
• [8] Buchbinder N, Segev D, Tkach Y (2017) Online algorithms for maximum cardinality matching with edge arrivals. Pruhs K, Sohler C, eds. Proc. 25th Annual Eur. Sympos. (Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 22:1–22:14.Google Scholar
• [9] Chawla S, Hartline J, Kleinberg R (2007) Algorithmic pricing via virtual valuations. Proc. Eighth ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 243–251.Google Scholar
• [10] Chawla S, Hartline J, Malec D, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Proc. 42nd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 311–320.Google Scholar
• [11] Chiplunkar A, Tirodkar S, Vishwanathan S (2015) On randomized algorithms for matching in the online preemptive model. Bansal N, Finocchi I, eds. Proc. 23rd Annual Eur. Sympos. Algorithms (Springer, Berlin), 325–336.Google Scholar
• [12] Cohen IR, Eden A, Fiat A, Jez L (2015) Pricing online decisions: Beyond auctions. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 73–91.Google Scholar
• [13] Cohen-Addad V, Eden A, Feldman M, Fiat A (2016) The invisible hand of dynamic market pricing. Proc. 2016 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 383–400.Google Scholar
• [14] Correa J, Cristi A, Epstein B, Soto J (2020) The two-sided game of googol and sample-based prophet inequalities. Chawla S, ed. Proc. 2020 ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2066–2081.Google Scholar
• [15] Correa J, Dütting P, Fischer F, Schewior K (2019) Prophet inequalities for I.I.D. random variables from an unknown distribution. Karlin A, Immorlica N, Johari R, eds. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 3–17.Google Scholar
• [16] Correa J, Foncea P, Pizarro D, Verdugo V (2019) From pricing to prophets, and back! Oper. Res. Lett. 47(1):25–29.Crossref, Google Scholar
• [17] Devanur N, Hayes T (2009) The Adwords problem: Online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 71–78.Google Scholar
• [18] Devanur N, Jain K, Sivan B, Wilkens C (2019) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM 66(1):7:1–7:41.Crossref, Google Scholar
• [19] Dütting P, Kesselheim T (2019) Posted pricing and prophet inequalities with inaccurate priors. Karlin A, Immorlica N, Johari R, eds. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 111–129.Google Scholar
• [20] Dütting P, Kleinberg R (2015) Polymatroid prophet inequalities. Proc. 23rd Annual Eur. Sympos. Algorithms (Springer, Berlin), 437–449.Google Scholar
• [21] Dütting P, Kesselheim T, Lucier B (2020) An O(log log m) prophet inequality for subadditive combinatorial auctions. Proc. IEEE 61st Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 306–317.Google Scholar
• [22] Dütting P, Feldman M, Kesselheim T, Lucier B (2017) Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. Proc. 58th IEEE Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 540–551.Google Scholar
• [23] Epstein L, Levin A, Segev D, Weimann O (2013) Improved bounds for online preemptive matching. Portier N, Wilke T, eds. Proc. 30th Internat. Sympos. Theoret. Aspects Comput. Sci. (Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 389–399.Google Scholar
• [24] Ezra T, Feldman M, Gravin N, Tang Z (2020) Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models. Biró P, Hartline J, Ostrovsky M, Procaccia A, eds. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 769–787.Google Scholar
• [25] Feldman M, Fiat A, Roytman A (2017) Makespan minimization via posted prices. Proc. 2017 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 405–422.Google Scholar
• [26] Feldman M, Gravin N, Lucier B (2015) Combinatorial auctions via posted prices. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 123–135.Crossref, Google Scholar
• [27] Feldman M, Svensson O, Zenklusen R (2016) Online contention resolution schemes. Proc. 27th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1014–1033.Google Scholar
• [28] Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1 − 1/e. Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 117–126.Google Scholar
• [29] Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to Adwords. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 982–991.Google Scholar
• [30] Haeupler B, Mirrokni V, Zadimoghaddam M (2011) Online stochastic weighted matching: Improved approximation algorithms. Chen N, Elkind E, Koutsoupias E, eds. Proc. Seventh Internat. Workshop Internet Network Econom. (Springer, Berlin), 170–181.Google Scholar
• [31] Hajiaghayi M, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Proc. 22nd AAAI Conf. Artificial Intelligence (Association for the Advancement of Artificial Intelligence, Menlo Park, CA), 58–65.Google Scholar
• [32] Hill TP, Kertz RP (1992) A survey of prophet inequalities in optimal stopping theory. Contemporary Math. 125:191–207.Crossref, Google Scholar
• [33] Huang Z, Kang N, Tang Z, Wu X, Zhang Y, Zhu X (2018) How to match when all vertices arrive online. Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 17–29.Google Scholar
• [34] Huang Z, Peng B, Tang Z, Tao R, Wu X, Zhang Y (2019) Tight competitive ratios of classic matching algorithms in the fully online model. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2875–2886.Google Scholar
• [35] Karande C, Mehta A, Tripathi P (2011) Online bipartite matching with unknown distributions. Proc. 43rd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 587–596.Google Scholar
• [36] Karp R, Vazirani U, Vazirani V (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 352–358.Google Scholar
• [37] Kennedy DP (1985) Optimal stopping of independent random variables and maximizing prophets. Ann. Probab. 13(2):566–571.Google Scholar
• [38] Kennedy DP (1987) Prophet-type inequalities for multi-choice optimal stopping. Stochastic Proc. Their Appl. 24:77–88.Crossref, Google Scholar
• [39] Kertz RP (1986) Comparison of optimal value and constrained maxima expectations for independent random variables. Adv. Appl. Probab. 18(2):311–340.Crossref, Google Scholar
• [40] Kleinberg R, Weinberg M (2012) Matroid prophet inequalities. Proc. 44th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 123–136.Google Scholar
• [41] Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83(4):745–747.Crossref, Google Scholar
• [42] Mahdian M, Yan Q (2011) Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. Proc. 43rd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 597–606.Google Scholar
• [43] Manshadi VH, Gharan SO, Saberi A (2011) Online stochastic matching: Online actions based on offline statistics. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1285–1294.Google Scholar
• [44] McGregor A (2005) Finding graph matchings in data streams. Chekuri C, Jansen K, Rolim JDP, Trevisan L, eds. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science, vol. 3624 (Springer, Berlin), 170–181.Google Scholar
• [45] Mehta A, Saberi A, Vazirani U, Vazirani V (2007) AdWords and generalized online matching. J. ACM 54(5):22.Google Scholar
• [46] Mirrokni V, Gharan S, Zadimoghaddam M (2012) Simultaneous approximations for adversarial and stochastic online budgeted allocation. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1690–1701.Google Scholar
• [47] Rubinstein A (2016) Beyond matroids: secretary problem and prophet inequality with general constraints. Proc. 48th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 324–332.Google Scholar
• [48] Rubinstein A, Vardi S (2017) Sorting from noisier samples. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 960–972.Google Scholar
• [49] Rubinstein A, Wang J, Weinberg M (2020) Optimal single-choice prophet inequalities from samples. Vidick T, ed. Proc. 11th Innovations Theoret. Comput. Sci. Conf. Leibniz International Proceedings in Informatics, vol. 151 (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 60:1–60:10.Google Scholar
• [50] Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4):1213–1216.Crossref, Google Scholar