Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Optimization with Demand Oracles

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We study maximization subject to a budget constraint, where we are given a valuation function v, budget B and a cost \(c_i\) for each item i. The goal is to find a set S that maximizes v(S) subject to \(\Sigma _{i\in S}c_i\le B\). Special cases of this problem are well-studied problems from submodular optimization. In particular, when the costs are all equal (cardinality constraint), a classic result by Nemhauser et al. shows that the greedy algorithm provides an \(\frac{e}{e-1}\) approximation. Motivated by a large body of literature that utilizes demand queries to elicit the preferences of agents in economic settings, we develop algorithms that guarantee improved approximation ratios in the presence of demand oracles. We are able to break the \(\frac{e}{e-1}\) barrier: we present algorithms that use only polynomially many demand queries and have approximation ratios of \(\frac{9}{8}+\epsilon \) for the general problem and \(\frac{9}{8}\) for maximization subject to a cardinality constraint. We also consider the more general class of subadditive valuations. Here, if the valuations can only be accessed by value queries, only trivial approximation ratios can be guaranteed. In contrast, we present algorithms that use demand queries and obtain an approximation ratio of \(2+\epsilon \) for the general problem and 2 for maximization subject to a cardinality constraint. We guarantee these approximation ratios even when the valuations are non-monotone. We show that these ratios are essentially optimal, in the sense that for any constant \(\epsilon >0\), obtaining an approximation ratio of \(2-\epsilon \) requires exponentially many demand queries.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. This bound holds even if the valuation is fractionally subadditive—a valuation is fractionally subadditive (a.k.a. XOS) if it is the maximum of several additive valuations. A formal definition will be presented later.

  2. This first step is very similar to the use of demand oracles in algorithms for combinatorial auctions, where demand oracles are used to solve the LP [10, 14, 15], but the similarity between the algorithms ends here.

  3. Simultaneously and independently, a constant-factor algorithm for this problem was also obtained in [4], but with a worse approximation factor. Their algorithm can be seen as a more subtle variant of the logarithmic approximation of [12] and is not based on LP rounding, as ours.

  4. The most relevant lower bound that applies specifically to demand queries is that of Nisan and Segal [26]. However, the setting of [26] is much simpler, and their ideas do not seem to be applicable in our case.

  5. We also consider some generalizations, which will be defined in the proper subsections.

  6. Of course, to obtain a discrete process one may increment \(\lambda \) in some discrete amount. This results in some loss in the approximation ratios of the algorithms that we construct (the loss depends on the size of the increments).

References

  1. Anari, N., Goel, G., Nikzad, A.: Mechanism design for crowdsourcing: an optimal 1-1/e competitive budget-feasible mechanism for large markets. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 266–275. IEEE (2014)

  2. Badanidiyuru, A., Dobzinski, S., Fu, H., Kleinberg, R., Nisan, N., Roughgarden, T.: Sketching valuation functions. In: SODA, pp. 1025–1035 (2012)

  3. Balcan, M.F., Blum, A., Mansour, Y.: Item pricing for revenue maximization. In: EC (2008)

  4. Bei, X., Chen, N., Gravin, N., Lu, P.: Budget feasible mechanism design: from prior-free to Bayesian. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 449–458. ACM (2012)

  5. Blumrosen, L., Nisan, N.: Combinatorial auctions (a survey). In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)

    Google Scholar 

  6. Blumrosen, L., Nisan, N.: On the computational power of demand queries. SIAM J. Comput. 39(4), 1372–1391 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chekuri, C., Vondrák, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: STOC (2011)

  8. Cohavi, K., Dobzinski, S.: Faster and simpler sketches of valuation functions. ACM Trans. Algorithms (TALG) 13(3), 30 (2017)

    MathSciNet  MATH  Google Scholar 

  9. Dobzinski, S., Fu, H., Kleinberg, R.: On the complexity of computing an equilibrium in combinatorial auctions. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 110–122. SIAM (2014)

  10. Dobzinski, S., Nisan, N., Schapira, M.: Approximation algorithms for combinatorial auctions with complement-free bidders. In: STOC (2005)

  11. Dobzinski, S., Nisan, N., Schapira, M.: Truthful randomized mechanisms for combinatorial auctions. In: STOC (2006)

  12. Dobzinski, S., Papadimitriou, C., Singer, Y.: Mechanisms for complement-free procurement. In: EC (2011)

  13. Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634–652 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  14. Feige, U.: On maximizing welfare where the utility functions are subadditive. In: STOC (2006)

  15. Feige, U., Vondrák, J.: Approximation algorithms for allocation problems: improving the factor of 1-1/e. In: FOCS (2006)

  16. Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions: II. Polyhedral Combinatorics. Volume 8 of Mathematical Programming Studies, pp. 73–87. Springer, Berlin (1978)

    Chapter  Google Scholar 

  17. Gharan, S.O., Vondrák, J.: Submodular maximization by simulated annealing. In: SODA (2011)

  18. Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39–45 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  19. Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear constraints. In: SODA (2009)

  20. Kulik, A., Shachnai, H., Tamir, T.: Approximations for monotone and non-monotone submodular maximization with knapsack constraints. CoRR. arXiv:1101.2940 [cs.DS] (2011)

  21. Lahaie, S., Constantin, F., Parkes, D.C.: More on the power of demand queries in combinatorial auctions: learning atomic languages and handling incentives. In: IJCAI (2005)

  22. Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. In: FOCS (2005)

  23. Lee, J., Mirrokni, V.S.., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: STOC (2009)

  24. Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. In: EC (2001)

  25. Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177–188 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  26. Nisan, N., Segal, I.: Exponential communication inefficiency of demand queries. In: TARK (2005)

  27. Sandholm, T., Boutilier, C.: Preference elicitation in combinatorial auctions. In: Cramton, P., Shoham, Y., Steinberg, R. (eds.) Combinatorial Auctions Cramton. MIT Press, Boston (2006)

    Google Scholar 

  28. Singer, Y.: Budget feasible mechanisms. In: FOCS (2010)

  29. Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41–43 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  30. Vondrák, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: STOC (2008)

