{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:10:09Z","timestamp":1750306209312,"version":"3.41.0"},"reference-count":8,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,1,12]],"date-time":"2017-01-12T00:00:00Z","timestamp":1484179200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2017,1,12]]},"abstract":"<jats:p>An online truthful budgeted matching problem is considered for a bipartite graph, where the right vertices are available ahead of time, and individual left vertices arrive sequentially. On arrival of a left vertex, its edge utilities (or weights) to all the right vertices and a corresponding cost (or bid) are revealed. If a left vertex is matched to any of the right vertices, then it has to be paid at least as much as its cost. The problem is to match each left vertex instantaneously and irrevocably to any one of the right vertices, if at all, to find the maximum weight matching that is truthful, under a payment budget constraint. Truthfulness condition requires that no left vertex has any incentive of misreporting its cost. Assuming that the vertices arrive in an uniformly random order (secretary model) with arbitrary utilities, a truthful algorithm is proposed that is 24\u00df- competitive (where \u00df is the ratio of the maximum and the minimum utility) and satisfies the payment budget constraint. Direct applications of this problem include crowdsourcing auctions, and matching wireless users to cooperative relays in device-to-device enabled cellular network.<\/jats:p>","DOI":"10.1145\/3040230.3040232","type":"journal-article","created":{"date-parts":[[2017,1,17]],"date-time":"2017-01-17T13:42:08Z","timestamp":1484660528000},"page":"3-6","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Online Budgeted Truthful Matching"],"prefix":"10.1145","volume":"44","author":[{"given":"Rahul","family":"Vaze","sequence":"first","affiliation":[{"name":"School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marceau","family":"Coupechoux","sequence":"additional","affiliation":[{"name":"LTCI, CNRS, Telecom ParisTech, University, Paris-Saclay, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,1,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.78"},{"volume-title":"NIPS Workshop on Crowdsourcing","year":"2013","author":"Goel Gagan","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488489"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2348543.2348567"},{"key":"e_1_2_1_7_1","first-page":"403","volume-title":"2015 13th International Symposium on","author":"Subramanian Ashwin","year":"2015"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_42"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3040230.3040232","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3040230.3040232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:50:38Z","timestamp":1750218638000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3040230.3040232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,12]]},"references-count":8,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,1,12]]}},"alternative-id":["10.1145\/3040230.3040232"],"URL":"https:\/\/doi.org\/10.1145\/3040230.3040232","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2017,1,12]]},"assertion":[{"value":"2017-01-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}