{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,22]],"date-time":"2024-04-22T00:10:24Z","timestamp":1713744624794},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,1,16]],"date-time":"2024-01-16T00:00:00Z","timestamp":1705363200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,16]],"date-time":"2024-01-16T00:00:00Z","timestamp":1705363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e0 degli Studi di Roma La Sapienza"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study truthful mechanisms for welfare maximization in online bipartite matching. In our (multi-parameter) setting, every buyer is associated with a (possibly private) desired set of items, and has a private value for being assigned an item in her desired set. Unlike most online matching settings, where agents arrive online, in our setting the items arrive one by one in an adversarial order while the buyers are present for the entire duration of the process. This poses a significant challenge to the design of truthful mechanisms, due to the ability of buyers to strategize over future rounds. We provide an almost full picture of the competitive ratios in different scenarios, including myopic vs. non-myopic agents, tardy vs. prompt payments, and private vs. public desired sets. Among other results, we identify the frontier up to which the celebrated <jats:inline-formula><jats:alternatives><jats:tex-math>$$e\/(e-1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>e<\/mml:mi>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>e<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> competitive ratio for the vertex-weighted online matching of Karp, Vazirani and Vazirani extends to truthful agents and online items.\n<\/jats:p>","DOI":"10.1007\/s00453-023-01202-3","type":"journal-article","created":{"date-parts":[[2024,1,16]],"date-time":"2024-01-16T09:02:18Z","timestamp":1705395738000},"page":"1600-1622","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Truthful Matching with Online Items and Offline Agents"],"prefix":"10.1007","volume":"86","author":[{"given":"Michal","family":"Feldman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Federico","family":"Fusco","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon","family":"Mauras","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rebecca","family":"Reiffenh\u00e4user","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,16]]},"reference":[{"key":"1202_CR1","doi-asserted-by":"crossref","unstructured":"Feldman, M., Fusco, F., Mauras, S., Reiffenh\u00e4user, R.: Truthful matching with online items and offline agents. In: ICALP. LIPIcs, vol. 261, pp. 58\u201315820. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany (2023)","DOI":"10.1007\/s00453-023-01202-3"},{"key":"1202_CR2","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: STOC, pp. 352\u2013358. ACM, USA (1990)","DOI":"10.1145\/100216.100262"},{"key":"1202_CR3","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: SODA, pp. 1253\u20131264. SIAM, USA (2011)","DOI":"10.1137\/1.9781611973082.95"},{"key":"1202_CR4","doi-asserted-by":"crossref","unstructured":"Krysta, P., V\u00f6cking, B.: Online mechanism design (randomized rounding on the fly). In: ICALP (2). Lecture Notes in Computer Science, vol. 7392, pp. 636\u2013647. Springer, Germany (2012)","DOI":"10.1007\/978-3-642-31585-5_56"},{"key":"1202_CR5","doi-asserted-by":"crossref","unstructured":"Reiffenh\u00e4user, R.: An optimal truthful mechanism for the online weighted bipartite matching problem. In: SODA, pp. 1982\u20131993. SIAM, USA (2019)","DOI":"10.1137\/1.9781611975482.120"},{"key":"1202_CR6","doi-asserted-by":"crossref","unstructured":"D\u00fctting, P., Fusco, F., Lazos, P., Leonardi, S., Reiffenh\u00e4user, R.: Efficient two-sided markets with limited information. In: STOC, pp. 1452\u20131465. ACM, USA (2021)","DOI":"10.1145\/3406325.3451076"},{"key":"1202_CR7","doi-asserted-by":"crossref","unstructured":"Caramanis, C., D\u00fctting, P., Faw, M., Fusco, F., Lazos, P., Leonardi, S., Papadigenopoulos, O., Pountourakis, E., Reiffenh\u00e4user, R.: Single-sample prophet inequalities via greedy-ordered selection. In: SODA, pp. 1298\u20131325. SIAM, USA (2022)","DOI":"10.1137\/1.9781611977073.54"},{"key":"1202_CR8","doi-asserted-by":"crossref","unstructured":"Cole, R., Dobzinski, S., Fleischer, L.: Prompt mechanisms for online auctions. In: SAGT. Lecture Notes in Computer Science, vol. 4997, pp. 170\u2013181. Springer, Germany (2008)","DOI":"10.1007\/978-3-540-79309-0_16"},{"key":"1202_CR9","doi-asserted-by":"crossref","unstructured":"Deng, Y., Panigrahi, D., Zhang, H.: Online combinatorial auctions. In: SODA, pp. 1131\u20131149. SIAM, USA (2021)","DOI":"10.1137\/1.9781611976465.70"},{"issue":"1","key":"1202_CR10","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1287\/moor.6.1.58","volume":"6","author":"RB Myerson","year":"1981","unstructured":"Myerson, R.B.: Optimal auction design. Math. Operat. Res. 6(1), 58\u201373 (1981)","journal-title":"Math. Operat. Res."},{"issue":"1","key":"1202_CR11","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1145\/1360443.1360462","volume":"39","author":"B Birnbaum","year":"2008","unstructured":"Birnbaum, B., Mathieu, C.: On-line bipartite matching made simple. Acm Sigact News 39(1), 80\u201387 (2008)","journal-title":"Acm Sigact News"},{"key":"1202_CR12","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of RANKING for online bipartite matching. In: SODA, pp. 101\u2013107. SIAM, USA (2013)","DOI":"10.1137\/1.9781611973105.7"},{"key":"1202_CR13","doi-asserted-by":"crossref","unstructured":"Feige, U.: Tighter bounds for online bipartite matching. In: Building Bridges II, pp. 235\u2013255. Springer, Germany (2019)","DOI":"10.1007\/978-3-662-59204-5_7"},{"key":"1202_CR14","doi-asserted-by":"crossref","unstructured":"Eden, A., Feldman, M., Fiat, A., Segal, K.: An economics-based analysis of RANKING for online bipartite matching. In: SOSA, pp. 107\u2013110. SIAM, USA (2021)","DOI":"10.1137\/1.9781611976496.12"},{"issue":"4","key":"1202_CR15","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1561\/0400000057","volume":"8","author":"A Mehta","year":"2013","unstructured":"Mehta, A.: Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4), 265\u2013368 (2013)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"1202_CR16","doi-asserted-by":"crossref","unstructured":"Kesselheim, T., Radke, K., T\u00f6nnis, A., V\u00f6cking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: ESA. Lecture Notes in Computer Science, vol. 8125, pp. 589\u2013600. Springer, Germany (2013)","DOI":"10.1007\/978-3-642-40450-4_50"},{"key":"1202_CR17","doi-asserted-by":"crossref","unstructured":"Korula, N., P\u00e1l, M.: Algorithms for secretary problems on graphs and hypergraphs. In: ICALP (2). Lecture Notes in Computer Science, vol. 5556, pp. 508\u2013520. Springer, Germany (2009)","DOI":"10.1007\/978-3-642-02930-1_42"},{"key":"1202_CR18","doi-asserted-by":"crossref","unstructured":"Ezra, T., Feldman, M., Gravin, N., Tang, Z.G.: Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models. In: EC, pp. 769\u2013787. ACM, USA (2020)","DOI":"10.1145\/3391403.3399513"},{"key":"1202_CR19","unstructured":"Gravin, N., Tang, Z.G., Wang, K.: Online stochastic matching with edge arrivals. In: ICALP. LIPIcs, vol. 198, pp. 74\u201317420. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"1202_CR20","doi-asserted-by":"crossref","unstructured":"Gamlath, B., Kale, S., Svensson, O.: Beating greedy for stochastic bipartite matching. In: SODA, pp. 2841\u20132854. SIAM, USA (2019)","DOI":"10.1137\/1.9781611975482.176"},{"key":"1202_CR21","doi-asserted-by":"crossref","unstructured":"Gamlath, B., Kapralov, M., Maggiori, A., Svensson, O., Wajc, D.: Online matching with general arrivals. In: FOCS, pp. 26\u201337. IEEE Computer Society, USA (2019)","DOI":"10.1109\/FOCS.2019.00011"},{"key":"1202_CR22","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.geb.2015.01.004","volume":"90","author":"M Babaioff","year":"2015","unstructured":"Babaioff, M., Blumrosen, L., Roth, A.: Auctions with online supply. Games Econ. Behav. 90, 227\u2013246 (2015)","journal-title":"Games Econ. Behav."},{"key":"1202_CR23","doi-asserted-by":"crossref","unstructured":"Azar, Y., Khaitzin, E.: Prompt mechanism for ad placement over time. In: International Symposium on Algorithmic Game Theory SAGT, Germany, pp. 19\u201330 (2011). Springer","DOI":"10.1007\/978-3-642-24829-0_4"},{"issue":"2","key":"1202_CR24","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10878-014-9754-9","volume":"30","author":"X Xiang","year":"2015","unstructured":"Xiang, X.: Prompt mechanism for online auctions with multi-unit demands. J. Combinat. Optimiz. 30(2), 335\u2013346 (2015)","journal-title":"J. Combinat. Optimiz."},{"key":"1202_CR25","doi-asserted-by":"crossref","unstructured":"Mirrokni, V.S., Leme, R.P., Tang, P., Zuo, S.: Non-clairvoyant dynamic mechanism design. In: EC, p. 169. ACM, USA (2018)","DOI":"10.1145\/3219166.3219224"},{"issue":"6","key":"1202_CR26","doi-asserted-by":"publisher","first-page":"2463","DOI":"10.3982\/ECTA6995","volume":"81","author":"S Athey","year":"2013","unstructured":"Athey, S., Segal, I.: An efficient dynamic mechanism. Econometrica 81(6), 2463\u20132485 (2013)","journal-title":"Econometrica"},{"issue":"2","key":"1202_CR27","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1257\/jel.20180892","volume":"57","author":"D Bergemann","year":"2019","unstructured":"Bergemann, D., V\u00e4lim\u00e4ki, J.: Dynamic mechanism design: an introduction. J. Econ. Literat. 57(2), 235\u201374 (2019)","journal-title":"J. Econ. Literat."},{"issue":"1","key":"1202_CR28","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","volume":"16","author":"W Vickrey","year":"1961","unstructured":"Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. J. Fin. 16(1), 8\u201337 (1961)","journal-title":"J. Fin."},{"key":"1202_CR29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316779309","volume-title":"Twenty Lectures on Algorithmic Game Theory","author":"T Roughgarden","year":"2016","unstructured":"Roughgarden, T.: Twenty Lectures on Algorithmic Game Theory. Cambridge University Press, United Kingdom (2016)"},{"key":"1202_CR30","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Probabilistic computations: Toward a unified measure of complexity (extended abstract). In: FOCS, pp. 222\u2013227. IEEE Computer Society, USA (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01202-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01202-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01202-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,21]],"date-time":"2024-04-21T03:04:11Z","timestamp":1713668651000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01202-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,16]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1202"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01202-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,16]]},"assertion":[{"value":"3 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors do not have any financial or non financial interests that are directly or indirectly related to the work submitted for publication.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}