{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:07:55Z","timestamp":1750306075605,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T00:00:00Z","timestamp":1501200000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"TUM Institute for Advanced Studies"},{"name":"Deutsche Forschungsgemeinschaft (DFG)"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>\n            We propose a truthful-in-expectation, (1-1\/\n            <jats:italic>e<\/jats:italic>\n            )-approximation mechanism for a strategic variant of the generalized assignment problem (GAP). In GAP, a set of items has to be optimally assigned to a set of bins without exceeding the capacity of any singular bin. In the strategic variant of the problem we study, values for assigning items to bins are the private information of bidders and the mechanism should provide bidders with incentives to truthfully report their values. The approximation ratio of the mechanism is a significant improvement over the approximation ratio of the existing truthful mechanism for GAP.\n          <\/jats:p>\n          <jats:p>The proposed mechanism comprises a novel convex optimization program as the allocation rule as well as an appropriate payment rule. To implement the convex program in polynomial time, we propose a fractional local search algorithm which approximates the optimal solution within an arbitrarily small error leading to an approximately truthful-in-expectation mechanism. The proposed algorithm improves upon the existing optimization algorithms for GAP in terms of simplicity and runtime while the approximation ratio closely matches the best approximation ratio known for GAP when all inputs are publicly known.<\/jats:p>","DOI":"10.1145\/3105787","type":"journal-article","created":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T12:12:00Z","timestamp":1501503120000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A Truthful Mechanism for the Generalized Assignment Problem"],"prefix":"10.1145","volume":"5","author":[{"given":"Salman","family":"Fadaei","sequence":"first","affiliation":[{"name":"Technical University of Munich, Munich, Germany"}]},{"given":"Martin","family":"Bichler","sequence":"additional","affiliation":[{"name":"Technical University of Munich, Boltzmannstr, Munich, Germany"}]}],"member":"320","published-online":{"date-parts":[[2017,7,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/120878422"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764503"},{"volume-title":"Convex Optimization","author":"Boyd Stephen","key":"e_1_2_1_3_1","unstructured":"Stephen Boyd and Lieven Vandenberghe . 2009. Convex Optimization . Cambridge University Press . Stephen Boyd and Lieven Vandenberghe. 2009. Convex Optimization. Cambridge University Press."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. ACM, 58--62","author":"Carr Robert","year":"2000","unstructured":"Robert Carr and Santosh Vempala . 2000 . Randomized metarounding . In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. ACM, 58--62 . Robert Carr and Santosh Vempala. 2000. Randomized metarounding. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. ACM, 58--62."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/080735503"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382820"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0625"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897569"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.42"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229044"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.87"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993614"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807394"},{"key":"e_1_2_1_15_1","volume-title":"An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries. arXiv Preprint arXiv:1109.1053","author":"Dughmi Shaddin","year":"2011","unstructured":"Shaddin Dughmi , Tim Roughgarden , Jan Vondr\u00e1k , and Qiqi Yan . 2011b. An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries. arXiv Preprint arXiv:1109.1053 ( 2011 ). Shaddin Dughmi, Tim Roughgarden, Jan Vondr\u00e1k, and Qiqi Yan. 2011b. An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries. arXiv Preprint arXiv:1109.1053 (2011)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993657"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.01.007"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2016.12.003"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.14"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055881"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109624"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.58"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011589804040"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238230"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049699"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56279-6_88"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_29_1","volume-title":"Computationally feasible VCG mechanisms.Journal of Artificial Intelligence Research 29","author":"Nisan Noam","year":"2007","unstructured":"Noam Nisan and Amir Ronen . 2007. Computationally feasible VCG mechanisms.Journal of Artificial Intelligence Research 29 ( 2007 ), 19--47. Noam Nisan and Amir Ronen. 2007. Computationally feasible VCG mechanisms.Journal of Artificial Intelligence Research 29 (2007), 19--47."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.3138\/infor.45.3.123"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.54"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585178"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105787","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3105787","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:03Z","timestamp":1750217403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105787"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,28]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3105787"],"URL":"https:\/\/doi.org\/10.1145\/3105787","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2017,7,28]]},"assertion":[{"value":"2016-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}