Document Open Access Logo

Prophet Matching in the Probe-Commit Model

Authors Allan Borodin, Calum MacRury, Akash Rakheja

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.46.pdf
  • Filesize: 0.83 MB
  • 24 pages

Document Identifiers

Author Details

Allan Borodin
  • Department of Computer Science, University of Toronto, Canada
Calum MacRury
  • Department of Computer Science, University of Toronto, Canada
Akash Rakheja
  • Department of Computer Science, University of Toronto, Canada

Acknowledgements

We would like to thank Brendan Lucier and David Wajc for their constructive comments on an early version of this paper.

Cite AsGet BibTex

Allan Borodin, Calum MacRury, and Akash Rakheja. Prophet Matching in the Probe-Commit Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 46:1-46:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.46

Abstract

We consider the online bipartite stochastic matching problem with known i.d. (independently distributed) online vertex arrivals. In this problem, when an online vertex arrives, its weighted edges must be probed (queried) to determine if they exist, based on known edge probabilities. Our algorithms operate in the probe-commit model, in that if a probed edge exists, it must be used in the matching. Additionally, each online node has a downward-closed probing constraint on its adjacent edges which indicates which sequences of edge probes are allowable. Our setting generalizes the commonly studied patience (or time-out) constraint which limits the number of probes that can be made to an online node’s adjacent edges. Most notably, this includes non-uniform edge probing costs (specified by knapsack/budget constraint). We extend a recently introduced configuration LP to the known i.d. setting, and also provide the first proof that it is a relaxation of an optimal offline probing algorithm (the offline adaptive benchmark). Using this LP, we establish the following competitive ratio results against the offline adaptive benchmark: 1) A tight 1/2 ratio when the arrival ordering π is chosen adversarially. 2) A 1-1/e ratio when the arrival ordering π is chosen u.a.r. (uniformly at random). If π is generated adversarially, we generalize the prophet inequality matching problem. If π is u.a.r., we generalize the prophet secretary matching problem. Both results improve upon the previous best competitive ratio of 0.46 in the more restricted known i.i.d. (independent and identically distributed) arrival model against the standard offline adaptive benchmark due to Brubach et al. We are the first to study the prophet secretary matching problem in the context of probing, and our 1-1/e ratio matches the best known result without probing due to Ehsani et al. This result also applies to the unconstrained bipartite matching probe-commit problem, where we match the best known result due to Gamlath et al.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Stochastic probing
  • Online algorithms
  • Bipartite matching
  • Optimization under uncertainty

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Marek Adamczyk. Improved analysis of the greedy algorithm for stochastic matching. Inf. Process. Lett., 111(15):731-737, 2011. Google Scholar
  2. Marek Adamczyk, Fabrizio Grandoni, and Joydeep Mukherjee. Improved approximation algorithms for stochastic matching. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 1-12. Springer, 2015. Google Scholar
  3. Marek Adamczyk and Michał Włodarczyk. Random order contention resolution schemes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 790-801. IEEE, 2018. Google Scholar
  4. Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. Online prophet-inequality matching with applications to ad allocation. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC '12, pages 18-35, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2229012.2229018.
  5. Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Prophet secretary: Surpassing the 1-1/e barrier. In Éva Tardos, Edith Elkind, and Rakesh Vohra, editors, Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 303-318. ACM, 2018. Google Scholar
  6. Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri Rudra. When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica, 63(4):733-762, 2012. URL: https://doi.org/10.1007/s00453-011-9511-8.
  7. Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, and Pan Xu. Improved bounds in stochastic matching and optimization. Algorithmica, 80(11):3225-3252, November 2018. URL: https://doi.org/10.1007/s00453-017-0383-4.
  8. Allan Borodin, Calum MacRury, and Akash Rakheja. Bipartite stochastic matching: Online, random order, and I.I.D. models. CoRR, abs/2004.14304, 2020. URL: http://arxiv.org/abs/2004.14304.
  9. Allan Borodin, Calum MacRury, and Akash Rakheja. Prophet matching meets probing with commitment. CoRR, abs/2102.04325, 2021. URL: http://arxiv.org/abs/2102.04325.
  10. Allan Borodin, Calum MacRury, and Akash Rakheja. Secretary matching meets probing with commitment. In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), volume 207 of LIPIcs, pages 13:1-13:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  11. Brian Brubach, Nathaniel Grammel, Will Ma, and Aravind Srinivasan. Follow your star: New frameworks for online stochastic matching with known and unknown patience. CoRR, abs/1907.03963, 2021. URL: http://arxiv.org/abs/1907.03963.
  12. Brian Brubach, Nathaniel Grammel, Will Ma, and Aravind Srinivasan. Follow your star: New frameworks for online stochastic matching with known and unknown patience. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2872-2880. PMLR, 13-15 April 2021. URL: http://proceedings.mlr.press/v130/brubach21a.html.
  13. Brian Brubach, Nathaniel Grammel, Will Ma, and Aravind Srinivasan. Improved guarantees for offline stochastic matching via new ordered contention resolution schemes. In Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 27184-27195, 2021. URL: https://proceedings.neurips.cc/paper/2021/hash/e43739bba7cdb577e9e3e4e42447f5a5-Abstract.html.
  14. Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. New algorithms, better bounds, and a novel model for online stochastic matching. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 24:1-24:16, 2016. Google Scholar
  15. Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. Attenuate locally, win globally: Attenuation-based frameworks for online stochastic matching with timeouts. Algorithmica, 82(1):64-87, 2020. URL: https://doi.org/10.1007/s00453-019-00603-7.
  16. Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and Rebecca Reiffenhäuser. Single-sample prophet inequalities via greedy-ordered selection. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pages 1298-1325, 2022. URL: https://doi.org/10.1137/1.9781611977073.54.
  17. Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 311-320. ACM, 2010. Google Scholar
  18. Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, and Atri Rudra. Approximating matches made in heaven. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I, ICALP '09, pages 266-278, 2009. Google Scholar
  19. José R. Correa, Patricio Foncea, Dana Pizarro, and Victor Verdugo. From pricing to prophets, and back! Oper. Res. Lett., 47(1):25-29, 2019. Google Scholar
  20. José R. Correa, Raimundo Saona, and Bruno Ziliotto. Prophet secretary through blind strategies. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1946-1961, 2019. Google Scholar
  21. Kevin P. Costello, Prasad Tetali, and Pushkar Tripathi. Stochastic matching with commitment. In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming, pages 822-833, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  22. Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla. Prophet secretary for combinatorial auctions and matroids. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, pages 700-714, USA, 2018. Society for Industrial and Applied Mathematics. Google Scholar
  23. Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models. In Proceedings of the 21st ACM Conference on Economics and Computation, EC '20, pages 769-787, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3391403.3399513.
  24. Elaheh Fata, Will Ma, and David Simchi-Levi. Multi-stage and multi-customer assortment optimization with inventory constraints. CoRR, abs/1908.09808, 2019. URL: http://arxiv.org/abs/1908.09808.
  25. Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1014-1033. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch72.
  26. Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang. Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 68:1-68:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.68.
  27. Buddhima Gamlath, Sagar Kale, and Ola Svensson. Beating greedy for stochastic bipartite matching. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, pages 2841-2854, USA, 2019. Society for Industrial and Applied Mathematics. Google Scholar
  28. Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. J. ACM, 53(3):324-360, May 2006. URL: https://doi.org/10.1145/1147954.1147956.
  29. Bernd Gärtner and Jirí Matousek. Understanding and using linear programming. Universitext. Springer, 2007. Google Scholar
  30. Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Algorithms and adaptivity gaps for stochastic probing. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1731-1747. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch120.
  31. Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22-26, 2007, Vancouver, British Columbia, Canada, pages 58-65. AAAI Press, 2007. Google Scholar
  32. Zhiyi Huang, Xinkai Shu, and Shuyi Yan. The power of multiple choices in online stochastic matching, 2022. URL: https://doi.org/10.48550/ARXIV.2203.02883.
  33. Haim Kaplan and David Naori dand Danny Raz. Online weighted bipartite matching with a sample. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), 2022. URL: https://doi.org/10.1137/1.9781611977073.52.
  34. Euiwoong Lee and Sahil Singla. Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 57:1-57:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.57.
  35. Tristan Pollner, Mohammad Roghani, Amin Saberi, and David Wajc. Improved online contention resolution for matchings and applications to the gig economy. In David M. Pennock, Ilya Segal, and Sven Seuken, editors, EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022, pages 321-322. ACM, 2022. URL: https://doi.org/10.1145/3490486.3538295.
  36. D. Seese. Groetschel, m., l. lovasz, a. schrijver: Geometric algorithms and combinatorial optimization. (algorithms and combinatorics. eds.: R. l. graham, b. korte, l. lovasz. vol. 2), springer-verlag 1988, xii, 362 pp., 23 figs., dm 148,-. isbn 3–540–13624-x. Biometrical Journal, 32(8):930-930, 1990. URL: https://doi.org/10.1002/bimj.4710320805.
  37. Danny Segev and Sahil Singla. Efficient approximation schemes for stochastic probing and prophet problems. In Proceedings of the 22nd ACM Conference on Economics and Computation, EC '21, pages 793-794, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3465456.3467614.
  38. Jan Vondrák, Chandra Chekuri, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, pages 783-792, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/1993636.1993740.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact