{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:08Z","timestamp":1759637768504,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2019,3,30]],"date-time":"2019-03-30T00:00:00Z","timestamp":1553904000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"crossref","award":["337122"],"award-info":[{"award-number":["337122"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s00224-019-09918-y","type":"journal-article","created":{"date-parts":[[2019,3,30]],"date-time":"2019-03-30T06:02:55Z","timestamp":1553925775000},"page":"1470-1498","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Random Sampling for Budgeted Settings"],"prefix":"10.1007","volume":"63","author":[{"given":"Alon","family":"Eden","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adi","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,3,30]]},"reference":[{"key":"9918_CR1","doi-asserted-by":"crossref","unstructured":"Abrams, Z.: Revenue maximization when bidders have budgets. In: SODA, pp. 1074\u20131082. ACM (2006)","DOI":"10.1145\/1109557.1109676"},{"key":"9918_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Meyerson, A.: Reducing truth-telling online mechanisms to online optimization. In: STOC, pp. 503\u2013510. ACM (2003)","DOI":"10.1145\/780542.780616"},{"key":"9918_CR3","unstructured":"Azar, Y., Feldman, M., Gravin, N., Roytman, A.: Liquid price of anarchy. In: Algorithmic Game Theory - 10th International Symposium, SAGT 2017, L\u2019aquila, Italy, September 12\u201314, 2017, Proceedings, pp. 3\u201315 (2017)"},{"key":"9918_CR4","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: SODA, pp. 434\u2013443. SIAM (2007)"},{"key":"9918_CR5","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Immorlica, N., Lucier, B., Weinberg, S.M.: A simple and approximately optimal mechanism for an additive buyer. In: FOCS (2014)","DOI":"10.1109\/FOCS.2014.11"},{"key":"9918_CR6","unstructured":"Bar-Yossef, Z., Hildrum, K., Wu, F.: Incentive-compatible online auctions for digital goods. In: SODA. Society for industrial and applied mathematics, pp. 964\u2013970 (2002)"},{"key":"9918_CR7","unstructured":"Blum, A., Hartline, J.D.: Near-optimal online auctions. In: SODA. Society for industrial and applied mathematics, pp. 1156\u20131163 (2005)"},{"key":"9918_CR8","doi-asserted-by":"crossref","unstructured":"Borgs, C., Chayes, J., Immorlica, N., Mahdian, M., Saberi, A.: Multi-unit auctions with budget-constrained bidders. In: EC, pp. 44\u201351. ACM (2005)","DOI":"10.1145\/1064009.1064014"},{"key":"9918_CR9","unstructured":"Caragiannis, I., Voudouris, A.A.: The efficiency of resource allocation mechanisms for budget-constrained users. In: Proceedings of the 2018 ACM Conference On Economics and Computation, Ithaca, NY, USA, June 18\u201322, 2018, pp. 681\u2013698 (2018)"},{"key":"9918_CR10","doi-asserted-by":"crossref","unstructured":"Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: STOC (2010)","DOI":"10.1145\/1807406.1807428"},{"key":"9918_CR11","doi-asserted-by":"crossref","unstructured":"Chawla, S., Malec, D.L., Malekian, A.: Bayesian mechanism design for budget-constrained agents. In: EC, pp. 253\u2013262. ACM (2011)","DOI":"10.1145\/1993574.1993613"},{"key":"9918_CR12","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/j.geb.2012.08.010","volume":"91","author":"S Chawla","year":"2015","unstructured":"Chawla, S., Malec, D.L., Sivan, B.: The power of randomness in bayesian optimal mechanism design. Games Econom. Behav. 91, 297\u2013317 (2015)","journal-title":"Games Econom. Behav."},{"key":"9918_CR13","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Ha, B.Q., Hartline, J.D.: Prior-free auctions for budgeted agents. In: EC, pp. 287\u2013304. ACM (2013)","DOI":"10.1145\/2482540.2482554"},{"issue":"2","key":"9918_CR14","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1016\/j.geb.2011.08.003","volume":"74","author":"S Dobzinski","year":"2012","unstructured":"Dobzinski, S., Lavi, R., Nisan, N.: Multi-unit auctions with budget limits. Games Econom. Behav. 74(2), 486\u2013503 (2012)","journal-title":"Games Econom. Behav."},{"key":"9918_CR15","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Leme, R.P.: Efficiency guarantees in auctions with budgets. In: ICALP, pp. 392\u2013404. Springer (2014)","DOI":"10.1007\/978-3-662-43948-7_33"},{"key":"9918_CR16","unstructured":"Dughmi, S., Eden, A., Feldman, M., Fiat, A., Leonardi, S.: Lottery pricing equilibria. In: Proceedings of the 2016 ACM Conference On Economics and Computation, EC \u201916, Maastricht, The Netherlands, July 24-28, 2016, pp. 401\u2013418 (2016)"},{"key":"9918_CR17","doi-asserted-by":"crossref","unstructured":"Feldman, M., Fiat, A., Leonardi, S., Sankowski, P.: Revenue maximizing envy-free multi-unit auctions with budgets. In: EC, pp. 532\u2013549. ACM (2012)","DOI":"10.1145\/2229012.2229052"},{"key":"9918_CR18","doi-asserted-by":"crossref","unstructured":"Fiat, A., Leonardi, S., Saia, J., Sankowski, P.: Single valued combinatorial auctions with budgets. In: EC, pp. 223\u2013232. ACM (2011)","DOI":"10.1145\/1993574.1993609"},{"key":"9918_CR19","doi-asserted-by":"crossref","unstructured":"Fotakis, D., Lotidis, K., Podimata, C.: A bridge between liquid and social welfare in combinatorial auctions with submodular bidders. arXiv: 1809.01803 (2018)","DOI":"10.1609\/aaai.v33i01.33011949"},{"key":"9918_CR20","doi-asserted-by":"crossref","unstructured":"Friedman, E.J., Parkes, D.C.: Pricing Wifi at Starbucks: issues in online mechanism design. In: EC, pp. 240\u2013241. ACM (2003)","DOI":"10.1145\/779928.779978"},{"key":"9918_CR21","doi-asserted-by":"crossref","unstructured":"Goel, G., Mirrokni, V., Leme, R.P.: Clinching auctions with online supply. In: SODA, pp. 605\u2013619. SIAM (2013)","DOI":"10.1137\/1.9781611973105.44"},{"issue":"2","key":"9918_CR22","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1016\/j.geb.2006.02.003","volume":"55","author":"AV Goldberg","year":"2006","unstructured":"Goldberg, A.V., Hartline, J.D., Karlin, A.R., Saks, M., Wright, A.: Competitive auctions. Games Econom. Behav. 55(2), 242\u2013269 (2006)","journal-title":"Games Econom. Behav."},{"key":"9918_CR23","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Kleinberg, R., Parkes, D.C.: Adaptive limited-supply online auctions. In: EC, pp. 71\u201380. ACM (2004)","DOI":"10.1145\/988772.988784"},{"key":"9918_CR24","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Kleinberg, R.D., Mahdian, M., Parkes, D.C.: Online auctions with re-usable goods. In: EC, pp. 165\u2013174. ACM (2005)","DOI":"10.1145\/1064009.1064027"},{"key":"9918_CR25","unstructured":"Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. In: SODA. Society for industrial and applied mathematics, pp. 630\u2013631 (2005)"},{"key":"9918_CR26","doi-asserted-by":"crossref","unstructured":"Lavi, R., Nisan, N.: Competitive analysis of incentive compatible on-line auctions. In: EC, pp. 233\u2013241. ACM (2000)","DOI":"10.1145\/352871.352897"},{"key":"9918_CR27","unstructured":"Lavi, R., Nisan, N.: Online ascending auctions for gradually expiring items. In: SODA, pp. 1146\u20131155. SIAM (2005)"},{"key":"9918_CR28","unstructured":"Lu, P., Xiao, T.: Improved efficiency guarantees in auctions with budgets. In: EC 15, Portland, OR, USA, June 15\u201319, 2015, pp. 397\u2013413 (2015)"},{"key":"9918_CR29","unstructured":"Lu, P., Xiao, T.: Liquid welfare maximization in auctions with multiple items. In: Algorithmic Game Theory - 10th International Symposium, SAGT 2017, L\u2019aquila, Italy, September 12\u201314, 2017, Proceedings, pp. 41\u201352 (2017)"},{"key":"9918_CR30","doi-asserted-by":"crossref","unstructured":"Parkes, D.C.: Online mechanisms (2007)","DOI":"10.1017\/CBO9780511800481.018"},{"key":"9918_CR31","unstructured":"Parkes, D.C., Singh, S.P.: An Mdp-based approach to online mechanism design. In: NIPS (2003)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09918-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09918-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09918-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T21:42:44Z","timestamp":1663191764000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09918-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,30]]},"references-count":31,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["9918"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09918-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2019,3,30]]},"assertion":[{"value":"30 March 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}