Download references

Acknowledgements

We thank Bobby Kleinberg for helpful discussions.

Funding

Funding was provided by Israel Science Foundation.

Author information

Authors and Affiliations

  1. Google Research, Mountain View, CA, USA

    Ashwinkumar Badanidiyuru

  2. Weizmann Institute of Science, Rehovot, Israel

    Shahar Dobzinski

  3. Ben-Gurion University of the Negev, Beer Sheva, Israel

    Sigal Oren

Authors
  1. Ashwinkumar Badanidiyuru
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shahar Dobzinski
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sigal Oren
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shahar Dobzinski.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of this paper appeared in EC’12.

Appendix for Section 4

Appendix for Section 4

1.1 Proof of Claim 4.5

The proof is basically an algebraic manipulation:

$$\begin{aligned} \gamma= & {} \underset{k_1\le k\le k_2}{\max } \alpha \cdot \frac{k_2}{k_1+k_2-k}+ \left( (1-\alpha )-\alpha \cdot \frac{k-k_1}{k_1+k_2-k}\right) \frac{k_2}{k} \nonumber \\= & {} \underset{k_1\le k\le k_2}{\max } \frac{k_2-k}{k_2-k_1}\cdot \frac{k_2}{k_1+k_2-k} +\left( \frac{k-k_1}{k_2-k_1}-\frac{k_2-k}{k_2-k_1}\cdot \frac{k-k_1}{k_1+k_2-k}\right) \frac{k_2}{k} \nonumber \\= & {} \underset{k_1\le k\le k_2}{\max } \frac{k_2-k}{k_2-k_1}\cdot \frac{k_2}{k_1+k_2-k} \cdot \left( 1-\frac{k-k_1}{k}\right) +\frac{k-k_1}{k_2-k_1}\cdot \frac{k_2}{k} \nonumber \\= & {} \underset{k_1\le k\le k_2}{\max } \frac{k_2-k}{k_2-k_1}\cdot \frac{k_2}{k_1+k_2-k} \cdot \frac{k_1}{k}+\frac{k-k_1}{k_2-k_1}\cdot \frac{k_2}{k}\nonumber \\= & {} \underset{k_1\le k\le k_2}{\max } \frac{k_2}{k(k_2-k_1)}\cdot \frac{k(k_1+k_2)-k^2-k_1^2}{k_1+k_2-k} \nonumber \\= & {} \underset{k_1\le k\le k_2}{\max } \frac{k_2}{(k_2-k_1)}\cdot \left( 1-\frac{k_1^2}{k(k_1+k_2-k)}\right) \nonumber \\= & {} \underset{k_1\le k_2}{\max } \frac{k_2}{(k_2-k_1)}\cdot \left( 1-\frac{4k_1^2}{(k_1+k_2)^2}\right) \nonumber \\= & {} \underset{k_1\le k_2}{\max } \frac{k_2}{(k_2-k_1)}\cdot \frac{k_2^2+2k_1k_2-3k_1^2}{(k_1+k_2)^2} \nonumber \\= & {} \underset{k_1\le k_2}{\max } \frac{k_2}{(k_2-k_1)}\cdot \frac{(k_2+3k_1)\cdot (k_2-k_1)}{(k_1+k_2)^2} \nonumber \\= & {} \underset{k_1\le k_2}{\max } \frac{(k_2+3k_1)\cdot k_2}{(k_1+k_2)^2} \nonumber \\= & {} \underset{x\ge 1}{\max } \frac{(x+3)\cdot x}{(x+1)^2} \nonumber \\= & {} \frac{9}{8} \end{aligned}$$
(5)

where in (5) we use the fact that the expression is maximized at \(k=\frac{k_1+k_2}{2}\). In the second to last equation we set \(x=\frac{k_2}{k_1}\).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Badanidiyuru, A., Dobzinski, S. & Oren, S. Optimization with Demand Oracles. Algorithmica 81, 2244–2269 (2019). https://doi.org/10.1007/s00453-018-00532-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-018-00532-x

Keywords

Search

Navigation