Document Open Access Logo

Improved Prophet Inequalities for Combinatorial Welfare Maximization with (Approximately) Subadditive Agents

Author Hanrui Zhang

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.82.pdf
  • Filesize: 463 kB
  • 17 pages

Document Identifiers

Author Details

Hanrui Zhang
  • Duke University, Durham, NC, USA

Funding

  • Zhang, Hanrui: Supported by NSF award IIS-1814056.

Acknowledgements

The author thanks Yuan Deng, Kamesh Munagala, and anonymous reviewers for helpful feedback.

Cite As Get BibTex

Hanrui Zhang. Improved Prophet Inequalities for Combinatorial Welfare Maximization with (Approximately) Subadditive Agents. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 82:1-82:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.82

Abstract

We give a framework for designing prophet inequalities for combinatorial welfare maximization. Instantiated with different parameters, our framework implies (1) an O(log m / log log m)-competitive prophet inequality for subadditive agents, improving over the O(log m) upper bound via item pricing, (2) an O(D log m / log log m)-competitive prophet inequality for D-approximately subadditive agents, where D ∈ {1, … , m-1} measures the maximum number of items that complement each other, and (3) as a byproduct, an O(1)-competitive prophet inequality for submodular or fractionally subadditive (a.k.a. XOS) agents, matching the optimal ratio asymptotically. Our framework is computationally efficient given sample access to the prior and demand queries.

Subject Classification

ACM Subject Classification
  • Theory of computation → Stochastic approximation
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • Prophet Inequalities
  • Combinatorial Welfare Maximization
  • (Approximate) Subadditivity

Metrics

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

References

  1. Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing, 43(2):930-972, 2014. Google Scholar
  2. Kshipra Bhawalkar and Tim Roughgarden. Welfare guarantees for combinatorial auctions with item bidding. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 700-709. Society for Industrial and Applied Mathematics, 2011. Google Scholar
  3. Liad Blumrosen and Thomas Holenstein. Posted prices vs. negotiations: an asymptotic analysis. In EC, page 49. Citeseer, 2008. Google Scholar
  4. Yang Cai and Mingfei Zhao. Simple mechanisms for subadditive buyers via duality. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 170-183. ACM, 2017. Google Scholar
  5. Shuchi Chawla, Jason D Hartline, and Robert Kleinberg. Algorithmic pricing via virtual valuations. In Proceedings of the 8th ACM conference on Electronic commerce, pages 243-251. ACM, 2007. Google Scholar
  6. Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 311-320. ACM, 2010. Google Scholar
  7. Wei Chen, Shang-Hua Teng, and Hanrui Zhang. Capturing complementarity in set functions by going beyond submodularity/subadditivity. 10th Innovations in Theoretical Computer Science, 2019. Google Scholar
  8. Vincent Cohen-Addad, Alon Eden, Michal Feldman, and Amos Fiat. The invisible hand of dynamic market pricing. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 383-400. ACM, 2016. Google Scholar
  9. Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 610-618. ACM, 2005. Google Scholar
  10. Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 540-551. IEEE, 2017. Google Scholar
  11. Paul Dütting, Thomas Kesselheim, and Brendan Lucier. An o (log log m) prophet inequality for subadditive combinatorial auctions. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.09784.
  12. Paul Dütting and Robert Kleinberg. Polymatroid prophet inequalities. In Algorithms-ESA 2015, pages 437-449. Springer, 2015. Google Scholar
  13. 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, pages 700-714. SIAM, 2018. Google Scholar
  14. Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM Journal on Computing, 39(1):122-142, 2009. Google Scholar
  15. Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, and Vasilis Syrgkanis. A unifying hierarchy of valuations with complements and substitutes. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015. Google Scholar
  16. Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 123-135. Society for Industrial and Applied Mathematics, 2015. Google Scholar
  17. Moran Feldman, Ola Svensson, and Rico Zenklusen. A simple O (log log (rank))-competitive algorithm for the matroid secretary problem. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1189-1201. SIAM, 2014. Google Scholar
  18. Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In AAAI, volume 7, pages 58-65, 2007. Google Scholar
  19. Svante Janson. Large deviation inequalities for sums of indicator variables. arXiv preprint, 2016. URL: http://arxiv.org/abs/1609.00533.
  20. Robert Kleinberg and Seth Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 123-136. ACM, 2012. Google Scholar
  21. Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. Bulletin of the American Mathematical Society, 83(4):745-747, 1977. Google Scholar
  22. Ulrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. Probability on Banach spaces, 4:197-266, 1978. Google Scholar
  23. Brendan Lucier. An economic view of prophet inequalities. ACM SIGecom Exchanges, 16(1):24-47, 2017. Google Scholar
  24. Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices. Journal of Economic Theory, 129(1):192-224, 2006. Google Scholar
  25. Aviad Rubinstein and Sahil Singla. Combinatorial prophet inequalities. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1671-1687. SIAM, 2017. Google Scholar
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 About DROPS Imprint Privacy Contact