Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 8, 2026

Available Issues

April 10, 2013 - May 8, 2026

Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online

Published Online:19 Jan 2022https://doi.org/10.1287/moor.2021.1208

References

  • [1] Amanatidis G, Birmpas G, Markakis E (2016) Coverage, matching, and beyond: New results on budgeted mechanism design. Proc. 12th Internat. Conf. Web Internet Econom. Lecture Notes in Computer Science, vol. 10123 (Springer, Cham, Switzerland), 414–428.Google Scholar
  • [2] Amanatidis G, Birmpas G, Markakis E (2017) On budget-feasible mechanism design for symmetric submodular objectives. Proc. 13th Internat. Conf. Web Internet Econom. Lecture Notes in Computer Science, vol. 10660 (Springer, Cham, Switzerland), 1–15.Google Scholar
  • [3] Amanatidis G, Kleer P, Schäfer G (2019) Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 901–919.Google Scholar
  • [4] Amanatidis G, Fusco F, Lazos P, Leonardi S, Reiffenhäuser R (2020) Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. Proc. Annual Conf. Neural Inform. Processing Systems. Advances in Neural Information Processing Systems, vol. 33.Google Scholar
  • [5] Anari N, Goel G, Nikzad A (2014) Mechanism design for crowdsourcing: An optimal 1-1/e competitive budget-feasible mechanism for large markets. Proc. 55th IEEE Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 266–275.Google Scholar
  • [6] Azar PD, Kleinberg R, Weinberg SM (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] Babaioff M, Immorlica N, Kempe D, Kleinberg R (2007) A knapsack secretary problem with applications. Proc. 10th Internat. Workshop Approximation and 11th Internat. Workshop Randomization Combin. Optim. Algorithms Techniques. Lecture Notes in Computer Science, vol. 4627 (Springer, Berlin), 16–28.Google Scholar
  • [8] Badanidiyuru A, Vondrák J (2014) Fast algorithms for maximizing submodular functions. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1497–1514.Google Scholar
  • [9] Badanidiyuru A, Kleinberg R, Singer Y (2012) Learning on a budget: Posted price mechanisms for online procurement. Proc. 13th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 128–145.Google Scholar
  • [10] Balkanski E, Hartline JD (2016) Bayesian budget feasibility with posted pricing. Proc. 25th Internat. Conf. World Wide Web (Association for Computing Machinery, New York), 189–203.Google Scholar
  • [11] Bateni M, Hajiaghayi MT, Zadimoghaddam M (2013) Submodular secretary problem and extensions. ACM Trans. Algorithms 9(4):32.Crossref, Google Scholar
  • [12] Bei X, Chen N, Gravin N, Lu P (2012) Budget feasible mechanism design: From prior-free to Bayesian. Proc. 44th Sympos. Theory Comput. (Association for Computing Machinery, New York), 449–458.Google Scholar
  • [13] Bei X, Chen N, Gravin N, Lu P (2017) Worst-case mechanism design via Bayesian analysis. SIAM J. Comput. 46(4):1428–1448.Crossref, Google Scholar
  • [14] Blumrosen L, Nisan N (2009) On the computational power of demand queries. SIAM J. Comput. 39(4):1372–1391.Crossref, Google Scholar
  • [15] Borodin A, Filmus Y, Oren J (2010) Threshold models for competitive influence in social networks. Proc. Sixth Internat. Workshop Internet Network Econom. (Springer, Berlin), 539–550.Google Scholar
  • [16] Buchbinder N, Feldman M (2018) Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms 14(3):32.Crossref, Google Scholar
  • [17] Buchbinder N, Feldman M, Naor J, Schwartz R (2014) Submodular maximization with cardinality constraints. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1433–1452.Google Scholar
  • [18] Chekuri C, Gupta S, Quanrud K (2015) Streaming algorithms for submodular function maximization. Proc. 42nd Internat. Colloquium Automata, Languages, Programming, Part I. Lecture Notes in Computer Science, vol. 9134 (Springer, Berlin), 318–330.Google Scholar
  • [19] Chekuri C, Vondrák J, Zenklusen R (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6):1831–1879.Crossref, Google Scholar
  • [20] Chen N, Gravin N, Lu P (2011) On the approximability of budget feasible mechanisms. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 685–699.Google Scholar
  • [21] Dobzinski S, Papadimitriou CH, Singer Y (2011) Mechanisms for complement-free procurement. Proc. 12th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 273–282.Google Scholar
  • [22] Dynkin EB (1963) Optimal choice of the stopping moment of a Markov process. Doklady Akademii Nauk SSSR 150(2):238–240.Google Scholar
  • [23] Ene A, Nguyen HL (2019) A nearly-linear time algorithm for submodular maximization with a knapsack constraint. Proc. 46th Internat. Colloquium Automata, Languages, Programming. Leibniz International Proceedings in Informatics, vol. 132 (Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 53:1–53:12.Google Scholar
  • [24] Feige U, Mirrokni VS, Vondrák J (2011) Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4):1133–1153.Crossref, Google Scholar
  • [25] Feldman M, Zenklusen R (2018) The submodular secretary problem goes linear. SIAM J. Comput. 47(2):330–366.Crossref, Google Scholar
  • [26] Feldman M, Harshaw C, Karbasi A (2017) Greed is good: Near-optimal submodular maximization via greedy optimization. Proc. 30th Conf. Learning Theory. Proceedings of Machine Learning Research, vol. 65, 758–784.Google Scholar
  • [27] Feldman M, Naor J, Schwartz R (2011a) Improved competitive ratios for submodular secretary problems (extended abstract). Goldberg LA, Jansen K, Ravi R, Rolim JDP, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science, vol. 6845 (Springer, Berlin), 218–229.Crossref, Google Scholar
  • [28] Feldman M, Naor J, Schwartz R (2011b) A unified continuous greedy algorithm for submodular maximization. Proc. IEEE 52nd Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 570–579.Google Scholar
  • [29] Goel G, Nikzad A, Singla A (2014) Mechanism design for crowdsourcing markets with heterogeneous tasks. Proc. Second AAAI Conf. Human Comput. Crowdsourcing (Association for the Advancement of Artificial Intelligence, Menlo Park, CA).Google Scholar
  • [30] Gravin N, Jin Y, Lu P, Zhang C (2019) Optimal budget-feasible mechanisms for additive valuations. Proc. 2019 ACM Conf. Economics and Comput. (Association for Computing Machinery, New York), 887–900.Google Scholar
  • [31] Gupta A, Nagarajan V, Singla S (2017) Adaptivity gaps for stochastic probing: Submodular and XOS functions. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1688–1702.Google Scholar
  • [32] Gupta A, Roth A, Schoenebeck G, Talwar K (2010) Constrained non-monotone submodular maximization: Offline and secretary algorithms. Saberi A, ed. Proc. Sixth Internat. Workshop Internet Network Econom. Lecture Notes in Computer Science, vol. 6484 (Springer, Berlin), 246–257.Google Scholar
  • [33] Horel T, Ioannidis S, Muthukrishnan S (2014) Budget feasible mechanisms for experimental design. Pardo A, Viola A, eds. Proc. 11th Latin Amer. Sympos. Theoret. Inform. Lecture Notes in Computer Science, vol. 8392 (Springer, Berlin), 719–730.Google Scholar
  • [34] Kesselheim T, Tönnis A (2017) Submodular secretary problems: Cardinality, matching, and linear constraints. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Leibniz International Proceedings in Informatics, vol. 81 (Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 16:1–16:22.Google Scholar
  • [35] Khalilabadi PJ, Tardos É (2018) Simple and efficient budget feasible mechanisms for monotone submodular valuations. Proc. 14th Internat. Conf. Web Internet Econom. Lecture Notes in Computer Science, vol. 11316 (Springer, Cham, Switzerland), 246–263.Google Scholar
  • [36] Kulik A, Shachnai H, Tamir T (2013) Approximations for monotone and non-monotone submodular maximization with knapsack constraints. Math. Oper. Res. 38(4):729–739.Link, Google Scholar
  • [37] Lehmann B, Lehmann DJ, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav. 55(2):270–296.Crossref, Google Scholar
  • [38] Leonardi S, Monaco G, Sankowski P, Zhang Q (2016) Budget feasible mechanisms on matroids. Preprint, submitted December 9, https://arxiv.org/abs/1612.03150.Google Scholar
  • [39] Leonardi S, Monaco G, Sankowski P, Zhang Q (2017) Budget feasible mechanisms on matroids. Proc. 19th Internat. Conf. Integer Programming Combin. Optim. Lecture Notes in Computer Science, vol. 10328 (Springer, Cham, Switzerland), 368–379.Google Scholar
  • [40] Mirrokni VS, Schapira M, Vondrák J (2008) Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. Proc. Ninth ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 70–77.Google Scholar
  • [41] Mirzasoleiman B, Badanidiyuru A, Karbasi A (2016) Fast constrained submodular maximization: Personalized data summarization. Proc. 33rd Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 48, 1358–1367.Google Scholar
  • [42] Myerson R (1981) Optimal auction design. Math. Oper. Res. 6(1):58–73.Link, Google Scholar
  • [43] Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Crossref, Google Scholar
  • [44] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24 (Springer Science and Business Media, Berlin).Google Scholar
  • [45] Singer Y (2010) Budget feasible mechanisms. Proc. 51th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 765–774.Google Scholar
  • [46] Singer Y (2012) How to win friends and influence people, truthfully: Influence maximization mechanisms for social networks. Proc. Fifth Internat. Conf. Web Search Web Data Mining (Association for Computing Machinery, New York), 733–742.Google Scholar
  • [47] Singer Y, Mittal M (2013) Pricing mechanisms for crowdsourcing markets. Proc. 22nd Internat. World Wide Web Conf. (International World Wide Web Conferences Steering Committee/Association for Computing Machinery, New York), 1157–1166.Google Scholar
  • [48] Singla A, Krause A (2013) Incentives for privacy tradeoff in community sensing. Proc. First AAAI Conf. Human Comput. Crowdsourcing (Association for the Advancement of Artificial Intelligence, Menlo Park, CA).Google Scholar
  • [49] Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1):41–43.Crossref, Google Scholar
  • [50] Wolsey LA (1982) Maximising real-valued submodular functions: Primal and dual heuristics for location problems. Math. Oper. Res. 7(3):410–425.Link, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree