Document Open Access Logo

Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity

Authors Wei Chen, Shang-Hua Teng, Hanrui Zhang

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.24.pdf
  • Filesize: 0.56 MB
  • 20 pages

Document Identifiers

Author Details

Wei Chen
  • Microsoft Research, Beijing, China
Shang-Hua Teng
  • USC, Los Angeles, CA, USA
Hanrui Zhang
  • Duke University, Durham, NC, USA

Funding

  • Chen, Wei: Supported in part by the National Natural Science Foundation of China (Grant No. 61433014).
  • Teng, Shang-Hua: Supported in part by Simons Investigator Award and by NSF grant CCF-1815254.
  • Zhang, Hanrui: Supported by NSF awards IIS-1814056 and IIS-1527434.

Cite As Get BibTex

Wei Chen, Shang-Hua Teng, and Hanrui Zhang. Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.24

Abstract

We introduce two new "degree of complementarity" measures: supermodular width and superadditive width. Both are formulated based on natural witnesses of complementarity. We show that both measures are robust by proving that they, respectively, characterize the gap of monotone set functions from being submodular and subadditive. Thus, they define two new hierarchies over monotone set functions, which we will refer to as Supermodular Width (SMW) hierarchy and Superadditive Width (SAW) hierarchy, with foundations - i.e. level 0 of the hierarchies - resting exactly on submodular and subadditive functions, respectively.
We present a comprehensive comparative analysis of the SMW hierarchy and the Supermodular Degree (SD) hierarchy, defined by Feige and Izsak. We prove that the SMW hierarchy is strictly more expressive than the SD hierarchy: Every monotone set function of supermodular degree d has supermodular width at most d, and there exists a supermodular-width-1 function over a ground set of m elements whose supermodular degree is m-1. We show that previous results regarding approximation guarantees for welfare and constrained maximization as well as regarding the Price of Anarchy (PoA) of simple auctions can be extended without any loss from the supermodular degree to the supermodular width. We also establish almost matching information-theoretical lower bounds for these two well-studied fundamental maximization problems over set functions. The combination of these approximation and hardness results illustrate that the SMW hierarchy provides not only a natural notion of complementarity, but also an accurate characterization of "near submodularity" needed for maximization approximation. While SD and SMW hierarchies support nontrivial bounds on the PoA of simple auctions, we show that our SAW hierarchy seems to capture more intrinsic properties needed to realize the efficiency of simple auctions. So far, the SAW hierarchy provides the best dependency for the PoA of Single-bid Auction, and is nearly as competitive as the Maximum over Positive Hypergraphs (MPH) hierarchy for Simultaneous Item First Price Auction (SIA). We also provide almost tight lower bounds for the PoA of both auctions with respect to the SAW hierarchy.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • set functions
  • measure of complementarity
  • submodularity
  • subadditivity
  • cardinality constrained maximization
  • welfare maximization
  • simple auctions
  • price of anarchy

Metrics

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

Related Versions

References

  1. Ittai Abraham, Moshe Babaioff, Shaddin Dughmi, and Tim Roughgarden. Combinatorial auctions with restricted complements. In Proceedings of the Thirteenth ACM Conference on Electronic Commerce, pages 3-16. ACM, 2012. Google Scholar
  2. Maria-Florina Balcan and Nicholas JA Harvey. Learning submodular functions. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pages 793-802. ACM, 2011. Google Scholar
  3. Shuchi Chawla, Jason D. Hartline, and Robert Kleinberg. Algorithmic Pricing via Virtual Valuations. In Proceedings of the Eighth ACM Conference on Electronic Commerce, pages 243-251. ACM, 2007. Google Scholar
  4. Wei Chen, Shang-Hua Teng, and Hanrui Zhang. Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity. arXiv preprint, 2018. URL: http://arxiv.org/abs/1805.04436.
  5. Nikhil Devanur, Jamie Morgenstern, Vasilis Syrgkanis, and S Matthew Weinberg. Simple auctions with simple strategies. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 305-322. ACM, 2015. Google Scholar
  6. Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, and S Matthew Weinberg. A Simple and Approximately Optimal Mechanism for a Buyer with Complements. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 323-323. ACM, 2017. Google Scholar
  7. Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998. Google Scholar
  8. Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM Journal on Computing, 39(1):122-142, 2009. Google Scholar
  9. 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
  10. Uriel Feige and Rani Izsak. Welfare maximization and the supermodular degree. In Proceedings of the Fourth Conference on Innovations in Theoretical Computer Science, pages 247-256. ACM, 2013. Google Scholar
  11. Michal Feldman, Ophir Friedler, Jamie Morgenstern, and Guy Reiner. Simple mechanisms for agents with complements. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 251-267. ACM, 2016. Google Scholar
  12. Michal Feldman, Hu Fu, Nick Gravin, and Brendan Lucier. Simultaneous auctions are (almost) efficient. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pages 201-210. ACM, 2013. Google Scholar
  13. 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
  14. Moran Feldman and Rani Izsak. Constrained Monotone Function Maximization and the Supermodular Degree. In Seventeenth International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2014. Google Scholar
  15. Moran Feldman and Rani Izsak. Building a good team: Secretary problems and the supermodular degree. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1651-1670. SIAM, 2017. Google Scholar
  16. Marshall L Fisher, George L Nemhauser, and Laurence A Wolsey. An analysis of approximations for maximizing submodular set functions—II. In Polyhedral Combinatorics, pages 73-87. Springer, 1978. Google Scholar
  17. David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 137-146. ACM, 2003. Google Scholar
  18. Subhash Khot, Richard J Lipton, Evangelos Markakis, and Aranyak Mehta. Inapproximability results for combinatorial auctions with submodular utility functions. In International Workshop on Internet and Network Economics, pages 92-101. Springer, 2005. Google Scholar
  19. Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2):270-296, 2006. Google Scholar
  20. Vahab Mirrokni, Michael Schapira, and Jan Vondrák. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In Proceedings of the Ninth ACM Conference on Electronic Commerce, pages 70-77. ACM, 2008. Google Scholar
  21. George L Nemhauser and Laurence A Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3(3):177-188, 1978. Google Scholar
  22. George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions-I. Mathematical Programming, 14(1):265-294, 1978. Google Scholar
  23. Noam Nisan and Amir Ronen. Algorithmic Mechanism Design (Extended Abstract). In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, pages 129-140. ACM, 1999. Google Scholar
  24. Matthew Richardson and Pedro Domingos. Mining Knowledge-sharing Sites for Viral Marketing. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 61-70, 2002. Google Scholar
  25. H. E. Scarf. The core of an N person game. Econometrica, 69:35-50, 1967. Google Scholar
  26. L. S. Shapley. On balanced sets and cores. Naval Res. Logist. Quarter., 14, 1967. Google Scholar
  27. Vasilis Syrgkanis and Eva Tardos. Composable and efficient mechanisms. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pages 211-220. ACM, 2013. Google Scholar
  28. Shang-Hua Teng. Network Essence: PageRank Completion and Centrality-Conforming Markov Chains. In M. Loebl, J. Nesetril, and R. Thomas, editors, Journey Through Discrete Mathematis: A Tribute to Jiří Matoušek. Springer, 2017. Google Scholar
  29. Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pages 67-74. ACM, 2008. Google Scholar
  30. Hanrui Zhang. Learning Set Functions with Limited Complementarity. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019. 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