×

zbMATH — the first resource for mathematics

Online allocation and pricing with economies of scale. (English) Zbl 1406.91213
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 159-172 (2015).
Summary: Allocating multiple goods to customers in a way that maximizes some desired objective is a fundamental part of algorithmic mechanism design. We consider here the problem of offline and online allocation of goods that have economies of scale, or decreasing marginal cost per item for the seller. In particular, we analyze the case where customers have unit-demand and arrive one at a time with valuations on items, sampled iid from some unknown underlying distribution over valuations. Our strategy operates by using an initial sample to learn enough about the distribution to determine how best to allocate to future customers, together with an analysis of structural properties of optimal solutions that allow for uniform convergence analysis. We show, for instance, if customers have \(\{0,1\}\) valuations over items, and the goal of the allocator is to give each customer an item he or she values, we can efficiently produce such an allocation with cost at most a constant factor greater than the minimum over such allocations in hindsight, so long as the marginal costs do not decrease too rapidly. We also give a bicriteria approximation to social welfare for the case of more general valuation functions when the allocator is budget constrained.
For the entire collection see [Zbl 1326.68026].
MSC:
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
91B24 Microeconomic theory (price theory and economic markets)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. SIAM J. Comput. 39(2), 361–370 (2009) · Zbl 1200.68271 · doi:10.1137/060661946
[2] Blum, A., Gupta, A., Mansour, Y., Sharma, A.: Welfare and profit maximization with production costs. In: FOCS, pp. 77–86 (2011) · Zbl 1292.91078 · doi:10.1109/FOCS.2011.68
[3] Devanur, N.R., Hayes, T.P.: The adwords problem: Online keyword matching with budgeted bidders under random permutations. In: Proc. ACM EC, EC 2009, pp. 71–78 (2009) · doi:10.1145/1566374.1566384
[4] Devanur, N.R., Jain, K.: Online matching with concave returns. In: Proc. STOC, pp. 137–144 (2012) · Zbl 1286.68510 · doi:10.1145/2213977.2213992
[5] Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: Proc. SODA, pp. 982–991 (2008) · Zbl 1192.68482
[6] Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proc. STOC, pp. 352–358 (1990) · doi:10.1145/100216.100262
[7] Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39–45 (1999) · Zbl 1002.68203 · doi:10.1016/S0020-0190(99)00031-9
[8] Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. J. ACM 54(5), 22 (2007) · Zbl 1312.68239 · doi:10.1145/1284320.1284321
[9] Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007) · Zbl 1130.91005 · doi:10.1017/CBO9780511800481
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.